# Chaos

## 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:

```python
from secret import flag
def ROTL(value, bits, size=32):
    return ((value % (1 << (size - bits))) << bits) | (value >> (size - bits))

def ROTR(value, bits, size=32):
    return ((value % (1 << bits)) << (size - bits)) | (value >> bits)

def pad(pt):
    pt+=b'\x80'
    L = len(pt)
    to_pad = 60-(L%64) if L%64 <= 60 else 124-(L%64)
    padding = bytearray(to_pad) + int.to_bytes(L-1,4,'big')
    return pt+padding

def hash(text:bytes):
    text = pad(text)
    text = [int.from_bytes(text[i:i+4],'big') for i in range(0,len(text),4)]
    M = 0xffff
    x,y,z,u = 0x0124fdce, 0x89ab57ea, 0xba89370a, 0xfedc45ef
    A,B,C,D = 0x401ab257, 0xb7cd34e1, 0x76b3a27c, 0xf13c3adf
    RV1,RV2,RV3,RV4 = 0xe12f23cd, 0xc5ab6789, 0xf1234567, 0x9a8bc7ef
    for i in range(0,len(text),4):
        X,Y,Z,U = text[i]^x,text[i+1]^y,text[i+2]^z,text[i+3]^u
        RV1 ^= (x := (X&0xffff)*(M - (Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A)
        RV2 ^= (y := (Y&0xffff)*(M - (Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B)
        RV3 ^= (z := (Z&0xffff)*(M - (U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C)
        RV4 ^= (u := (U&0xffff)*(M - (X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D)
    for i in range(4):
        RV1 ^= (x := (X&0xffff)*(M - (Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A)
        RV2 ^= (y := (Y&0xffff)*(M - (Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B)
        RV3 ^= (z := (Z&0xffff)*(M - (U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C)
        RV4 ^= (u := (U&0xffff)*(M - (X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D)
    return int.to_bytes( (RV1<<96)|(RV2<<64)|(RV3<<32)|RV4 ,16,'big')

try:
    m1 = bytes.fromhex(input("input first string to hash : "))
    m2 = bytes.fromhex(input("input second string to hash : "))
    print(hash(m1).hex(), hash(m2).hex())
    if m1!=m2 and hash(m1)==hash(m2):
        print(flag)
    else:
        print('Never gonna give you up')
except:
    print('Never gonna let you down')
```

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

```
$ nc crypto.zh3r0.cf 2222
input first string to hash : fedb02317654a8154576c8f50123ba10bfe54da84832cb1e894c5d830ec3c520
input second string to hash : 0124fdce89ab57eaba89370afedc45ef401ab257b7cd34e176b3a27cf13c3adf
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/'
```

### 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:

```python
x,y,z,u = 0x0124fdce, 0x89ab57ea, 0xba89370a, 0xfedc45ef
```

Then, the following

```python
X,Y,Z,U = text[i]^x,text[i+1]^y,text[i+2]^z,text[i+3]^u
```

would be equivalent to

```python
X,Y,Z,U = x^x,y^y,z^z,u^u
```

Since $$a \oplus a=0$$, this sets `X,Y,Z,U` to all 0's.

The following

```python
RV1 ^= (x := (X&0xffff)*(M - (Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A)
RV2 ^= (y := (Y&0xffff)*(M - (Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B)
RV3 ^= (z := (Z&0xffff)*(M - (U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C)
RV4 ^= (u := (U&0xffff)*(M - (X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D)
```

would therefore be equivalent to

```python
RV1 ^= (x := 0 ^ A)
RV2 ^= (y := 0 ^ B)
RV3 ^= (z := 0 ^ C)
RV4 ^= (u := 0 ^ D)
```

Since $$a \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

$$
RV\_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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ctf.zeyu2001.com/2021/zh3ro-ctf-v2/chaos.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.