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.
