Chaos
Collisions in the chaotic hash function.

Problem

What's the fun of rolling up a hash function if it's not chaotic enough?

Solution

We are given the following source code:
1
from secret import flag
2
def ROTL(value, bits, size=32):
3
return ((value % (1 << (size - bits))) << bits) | (value >> (size - bits))
4
​
5
def ROTR(value, bits, size=32):
6
return ((value % (1 << bits)) << (size - bits)) | (value >> bits)
7
​
8
def pad(pt):
9
pt+=b'\x80'
10
L = len(pt)
11
to_pad = 60-(L%64) if L%64 <= 60 else 124-(L%64)
12
padding = bytearray(to_pad) + int.to_bytes(L-1,4,'big')
13
return pt+padding
14
​
15
def hash(text:bytes):
16
text = pad(text)
17
text = [int.from_bytes(text[i:i+4],'big') for i in range(0,len(text),4)]
18
M = 0xffff
19
x,y,z,u = 0x0124fdce, 0x89ab57ea, 0xba89370a, 0xfedc45ef
20
A,B,C,D = 0x401ab257, 0xb7cd34e1, 0x76b3a27c, 0xf13c3adf
21
RV1,RV2,RV3,RV4 = 0xe12f23cd, 0xc5ab6789, 0xf1234567, 0x9a8bc7ef
22
for i in range(0,len(text),4):
23
X,Y,Z,U = text[i]^x,text[i+1]^y,text[i+2]^z,text[i+3]^u
24
RV1 ^= (x := (X&0xffff)*(M - (Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A)
25
RV2 ^= (y := (Y&0xffff)*(M - (Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B)
26
RV3 ^= (z := (Z&0xffff)*(M - (U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C)
27
RV4 ^= (u := (U&0xffff)*(M - (X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D)
28
for i in range(4):
29
RV1 ^= (x := (X&0xffff)*(M - (Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A)
30
RV2 ^= (y := (Y&0xffff)*(M - (Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B)
31
RV3 ^= (z := (Z&0xffff)*(M - (U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C)
32
RV4 ^= (u := (U&0xffff)*(M - (X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D)
33
return int.to_bytes( (RV1<<96)|(RV2<<64)|(RV3<<32)|RV4 ,16,'big')
34
​
35
try:
36
m1 = bytes.fromhex(input("input first string to hash : "))
37
m2 = bytes.fromhex(input("input second string to hash : "))
38
print(hash(m1).hex(), hash(m2).hex())
39
if m1!=m2 and hash(m1)==hash(m2):
40
print(flag)
41
else:
42
print('Never gonna give you up')
43
except:
44
print('Never gonna let you down')
Copied!
Collisions in this hash function have been proven in the following paper: https://eprint.iacr.org/2005/403.pdf.
To solve the challenge, we only need to use two of the examples from the paper.
For instance:
  • fedb02317654a8154576c8f50123ba10bfe54da84832cb1e894c5d830ec3c520
  • 0124fdce89ab57eaba89370afedc45ef401ab257b7cd34e176b3a27cf13c3adf
1
$ nc crypto.zh3r0.cf 2222
2
input first string to hash : fedb02317654a8154576c8f50123ba10bfe54da84832cb1e894c5d830ec3c520
3
input second string to hash : 0124fdce89ab57eaba89370afedc45ef401ab257b7cd34e176b3a27cf13c3adf
4
b'zh3r0{something_chaotic_may_look_random_enough_but_may_be_not_sufficiently_secure} ,courtsey crazy contini : https://littlemaninmyhead.wordpress.com/2015/09/28/so-you-want-to-learn-to-break-ciphers/'
Copied!

How it Works

For the sake of completeness, however, I will briefly explain one of the collisions: the "appending" case.
For the first input, use two 128-bit blocks. Set the first block to the x,y,x,u values:
1
x,y,z,u = 0x0124fdce, 0x89ab57ea, 0xba89370a, 0xfedc45ef
Copied!
Then, the following
1
X,Y,Z,U = text[i]^x,text[i+1]^y,text[i+2]^z,text[i+3]^u
Copied!
would be equivalent to
1
X,Y,Z,U = x^x,y^y,z^z,u^u
Copied!
Since
aβŠ•a=0a \oplus a=0
, this sets X,Y,Z,U to all 0's.
The following
1
RV1 ^= (x := (X&0xffff)*(M - (Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A)
2
RV2 ^= (y := (Y&0xffff)*(M - (Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B)
3
RV3 ^= (z := (Z&0xffff)*(M - (U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C)
4
RV4 ^= (u := (U&0xffff)*(M - (X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D)
Copied!
would therefore be equivalent to
1
RV1 ^= (x := 0 ^ A)
2
RV2 ^= (y := 0 ^ B)
3
RV3 ^= (z := 0 ^ C)
4
RV4 ^= (u := 0 ^ D)
Copied!
Since
aβŠ•0=aa \oplus 0=a
, x,y,z,u = A,B,C,D and RV1 = RV1 ^ A, RV2 = RV2 ^ B, ...
For the second block, simply use the values of A,B,C,D. Following the same steps above, we would find that we have again RV1 = RV1 ^ A, RV2 = RV2 ^ B, ...
Thus, we have
RV1=RV1βŠ•AβŠ•A=RV1βŠ•0=RV1RV_1 = RV_1 \oplus A \oplus A = RV_1 \oplus 0 =RV_1
Without loss of generality, the rotation vectors would therefore go back to their original values.
For the second input, we simply have to append to the first input A,B,C,D two more times. Since x,y,z,u and X,Y,Z,U remain the same, the rotation vectors will again return to their default values.
There are several other collisions mentioned in the paper.
Last modified 7mo ago