Lunette Cosmico-Galactique (1/2) (Cryptanalyse) - 404CTF2025

Principe:
Retrouver la seed et les paramètres d'un générateur pseudo-aléatoire en brute forçant les incrément possibles issus d'une étape intermédiaire, puis déchiffrer le flag (RSA)

Infos (cf menu latéral):
🚩 Flaggué! +433 points gagnés — 💾 Téléchargez les fichiers du challenge
404CTF{On_p3ut_v0ir3_tr3s_l01n_4v3c...}

Le challenge

Difficile?

J'en déduis que ce challenge, pourtant dit "Difficile" doit en faire être plus simple que prévu

Script

Si on demande des mesures, puis le flag, alors la seed est réinitialisée, ce qui semble rendre le déchiffrement impossible

On va donc faire l'inverse: demander d'abord le flag chiffré, puis faire 3 mesures avec la même seed que le flag chiffré

Tests

En premier lieu, bricolons-nous un script de test qui, à partir d'une seed qu'on connait, va faire les opérations de chiffrement et de mesure (et on essayera alors de retrouver la seed à partir de ça)

Une première piste serait de chercher une faille dans le choix des nombres: mais `getPrime` semble cryptographiquement sûre, et la longueur du nombre premier est trop longue pour être brute forcée

Incrément inconnu

Le coeur du problème va se situer ici: le nombre issu du générateur pseudo-aléatoire est incrémenter d'une valeur, inconnue, jusqu'au nombre premier immédiatement supérieur

Cette opération ne sera pas inversible: pour deux sorties différentes du générateur, disons N pair et N+2 pair aussi, on pourrait avoir le même nombre premier N+3 retourné par genPrime. Il faudra donc trouver une autre méthode que l'inversion de cette fonction.

Avec un petit test, on constate que l'incrémentation est relativement faible, moins de 1102 ici.

L'idée de brute-force est donc éventuellement envisageable: avec 4 appels à genPrime, chacun nécessitant 1102 tests environ, on arriverait à un brute force de l'ordre du milliard de possibilités: cela semble limite.

On ne compte en pratique que 3 appels à genPrime: le 4e provient du flag chiffré, qui ne fait pas partie du brute force à faire

Mais en faisant d'autres essais aléatoire, on s'aperçoit que `genPrime` peut avoir n'incrémenté que très peu, moins de 400 fois (voire moins de 100 fois), ce qui réduirait le brute force à environ 1.000.000 de possibilités: totalement accessible!

Simplifions

D'abord, on va ignorer le `genPrime` et supposer que l'on a directement le retour du générateur aléatoire: à partir de cela, peut-on retrouver la seed?

On peut demander à chatGPT quelle serait la méthode: il en propose une (il propose toujours des trucs de toute manière)

Mais cette fois, la solution n'est pas déconnante: soustraire les deux équations est possible, et ensuite, ayant (x2-x1)*(1/(x1-x0))=a mod M, on voit que la recherche de l'inverse mod M fait sens

Sympa, chatGPT nous donne même le code Python

On teste, et cette fois, la proposition est bonne, on valide l'idée

genPrime

Si on essaie bille en tête, on se mange une erreur

Et en effet, une valeur n'est inversible modulo M que si cette valeur et M n'ont pas de multiple commun

Prenons M = 6. Les valeurs possibles sont alors:

	1	2	3	4	5
0	0	0	0	0	0
1	1	2	3	4	5
2	2	4	0	2	4
3	3	0	3	0	3
4	4	2	0	4	2
5	5	4	3	2	1

On s'aperçoit alors que seules les entrées 1;1 et 5;5 ont une valeur 1 dans le tableau. Donc, seuls 1 x 1 = 1 % 6 et 5 x 5 = 1 % 6 correspondent à l'équation A x B = 1 % 6 définissant A comme étant l'inverse de B modulo 6.
Les autres nombres 2 3 4 n'ont pas d'inverse, et effectivement, ils ont un diviseur commun avec 6.

On peut le voir aussi en disant que X(A=kb) mod (M=kP) <=> k(Xb) mod (kP) sera toujours 0 (si X*b est un multiple de P) ou sera un multiple de k si X*b = P + quelquechose. Et donc, si k n'est pas 1, on ne pourra pas avoir k*(P+qqc) = 1 et A = X*b n'a donc pas d'inverse.

Brute!

Et on retrouve alors nos valeurs de A et B…

… ou pas! `A` semble correct, mais pas `B`!

On va donc laisser tourner le brute force, et au lieu de s'arreter à la première valeur trouvée, on va toutes les afficher: l'une d'elles est alors la bonne paire de valeurs `A;B`

Mais ce script est lent: je n'ai fait qu'un range de 100 valeurs ici: avec un range de 10x plus grand (0 à 1000), il me faudrait 10³ fois plus de temps!

On va donc optimiser la recherche de B, et considérer que dès que le A est trouvé, on le garde

Recover

Ayant réussi à retrouver les paramètres du générateur, on n'a plus qu'à implémenter la résolution du challenge étape par étape en commençant par retrouver Q et P

Ça marche, et on retrouve bien, dans l'une des propositions, la valeur de notre test

On valide que les valeurs P et Q trouvées correspondent bien aux valeurs N données: c'est tout bon

Bien faire étape par étape évitera de se perdre, ou d'avoir un faux résultat intermédiaire dont on ne saurait pas identifier l'origine

RSA

Comme j'ai un peu la flemme, je demande à ChatGPT l'implé de déchiffrement standard du RSA, connaissant P et Q

Là, c'est une implé standard (déjà existante sur le web), donc chatGPT saura faire

On implémente, on teste, et c'est OK: on retrouve notre flag de test!

On demande donc des vraies valeurs au serveur, histoire de pouvoir les brute-forcer

Afin d'encore accélérer les choses, on peut paralléliser le brute force

Plutôt que d'utiliser une lib de parallélisation, ce qui pourrait être un peu chiant, j'ai préféré ajouter trois paramètres au script. Avec le premier, je définis la longueur du range à brute-forcer (100). Avec le second, je découpe le 1er range en N, et ne ferait qu'un seul d'entre eux. Avec le troisième, j'indique lequel des ranges découpées je fait.
Notez que j'aurai aussi pu faire quelque chose du genre range(arg1 / arg2 arg3, arg1 / arg2 (arg3+1)

On le lance avec un range de 500 et 12 cores

Si on n'avait rien trouvé, alors on aurait dû demander de nouvelles valeurs au serveur. En effet, agrandir le range aurait nécessité un long calcul. Il aurait donc été préférable de demander des nouvelles valeurs, en espérant que les genPrime aient nécessité moins d'incrémentation.

Parasite!

Hum… j'avais oublié l'espace entre les deux `print`! 😅

Une fois cette coquille corrigée, c'est tout bon!

Flag: 404CTF{On_p3ut_v0ir3_tr3s_l01n_4v3c...}