You are here: Links of Interest » HEIG-VD » Summer University 2016 » Software Reverse Engineering » Lab 2 - Hash Collisions Galore
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionLast revisionBoth sides next revision | ||
heig:su16:sre:lab2 [2016/07/11 10:00] – Laureline David | heig:su16:sre:lab2 [2018/01/30 15:39] – [Lab 2 - Hash Collisions Galore] Laureline David | ||
---|---|---|---|
Line 1: | Line 1: | ||
====== Lab 2 - Hash Collisions Galore ====== | ====== Lab 2 - Hash Collisions Galore ====== | ||
- | Upon its first execution the '' | + | Upon its first execution the '' |
- | + | ||
- | {{ : | + | |
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. | 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 ==== |
- | {{ : | ||
The first step is to use IDA to disassemble the '' | The first step is to use IDA to disassemble the '' | ||
- | ==== Algorithm Analysis ==== | + | === Algorithm Analysis === |
+ | |||
+ | {{ : | ||
+ | The first block of code checks for the length of the string using the '' | ||
+ | |||
+ | 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. | ||
- | The first block of code checks | + | pairs = { 0x5a: [], 0x15: [], 0x5e: [], 0x39: [] } |
+ | char_range = [c for c in range(33, 127)] | ||
+ | permutations = it.product(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 | ||
+ | for pps in it.product(pairs[0x5a], | ||
+ | pwd = str.join("", | ||
+ | print(" | ||
+ | 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). |