samedi 26 février 2011

NDH Cryptographie Epreuve 3

L'épreuve 3 de cryptographie de la nuit du hack 2010 se présente de cette façon :

Ws szdv od gowhooehzb od nsesp saqpigd pge kp ao5 cp qp spled doyr pgazns
Pour commencer et pour tous les messages chiffrés, il est important de faire une bonne première analyse pour écarter les mauvaises pistes. Ici plusieurs éléments sont marquants :

  • Le message chiffré contient une majuscule en début de phrase
  • Le message chiffré contient des espaces, et la proportion des "mots" semble respectée
  • Le chiffre 5 apparaît dans le message chiffré, avec deux caractères avant ce qui nous fait penser à md5
Ici on écarte rapidement le chiffrement de transposition, car la majuscule en début de phrase et la proportion des mots qui semble respectée ne collent pas.

Le calcul de l'indice de coïncidence donne le résultat suivant (après retrait des espaces, du 5 et transformation du W en w) :

# ./indice_coincidence.rb "wsszdvodgowhooehzbodnsespsaqpigdpgekpao cpqpspleddoyrpgazns"
0.0647307924984876
L'indice de coïncidence est proche de celui de l'anglais et un peu bas pour du français. Cependant le texte est très court, et se fier aveuglément sur l'indice de coïncidence sur un texte de cette longueur est risqué.
Même si la substitution mono-alphabétique a déjà été utilisée lors de la ndh, c'était une mono-substitution particulière puisqu'un chiffrement de césar, donc on se lance dans cette voie, peut être sans issue.

Des outils existent pour casser une mono-substitution comme SCBSolvr. Cependant je trouve que dans ce genre de challenge, le cheminement vers la solution est plus important que la solution en elle même, du coup on n'utilisera pas cet outil.

J'ai écrit un petit outil sans prétention, permettant de faire une recherche de motif dans une liste de mot. Par exemple si on lui passe 123123 ou abcabc en paramètre il sortira tous les mots comme coucou, tintin ou encore bonbon. Le 4° mot du message chiffré gowhooehzb paraît suffisamment long avec plusieurs lettres répétées, un candidat parfait comme pattern.
# pattern -f dict_fr.txt -p gowhooehzb

# pattern -f dict_en.txt -p gowhooehzb
Ca s'annonce mal... un mot de ce type n'existe ni en français, ni en anglais. Donc soit ce mot est un mot inventé, soit ce n'est pas une mono-substitution. On tente d'autres combinaisons pour confirmer ou infirmer nos hypothèses.
# pattern -f dict_fr.txt -p nsesp,spled,pgazns
...
balai aigle intuba
...
maias asdic stroma
...
Bon hormis le fait que mon dictionnaire est à retravailler... aucun groupe de mots ne semble réellement correspondre à ce que nous recherchons. La voie de la mono-substitution est donc sans issue.

On va tenter l'algorithme Vigenère qui est un algorithme très connu et largement utilisé dans les challenges. Plusieurs techniques existent pour casser l'algorithme Vigenère, mais ici une technique est à privilégier. L'analyse préalable du cipher a laissé supposer que le mot md5 était présent dans le texte en clair, une attaque par mot connue ou KPTA pour known Plain Text Attack sera donc utilisée.

Pour que md5 devienne ao5, il faut qu'il y ait un décalage de 14 (soit la lettre "O" dans l'alphabet) sur la première lettre et de 11 (soit la lettre "L" dans l'alphabet) sur la deuxième. On connait donc deux lettres de notre clé, on va tester ces deux lettres comme clé (et donc supposer que la clé fait deux caractères).
Cipher : WSSZDVODGOWHOOEHZBODNSESPSAQPIGDPGEKPAOCPQPSPLEDDOYRPGAZNS
Clé :    LOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLOLO
Plain :  LEHLSHDPVALTDATTONDPCETEEEPCEUVPESTWEMDOECEEEXTPSANDESPLCE
Intéressant... on devine le mot validation. L'algorithme de chiffrement est donc le bon mais la clé est encore mauvaise.

Le chiffré GOWHOOEHZB doit donc devenir VALIDATION. Pour cela, la clé doit être LOLZLOLZLO. On voit bien la répétition, on teste donc la clé LOLZ.

# vigenere.rb -d WSSZDVODGOWHOOEHZBODNSESPSAQPIGDPGEKPAOCPQPSPLEDDOYRPGAZNS -k LOLZ
LEHASHDEVALIDATIONDECETTEEPREUVEESTLEMDDECETEXTESANSESPACE
Voilà épreuve terminée :)

1 commentaire: