Je suis pas docteur en crypto, mais ca m'empeche pas de chier droit!
Par eau le vendredi 5 février 2010, 04:05 - geeking - Lien permanent
Il y a quelques semaines, une connaissance postait ce truc la en discutant, après avoir jeté un oeil, je ne trouve pas de solution triviale et je me dis bon... c'est juste je suis une quiche en crypto y a un truc incroyable a faire, j'y comprendrais rien... j'apprends ensuite qu'un pote qui mattait aussi l'a pété en 30 minutes... alors bon ok c'est une grosse brute poilue qui a une sorte de "don" pour voir la matrice, mais voilà, ca me fait chier de me sentir comme une merde et pourquoi pas ? je suis peut-être moins mediocre que je pense.
Je me suis dit bon faudra que j'essaye, le temps passe, je tourne autour un peu comme un puceau autour de sa premiere meuf, je flippe et quand je commence a m'approcher, oula trop dur beaucoup trop dur et je rebrousse chemin !
Après quelque temps a tergiverser, à me fouetter et a me sentir comme un clochard, je m'y suis mis hier soir et comme je suis un gros newbie en crypto, je me suis dit que j'allais ecrire comment j'avais attaqué la chose, sans la paperasse de "docteur en crypto" (ou chiffrement, j'en sais rien, j'm'en fous).
Etape 1 - Le probleme
#include <iostream>
#include <cstdlib>
using namespace std;
char *key = "????????";
//char secret[] = "ZJ]]_Y2ec%_hXH]P\\%k_eS2OSW4n\\]f+RJincNUS.QU_eLW].Ngn7F^^.IY17XUSZZYmjJ^!";
//char out[100];
void decrypt(char *secret, char *key){
char c;
char *k = key;
while ((c = *secret) != 0){
*secret++ = (c-32) - ((*k)-64) + 32;
k = *(k+1) ? k+1 : key;
}
}
int main(int argc, char *argv[]){
strcpy(secret, "ZJ]]_Y2ec%_hXH]P\\%k_eS2OSW4n\\]f+RJincNUS.QU_eLW].Ngn7F^^.IY17XUSZZYmjJ^!");
decrypt(secret,key);
cout << "SECRET MESSAGE: " << secret << endl;
return EXIT_SUCCESS;
}
Et là faut retrouver le plaintext.
Etape 2 - C'est quoi ce bordel..?!
On se dit : première hypothèse, si c'est un "challenge" la taille de la clef dans le code source doit bien etre de 8 chars et le "plaintext" doit etre un texte standard en anglais. Ensuite on matte la routine de decryption, on voit que ca "rotate" sur la taille de la key, donc des blocs encrypted de 8 chars à chaque fois, chaque bloc est chiffré avec la même clef.
- c'est un "challenge" donc le plaintext est certainement une phrase, donc des caractères imprimables.
- c'est un "challenge" donc la clef est probablement un mot anglais un truc du genre (vu le language du forum).
- c'est un "challenge" donc le \?\?\?\?\?\?\?\? veut aussi probablement dire que la clef fait 8 bytes"
Etape 3 - Par où je commence !?
Première idée... bon-je-sais-pas-quoi-faire, "when in doubt, use brute force", alors hop on bricole un bruteforcer en carton avec un trombonne, un chewing gum et de l'ammoniac et on se dit que "youpi youpi" dans 10 minutes on a la reponse et pfiou je suis pas trop une grosse tanche comme je pensais, après tout, mon bruteforcer, il est recursif, il verifie que pour chaque byte de clef teste, le "plaintext" sur tous les blocs reste un caractere "possible" (comprendre printable à l'ecran soit entre 0x20 et 0x7D ou 0x7E} et la récursivité arrive pour aller bruteforcer le bytes de clef suivant, si j ai verifié cette condition.
Naif que j'étais je me suis dit... "wai tranquille, devrait pas trop y en avoir", mes fesses wai.. lancant le bruteforce et en loggant dans un fichier, je me suis retrouve avec un file de plus de 18 Go de candidats possibles (./bruteforcer^C^C^C^C^C) qui matchaient mes conditions, pleins de garbage et wai... il fallait tester rien que :
$ bc bc 1.06.94 Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc. This is free software with ABSOLUTELY NO WARRANTY. For details type `warranty'. 255^8 17878103347812890625
hmm merde...je pensais pas autant...hmm et pis ma machine est sur les genoux avec tout ça et mon disque en prends plein la gueule... bruteforce..meme apres triturage pas une bonne idée...
Etape 4 - Le *plaign* et le-pote-qui-connaît-la-crypto (tm)
Un vague optimisation apres exposition du problème a votre "local guru crypto", equation bla, limiter le range des bytes a tester, verifier correlations binaire bla, ne pas bruteforcer tout les chars, effectivement, j'enlève un TAS de candidats, je sais plus je crois que j'etais descendu aux alentours des 12 Go pour le file et la aussi ./bruteforcer-DrCrypto^C^C^C^C, bon j'ai aucun bagage en math, ni aucune technique pour trouver des super algo de pétage de crypto, donc hopla retour case depart, ma bite et mon couteau.
Entre temps j'ai dû passer deja 8 heures effectives sur cette connerie...c'etait il y a 1 ou 2 semaines.
Etape 5 - La bonne vieille haine des familles ou l'envie profonde de soumission !
Alors ma bite et mon couteau, hmm j'ai un cerveau, regardons ça de plus pres a nouveau...je me ré-ouvre tout ca (Featuring la grosse haine) hier soir... je regarde curieusement le ciphertext et je commence par le séparer en bloc comme au debut..
ZJ]]_Y2e c%_hXH]P \%k_eS2O SW4n\]f+ RJincNUS .QU_eLW] .Ngn7F^^ .IY17XUS ZZYmjJ^!
Hmm pas top lisible.. comme ca so..ouais beaucoup mieux..
0 1 2 3 4 5 6 7 Z J ] ] _ Y 2 e c % _ h X H ] P \ % k _ e S 2 O S W 4 n \ ] f + R J i n c N U S . Q U _ e L W ] . N g n 7 F ^ ^ . I Y 1 7 X U S Z Z Y m j J ^ !
Je reviens a mes hypotheses.. je me dis bon, si c'est une phrase, il y aura des espaces et peut etre des virgules, mais pour un challenge mettre de la ponctuation ca me parait chiant.. alors je me dis ok, espaces seulements... ensuite mon oeil est attiré par les 3 . . . sur la colonne du byte 0 de la clef.. en mattant la ligne plus haut je me dis que ca passe pas mal si c'est un espace ca separe bien des mots.., je me bricole vite fait 2 ptits tools a la con... pour bruteforcer la valeur de la clef pour obtenir le plaintext et un autre juste pour encoder 1 byte en lui filant le byte de la clef.
alors, si '.' est un espace quelle est la clef necessaire pour l'obtenir:
$ ./findk . " " cipher: . -> plain: key: 0x4e (N)
Ok "N" bon ca serait eventuellement le premier byte de la clef, c'est possible c'est "printable", on va verifier avec les autres bytes de la meme colonne:
$ ./usek Z N cipher: Z - N -> plain: 4c(L) $ ./usek c N cipher: c - N -> plain: 55(U) $ ./usek \\ N cipher: \ - N -> plain: 4e(N) $ ./usek S N cipher: S - N -> plain: 45(E) $ ./usek R N cipher: R - N -> plain: 44(D) $ ./usek . N cipher: . - N -> plain: 20( ) $ ./usek Z N cipher: Z - N -> plain: 4c(L)
Hmm là je me dis, intéressant, il n'y a pas un seul caractère relou, genre virgule, caractères de contrôles a la noix, #, @ etc... que des chars et étrangement ils sont tous en majuscule. Je me refais une petite ligne :
//char dasecret[] = "ZJ]]_Y2ec%_hXH]P\%k_eS2OSW4n\]f+RJincNUS.QU_eLW].Ngn7F^^.IY17XUSZZYmjJ^!"; // = = = = = = = = = // L U N E D . . . L KEY: N???????
Je représente les "espaces" par des "." histoire de rendre ça un peu plus lisible pour mon cerveau de mollusque ! Je reviens sur ma petite matrice de caractères, je matte la colonne #2 et je me dis, tiens les "%" ca pourrait être les espaces du début de la phrase, vu que j'ai trouvé les espaces de la fin de la phrase (enfin je crois), alors j'essaye..
$ ./findk % " " cipher: % -> plain: key: 0x45 (E) $ ./usek J E cipher: J - E -> plain: 45(E) $ ./usek % E cipher: % - E -> plain: 20( ) $ ./usek W E cipher: W - E -> plain: 52(R) $ ./usek Q E cipher: Q - E -> plain: 4c(L) $ ./usek N E cipher: N - E -> plain: 49(I) $ ./usek I E cipher: I - E -> plain: 44(D) $ ./usek Z E cipher: Z - E -> plain: 55(U)
Et là je me dis, ca sent le mouflon ! J'ai de nouveau que des lettres capitales et le second byte de ma clef est aussi en lettre capitale, ca ne me semble plus etre une coincidence... Yes j'ai 2 bytes de la clef ! NE.. hmm
//char dasecret[] = "ZJ]]_Y2ec%_hXH]P\%k_eS2OSW4n\]f+RJincNUS.QU_eLW].Ngn7F^^.IY17XUSZZYmjJ^!"; // = = = = = = = = = // LE U. N. ER DE .L .I .D LU KEY: NE??????
Bon première idée qui me vient en tête, NE, NET ?! 'vais essayer donc "T" pour la 3ème lettre...
// LEI U.K N.W ER. DEU .LA .IS .DE LUE KEY: NET????? NET could be a word but..
Alors je cherche des mots anglais commencant par NET (comme NETWORK) pour la clef, mais je ne trouve rien dont la 4ème lettre passe..hmm Ensuite en mattant de le plaintext avec 3 lettres, LEI, DEU, LUE, je trouve pas ou peu de mots en anglais.. j'ai pas ou peu d'idées de comment passer à la prochaine étape, hmm mais j'ai dit que j'allais te soumettre alors tu m'echapperas pas $#@!$#@!$!@$!
Etape 6 - Le breakthrough
Grmlgrmlgrm, quelques verres dans le nez avec une copine, une bonne discussion, du vibe... je rentre chez moi vers 0h00, je mange rapidos, je rouvre mon petit fichier.. et hmm Je commence à douter de ma 3ème lettre... je fais marche arrière pour la 3ème lettre et je réfléchis...
0 1 2 3 4 5 6 7 N E ? ? ? ? ? ? Z J ] ] _ Y 2 e c % _ h X H ] P \ % k _ e S 2 O S W 4 n \ ] f + R J i n c N U S . Q U _ e L W ] . N g n 7 F ^ ^ . I Y 1 7 X U S Z Z Y m j J ^ !
4ème colonne 3 x n, hmm le coup des espaces peut-être, je retente, groumpf je tombe sur des caractères relous en decodant la colonne.. pas la bonne partie de la clef, je refais la même chose pour le reste... 2x7, 2x_, etc... ca passe pas.. grmlbmlbmb..
Je me dis bon... qu'est-ce que j'ai là.. et je me rends compte que j'ai de nouvelles hypothèses de base sur mes trouvailles précédentes..
- phrase entièrement en majuscules.
- clef entièrement en majuscules.
- 1 byte de clef valide devrait vérifier une colonne entière en majuscule ou avec un espace
Chassez le naturel, il revient au galop : when in doubt, use brute force! Cette fois je bruteforce uniquement 2 blocs de ciphertext, je prends entre 0x41 et 0x5A pour les bytes de la clef, je ne teste que isupper(), isblank() et isdigit() on sait jamais si il y a du "leet speak"..
$ ./bf2 > bf2results $ ls -la bf2results -rw------- 1 eau users 41570100 2010-02-05 01:33 bf2results
Hmm 41 Mo de results, ca va, c'est très très loin des 12 Go, je dois pas être loin! Je matte le contenu :
key: NEITVARW, index: 8 buffer: LETIIX NU VTBGK9N key: NEITVARX, index: 8 buffer: LETIIX MU VTBGK8N key: NEITVARY, index: 8 buffer: LETIIX LU VTBGK7N key: NEITVARZ, index: 8 buffer: LETIIX KU VTBGK6N key: NEITVBRK, index: 8 buffer: LETIIW ZU VTBFKEN key: NEITVBRL, index: 8 buffer: LETIIW YU VTBFKDN key: NEITVBRM, index: 8 buffer: LETIIW XU VTBFKCN key: NEITVBRN, index: 8 buffer: LETIIW WU VTBFKBN
Bon signe, les candidats font à peu pres tous la meme taille, et y a ces 2 chars partout, ensuite je commence par virer les trucs improbables à coup de grep
$ cat bf2results | grep -v QQ | grep -v GKD | grep -v VXM | grep -v KDN \ | grep -v K9N | grep -v K8N | grep -v K[0-9]N | grep -v YSN | grep -v EZX \ | grep -v XTF | grep -v KBN | grep -v NTT | grep -v KCN | grep -v YRF \ | grep -v SQL [...] key: NETYPSRO, index: 8 buffer: LEIDOF VU KOH5KAN key: NETYPTRK, index: 8 buffer: LEIDOE ZU KOH4KEN key: NETYPTRO, index: 8 buffer: LEIDOE VU KOH4KAN key: NETYPURK, index: 8 buffer: LEIDOD ZU KOH3KEN key: NETYPURO, index: 8 buffer: LEIDOD VU KOH3KAN key: NETYPVRK, index: 8 buffer: LEIDOC ZU KOH2KEN [...]
Etape 7 - Finish HIM!!
Et la je me dit tiens c'est bizarre... VU ca veut rien dire en anglais, mais ZU en ALLEMAND.. c'est TO... et la je commence a me dire merde, c'etait pas en anglais, on va verifier... je filtre que les " ZU ", du coup je vois que les 2 derniers bytes de la clef sont toujours "RK" :
key: NEZZWRRK, index: 8 buffer: LECCHG ZU ENA6KEN key: NEZZWSRK, index: 8 buffer: LECCHF ZU ENA5KEN
Et là ca devient de plus en plus des mots, alors je m'excite, mais peut-être que mon "T" pour le 3ème char était bon !!!!!! Hop hop hop!
$ cat bf2results | grep -v QQ | grep -v GKD | grep -v VXM \ | grep -v KDN | grep -v K9N | grep -v K8N | grep -v K[0-9]N \ | grep -v YSN | grep -v EZX | grep -v XTF | grep -v KBN \ | grep -v NTT | grep -v KCN | grep -v YRF | grep -v SQL \ | grep " ZU " | grep "key: NET" | wc -l 4146
Je matte vite fait les results :
key: NETZWDRK, index: 8 buffer: LEICHU ZU KNADKEN __key: NETZWERK, index: 8 buffer: LEICHT ZU KNACKEN__ key: NETZWFRK, index: 8 buffer: LEICHS ZU KNABKEN key: NETZWGRK, index: 8 buffer: LEICHR ZU KNAAKEN key: NETZWORK, index: 8 buffer: LEICHJ ZU KNA9KEN
Et là je me dis BORDEL C'EST DE L'ALLEMAND DE MERDE $#@! $#@!$#@!$!#@$#@! Je vérifie sur translate bidule.... "Easy to crack" RAH $#@ $ #@!$ #@! $#@! $ #@!$ #@! Hop je passe le tout avec la super clef que je viens de recover, NETZWERK :
Et voilà le plaintext :
"LEICHT ZU KNACKEN WENN DER TEXT DEUTLICH LAENGER IST ALS DE SCHLUESSEL"
Et sa traduction :
"Easy to crack WHEN THE TEXT IS SIGNIFICANTLY LONGER THAN DE KEY"
Juste pour les relous, il y a certainement 10000321432 moyens de faire mieux et plus simple, les commentaires sont les bienvenus pour les critiques constructives ! N'hesitez pas, c'etait certainement pas la methode la plus élégante, mais c'est passé et le temps effectif passé dessus est de bien une 15 aines d'heures, pas vraiment les quelques jours que je pensais... mais je suis toujours très loin des 30 minutes :)
Enjoy !

Commentaires
Le code C est assez straightforward : la clef est répétée. Je suppose une taille de clef de 8, comme il y a 8 "?". Donc les caractères n°0, 8, 16, 22, etc. du message sont encodés avec le caractère 0 de la clef, les caractères n°1, 9, 17, 25, etc. avec le caractère 1 et ainsi de suite. Donc, pour faciliter l'analyse, on regroupe les caractères qui correspondent à un même caractère de clef.
C'est chose faite. Le message n'est pas bien grand, mais regardons tout de même, au sein de chaque set de caractère qui correspond à un caractère de clef, quels sont les éléments récurrents.
... info = {}... print '[', i, ']', per_key[i], ':', idx, '(', info[idx], ')'Parfait. De là, on peut commencer à faire des suppositions. Par exemple, si dans le set 0, le "." est un espace, alors nous sommes capables de traduire l'ensemble des caractères de la liste et de trouver le caractère de clef correspondant. C'est ce que fait la méthode suppose().
La méthode seek(), codée avec les pieds, se charge de faire des suppose()-itions avec un charset donné (je considère que le message source est [a-zA-Z0-9,:\.! ], qui est parcouru dans l'ordre de distribution naturel des caractères dans la langue française (merci wikipedia), auquel j'ai rajouté l'espace, élément le plus récurrent dans un texte. Si le résultat à l'air correct, elle le retourne. Sinon, elle ne trouvera rien.
... raise ValueError('')... raise ValueError('')C'est parti, recherchons pour le premier set, en se basant sur le caractère qui est apparu le plus souvent.
Il semble donc que le caractère "." est un espace, et que le premier caractère de clef est donc N... Le choix est simple, le texte ayant l'air a priori plus propre et respecter une distribution correcte. Le doublon est dû au code ci-dessus codé à la rache (tm). On sauve, et on continue...
Ce résultat a plutôt tendance à conforter dans le résultat que le premier était bon, on continue... Deuxième caractère de clef obtenu : NE...
Troisième caractère de clef obtenu : NET...
WTF?!@# OK, rien de trouvé, il y a certainement des caractères bizarres, ou accentués. On y reviendra.
On sauve, on en est donc à : NET?W...
Là, à peu près tous ont l'air cohérent. On prend le premier, parce que c'est celui qui avait le plus de tomber (ordre de distribution). S'il est faux, on y reviendra. On sauve, on en est donc à : NET?WE...
On sauve, on en est donc à : NET?WER...
Re-WTF!@#!@ Certainement d'autres caractères chelous. On va les chercher à la main, juste avec suppose(). Mais d'abord, pour avoir une idée sur quoi chercher, regardons à quoi ressemble la chaîne de caractère.
Ce n'est pas du Molière. On peut supposer de l'allemand, avec un premier "LEICHT". Voyons-voir...
>>> suppose(per_key[3], (']', 'C'))('Z', 'CNETTET\x17S')Ca a l'air correct, la clef serait donc NETZWER? on sauve, et on continue...
On peut supposer un "ZU" en lieu et place de "eU"...
>>> suppose(per_key[7], ('e', 'Z'))('K', 'ZED HRSH\x16')Ca a l'air pas mal, la clef serait donc NETZWERK, voyons voir...
Et voilà ! A noter que ça aurait pu très bien s'automatiser beaucoup plus... Mais tout ça est loin. Et rajouter des caractères bizarres c'est tricher. Vraiment.
C'est facile, la clef c'est "NETWERK", pas besoin de crypto pour la trouver, vive google :-)