Il s'agit d'un challenge à 200 points au FCSC 2021.
Le contenu de hashy_parmentier.py est le suivant :
#!/usr/bin/ipython
import sys
from Crypto.Cipher import AES
from Crypto.Util.strxor import strxor
N = 64
class Hash:
def __init__(self):
self.h = b"\x00" * 4
def update(self, data):
assert len(data) % 4 == 0 # TODO
for i in range(0, len(data), 4):
block = data[i:i+4] * 4
h = self.h * 4
self.h = strxor(strxor(h, block), AES.new(h, AES.MODE_ECB).encrypt(block))[:4]
return self
def digest(self):
return self.h
if __name__ == "__main__":
S = set()
for i in range(4, 4 * (N + 1), 4):
try:
m = input(">>> Message #{:d}: ".format(i // 4))
m = bytes.fromhex(m)
assert len(m) == i
H = Hash()
S.add(H.update(m).digest())
except:
print("Error input.")
exit(1)
if len(S) <= 6:
print("Congratulations!! Here is your flag:")
print(open("flag.txt", "r").read().strip())
elif len(S) < 12:
print("Almost there!")
elif len(S) < 36:
print("Keep it up!")
elif len(S) < 64:
print("This is a good start, try again")
else:
print("Nope!")
Le but est donc de trouver un ensemble de \(N\) messages ayant une taille allant de 4 à \(4N\). Le hash de chacun de ces messages doit être le même.
Analyse du problème
On peut réécrire la fonction de hash comme ceci :
def hash(data):
assert len(data) % 4 == 0
h = b"\x00" * 4
for i in range(0, len(data), 4):
block = data[i:i+4] * 4
h = self.h * 4
h = strxor(strxor(h, block), AES.new(h, AES.MODE_ECB).encrypt(block))[:4]
return h
Essayons de formaliser un peu tout ca.
Pour chaque message \(b\) découpée en blocs de 4 t.q. \(b = b_0||..||b_{n-1}\), on calcule \(h_{i+1} = \mathcal{F}(h_i,b_i)\) , où \(\mathcal{F}\) est l'intérieur de la boucle for. Le hash final est \(h_n\).
On remarque que si pour un \(h_1\) donné (par exemple \(h_1 = \mathcal{F}(h_0,0)\)), on arrive à trouver un bloc \(x\) tel que \(\mathcal{F}(h_1,x) = h_1\), alors non seulement on aura une collision, mais en plus il suffit de répéter le bloc \(x\) pour avoir des blocs de différentes tailles ayant le même hash.
En effet, si \(\mathcal{F}(h_1, x) = h_1\), alors \(\mathcal{F}(\mathcal{F}(h_1, x), x) = h_1, \mathcal{F}(\mathcal{F}(\mathcal{F}(h_1, x), x), x) = h_1\), donc \(b = 0||x\), \(b' = 0||x||\), et \(b'' = 0||x||x||x\) auront le même hash, et ainsi de suite.
Reste à trouver notre collision sur \(\mathcal{F}\).
Trouver une collision sur \(\mathcal{F}\)
Pour ca, on commence par fixer b_0 = h_0 = b"\x00" * 4
On a alors h_1 = b'f\xe9K\xd4'.
Le but va donc être de trouver 4 octets x tel que
h_1 == strxor(strxor(h_1 * 4, x * 4), AES.new(h_1 * 4, AES.MODE_ECB).encrypt(x * 4))[:4]
est vrai, c'est a dire \(h_1 = (h_1 \oplus x) \oplus AES_{h_1||h_1||h_1||h_1}(x||x||x||x)[4:]\)
Par les propriétés du xor, ca se simplifie en \(x = AES_{h_1||h_1||h_1||h_1}(x||x||x||x)[4:]\).
Pour trouver cette valeur, j'ai lancer un bout de script avant d'aller me coucher :
from tqdm import tqdm
from Crypto.Cipher import AES
h_0 = b_0 = b"\x00" * 4
h_1 = AES.new(h_0 * 4, AES.MODE_ECB).encrypt(b_0 * 4)[:4]
aes = AES.new(h_1 * 4, AES.MODE_ECB)
for x in tqdm(range(2**32)):
x4 = int.to_bytes(x,4,"big") * 4
if aes.encrypt(x4)[:4] == x:
print("got one ! ", val)
else:
print("nope :(")
Au petit matin, j'ai obtenu la valeur 3216551748 soit b'\xbf\xb8\xafD' en bytes.
Il suffit maintenant de créer les collisions comme décrit dans la 1ère partie, et c'est terminé.
Petit script des familles:
from pwn import remote
io = remote("challenges1.france-cybersecurity-challenge.fr", 6001)
x = int.to_bytes(3216551748, 4, "big")
bn = b"\x00" * 4
io.sendline(bn.hex())
for n in range(65):
bn += x
io.sendline(bn.hex())
for _ in range(10):
print(io.recvline()) # FCSC{b400aabf21470544850632fb99c4fd06df6b69c07fd02fc2ef685a71b57afd99}
Note:
Cette manière de construire une fonction de hash en se basant sur une fonction de compression appelée itérativement pour chaque bloc s'appelle construction de Merkle-Damgård. c'est une forme assez classique notamment utilisé par MD5 et SHA-1.
