dimanche 9 janvier 2011

NDH Cryptographie Epreuve 2

L'épreuve 2 de cryptographie du challenge public de la ndh 2010 demande une bonne analyse du cipher (texte chiffré). Pour commencer, il ne faut pas tomber dans le piège du HTML en récupérant le cipher. Le HTML transforme plusieurs espaces en un seul espace par défaut, du coup la résolution du problème devient bien plus ardue.

Le cipher à décrypter est donc :

pArmpamete an, canps'  aeetot pru   drdahefrcief ror.P u llgef,aa tsfi e deeem mea avc lgledinu e sudssoX.XXXXXX

Que nous dit l'analyse du cipher ?
  • On trouve plusieurs classe de caractères : minuscules (en majorité), majuscule, signes de ponctuation. La fréquence de chaque classe à l'air d'être cohérente (à première vue) avec un texte classique. La position par contre n'est pas classique.
  • Il y a un ensemble de X à la fin, comme un espèce de padding.
  • L'analyse de fréquence des lettres nous dit que les lettres E et A sont les lettres qui reviennent le plus souvent, ce qui correspond aux deux lettres les plus fréquentes en Français. Bon l'analyse de fréquence avec un texte aussi court est à prendre avec des pincettes, mais ça reste une information intéressante.
Tous ces éléments ici font passer à un chiffre de transposition. Les chiffres de transposition rectangulaire respectent la fréquence des lettres, ils ne font que mélanger l'ensemble des caractères. En plus ce chiffre nécessite un padding pour pouvoir réaliser correctement le rectangle.

La longueur du cipher est 112. Pour ranger 112 caractères dans un rectangle, on a pas beaucoup de choix sur les différents rectangles possibles : 56x2, 28x4, 16x7, 14x8, 8x14, 7x16, 4x28 et 2x56 (colonne x ligne).

De tous ces rectangles possibles, seuls les rectangles suivants mettent le padding sur la même ligne : 56x2, 28x4, 16x7, 14x8 et 8x14.

On va commencer par le tableau 8x14 qui est celui qui demande la clé la plus petite (clé de 8).

0 1 2 3 4 5 6 7
p A r m p a m e
t e a n , c
a n p s ' a
e e t o t p r
u d r d a
h e f r c i e f
r o r . P u
l l g e f , a
a t s f i e
d e e e m m
e a a v c l
g l e d i n u
e s u d s s o
X . X X X X X X


On remarque que la 2° colonne possède une majuscule sur la première ligne et que c'est le seul caractère différent de X sur la dernière. C'est intéressant, la 2° colonne est donc probablement en réalité la première.
On recherche donc un mot commençant par un A faisant au minimum 9 caractères (il y a un E sous le A), ne possédant que les caractères A, R, P, M, E sur ces 8 premiers caractères et un E en 9° caractère. On regarde les mots du dictionnaire qui respectent cette règle :

time0ut# grep --color -E '^a(r|p|m)(a|r|p|m|e)(a|r|p|m|e)(a|r|p|m|e)(a|r|p|m|e)(a|r|p|m|e)(a|r|p|m|e)e' dic.txt
apparemment

Super ! Un seul mot correspond. De plus les deux lettres suivantes N et T se trouvent sur la deuxième ligne sous les lettres P. Tout fonctionne bien.

Deux clés sont donc possibles car on ne peut pas différencier les deux M dans apparemment :
  • 1,4,0,5,2,7,3,6
  • 1,4,0,5,2,7,6,3
On regarde ce que ça donne :

14052736
A
p
p
a
r
e
m
m
e
n
t
,
c
a
n
'
a
p
a
s
e
t
e
t
r
o
p
d
u
r
a
d
e
c
h
i
f
f
r
e
r
.
P
o
u
r
l
e
f
l
a
g
,
f
a
i
t
e
s
d
e
m
e
m
e
a
v
e
c
l
a
l
i
g
n
e
d
u
d
e
s
s
o
u
s
.
X
X
X
X
X
X
X


14052763
Apparemm
ent,ca
n'apas
etetrpo
durad
echiffer
r.Pour
lefla,g
faites
dememe
avecla
ligneud
dessosu
.XXXXXXX


On voit que la bonne clé est 1,4,0,5,2,7,3,6. Le texte déchiffré est donc :
Apparemment, ca n'a pas ete trop dur a dechiffrer. Pour le flag, faites de meme avec la ligne du dessous.XXXXXXX
Il ne reste plus qu'à appliquer la même opération sur la deuxième ligne et obtenir le résultat.
1b6d0ccf12a5ccbc7d0329cd1580226f

3 commentaires:

  1. Re-Salut, Une fois de plus bien joué.
    Pourrais tu détailler ta commande : grep --color -E '^a(r|p|m)(a|r|p|m|e)(a|r|p|m|e)(a|r|p|m|e)(a|r|p|m|e)(a|r|p|m|e)(a|r|p|m|e)e' dic.txt stp ?

    J'ai bien compris que tu es allé rechercher dans un dico contenant tous les mots existants, mais je ne comprend pas la décomposition que tu fais.

    Merci par avance.

    RépondreSupprimer
  2. Cette commande n'est pas bien compliquée, elle fait appel aux expressions régulières de grep (-E). Un man grep te donnera plus d'informations.
    En gros elle dit :

    Je cherche un mot qui commence par a (^a), puis qui a en deuxième lettre un r, un p, ou un m (r|p|m), puis en 3° lettre un a, un r, un p, un m ou un e (a|r|p|m|e), ainsi de suite... et qui finit par un e (e$).

    RépondreSupprimer
  3. Super, merci bcp pour l'explication.

    RépondreSupprimer