Tuesday, October 28, 2014

Bruteforcing random strings, randomly

I haven't written about anything in a while, sorry about that.

I come across a type of vulnerability quite often regarding weak codes being generated. These can be used for OTP, for password resets, etc. Many times, they are 6-8 characters long, with a smaller key space (a-f, 0-9), and case-insensitive. All in all, easily brute-forceable if no rate limiting (or improper rate limiting) is in place.

The question I ask myself each time I find a vulnerability like this is, would attempting to brute force this string be faster if I were to attempt to brute force it randomly or serially. Serially is obviously the easiest way to go about writing some code to automate this task. For a 6-character code, starting at 'aaaaaa', and going through '999999' is a simple loop in Ruby:

[*('a'..'f'), *('0'..'9')].repeated_permutation(6).each do |perm|
  p perm.join
end

The benefit to this (at face value) is that you do not need to generate the entire keyspace before attempting to brute force the key. You simply iterate over each subsequent permutation.

Theoretically, the chances of a code being generated equalling 'aaaaaa' and 'f04ab4' are the same. But I am not super concerned about theoretical outcomes here. I am concerned with practical outcomes and telling me the chances a code being generated by a computer being 'aaaaaa' and 'f04ab4' are the same is something I simply don't buy. Theoretically, in a perfect world on paper this might be true. In the real world, that doesn't add up.

So I started playing around with the idea of cracking these codes randomly. At first, I believed I needed to generate the full keyspace before attempting this, and my examples and results below do this. However, I will explain below how I believe you could get away with not generating the full keyspace in order to select from it randomly. All you really need are the number of possible combinations.

Let's see some code for serially cracking a random uuid, truncated to 6 characters:

  1 require 'securerandom'
  2 
  3 results = []
  4 0.upto(ARGV[0].to_i) do |fdsa|
  5   uuid = SecureRandom.uuid
  6   uuid = uuid[0..5]
  7 
  8   beg = Time.now
  9   en = nil
 10   [*('a'..'f'), *('0'..'9')].repeated_permutation(6).each do |perm|
 11     if perm.join == uuid
 12       en = Time.now
 13       break
 14     end
 15   end
 16 
 17   results << en-beg
 18 end
 19 
 20 min = 999 #an impossible number
 21 max = 0
 22 median = 0
 23 average = 0
 24 
 25 results.each do |result|
 26   if result < min
 27     min = result
 28   end
 29 
 30   if result > max
 31     max = result
 32   end
 33 
 34   average = average + result
 35 end
 36 
 37 average = average / results.length.to_f
 38 
 39 sorted = results.sort
 40 
 41 median = (sorted[(results.length - 1)/2] + sorted[results.length / 2]) / 2.0
 42 
 43 p "Max: #{max}"
 44 p "Min: #{min}"
 45 p "Median: #{median}"
 46 p "Average: #{average}"

What is happening should be straight forward. Accepting an integer as the first argument, I iterate this number of times, generating a random uuid, truncating it, then attempting to brute force it serially. Once I have iterated the predefined number of times, storing the time it took to crack the short code in an array, I calculate a few statistics (the max time required to crack a code, the minimum time required, the median time, and the average time.

Here are some results for iterations of different sizes:

--- serial 100 iters ---
"Max: 15.138325266"
"Min: 0.154493369"
"Median: 7.413371801"
"Average: 7.347536151386141"

--- serial 1000 iters ---
"Max: 15.998030706"
"Min: 0.103791957"
"Median: 8.027371177"
"Average: 7.912778955110889"

You can see the results for 100 iterations and 1000 iterations are pretty much in line with each other. The longest time to crack a 6-character truncated uuid took between 15-16 seconds. The minimum time it took was 0.10-0.15 seconds. In both sets, median and average times are relatively in line between 7-8 seconds.

Ok, what about randomly trying to brute force the randomly generated uuid truncated to 6 characters? Here is the code I used for this:

  1 require 'securerandom'
  2 
  3 table = File.read('rainbow_table').split("\n")
  4 random_table = []
  5 
  6 0.upto(table.length) do |i|
  7   random_table << i
  8 end
  9 
 10 results = []
 11 
 12 0.upto(ARGV[0].to_i) do |fdsa|
 13   random_table = random_table.shuffle
 14   uuid = SecureRandom.uuid
 15   uuid = uuid[0..5]
 16 
 17   beg = Time.now
 18   en = nil
 19   random_table.each do |i|
 20     if table[i] == uuid
 21       en = Time.now
 22       break
 23     end
 24   end
 25   results << en-beg
 26 end
 27 
 28 min = 999
 29 max = 0
 30 median = 0
 31 average = 0
 32 
 33 results.each do |result|
 34   if result < min
 35     min = result
 36   end
 37 
 38   if result > max
 39     max = result
 40   end
 41 
 42   average = average + result
 43 end
 44 
 45 average = average / results.length.to_f
 46 
 47 sorted = results.sort
 48 
 49 median = (sorted[(results.length - 1)/2] + sorted[results.length/2])/2.0
 50 
 51 p "Max: #{max}"
 52 p "Min: #{min}"
 53 p "Median: #{median}"
 54 p "Average: #{average}"

Very similar to the previous code, except I read in the keyspace from a rainbow table generated separately, and iterate over these values (in a sense). I also create an array called random_table that contains all the possible indexes in the array that hold all the possible keys.

I iterate the number of times defined by ARGV[0], and each iterations, I shuffle the random_table. This shuffle algorithm is built into Ruby and is the Fisher-Yates shuffle algorithm. I also generate my uuid and truncate it on each iteration. Inside this iteration, I iterate over each index (that has now been shuffled) in the random_table array and attempt to brute force the 6-character code by referencing the rainbow table by the index of the current inner iteration. I gather the same statistical information as the serial cracking. These are the results for iterations of 100 and 1000:

--- random 100 iters ---
"Max: 4.961166269"
"Min: 0.130944814"
"Median: 2.494897051"
"Average: 2.452227394910891"

--- random 1000 iters ---
"Max: 5.021977897"
"Min: 0.006075905"
"Median: 2.502533613"
"Average: 2.4856869913756237"

As you can see, there is a massive and consistent difference in the speed of cracking the 6-character uuid when being performed "randomly" versus serially. The max number of second is a full 10 seconds faster than cracking serially. The minimums across both serial and random are in line with each other, but the median and average times cracking randomly are almost a quarter that of the serial median and average times. I think these results speak for themselves.

Now, I will admit that I am also measuring the time it takes to generate the permutation in the serial runs, as opposed to the random runs where the values have been precomputed. I do not believe this has that large of an effect on the times recorded. However, if you wanted to compute the value to test against in the random runs at runtime as opposed to beforehand, you could calculate the value of the string based on the current index it resides at in the keyspace.

Assuming a consistent keyspace (a-z,0-9), which leaves no gaps in between characters available for the possible codes to generate, you can calculate this code on the fly. By using powers of 36, and dividing the current index by 36 to the power of the index (from right to left!) of the character in the code to be generated, you can generate your 'random' code on the fly. This is left to an exercise of the reader. If there are gaps in the characters available for code generation, this is still doable, but you must compensate for the fact that, say, 'f' is 20 characters away from '0', and take this into account when generating the code.