Bases de la cryptanalyse

Cryptanalyse

Nous faisons ici un bref survol des techniques qui s'offrent au cryptanalyste (à "l'ennemi").

Nous voyons trois origines principales aux faiblesses des systèmes de cryptage. Au fil du temps, l'évolution de la technique et de la théorie ont modifié leur importance relative.

I. Faiblesses provenant du langage

substitutions monoalphabétiques

Toute langue a une histoire et une structure. L'étymologie, la grammaire, la conjugaison ont une incidence sur la proportion d'utilisation des différentes lettres de l'alphabet utilisé. Pour peu que le texte soit suffisamment long, les fréquences d'apparition des différentes lettres (surtout les plus usitées) se conforment quasi certainement à la répartition de base du langage utilisé.

Pour le français actuel, la répartition de référence s'établit selon l'histogramme suivant :

Cet histogramme est distinctif. Il présente un pic très élevé correspondant au "E", flanqué de deux autres associés à "A" et "I". Viennent ensuite deux bosses correspondant à L-M-N-O et R-S-T-U

L'ordre des fréquences s'établit ainsi [¹] :

E	A	S	I	T	N	...	K
17,14	8,12	7,95	7,58	7,24	7,09		0,05

Si les fréquences individuelles ne suffisaient pas, on pourrait aussi compter le bigrammes :


ES	EN	LE	DE	ON	RE	NT	...
3,97	2,59	2,21	2,16	2,15	2,12	2,12

... voire les trigrammes :

ENT	LES	ION	QUE	TIO	DES	ATI	MEN	...
1,66	1,24	1,20	1,12	1,01	0,86	0,84	0,73

Les différences sont significatives. On conçoit qu'une analyse des fréquences judicieusement menée vienne facilement à bout d'un tel chiffrage.

Exemples dans les cryptages Jules César, affine.

substitutions polyalphabétiques

Dans ce cas, le calcul brut des fréquences n'aide pas, puisque chaque lettre est codée de différentes façons.

Il revient à Charles Babbage, scientifique génial et éclectique, d'avoir trouvé (en 1854) la première méthode d'attaque contre un tel cryptage (Vigenère). L'idée est de rechercher les séquences de lettres, comme XYZ, qui se répètent dans le chiffré. Comment peut s'expliquer une telle répétition ?

il se pourrait que deux séquences différentes du clair, chiffrées avec deux fragments différents de la clef, aient produit par coïncidence deux séquences identiques dans le chiffré. C'est assez peu probable, surtout si la séquence dont on observe la réapparition est suffisamment longue.
le plus vraisemblable est que ces séquences identiques du chiffré correspondent à deux séquences identiques du clair, chiffrées avec le même fragment de la clef. Mais alors, la distance entre ces deux séquences est un multiple de la longueur k de la clef.

Si l'on recommence cet examen pour suffisamment de séquences qui se répètent au sein du chiffré, on obtient un certain nombre de distances qui sont toutes des multiples de k. Celui-ci doit donc diviser le PGCD de toutes ces distances.

Il n'y a plus qu'à subdiviser le chiffré en k "sous-chiffrés" (monoalphabétiques !) auxquels on applique alors une analyse des fréquences.

Exemple dans le chiffre de Vigenère.

Au tournant de la 2^nde guerre, des machines électromécaniques (Hagelin, Enigma) ont rendu possible des périodes k colossales (plusieurs dizaines de millions...) Mais dans le même temps, les cryptanalystes profitaient d'une capacité de calcul accrue... et de l'augmentation du trafic, leur procurant un matériel plus important.

L'équilibre cryptographes/cryptanalystes était ainsi restauré. Le point faible de ces systèmes reste essentiellement le même.

II. Faiblesses liées à l'algorithme

Dans un système de codage contemporain, la fonction qui définit le cryptage ne s'applique pas sur les caractères du clair, mais sur leurs équivalents numériques.

Chaque bloc de nombres du clair est converti en un bloc de nombres du chiffré par une fonction arithmétique. Même en supposant connue sa forme générale, ses paramètres restent difficiles à déterminer. Ils constituent dans ce cas l'objectif du cryptanalyste.

Parmi les pièges qui guettent le cryptographe, citons

les attaques algébriques en direction des systèmes symétriques (DES, AES) ;
les systèmes à clef publique sont peu nombreux et très utilisés. On sait que leur sécurité repose sur une fonction one-way :

logarithme discret pour Diffie-Hellman ;

exponentielle modulaire pour RSA,
qui, si elle est utilisée incorrectement, va pouvoir être inversée par le cryptanalyste

Des méthodes récentes ont fait leur apparition :

cryptanalyse différentielle (E. Biham - A. Shamir) : étude fine de la propagation des différences (M ⊕ M') entre deux couples de clairs lors du chiffrage ;
cryptanalyse linéaire (M. Matsui) : exploitation de biais statistiques dans des relations entre sommes de certains bits clair/chiffré/clef.

Ces méthodes nécessitent de nombreux couples clair-chiffré, et sont donc des moyens d'analyse plutôt que d'attaque.

III. Faiblesses de l'implémentation

Même en supposant un procédé de cryptage (littéral ou numérique) "parfait", sa réalisation matérielle peut trahir le code.

lorsque le chiffrage est (était) confié à un être humain, la fatigue, la paresse pouvaient l'entraîner dans une certaine routine source de redondances exploitables par le cryptanalyste (exemples dans les One-time pad russes) ;
à l'heure actuelle (cryptage numérique calculé par ordinateur), c'est le fonctionnement même de l'électronique qui peut engendrer des "fuites" compromettant un chiffrage mathématiquement sûr. C'est l'origine des redoutables attaques par canaux auxiliaires, qui supposent en général l'accès au hardware de cryptage, ou du moins sa parfaite connaissance. Donnons trois exemples :

attaques temporelles (timing attacks)

Considérons l'algorithme d'exponentiation modulaire rapide programmé naïvement :

    
    expo_mod_rapide(y,x,n)
    resultat ← 1
    tant que x > 0
    faire
      si bit_poids_faible(x) ==  1
        alors resultat ← resultat * y mod n
      fin_si ;
      y ← y² mod n ;
      x ← décalage_droite(x)
    fin_faire
    retourner resultat

À cause de la ligne du test, une différence de marche survient entre un exposant "creux" (avec beaucoup de zéros) et un autre "plein". Ainsi, un chronométrage précis peut révéler des informations sur l'exposant, surtout si l'attaquant fait varier "y".

Une parade consiste à programmer la boucle de manière qu'elle fasse toujours quelque chose, même si le chiffre en cours est 0 (technique de l'échelle de Montgomery).

attaques par consommation électrique (power analysis)

Les circuits électroniques consomment de manière variable en fonction des opérations effectuées. Ces variations sont mesurables par diférentes méthodes (oscillo. rapide / shunt / effet Hall...) Il en résulte un graphe "SPA" (Simple Power Analysis) qui présente différents pics. Le problème est d'isoler les activités en rapport avec le cryptage, ce qui nous amène à...

rayonnement électromagnétique local (EM analysis)

À l'aide d'un mini-solénoïde, on mesure B⃗ et E⃗ en surface d'un composant microélectronique.

On peut ainsi discriminer l'activité de chaque sous-ensemble (CPU, mémoire...)

On peut encore ajouter les attaques différentielles : validation d'une hypothèse de corrélation entre différents jeux de mesures.

Note

[¹] Cette répartition, qui a évolué au cours du temps, n'est pas immuable.

Bases de la cryptanalyse

Généralités

Stéganographie

Cryptanalyse

langage

subs. mono

subs. poly

algorithme

implémentation

timing

power

EM

Littérature

Transpositions

Subs. monoα

Subs. polyα 1 - 2

One-time pad

DES 1 - 2

Clef publique

Knapsack

Diffie-Hellman

RSA 1 - 2

Grands noms

Références