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 !