Hash Functions - Collisions

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....

In the two keys that we have to “insert”, one has to start with the prefix of “CryptoHack Secure Safe”, and the other must not have this prefix. The two keys have to pass this check: 1 2 3 4 5 6 7 8 h1 = hashes[0] h2 = hashes[1] for i in range(2, 2**(random.randint(2, 10))): h1 = xor(self.magic1, xor(h2, xor(xor(h2, xor(h1, h2)), h2))) h2 = xor(xor(xor(h1, xor(xor(h2, h1), h1)), h1), self....

Thanks to JosePisco for the very useful hint of “a property md5 has on collisions”. Completely shifted my approach. The server is signing the hash of the prime sent using RSA, and there is no information to figure out the private keys so we have to forge two numbers $n_1$ and $n_2$ such that $MD5(n_1) = MD5(n_2)$. Initially my approach is to use fastcoll to generate MD5 collisions with a given prefix, but this approach is just too unreliable, as the probability of finding a prime with some reasonably chosen prefix is too low - fastcoll always generate 1024-bit messages anyways....

Clearly the scheme given is not a hash function, in the sense that it is very easy to invert the function to obtain the original message. Hence, with any arbitrary hash, we can easily construct a message with that hash by inverting the operation. 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 from pwn import * import json BLOCK_SIZE = 32 # Nothing up my sleeve numbers (ref: Dual_EC_DRBG P-256 coordinates) W = [0x6b17d1f2, 0xe12c4247, 0xf8bce6e5, 0x63a440f2, 0x77037d81, 0x2deb33a0, 0xf4a13945, 0xd898c296] X = [0x4fe342e2, 0xfe1a7f9b, 0x8ee7eb4a, 0x7c0f9e16, 0x2bce3357, 0x6b315ece, 0xcbb64068, 0x37bf51f5] Y = [0xc97445f4, 0x5cdef9f0, 0xd3e05e1e, 0x585fc297, 0x235b82b5, 0xbe8ff3ef, 0xca67c598, 0x52018192] Z = [0xb28ef557, 0xba31dfcb, 0xdd21ac46, 0xe2a91e3c, 0x304f44cb, 0x87058ada, 0x2cb81515, 0x1e610046] # Lets work with bytes instead!...