Rating:
# BKPCTF 2016: ltseorg
## Challenge details
| Event | Challenge | Category | Points |
|:------|:----------|:---------|-------:|
| BKPCTF | ltseorg | Crypto | 4 |
### Description
> make some (charlie)hash collisions! ltseorg.bostonkey.party 5555 [https://s3.amazonaws.com/bostonkeyparty/2016/a531382ad51f8cd2b74369e2127e11dfefb1676b.tar](challenge)
## Write-up
The challenge consists of two scripts (one in ruby and one in python) the former of which simply serves to pass input to the second. The second script check whether two input strings passed to it are non-equal but have identical hashes (ie. have a collision) for a custom hash function.
```python
def check(hashstr1, hashstr2):
hash1 = binascii.unhexlify(hashstr1);hash2 = binascii.unhexlify(hashstr2)
if hashstr1 == hashstr2 or hash1 == hash2: return False
elif hash(hash1) == hash(hash2): return True
return False
```
As the name suggests (ltseorg is [groestel](https://en.wikipedia.org/wiki/Gr%C3%B8stl) backwards) the custom hash is based on the Grostl hashing algorithm:
```python
# March-15: After 23 tries I think we fixed the issue with the IV.
IV = binascii.unhexlify("696c61686773726c7177767576646968")
BLOCK_SIZE = 16
key1 = ["00" for x in xrange(32)]; key1[0] = "11";key1 = binascii.unhexlify("".join(key1))
key2 = ["00" for x in xrange(32)]; key2[0] = "FF";key2 = binascii.unhexlify("".join(key2))
P = AES.new(key1, AES.MODE_ECB)
Q = AES.new(key2, AES.MODE_ECB)
def pad_msg(msg):
while not (len(msg) % 16 == 0): msg+="\x00"
return msg
def xor(str1, str2):
out = []
for i in xrange(len(str1)):
out.append( chr(ord(str1[i])^ord(str2[i])) )
return "".join(out)
# "Pretty much" Grostl's provably secure compression function assuming ideal ciphers
# Grostl pseudo-code is: h = P(m + h) + h + Q(m) and this is basically the same thing, right?
# Ltsorg pseudo-code: h = P(m + h) + m + Q(h)
def compress(m, h): return xor( xor( P.encrypt( xor(m, h) ), m), Q.encrypt(h) )
def finalization(m, h): return xor(m, h)[0:14]
def hash(msg):
msg=pad_msg(msg)
# groestl's IV was boring
h = IV
for i in xrange(0, len(msg), BLOCK_SIZE):
m = msg[i: i+BLOCK_SIZE]
h = compress(m ,h)
return finalization(m, h)
```
The prime difference between this algorithm and Grostl proper lies in the compression function. Whereas Grostl's compression function pseudo-code is `h = P(m + h) + h + Q(m)` the compression function used by this algorithm is `h = P(m + h) + m + Q(h)`. As sarcastically hinted at by the comments this is not the same at all as in the latter function an attacker has full control over `m` (as opposed to `h` in the case of Grostl's compression function) which allows us to gain some limited control over the intermediate digest allowing for collisions. Consider the ltsorg compression function `P(m0 + h) + m0 + Q(h)` for the first block of a message where `h = IV` then if we set this block to `m0 = (Pinv(Q(h)) + h)` the resulting intermediate digest will be `P((Pinv(Q(h)) + h) + h) + (Pinv(Q(h)) + h) + Q(h) = (Pinv(Q(h)) + h)` ie. the intermediate digest is equal to the input block. Now consider two messages, the first consisting of a single block m00 and the second of two blocks [m10, m11]. If we set `m00 = (Pinv(Q(IV)) + IV)` the corresponding digest `h00 = (Pinv(Q(IV)) + IV)`. Since the finalization function performs `xor(m, h)[0:14]` we effectively XOR the final input block with its own intermediate digest to obtain the final digest, the result of which will be an all-zero hash digest if both are equal. As such we can set `m10 = (Pinv(Q(IV)) + IV) = h10` and `m11 = (Pinv(Q(h10)) + h10)` resulting in two different messages with identical hash digests as generated by our [solution script](solution/ltseorg_crack.py):
```python
b0 = xor(P.decrypt(Q.encrypt(IV)), IV)
h0 = compress(b0, IV)
b1 = xor(P.decrypt(Q.encrypt(h0)), h0)
input1 = b0.encode('hex')
input2 = (b0 + b1).encode('hex')
assert check(input1, input2)
print input1
print input2
```
Running it gives us:
```bash
nc ltseorg.bostonkey.party 5555
gimme str 1
31f6a1e65472588fab17aadb5e4cdd47
gimme str 2
31f6a1e65472588fab17aadb5e4cdd47723ac6e07026831b6a672f34e586281b
BKPCTF{really? more crypto?}
```
