Differences

This shows you the differences between two versions of the page.

--- heig:su16:sre:lab2 [2016/07/11 11:55] – Laureline David
+++ heig:su16:sre:lab2 [2018/01/30 16:39] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
 ====== 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 than the password is not directly hardcoded in the binary but will be processed and compared against a reference value and that this process will process at least 1024 passwords to this value.
+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.
-{{ :heig:su16:sre:lab2-output.png?nolink&200 |Lab 2 output}}
 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 =====
+==== Reverse Engineering ====
-{{ :heig:su16:sre:lab2-hash.png?nolink&300|Lab 2 hash function}}
 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 ====
+=== Algorithm Analysis ===
+{{ :heig:su16:sre:lab2-hash.png?nolink&200|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<sub>16</sub>'' or ''13<sub>10</sub>'' 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.
@@ Line 27: / Line 25: @@
     is hash equals to 0x5A155E39
-==== Breaking the Hash ====
+=== 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.
@@ Line 42: / Line 40: @@
         pairs[delta].append(chars)
-Then the cross product of the pairs allows to generate all possible passwords using the following code:
+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]):
@@ Line 48: / Line 46: @@
       print("Password:", pwd)
-Note that the last two values are swapped from their order in the desired hash.
+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).