Cryptographie symétrique¶
Ce sont les systèmes, qui, comme les exemples classiques vus au premier cours, fonctionnent avec une clé secrète partagée. Il en existe principalement deux types :
les chiffrements par blocs (block ciphers):
le texte clair est divisé en blocs de $N$ caractères (en général $N$ bits), et chacun d'eux est chiffré en un bloc de $M$ caractères (en général, $M=N$);les chiffrements par flux (stream ciphers) : on superpose au texte clair une suite pseudo-aléatoire, supposée imprédictible si on ne connaît pas la clé.
Par exemple, les chiffres monoalphabétiques opèrent sur des blocs de 1 caractère, et les chiffres polyalphabétiques sur des blocs de $N$ caractères, où $N$ est la longueur de la clé.
Parmi les chiffres en usage actuellement, DES (Data Encryption Standard),
maintenant remplacé par AES (Advanced Encryption Standard, ex Rinjdael),
Blowfish,
IDEA, sont des chiffrements par blocs.
RC4 (utilisé pour le WiFi, pdf, …) A5/1
(téléphonie mobile GSM), ou le one-time pad sont des chiffrements par flux.
Avec Python, on pourra utiliser le paquetage pycrypto.
import Crypto
help(Crypto)
Le DES (Data Encryption Standard)¶
Le prototype du chiffrement par blocs est le DES (maintenant abandonné au profit de l'AES).
Adopté comme standard aux USA en 1976. C'est une modification du chiffre Lucifer d'IBM, demandée par la NSA. On a longtemps supposé que cette modification était destinée à affaiblir l'algorithme. On a depuis découvert qu'elle lui permettait de résister à des attaques qui n'ont été rendues publiques que bien plus tard.
Le standard DES a été remplacé en 2001 par l'AES (Advanced Encryption Standard).
Il est déjà suffisamment complexe pour qu'on se contente d'une étude superficielle. Avant de l'aborder, commençons par nous familiariser avec son utilisation.
Le DES transforme un bloc de 64 bits en un autre bloc de 64 bits. Il utilise des clés de 56 bits, représentées sur 64 bits (avec un bit de contrôle de parité dans chaque octet).
Il est décrit par une structure de Feistel (du nom de Horst Feistel, auteur de Lucifer).
from Crypto.Cipher import DES
d = DES.new('azertyui') # Clef de 64 bits = 8 caractères
x = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.$$$$$"
print (len(x)) # doit être multiple de 8, d'où les $ ...
y = d.encrypt(x)
y
d.decrypt(y)
help(DES)
En plus de la clef, nous avons deux paramètres optionnels : le mode, et le vecteur d'initialisation.
Pour comprendre leur utilité, chiffrons une petite image (photographie d'un document secret) :
from PIL import Image
im = Image.open("x.png")
im.size, im.mode
s = im.tobytes()
t = d.encrypt(s)
Image.frombytes(im.mode,im.size,t).save('y.png')
Contemplons le résultat
Ce n'est pas brillant. Le problème vient du mode opératoire.
La manière naïve (chiffrer chaque bloc avec la même clé) est appelée mode ECB (Electronic Code Book). Évidemment, les blocs identiques sont chiffrés de manière identique, ce qui présente un risque certain.
Dans le mode CBC (Cipher Block Chaining), on applique sur chaque bloc un "OU exclusif" avec le chiffrement du bloc précédent avant qu’il ne soit lui-même chiffré.
d=DES.new('azertyui',DES.MODE_CBC, 'a1b2c3d4')
t=d.encrypt(s)
Image.frombytes(im.mode,im.size,t).save('z.png')
Contemplons le résultat :
On doit utiliser un vecteur d'initialisation, afin que deux messages identiques, bien que chiffrés avec la même clef, soient chiffrés de manière différente.
d=DES.new('azertyui',DES.MODE_CBC, 'blahblah')
t1=d.encrypt(s)
Image.frombytes(im.mode,im.size,t1).save('w.png')
On obtient
t[:40]
t1[:40]
Réseaux de permutations-substitutions (SPN, Substitution-Permutation Networks)¶
Ils se composent d'un certain nombre $r$ d'étages (ou tours, rounds), qui opérent sur des blocs de $N$ bits.
Chaque étage se compose de S-boîtes (S-boxes) et d'une P-boîte (P-box).
Les S-boîtes calculent des fonctions arbitraires $\{0,1\}^k\rightarrow \{0,1\}^l$.
Les P-boîtes réalisent des permutations des bits.
Un SPN est caractérisé par
- son nombre $r$ d'étages
- Un algorithme de diversification de la clef : $K \rightarrow K_1,K_2,\ldots,K_r$ (clefs d'étage)
- Sa fonction d'étage $w_i = f(w_{i-1},K_{i-1})$ ($w_0$ est le texte clair, $w_r$ le texte chiffré).
Structures de Feistel¶
Il s'agit d'une architecture facilitant la conception et l'implantation des SPN. Chiffrement et déchiffrement utilisent le même algorithme.
La sécurité d'un tel système dépend du choix de la fonction d'étage $f(x,y)$ (qui n'a pas besoin d'être injective), et de l'algorithme de diversification de la clé.
On travaille sur des blocs de longueur paire $N=2N'$ (pour le DES, $N=64$).
Conventions¶
Les blocs de texte clair (plaintext) sont notés $P$. On note $||$ l'opérateur de concaténation, et $\oplus$ l'opérateur de OU exclusif bit-à-bit.
Les blocs sont divisée en deux moitiés de $N'$ bits, $L$ et $R$.
Au départ, $P=L_0||R_0$.
Pour i de 1 à r :
a) calculer $R_i = L_i\oplus f(R_{i-1},K_i)$
b) $L_i = R_{i-1}$
Exemple¶
Pour chiffrer $P$, $${R_0\choose L_0}\rightarrow {R_1=L_0\oplus f(R_0,K_1)\choose L_1=R_0} \rightarrow {R_2=L_1\oplus f(R_1,K_2)\choose L_2=R_1} \rightarrow{R_3=L_2\oplus f(R_2,K_3)\choose L_3=R_2}$$ Pour déchiffrer, $${R_2=L_3\choose L_2=R_3\oplus f(R_2,K_3)}\rightarrow{R_1=L_2\choose L_1=R_2\oplus f(R_1,K_2)}\rightarrow{R_0=L_1\choose L_0=R_1\oplus f(R_0,K_1)}$$
Paramètres du DES¶
Blocs de $N=64$ bits, clef de 64 bits dont seulement 56 sont utilisés (les bits 8,16,24,32,40,48,56 sont des contrôles de parité).
Le nombre de clefs possible est $$2^{56} = 72.057.594.037.927.936$$
C'est beaucoup. Cependant, en 1998, l'EFF (Electronic Frontier Foundation) a pu construire une machine spécialisée, DES Cracker, dite DeepCrack pour seulement \$ 250 000, permettant de retrouver une clef DES en 56 heures. On estime qu'en 1976, une telle machine aurait pu être construite pour 20 millions de dollars, une somme à la portée de la NSA.
Dans la description officielle, les bits sont numérotés de 1 à 64, le bit de poids fort en premier. Par exemple, $18=2^4+2^1={12345\choose 10010}$.
Nombre d'étages $r=16$.
Diversification de la clef On élimine les bits $8i$, $i=1,\ldots,8$. On obtient deux moitiés de 28 bits $K_0=C_0||D_0$.
Pour $i=1,2,9,16$, on calcule $$C_i = {\rm lrot}_1(C_{i-1}),\ D_i = {\rm lrot}_1(D_{i-1})$$ Pour $i=38,10-15$, $$C_i = {\rm lrot}_2(C_{i-1}),\ D_i={\rm lrot}_2(C_{i-2})$$ Les résultats $C_i||D_i$ sont filtrés par une permutation sélective. On obtient 16 clés d'étage de 48 bits.
Fonction d'étage Elle prend en entrée 32 bits, filtrés par une permutation expansive qui en produit 48. Il passent par 8 S-boîtes différentes, ayant chacune 6 bits en entrée et 4 bits en sortie. Les 32 bits sortants sont passés dans une P-boîte.
AES (Advanced Encryption Standard)¶
Issu d'un appel à candidatures international lancé en janvier 1997 et adopté par le NIST (National Institute of Standards and Technology) en 2001. Il utilise peu de mémoire. Il n'est pas basé sur un schéma de Feistel, sa complexité est moindre et il est plus facile à mettre en oeuvre.
L'algorithme prend en entrée un bloc de 128 bits (16 octets), la clé fait 128, 192 ou 256 bits. Les 16 octets en entrée sont permutés selon une table définie au préalable. Ces octets sont ensuite placés dans une matrice de 4x4 éléments et ses lignes subissent une rotation vers la droite. L'incrément pour la rotation varie selon le numéro de la ligne. Une transformation linéaire est ensuite appliquée sur la matrice, elle consiste en la multiplication binaire de chaque élément de la matrice avec des polynômes issus d'une matrice auxiliaire, à coefficients dans le corps fini ${\mathbb F}_{2^8}$
Finalement, un OU exclusif XOR entre la matrice et une autre matrice permet d'obtenir une matrice intermédiaire. Ces différentes opérations sont répétées plusieurs fois et définissent un « tour ». Pour une clé de 128, 192 ou 256, AES nécessite respectivement 10, 12 ou 14 tours.
On trouvera des détails ici.
from Crypto.Cipher import AES
help(AES)
K = open('/dev/urandom','rb').read(16)
K
A = AES.new(K)
msg = '\x00'*128
msg
A.encrypt(msg)
A = AES.new(K,AES.MODE_CBC, b'\xff'*16)
A.encrypt(msg)
Modes opératoires¶
On note $E(P,K)$ la fonction de chiffrement d'un bloc $P$ avec la clef $K$, et $D(C,K)$ la fonction de déchiffrement.
ECB (Electronic Code Book)¶
Les blocs identiques sont chiffrés de la même manière $$C_i = E(P_i,K)$$ Comme on l'a vu, c'est à éviter.
CBC (Cipher Block Chaining)¶
On effectue sur chaque bloc un ‘OU exclusif’ avec le chiffrement du bloc précédent avant de le chiffrer. On utilise un vecteur d'initialisation (IV), généralement aléatoire, comme premier bloc. $$C_0 = IV,\ C_i = E(C_{i-1}\oplus P_i,K)$$
CFB (Cipher Feedback)¶
C'est un chiffrement par flux : $$C_0=IV,\ C_i=P_i\oplus E(C_{i-1},K)$$
CTR (Counter)¶
On engendre un flux en chiffrant un compteur (une fonction $g(i)$). $$C_i = P_i\oplus E(IV+g(i))$$
OFB (Output Feedback)¶
Ce mode transforme un chiffrement par blocs en un chiffrement par flux synchrone, c'est à dire que le flux est indépendant du clair et du chiffré. Cette propriété facilite l'emplo de codes correcteurs d'erreurs. $$I_0=IV,\ O_i=E(I_i,K),\ I_i=O_{i-1},\ C_i=P_i\oplus O_i$$
PGP (OpenPGP CFB Mode)¶
C'est une variante du mode CFB imposée par openPGP. Voir RFC 4880.
A = AES.new(K,AES.MODE_CFB, b'\xff'*16)
A.encrypt(msg)
from Crypto.Util import Counter
ctr = Counter.new(128, initial_value=42)
A = AES.new(K,AES.MODE_CTR, counter = ctr)
A.encrypt(msg)
A = AES.new(K,AES.MODE_OFB, b'\xff'*16)
A.encrypt(msg)
Sécurité des chiffrements par blocs.¶
On distingue plusieurs niveaux d'attaque :
- Chiffré connu seul
- Clair connu
- Clair choisi
On a vu que la force brute (test de toutes les clefs possibles) était devenue possible sur les $2^{56}$ clefs du DES. Elle reste impraticable avec des clefs plus longues, mais il existe des techniques permettant de réduire l'espace des clefs possibles.
La cryptanalyse linéaire (Matsui 1992).¶
Cette technique s'applique aux réseaux de permutations-substitutions (SPN). C'est une attaque à texte clair connu. L'attaquant doit disposer d'un grand nombre de couples (X,Y) de textes clairs/textes chiffrés.
L'idée est de trouver une relation linéaire
$$X_{i_1}\oplus X_{i_2}\oplus\cdots\oplus Y_{j_1}\oplus Y_{j_2}\cdots = K_{l_1}\oplus K_{l_2}\oplus\cdots$$entre certains bits de l'entrée $X$, de la sortie $Y$ et de la clé $K$ qui ne soit pas aléatoire. Si les bits d'entrée et de sortie étaient des variables aléatoires indépendantes, un telle relation serait vérifiée en moyenne une fois sur deux (probabilité $\frac12$).
Supposons qu'on en connaisse une qui ait une probabilité $p$ aussi différente de $\frac12$ que possible.
Algorithme 1 de Matsui¶
- Collecter un grand nombre $N$ de couples $(X,Y)$
- Pour chaque couple, calculer le membre gauche de l'expression linéaire. Soit $T$ le nombre de résultats nuls.
- Si $T$ est plus grand que $N/2$ et si $p > \frac12$ , on conclut que le membre droit doit être 0
- Si $T< N/2$ et si $p < \frac12$ , on conclut encore que le membre droit est 0
- Dans les autres cas, on conclut que le membre droit est 1
Ce n'est pas très efficace, mais on peut faire mieux avec le même principe. On va cette fois tester toutes les valeurs possibles des bits de la clé concernés par le membre droit de la relation.
Algorithme 2 de Matsui¶
- Collecter un grand nombre $N$ de couples $(X,Y)$
- Pour chaque jeu de bits de clé candidats, on calcule une valeur $T$ égale au nombre de fois que la relation est vérifiée
- On sélectionne les candidats qui ont un $T$ le plus éloigné possible de $N/2$.
Pour mettre en oeuvre cette technique, il faut commencer par calculer des « approximations linéaires » des seuls éléments non linéaires du système, à savoir les S-boîtes.
Si $X$ et $Y$ sont l'entrée et la sortie de la S-boîte considérée, sa table d'approximation linéaire est une matrice $2^l\times 2^m$ dont l'entrée $(i,j)$ est $T(i,j)-2^{l-1}$, où $T(i,j)$ est le nombre de fois que la relation linéaire $X|i = Y|j$ codée par les bits 1 de $i$ et $j$ est vérifiée.
Voir ici pour plus de détails.
Le livre Modern Cryptanalysis de Christopher Swenson contient un exemple détaillé en Python.
La cryptanalyse différentielle¶
C'est une attaque à texte clair choisi. Voir ici. La cryptanalyse repose sur des paires de textes clairs qui ont une différence constante. L'opération de différence peut être définie de diverses manières, la fonction OU exclusif est la plus courante. L'attaquant calcule ensuite les différences dans les textes chiffrés, afin d'en extraire des motifs pouvant indiquer un biais. Les différences en sortie du chiffrement sont nommées des différentielles.
Il est maintenant connu que le DES avait été modifié pour résister à cette attaque, alors qu'elle n'a été officiellement découverte qu'à la fin des années 80.
D'autres algorithmes, comme FEAL-4 ont pu être cassés par cette technique.
On trouvera une liste d'attaques ici.