There are two possible solutions to this problem. One involves the method of differential cryptanalysis (normally done on the substitution box SBOX like these), and another brute-force, or more specifically birthday attack solution.

I attempt this using the birthday attack solution. The idea is that the space of state is too small. Indeed, the shuffling of the first stage of the hash:

1
2
3
4
5
6
7
8
9

state = [16, 32, 48, 80, 80, 96, 112, 128]
for i in range(0, len(data), 4):
    block = data[i:i+4]
    state[4] ^= block[0]
    state[5] ^= block[1]
    state[6] ^= block[2]
    state[7] ^= block[3]
    state = permute(state)
    state = substitute(state)

Only state[4:] are modified from the block’s content. Hence, the state space is only 4 bytes (32 bits). To add on, the SBOX is not a true permutation (can verify this by sorting the values in SBOX), and a lot of the values are repeated. Hence, collision is extremely easy with this Substitution-Permutation Network (SPN). The other components of the SPN can be ignored as it is only some transformation of the state in the first stage, hence if we can find two different messages that yield the same state after the first stage, then deterministically we will obtain the same output.

Hence, we can create a one-block birthday attack in $2^{16}$ steps, which should not take too long.

Python Implementation:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105

from os import urandom
from pwn import * 
import json 

SBOX = [
    0xf0, 0xf3, 0xf1, 0x69, 0x45, 0xff, 0x2b, 0x4f, 0x63, 0xe1, 0xf3, 0x71, 0x44, 0x1b, 0x35, 0xc8,
    0xbe, 0xc0, 0x1a, 0x89, 0xec, 0x3e, 0x1d, 0x3a, 0xe3, 0xbe, 0xd3, 0xcf, 0x20, 0x4e, 0x56, 0x22,
    0xe4, 0x43, 0x9a, 0x6f, 0x43, 0xa9, 0x87, 0x37, 0xec, 0x2, 0x3b, 0x8a, 0x7a, 0x13, 0x7e, 0x79,
    0xcc, 0x92, 0xd7, 0xd1, 0xff, 0x5e, 0xe2, 0xb1, 0xc9, 0xd3, 0xda, 0x40, 0xfb, 0x80, 0xe6, 0x30,
    0x79, 0x1a, 0x28, 0x13, 0x1f, 0x2c, 0x73, 0xb9, 0x71, 0x9e, 0xa6, 0xd5, 0x30, 0x84, 0x9d, 0xa1,
    0x9b, 0x6d, 0xf9, 0x8a, 0x3d, 0xe9, 0x47, 0x15, 0x50, 0xb, 0xe2, 0x3d, 0x3f, 0x1, 0x59, 0x9b,
    0x85, 0xe4, 0xe5, 0x90, 0xe2, 0x2d, 0x80, 0x5e, 0x6b, 0x77, 0xa1, 0x10, 0x99, 0x72, 0x7f, 0x86,
    0x1f, 0x25, 0xa3, 0xea, 0x57, 0x5f, 0xc4, 0xc6, 0x7d, 0x7, 0x15, 0x90, 0xcb, 0x8c, 0xec, 0x11,
    0x9b, 0x59, 0x1, 0x3f, 0x3d, 0xe2, 0xb, 0x50, 0x15, 0x47, 0xe9, 0x3d, 0x8a, 0xf9, 0x6d, 0x9b,
    0xa1, 0x9d, 0x84, 0x30, 0xd5, 0xa6, 0x9e, 0x71, 0xb9, 0x73, 0x2c, 0x1f, 0x13, 0x28, 0x1a, 0x79,
    0x11, 0xec, 0x8c, 0xcb, 0x90, 0x15, 0x7, 0x7d, 0xc6, 0xc4, 0x5f, 0x57, 0xea, 0xa3, 0x25, 0x1f,
    0x86, 0x7f, 0x72, 0x99, 0x10, 0xa1, 0x77, 0x6b, 0x5e, 0x80, 0x2d, 0xe2, 0x90, 0xe5, 0xe4, 0x85,
    0x22, 0x56, 0x4e, 0x20, 0xcf, 0xd3, 0xbe, 0xe3, 0x3a, 0x1d, 0x3e, 0xec, 0x89, 0x1a, 0xc0, 0xbe,
    0xc8, 0x35, 0x1b, 0x44, 0x71, 0xf3, 0xe1, 0x63, 0x4f, 0x2b, 0xff, 0x45, 0x69, 0xf1, 0xf3, 0xf0,
    0x30, 0xe6, 0x80, 0xfb, 0x40, 0xda, 0xd3, 0xc9, 0xb1, 0xe2, 0x5e, 0xff, 0xd1, 0xd7, 0x92, 0xcc,
    0x79, 0x7e, 0x13, 0x7a, 0x8a, 0x3b, 0x2, 0xec, 0x37, 0x87, 0xa9, 0x43, 0x6f, 0x9a, 0x43, 0xe4,
]
FLAG = "crypto{??????????????????}"


# permute has the following properties:
# permute(permute(x)) = x
# permute(a) ^ permute(b) = permute(a ^ b)
def permute(block):
    result = [0 for _ in range(8)]
    for i in range(8):
        x = block[i]
        for j in range(8):
            result[j] |= (x & 1) << i
            x >>= 1
    return result

def substitute(block):
    return [SBOX[x] for x in block]

def invert_sub(block):
    return [SBOX.index(x) for x in block]

def hash(data):
    if len(data) % 4 != 0:
        return None

    state = [16, 32, 48, 80, 80, 96, 112, 128]
    for i in range(0, len(data), 4):
        block = data[i:i+4]
        state[4] ^= block[0]
        state[5] ^= block[1]
        state[6] ^= block[2]
        state[7] ^= block[3]
        state = permute(state)
        state = substitute(state)
    
    for _ in range(16):
        state = permute(state)
        state = substitute(state)

    output = []
    for _ in range(2):
        output += state[4:]
        state = permute(state)
        state = substitute(state)

    return bytes(output)

# First stage of the above function
def custom_hash(data):
    state = [16, 32, 48, 80, 80, 96, 112, 128]
    for i in range(0, len(data), 4):
        block = data[i:i+4]
        state[4] ^= block[0]
        state[5] ^= block[1]
        state[6] ^= block[2]
        state[7] ^= block[3]
        state = permute(state)
        state = substitute(state)

    return bytes(state)

# Birthday attack on the SPN
def brute_force():
    d = {}
    while True:
        test = bytes(urandom(4))
        hsh = custom_hash(test)
        
        if hsh in d.values() and test not in d.keys():
            other_entry = list(d.keys())[list(d.values()).index(hsh)]
            return other_entry, test 
        
        d[test] = hsh 

a, b = brute_force()
# a, b = (b'\x0b\xbe\x8a*', b'\x01\xb4\x8a ')
a, b = a.hex(), b.hex()

io = remote('socket.cryptohack.org', 13395)
io.recvline()
to_send = {'a': a, 'b': b}
io.sendline(json.dumps(to_send).encode())
print(io.recvline())

The differential analysis approach is well written on Cryptohack, so I would not cover in here. (also as at the time of writing I am clueless on how it works lmao)