Principe:
Lire la doc et le code Python-c sur le fonctionnement du hashage, et trouver des collisions
Le challenge
Le challenge nous demande de trouver des collisions avec la fonctions hash de Python
(les fichiers sont dispos ici)
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
Résolution en ligne
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):
FCSC{658232b18ebebc53c42dd373c6e9bc788f1fd5693cf8a45bcafbff46dae42e24}
Principe:
