L'algo prend un valeur aléatoire (os.urandom) qui servira de clef de chiffrement.
Puis, il construit un IV de chiffrement en dérivant cette valeur aléatoire 31337 fois.
Enfin, il chiffre le flag avec la clef aléatoire et l'IV dérivé 31337 fois.
On nous donne la valeur d'IV du flag, il faut donc remonter jusqu'à la key aléatoire originale
Inverser 1 itération implique de résoudre l'équation IV_n+1 = (2*IV_n+1)*IV_n % M
On cherche donc, en ligne, comment résoudre cette équation
Bien que j'ai utilisé Sage pour résoudre d'autres challenges,
je ne l'avais pas encore utilisé à ce moment-là et j'ignorai donc qu'il était la méthode à employer.
J'ai envisagé d'utiliser WolframAlpha, qui savait résoudre le problème,
mais le nombre de requêtes est limité: 31337 aurait fait sauter la limite gratuite
Chose amusante, avec (3*x+1)*x, Wolfram n'a pas de solution:
l'équation n'a pas été choisie au hasard
Je suis alors tombé sur cocalc
qui permet de résoudre ce genre d'équations (c'est un "Sage online")
Mais le nombre de messages est limité: si j'affiche la valeur antécédente de IV à chaque itération,
je serai bloqué
Quand un gros calcul doit être fait, afficher les résultat intermédiaires permet de limiter
le risque de perte de temps en cas de crash du calcul. Je le fais donc quasi systématiquement
J'ai donc commencé à réitérer la résolution via cocalc, en copiant/collant les valeurs,
puis en refaisant le calcul avec le dernier antécédant affiché (c'est long!)
En plus, le calcul crashait régulièrement, et nécessitait de redémarrer le projet…
Je suis alors tombé sur
Sage
que j'ai installé
Python plantait alors j'ai essayé Sage windows, via Wine
Le calcul était long sur mon PC… je l'ai donc lancé sur le Windows du travail
après avoir installé Sage (car la machine de taff est plus puissante)
J'ai pas trouvé de solution pour installer les paquets python manquant
J'ai cru que Sage n'utilisait pas la même version de Python que ma ligne de commande, mais non,
la version était bien la même
Et après du pif et du chocolat, j'ai vu que le PATH diffère, et que /home/dragon/.local
manquait, ce qui aurait expliqué le fait que Sage ne trouve pas certains import
Du coup, j'ai installé le paquet Python manquant en sudo pour qu'il soit dans un répertoire
global et non dans mon home .local
Et cela marche enfin! Sage remonte chaque itération de l'IV et retrouve la clef originale (de mon test)
On refait la même chose avec l'IV du challenge, et on laisse calculer
J'ai lancé le calcul sur mon PC de taff, 5 fois plus rapide que mon PC portable perso
Le Windows a terminé en premier, mon Linux moulinait encore
On a alors la clef originale de chiffrement AES (et l'IV, et l'encrypted)
On vérifie le résultat en re-dérivant la clef trouvée
et en vérifiant qu'on retombe sur le bon IV (en hexa)
Principe:
