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 revision | ||
heig:su16:sre:lab2 [2016/07/11 09:59] – 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 ====== | ====== 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. | ||
+ | |||
+ | 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 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], | ||
+ | pwd = str.join("", | ||
+ | print(" | ||
- | The first block of code checks for the length of the string using the '' | + | 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 |