Solution de poustouflan pour Fun with Hash

Le code demande à l’utilisateur une unique charge, en hexadécimal :

try:
	m = bytes.fromhex(input())
except:
	print("Access denied!")
	exit(1)

Afin de valider le challenge, la charge de l’utilisateur doit respecter trois contraintes :

• La charge doit contenir l’heure exacte à laquelle l’utilisateur s’est connecté au serveur. Plus précisément, la charge doit encoder le condensat hexadécimal SHA256 de l’heure, encodé une seconde fois en hexadécimal (hexadécimal-ception) :

now = str(datetime.now())
print(now)

# Récupération de la charge

t = sha256(now.encode()).hexdigest()
if t.encode() not in m:
	print("Access denied!")
	exit(1)

• Le condensat MD5 de la charge doit se terminer par les trois octets FC, 5C, 25 :

if not md5(m).hexdigest().endswith("fc5c25"):
	print("Access denied!")
	exit(1)

• Le condensat SHA1 de la charge doit également se terminer par les trois octets FC, 5C, 25 :

if not sha1(m).hexdigest().endswith("fc5c25"):
	print("Access denied!")
	exit(1)

Si la charge répond aux trois contraintes, alors le flag sera affiché. Attention cependant, l’énoncé indique que la connexion n’est maintenue que pour une durée de 30 minutes.

Analyse

Générer un message au hasard aura une chance sur $2^{48}$ de satisfaire en même temps la contrainte MD5 et la contrainte SHA1, c’est trop peu. On va donc étudier d’un peu plus près le fonctionnement de ces deux algorithmes pour essayer d’en tirer profit pour réduire la complexité de notre attaque.

MD5 et SHA1 ont un point commun, ils adoptent tous les deux la construction de Merkle-Damgård. Concrètement, les deux algorithmes suivent cette architecture :

[^1]

[^1]: TikZ for Cryptographers

Le message est décomposé en blocs de taille égale, et les algorithmes de hachage définissent une fonction de compression $f$, prenant deux blocs en entrée, et donnant un bloc en sortie. L’état de l’algorithme est noté par $h_i$ (initialement $h_0 = \text{IV}$ une valeur donnée en dur dans les spécifications de l’algorithme), et cette valeur est mise à jour tour à tour grâce à la fonction $f$, face à chaque bloc de message~: $$h_{i+1} = f(h_i, M_i)$$ La dernière valeur de $h$ correspond alors au condensat indiqué par l’algorithme.

Ce qu’il faut toujours garder en tête lorsqu’un algorithme adopte cette construction, c’est que rajouter un préfixe n’a pour effet que de changer l’état initial $h_0$. C’est le concept au cœur des attaques par extension de longueur, qu’on retrouve couramment en CTF.

MD5 et SHA1 sont réputés pour ne plus offrir de sécurité cryptographique depuis quelques temps.[^2]

[^2]: Cependant, les deux offrent toujours une résistance à la préimage et deuxième préimage suffisante aujourd’hui.

En particulier :

• Une collision MD5 se génère en à peine une minute sur un PC moderne avec \href{https://github.com/brimstone/fastcoll}{fastcoll},
• Une collision SHA1 peut se générer en l’équivalent de 110 ans GPU-unité (faisable en labo, quoi)

Considérons les implications dans notre situation.

• Vu que rajouter un préfixe revient juste à changer l’IV, spécifier un préfixe complexifie rarement la complexité de la recherche de collision. On peut donc considérer que nos messages commenceront tous par l’heure encodée comme demandée, ce qui changera simplement la valeur initiale de $h$, mais ne change rien à la suite de notre attaque. En clair, on n’a pas vraiment à se préoccuper de la contrainte sur l’heure.
• Supposons que l’on trouve une collision MD5 en une minute (avec l’heure en préfixe ou non). On a donc trouvé deux messages différents $m_0$ et $m’_0$ qui donnent le même condensat $h_1$ ($f(m_0, h_0) = f(m’_0, h_0) = h_1$). Par le principe d’extension de longueur, si je rajoute n’importe quel suffixe $m_1$ à $m_0$, alors le condensat de $m_0 || m_1$ sera identique au condensat de $m’_0 || m_1$.

Pour notre challenge, cela est plutôt intéressant, car on sait déjà que trouver un message dont le condensat se finit par les octets désirés se fait en rajoutant un suffixe $m_1$ au hasard environ $2^{24}$ fois (ce qui est très raisonnable). Si on le fait après avoir trouvé une collision entre $m_0$ et $m’_0$, alors on aura deux messages distincts dont le condensat se finit par les octets désirés pour le prix d’un !

Multicollisions

Pourquoi s’arrêter là ? En poussant le concept un peu plus loin, on peut chercher à trouver deux collisions. Partons de notre préfixe $m_0$, l’heure du jour. On se retrouve avec $h_1 = f(m_0, h_0)$. On trouve ensuite deux suffixes $m_1$ et $m’_1$ qui génèrent une collision MD5 depuis $h_1$ (en une minute à peine avec fastcoll). On a donc $m_0 || m_1$ et $m_0 || m’_1$, deux messages distincts qui entraînent un condensat MD5 $h_2 = f(m_1, h_1)$ identique.

Trouvons une nouvelle fois deux suffixes $m_2$ et $m’_2$ qui génèrent une collision MD5 depuis $h_2$ (toujours en une minute à peine). On se retrouve cette fois-ci avec $4$ messages distincts qui ont un condensat identique :

\begin{alignat*}{2}
    f(m_2, h_2) &= f(m'_2, h_2) \\
    \text{MD5}(m_0 || m_1 || m_2) &=  \text{MD5}(m_0 || m'_1 || m_2) = f(m_2, h_2) \\
    \text{MD5}(m_0 || m_1 || m'_2) &= \text{MD5}(m_0 || m'_1 || m'_2) = f(m'_2, h_2) \\
\end{alignat*}

En répétant une troisième fois, on trouverait alors 8 messages distincts ayant le même condensat MD5, etc… Ah, si seulement il existait un super dessin TikZ pour montrer plus visuellement le concept des multicollisions… Oh ! Surprise !

[^1]

Résolution

Avec cette méthode (décrite en beaucoup plus de détails dans le papier d’Antoine Joux, Multicollisions in iterated hash functions) on peut alors trouver $2^k$ collisions en $k$ fois le temps pour générer une seule collision. Si par la suite on trouve un suffixe à rajouter pour qu’un condensat se termine par les octets désirés, rajouter ce même suffixe aux autres messages permettra alors d’avoir une famille de $2^k$ messages distincts dont le condensat se finit tous par les octets désirés.

Utilisons cette méthode pour générer $2^{24}$ messages, préfixés par l’heure du jour, dont le condensat MD5 se finit par FC, 5C, 25 comme désiré. Si on vérifie simplement le condensat SHA1 de chacun de ces $2^{24}$ messages, on aura alors environ $63%$ de chance que l’un de ces messages ait un condensat SHA1 qui se finisse aussi par FC, 5C, 25, ce qui permet de valider les trois contraintes ! En prenant un nombre légèrement supérieur à $24$, on peut largement augmenter cette probabilité.

Au total, on génère $24$ collisions MD5 (ce qui prend à peine 4 minutes sur mon ordinateur portable), puis on cherche un suffixe à rajouter pour contrôler les derniers octets des condensats MD5 ($2^{24}$ condensats MD5 à évaluer sur un seul bloc si on calcule directement depuis $IV=h$ commun à tous nos messages, c’est très rapide), et enfin on calcule le condensat SHA1 de ces messages jusqu’à en trouver un qui respecte la dernière contrainte, soit $2^{24}$ condensats SHA1 à évaluer en moyenne (cette fois-ci, il faut parcourir tous les blocs de chacun des messages, c’est un peu plus long, mais cela reste très raisonnable).

En moyenne sur mon ordinateur portable, je trouve un message respectant les trois contraintes en plus ou moins 5 minutes.

Mise en œuvre

from hashlib import md5, sha1, sha256
from os import system
from Crypto.Util.number import long_to_bytes
from pwn import remote
r = remote('chall.fcsc.fr', 2152)

# Suffixe désiré
TARGET = bytes.fromhex('fc5c25')
ROUNDS = 8 * len(TARGET) + 3 # petite marge

def findcoll(prefix: bytes):
    # Trouve deux messages distincts (coll1, coll2) commençant par
    # le préfixe indiqué, ayant le même condensat MD5

    # Cette fonction utilise le conteneur brimstone/fastcoll,
    # il faut avoir docker d'installé, et c'est tout.

    with open("prefix.bin", "wb") as f:
        f.write(prefix)

    system("docker run --rm -it -v $PWD:/work -w /work brimstone/fastcoll "
           "--prefixfile prefix.bin -o collision1.bin collision2.bin")

    with open("collision1.bin", "rb") as f:
        coll1 = f.read()

    with open("collision2.bin", "rb") as f:
        coll2 = f.read()

    assert coll1.startswith(prefix)
    assert coll2.startswith(prefix)
    assert md5(coll1).digest() == md5(coll2).digest()

    return coll1, coll2


def multicoll(prefix: bytes):
    # Génère une liste de tuples de blocs, tel que choisir
    # n'importe quel bloc à chaque position donnera le même condensat
    # au final.

    blocs = [(prefix,)]
    for _ in range(ROUNDS):
        length = len(prefix)
        coll1, coll2 = findcoll(prefix)
        blocs.append((coll1[length:], coll2[length:]))
        prefix = coll1

    # Trouve un suffixe à rajouter de sorte que tous les condensats
    # finissent par le suffixe désiré.
    i = 0
    while True:
        suffix = long_to_bytes(i)
        payload = prefix + suffix
        if md5(payload).digest().endswith(TARGET):
            break
        i += 1

    blocs.append((suffix,))
    return blocs

def message_generator(blocs, i=0, payload=b''):
    # Génère tous les messages possibles depuis une liste de blocs

    if i >= len(blocs):
        # Sanity check, le message devrait avoir un MD5 finissant par FC5C25
        assert md5(payload).digest().endswith(TARGET)
        yield payload
        return

    for bloc in blocs[i]:
        yield from message_generator(blocs, i+1, payload + bloc)


# L'attaque au complet
if __name__ == '__main__':
    r.recvline()
    now = r.recvline().decode().strip()
    prefix = sha256(now.encode()).hexdigest().encode()
    blocs = multicoll(prefix)

    # On cherche maintenant un message qui a aussi un SHA1 finissant par FC5C25
    for payload in message_generator(blocs):
        if sha1(payload).digest().endswith(TARGET):
            r.sendline(payload.hex().encode())
            r.interactive()