Lab 2 - Hash Collisions Galore

Upon its first execution the L2 binary asks the user to generate 1024 passwords. With this information we can assume that the password is not directly hardcoded in the binary but will be processed and compared against a reference value and that this process will map at least 1024 passwords to this value.

Using this assumption we can assume that the binary computes a hash of the given password and check it against a reference hash. Moreover due to the need to provide multiple passwords, we can assume that this hash function is weak against collitions.

Reverse Engineering

The first step is to use IDA to disassemble the L2 binary. This gives us a symbolic representation of the program's code. After analysis of the general program flow, we can see that the program looks for the presence of a single argument which we can assume is the user-supplied password. The program then checks the password (pictured left) and prints a message if the password matches an expected input.

Algorithm Analysis

Lab 2 hash function The first block of code checks for the length of the string using the repne scasb instruction. This instruction is a complex instruction that decrements the ecx register while the byte at the address of the edi register is non zero. With this knowlege in mid we can infer that the program expects a password of length 0xFFFFFFFF - 0xFFFFFFF2 or 0xD₁₆ or 13₁₀ including the null-byte terminating the string so 12 significative characters. If the string does not contains 12 characters, the program jumps to the error block, otherwise it jumps to the second block.

The second to fourth block perform the hashing on the string. The hashing algorithm can be expressed as the following pseudocode:

  chunks is [[int8 * 4] * 3] := partition password in chunks of 4 characters
  hash is int32 := 0
  for each chunk in chunks do
    segment is int32 := chunk[0] || chunk[1] || chunk[3] || chunk[2]
    hash := hash xor segment
  end
  
  is hash equals to 0x5A155E39

Breaking the Hash

Since this algorithm performs a xor compression it is trivial to find three individual characters whose xor compression is equal to an 8 bit chunk out of the reference value. A script that can generate all possible passwords is then a trivial endeavour.

Firstly we need to generate all character triplets that xor to one of the desired values.

  pairs = { 0x5a: [], 0x15: [], 0x5e: [], 0x39: [] }
  char_range = [c for c in range(33, 127)]
  permutations = it.product(char_range, char_range, char_range)
  
  for chars in permutations:
    delta = chars[0] ^ chars[1] ^ chars[2]
    if delta in [0x5a, 0x15, 0x5e, 0x39]:
      pairs[delta].append(chars)

Then the cross product of the pairs allows to generate all possible passwords using the following code which computes the cross product of the four sets and creates a password for each entry.

  for pps in it.product(pairs[0x5a], pairs[0x15], pairs[0x5e], pairs[0x39]):
    pwd = str.join("", sum([[chr(pp[n]) for pp in pps] for n in range(0, 3)], []))
    print("Password:", pwd)

Note that the last two values are swapped from their order in the desired hash. The total number of passwords can be obtained by multiplying the size of the four sets and is 1781102812020000 (or 18.98Pb of data or 1.58Pb by compressing data).