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.

## No comments:

## Post a Comment