unix4fun

Le puzzle, oui, je parle bien de ce truc, ou on reconstitue une peinture de cheval dans un pre ou un voilier sur un soleil couchant.

Je ne sais pas pourquoi, quand je pense puzzle, j'associe les mots bibelot, kitsch et j'ai l'image testosterone d'un type (sans visage) portant ces t-shirts tres "male" d'un aigle attaquant un serpent au dessus d'un volcan flamboyant, l'image ultime de la determination masculine et motorise... bref...

Quand on est un déchet de l'informatique moderne comme moi, que la crypto c'est un peu comme apprendre le thaïlandais avec victor le matin sur france3 et que malgré tout ces "signes", on s'acharne a vouloir mal prononcer "bonjour" en thai, on en arrive a se retrouver face a des puzzles.. effectivement c'est étrange.. mais il y a parfois des liens marrants a lire sur ces petits "challenges" qui réclament un cerveau et de la curiosité...

Hope you enjoy: http://www.thephoenixsociety.org/puzzles/puzzlesolving.htm

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 !

Depuis hier c'est la me-merde, Debian et tout ses derives sont affectes par ce probleme, en cause un malheureux developpeur ayant commis une petite erreur d'appreciation quand a la suppression de 2 lignes dans le code d'OpenSSL package avec Debian et qui vont creer tout ca..

• explication #1
• explication #2
• explication #3 + si tu ouvres l'oeuf des ptits cadeaux a monter

Je peux pas tout expliquer, j'ai rien d'un matheux, mais je vous jure la maintenant en ce moment j'essaye de comprendre, j'imagine que c'est deja relaye partout, alors comme je bele aussi des fois, je le fais aussi...

C'est vaguement lie au post precedent, le Filesystem cryptographique est capable d'interagir avec l'architecture TCPA bla

le project TPM implemente une TCG Software stack (Trusted Computing Group Software Stack), ca vous permet (quand ca marche) d'utiliser votre chipset TCPA , via une API ouverte et documentee et donc de "potentiellement-avec-un-sacrifice-de-poulet" faire des application qui serait "potentiellement-blablabla" "trusted" (hanlanannaa le raccourci!!) :

• http://trousers.sourceforge.net/

enfin en gros c'est un driver et une API pour TCPA.

le project enforcer est une sorte de veriexec(4) qui utiliserait TPM/TCPA avec qqes features en plus :

• http://enforcer.sourceforge.net/

OpenTC est une tentative de federation avec pour but d'arriver a un "framework" unifie et open source (soit disant, on verra avec le temps..)

en passant j'ai decouvert ca :

• http://os.inf.tu-dresden.de/%7Ekauer/oslo/
• http://prosec.trust.rub.de/trusted_grub.html

En prime la spec TSS

C'est la tête haute, la main sur le coeur et le regard lointain que je débute les hostilités de ce WEF (Week-End Food pour les profanes), et 42ème billet.

Je commence par un papier pas évident à aborder, car il faudra se référer à ce qu'est la logique réversible (compulsez les archives des laboratoires de physique fondamentale du début des années 80 pour savoir de quoi je parle:), notion introduite par Fredkin et Toffoli surtout. Là où ça risque d'être complexe, c'est que moi-même j'avais eu du mal à avoir une version électronique du document, et je m'étais contenté d'imprimer un vieux truc jauni par les années. L'idée à avoir en tête c'est que cette logique à pour but de ne pas dissiper d'énergie (donc youpi les attaques sur canaux cachés, qui prennent du plomb dans l'aile... en théorie) :

1. Reversible Logic to Cryptographic Hardware: A New Paradigm

Un papier qui me semble (du haut de mes très faibles compétences) à première vue un peu fumeux, mais que je vais tâcher de lire quand même. Il semble décrire une forme puissante de cryptanalyse linéraire (merci Matsui) :

2. AES Seems Weak - Linear time secure cryptography

Et le dernier (en attendant d'autres contributions ?:), un article sur l'utilisation de la stéganographie et du watermarking dans le processus de sécurisation de la VoIP. Ca se passe par là :

3. New security and control protocol for VoIP (...)

NOTE : pour rappel, nous n'avons pas encore lu ces papiers (manque de temps, en général), nous estimons juste qu'ils peuvent présenter un intérêt.

Comme Mr week-end food est en vacance je lui pique la vedette.

Les choix de la semaine pour le week-end food, deux petits PDFs par forcément simples (en tout cas pour moi qui n'est pas une lumière, mais je vais me les lire ce week-end et "tenter" de comprendre).

Retenus :

• Cache attacks and countermeasures: the case of AES par Dag Arne Osvik, Adi Shamir et Eran Tromer.
• Introduction to win32 reverse engineering par trew

Bon app' !

Bon alors pour ceusses qui sortiraient de leurs cavernes récemment, voici quelques petits liens indispensables pour se tenir à jour des récentes avancées en crypto. Il s'agit ici de crypto... assez dure, donc ayez quelques notions en arithmétique et en algèbre. Ca serait mieux. Quand même.

L'archive ePrint de crypto

Les archives du Journal of Cryptology, depuis 1988.

Et puis, un truc un peu plus smooth et à la mode, une petite FAQ sur les ECC (oui, les courbes elliptiques).

Amusez-vous bien, en cette période de vacances.