Hash-ish (Cryptanalyse) - FCSC2022

Principe:
Lire la doc et le code Python-c sur le fonctionnement du hashage, et trouver des collisions

Infos (cf menu latéral):
🚩 Flaggué! +336 points gagnés — 💾 Téléchargez les fichiers du challenge
FCSC{658232b18ebebc53c42dd373c6e9bc788f1fd5693cf8a45bcafbff46dae42e24}

Le challenge

Le challenge nous demande de trouver des collisions avec la fonctions hash de Python
Le challenge nous donne une valeur (hash) et on doit trouver un tuple de 2 ints dont le hash lui est égal

Documentation Python

On cherche, sur le net, comment marche le hashage des tuples en Python
On voit alors que le hash d'un int est égal à lui-même (sauf -1, qui sert de flag d'erreur) modulo 2**61 - 1

Code Python-c

Sur le net, on cherche ensuite le fonctionnement du hashage d'objet, ce qui nous donne une fonction de l'API C Py_hash_t PyObject_Hash
On retrouve alors le code de cette API dans GitHub

Attention à bien prendre la bonne version de Python! L'API C a évolué dans le temps

Je me suis aperçu que j'avais la mauvaise version d'API quand les résultats de mes tests ne collaient pas au code Github

Python 3.9

La version Python précise (3.9) est donnée par le challenge en début de fichier, donc, on recommence avec la bonne API C
Je reproduis alors l'algo de hash en code Python pur
Et je m'assure qu'il marche pour quelques valeurs int au pif
On continue, en reversant le code du hash des tuples
On s'aidera d'Internet pour faire ce reverse, et éviter de foirer les bitwise operations :)

Sage

Une fois l'algo recodé, j'ai posé des inconnues en Sage var('a'), dans le but de laisser Sage résoudre le problème d'équations, et ça marche
Toutefois, j'ai arbitrairement fixé un des deux ints (b): parfois, on aura aucune solution et on recommencera avec un autre b

Résolution locale

On se trouve avec un algorithme fonctionnel, qui "bruteforce" un peu les valeurs de b
On utilise cet algo pour résoudre le challenge en ligne, qui nous renvoie un tuple d'ints
On décode ce tuple (la flemme m'a poussé à le faire en ligne via dcode)

Flag: FCSC{658232b18ebebc53c42dd373c6e9bc788f1fd5693cf8a45bcafbff46dae42e24}