Affichage des articles dont le libellé est cryptographie. Afficher tous les articles
Affichage des articles dont le libellé est cryptographie. Afficher tous les articles

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 :)

jeudi 17 février 2011

Indice de coïncidence

Quand on analyse un message chiffré, découvrir le type de chiffrement utilisé est primordial. Cette tâche n'est pas toujours évidente mais certains outils peuvent aider. Parmi ces outils l'indice de coïncidence ou IC est un passage obligé... autant que l'analyse de fréquence voire plus.

Présentation de l'Indice de Coïncidence

L'IC est une valeur décimale inventée par Wilfried Friedman et publiée en 1920 qui mesure la probabilité que deux lettres choisies aléatoirement dans un texte soient identiques.

La formule de l'IC est la suivante :
IC = SUM(1,N) Ni(Ni-1) / N(N-1

N : Nombre de lettre dans l'alphabet
Ni : Nombre d'occurrence de la lettre i
Chaque langue ayant ses propres caractéristiques, chaque langue a aussi un IC qui lui est propre (tableau original ici) :

LangueIndice
Russe0,0529
Serbe0,0643
Suédois0,0644
Anglais0,0667
Esperanto0,0690
Grec0,0691
Norvégien0,0694
Danois0,0707
Finnois0,0737
Italien0,0738
Portugais0,0745
Arabe0,0758
Allemand0,0762
Hébreu0,0768
Espagnol0,0770
Japonais0,0772
Français0,0778
Néerlandais0,0798
Malaysien0,0852


On peut trouver des IC différents selon les sources, tout dépend bien entendu du texte d'origine sur lequel il a été calculé. Par exemple un texte issu du livre La disparition de Georges Perec aura peu de chance d'être représentatif de la langue française et aura donc un IC bien différent.

Utilisation de l'Indice de Coïncidence


Bon c'est bien beau tout ça, mais ça n'explique pas en quoi l'IC peut aider au décryptage d'un texte. Pour commencer, la valeur de l'indice est indépendante des lettres utilisées, il mesure la probabilité de tomber deux fois sur la même lettre quelle que soit cette lettre.

Ce qui veut dire que dans le cas d'une substitution mono-alphabétique (césar, carré de polybe...), le texte chiffré et le texte en clair auront exactement le même IC. De la même façon les chiffres de transposition comme celui utilisé à la NDH par exemple, ne font que modifier l'ordre d'apparition des lettres dans le texte, sans en modifier la quantité, l'IC reste donc inchangé.

Quand on travaille sur un texte chiffré suffisamment long (pour être le plus représentatif possible), on peut donc facilement écarter certaines hypothèses grâce à cet outil. Si ce dernier a une valeur de 0.03 il y a peu de chance que ce soit une substitution mono-alphabétique ou une transposition, il faudra donc plus regarder en direction de chiffres polyalphabétiques par exemple de type Vigenère, Porta ou Gronsfeld qui eux modifient la quantité de chaque lettre.

L'utilisation de l'IC va bien au delà de la simple caractérisation du type de chiffrement utilisé. Prenons par exemple un texte en clair que l'on chiffre avec un algorithme qui va modifier la fréquence d'apparition de chaque lettre (Hill, ADFGVX, Playfair...), et on applique un surchiffrement dessus avec une substition mono-alphabétique. A priori l'exercice paraît compliqué pour passer du texte chiffré au texte en clair. Pourtant l'IC apporte ici une aide non négligeable.
Si on décide de faire une recherche exhaustive des clés du premier algo, il ne sera pas possible de savoir si on a trouvé la bonne clé, car le deuxième chiffrement nous masquera la réponse. Cependant on sait que le deuxième algo ne modifie pas l'IC. Il sera donc possible de réduire énormément l'espace de recherche, en ne sélectionnant que les textes qui ont un IC convenable. L'algorithme suivant permet d'expliquer cette démarche.
ecart_accepte = 0.01   // A adapter selon les besoins
Pour toutes les clés K faire
   plain = déchiffrer(cipher,K);
   Si abs(0.0778 - IC(plain)) < ecart_accepte Alors
      plain_possibles.add(plain);
   FinSi
FinPour
L'espace de recherche qui était constitué d'un ensemble aussi important que le nombre de clé est grandement réduit grâce à l'IC.

L'IC peut aussi être utilisé dans la recherche de la taille de la clé pour un message chiffré avec Vigenère. Cet algorithme modifie le rapport de fréquence d'apparition des lettres, et donc l'IC. Cependant il n'est ni plus ni moins qu'un ensemble de N décalages (N césar) où N est la taille de clé.

Prenons ce texte suivant : "CET ARTICLE PARLE DE L INDICE DE COINCIDENCE QUI EST UN OUTIL TRES UTILE EN CRYPTANALYSE" et chiffrons le avec la clé "CLE".

CETARTICLEPARLEDELINDICEDECOINCIDENCEQUIESTUNOUTILTRESUTILEENCRYPTANALYSE
CLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLECLEC
EPXCCXKNPGAETWIFPPKYHKNIFPGQTRETHGYGGBYKPWVFRQFXKWXTPWWEMNPIPNVAAXCYENJWG

Les 1°, 4°, 7°... caractères sont chiffrés avec le caractère C et sont donc décalés de 2 caractères (3° lettre de l'alphabet).
Les 2°, 5°, 8°... caractères sont chiffrés avec le caractère L et sont donc décalés de 11 caractères (12° lettre de l'alphabet).
Les 3°, 6°, 9°... caractères sont chiffrés avec le caractère E et sont donc décalés de 4 caractères (5° lettre de l'alphabet).

Il y a donc 3 groupes de lettres dans le texte en clair qui subissent chacun un décalage différent et chaque groupe de lettre a un IC proche de celui de sa langue d'origine. Etant donné qu'un décalage n'est qu'une substitution mono-alphabétique, l'IC de chaque groupe de lettres chiffrées doit être proche de celui de la langue d'origine, si c'est pas le cas c'est que le groupe n'est pas bon et que donc la taille de la clé est fausse.
# ./friedman_test.rb 1 4 EPXCCXKNPGAETWIFPPKYHKNIFPGQTRETHGYGGBYKP
WVFRQFXKWXTPWWEMNPIPNVAAXCYENJWG
Taille Clé:1 => 0.05213089802130898
Taille Clé:2 => 0.04804804804804805 0.050793650793650794
Taille Clé:3 => 0.07333333333333333 0.09057971014492754 0.07608695652173914
Taille Clé:4 => 0.08187134502923976 0.0915032679738562 0.026143790849673203 0.032679738562091505
Comme on peut le voir ici, une taille de clé égale à 3 donne les IC les plus proches du français. La taille de la clé sera probablement de 3 caractères. Bien entendu, une clé de longueur multiple de 3 doit donner aussi de bons résultats. Ce test est appelé le test de Friedman.

Voilà pourquoi l'indice de coïncidence est un outil indispensable en cryptanalyse qui peut nous aider dans bien des cas.

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

NDH Cryptographie Epreuve 1

Je continue mon parcours sur les épreuves du challenge public de la ndh 2010. Ici on s'attaque à l'épreuve 1 de le cryptographie.


Xnwrk ha dwod lkqn rwhezan aop 27wz62965aawa3b0b1319y489y107y99


Bon on se dit que c'est la première épreuve et que ça ne doit pas être bien difficile, on va commencer simple, voir très simple avec un simple césar.

time0ut# caesar.rb -b -f epreuve.txt
DEC:1 => WMVQJ GZ CVNC KJPM QVGDYZM ZNO 27VY62965ZZVZ3A0A1319X489X107X99
DEC:2 => VLUPI FY BUMB JIOL PUFCXYL YMN 27UX62965YYUY3Z0Z1319W489W107W99
DEC:3 => UKTOH EX ATLA IHNK OTEBWXK XLM 27TW62965XXTX3Y0Y1319V489V107V99
DEC:4 => TJSNG DW ZSKZ HGMJ NSDAVWJ WKL 27SV62965WWSW3X0X1319U489U107U99
DEC:5 => SIRMF CV YRJY GFLI MRCZUVI VJK 27RU62965VVRV3W0W1319T489T107T99
DEC:6 => RHQLE BU XQIX FEKH LQBYTUH UIJ 27QT62965UUQU3V0V1319S489S107S99
DEC:7 => QGPKD AT WPHW EDJG KPAXSTG THI 27PS62965TTPT3U0U1319R489R107R99
DEC:8 => PFOJC ZS VOGV DCIF JOZWRSF SGH 27OR62965SSOS3T0T1319Q489Q107Q99
DEC:9 => OENIB YR UNFU CBHE INYVQRE RFG 27NQ62965RRNR3S0S1319P489P107P99
DEC:10 => NDMHA XQ TMET BAGD HMXUPQD QEF 27MP62965QQMQ3R0R1319O489O107O99
DEC:11 => MCLGZ WP SLDS AZFC GLWTOPC PDE 27LO62965PPLP3Q0Q1319N489N107N99
DEC:12 => LBKFY VO RKCR ZYEB FKVSNOB OCD 27KN62965OOKO3P0P1319M489M107M99
DEC:13 => KAJEX UN QJBQ YXDA EJURMNA NBC 27JM62965NNJN3O0O1319L489L107L99
DEC:14 => JZIDW TM PIAP XWCZ DITQLMZ MAB 27IL62965MMIM3N0N1319K489K107K99
DEC:15 => IYHCV SL OHZO WVBY CHSPKLY LZA 27HK62965LLHL3M0M1319J489J107J99
DEC:16 => HXGBU RK NGYN VUAX BGROJKX KYZ 27GJ62965KKGK3L0L1319I489I107I99
DEC:17 => GWFAT QJ MFXM UTZW AFQNIJW JXY 27FI62965JJFJ3K0K1319H489H107H99
DEC:18 => FVEZS PI LEWL TSYV ZEPMHIV IWX 27EH62965IIEI3J0J1319G489G107G99
DEC:19 => EUDYR OH KDVK SRXU YDOLGHU HVW 27DG62965HHDH3I0I1319F489F107F99
DEC:20 => DTCXQ NG JCUJ RQWT XCNKFGT GUV 27CF62965GGCG3H0H1319E489E107E99
DEC:21 => CSBWP MF IBTI QPVS WBMJEFS FTU 27BE62965FFBF3G0G1319D489D107D99
DEC:22 => BRAVO LE HASH POUR VALIDER EST 27AD62965EEAE3F0F1319C489C107C99
DEC:23 => AQZUN KD GZRG ONTQ UZKHCDQ DRS 27ZC62965DDZD3E0E1319B489B107B99
DEC:24 => ZPYTM JC FYQF NMSP TYJGBCP CQR 27YB62965CCYC3D0D1319A489A107A99
DEC:25 => YOXSL IB EXPE MLRO SXIFABO BPQ 27XA62965BBXB3C0C1319Z489Z107Z99
caesar.rb est un programme faisant juste des décalage de lettres. L'option -b lui dit de tester toutes les possibilités (c'est à dire juste 25 pour un simple César). On voit que le décalage 22 donne le bon résulat.

vendredi 9 janvier 2009

Fonctions de Hachage

Aujourd'hui alors que je lisais le document d'un collègue parlant de la nouvelle attaque permettant de faire un rogue CA à partir de la vulnérabilité du MD5, je réalise que j'ai de nombreuses lacunes sur les fonctions de hachage. Ce billet permet donc de faire une petite introduction sur ces fonctions.

Une fonction de hachage qu'est ce que c'est ? C'est une fonction qui prend en entrée une donnée et qui calcule son empreinte, un petit peu comme l'empreinte digitale d'un doigt. Cette empreinte est une suite d'information caractéristique de la donnée initiale.

Les fonctions de hachage sont à sens unique, ce qui veut dire qu'à partir de l'empreinte, il est impossible de revenir aux données initiales. En d'autres termes, si x représente les données et f() une fonction de hachage, alors il n'existe pas de fonction f-¹() permettant à partir de f(x) de revenir x.

Ceci est assez simple à comprendre. Supposons que notre fonction f() ait comme sortie une empreinte de 128 bits (donc 2¹²⁸ empreintes différentes). Si on calcule f(x) pour x allant de 0 à 2¹²⁸ (donc 2¹²⁸+1 valeurs différentes), il y aura au minimum deux f(x) identiques pour deux x différents.

L'autre particularité importante de la fonction de hachage et qu'il est très difficile de trouver une valeur y qui a comme caractéristique que f(y) = f(x) pour x différent de y. Dans le cas idéal, il faudrait brute forcer la valeur de y (c'est à dire tester en moyenne 2¹²⁸/2=2¹²⁷ possibilités) pour trouver un f(y) = f(x) pour un x donné. Le "pour un x donné" est très important car si x n'est pas fixé, d'après le paradoxe des anniversaires, trouver n'importe quel couple x,y tel que f(x) = f(y) ne revient à faire "que" 2⁶⁴ opérations (racine carré de 2¹²⁸).

Ok tout ça c'est bien beau mais à quoi servent ces fonctions ? Ces fonctions sont très utilisées en informatique et particulièrement en sécurité. Les algorithmes MD5, SHA... sont des fonctions de hachages.
On trouve souvent le résultat de ces fonctions à coté de fichier que l'on veut télécharger par exemple. Ce résultat permet de s'assurer que le fichier en notre possession est bien conforme. Il suffit de calculer le md5 du fichier que l'on possède. Si les md5 sont les mêmes, on a bien la même version (et on ne possède pas a priori une version vérolée, excepté bien entendu si le pirate a pu modifier le site web et le md5 affiché).
Une autre utilité est par exemple l'utilisation pour stocker des mots de passe. On ne stocke plus le mot de passe, mais le hash du mot de passe. De cette façon si un pirate s'empare du fichier (ou accède à la base de données), il ne s'empare plus du mot de passe, mais seulement de son hash (et comme il est impossible de remonter aux données initiales...). La vérification de ce dernier se faisant du coup en comparant le hash de la chaîne fournie avec la valeur stockée.
Enfin un autre exemple d'utilité est la signature numérique. Quand quelqu'un vous envoie un fichier, il calcule l'empreinte de ce fichier et chiffre cette dernière avec sa clef privé. A la réception, il ne vous reste plus qu'à déchiffrer la signature grâce à la clef publique de l'émetteur et à la comparer avec l'empreinte du fichier. Si c'est la même, alors vous êtes sûrs que le fichier envoyé n'a pas été modifié par une tierce personne, car seul l'émetteur a pu chiffrer l'empreinte (seul détenteur de la clef privé).

Maintenant que se passe-t'il quand la fonction de hachage n'est pas idéale ? On ne peut bien entendu toujours pas remonter aux données pour les raisons évoquées précédemment, mais par contre la difficulté pour trouver un y tel que f(y) = f(x) peut être réduite. C'est ce qui s'est produit pour le md5, puis plus tard pour SHA-1 qui réduit la complexité pour trouver une collision de 2⁸⁰ itérations (car le SHA-1 produit une sortie de 160 bits) à 2⁶⁹ en Février 2005, puis de nouvelles recherches ont prouvé qu'il était encore possible de faire mieux.

Jusqu'à présent les failles découvertes permettaient de simplifier le calcul pour trouver un couple x,y tel que f(x) = f(y). Chose intéressante bien entendu, mais beaucoup moins que trouver un y tel que f(y) = f(x) pour un x donné. Cela reste un premier pas vers le cassage total de l'algorithme.

Aujourd'hui les recherches en cryptanalyse sur le MD5 montrent qu'il est possible de trouver un y tel que f(y) = f(x) avec seulement une partie de x fixée. Alors vous allez dire que ca casse pas trois pattes à un canard quand il s'agit du mot de passe. Dans ce cas là c'est vrai qu'une bonne atttaque par dictionnaire (ou par rainbow tables) sera toujours plus intéressante, mais dans certains cas cela peut avoir des conséquences beaucoup plus génantes.