Cryptographie symétrique 17 mars 2009

Cryptographie symétrique Terminologie

Texte chiffré ou
Texte en clair cryptogramme Texte en clair
(‘Cleartext’) (‘Ciphertext’) (‘Cleartext’)

Nicolas Pioch
17 mars 2009 Clé de chiffrement k1 Clé de déchiffrement k2
(‘Encryption Key’) (‘Decryption Key’)

Taxinomie Les chiffres symétriques

• Chiffres symétriques • Les chiffres en continu

– La même clé est utilisée pour chiffrer et – Fonctionnement semblable à un masque à
déchiffrer usage unique, mais avec une clé de taille limitée
– Chiffres en continu ou par bloc – La clé est « étirée » pour générer un long flux
• Chiffres à clé publique pseudo-aléatoire appelé ‘flot de clés’
(‘keystream’), qui est utilisé comme masque
– Deux clés distinctes : une clé publique pour
chiffrer, et une clé privée pour déchiffrer • Les chiffres par bloc
– Permet de réaliser des signatures digitales – Basés sur le concept du livre de codage
• Fonctions de hachage – Chaque clé fabrique un livre de codage différent
– Mettent en œuvre à la fois la confusion et la
diffusion

Les chiffres en continu

• Ils chiffrent un bit ou un octet à la fois

• On combine le texte en clair avec un flux
pseudo-aléatoire appelé ‘flot de clés’
((‘keystream’)
y ) obtenu en « étirant » la clé
• Une même clé ne doit jamais être utilisée
deux fois : la connaissance du message en
clair et du cryptogramme permet d’en
déduire le flot de clés, et donc de déchiffrer
tout autre cryptogramme chiffré avec la
LES CHIFFRES EN CONTINU même clé
(‘STREAM CIPHERS’)

Nicolas Pioch 1
Cryptographie symétrique 17 mars 2009

Les chiffres en continu synchrones Les chiffres en continu qui s’auto-

synchronisent (‘self-synchronizing’)
• Le flot de clés est généré indépendamment • ‘Self-synchronizing stream ciphers’,
du message à chiffrer ‘asynchronous’, ou ‘ciphertext autokey’
• Un caractère chiffré erroné transmis (CTAK)
p
n’impacte q
qu’un caractère du message g • Ils utilisent les n pprécédents caractères
déchiffré : cela rend ces chiffres plus chiffrés pour générer le flot de clés
vulnérables aux attaques actives • Un caractère chiffré erroné transmis affecte n
• Le destinataire doit être ‘aligné’ sur caractères déchiffrés au maximum
l’émetteur pour décoder correctement le • En cas d’insertion ou de perte de caractère
message : un protocole de resynchronisation chiffré, le destinataire se resynchronise
peut être nécessaire en cas de perte ou automatiquement au bout de n caractères
d’insertion de caractère – exemple : une chiffre par bloc en mode CFB

Exemples de chiffres en continu Addition binaire modulo 2,

‘OU exclusif’ (‘XOR’)
• A5/1 (GSM), basé sur un registre à décalage • On note  l’addition binaire modulo 2,
à rétroaction linéaire appelée également ‘ou exclusif’ ou ‘XOR’
• RC4 • Table de vérité :

• Très utilisés historiquement en raison de  0 1

leurs excellentes performances en
implémentation matérielle ou logicielle
– Permet ainsi de chiffrer de la voix en temps réel
0 0 1
• En perte de vitesse actuellement par rapport
aux chiffres par bloc 1 1 0

Les registres à décalage à Les registres à décalage à

rétroaction linéaire rétroaction linéaire
• ‘Linear Feedback Shift Register’ (LSFR)
x0 x1 x2 x3 x4 x5 x6 x7 x8 • Registre : suite binaire, initialisée à la valeur
Sortie initiale de la clé (état de départ)
• On décale à droite d’une
d une position pour
produire un bit
 • Rétroaction : on place le résultat du calcul
dans le bit le plus à gauche
Exemple de fonction de rétroaction :
• Cyclicité des clés produites :
x3  x6  x8 ö x0 – La période vaut au maximum 2n-1
– On peut prédire les sorties après 2n bits

Nicolas Pioch 2
Cryptographie symétrique 17 mars 2009

Combinaisons non-linéaires de Le chiffre A5 version 1 du GSM

registres à décalage linéaires
Pour compenser la prédictibilité des registres à A5/1 (inventé en 1989) utilise trois registres
décalage linéaires, on peut en combiner LSFR, initialisés par la clé de 64 bits ainsi que
plusieurs de taille différente (si possible le numéro de trame TDMA (public) sur 22 bits
relativement premières entre elles) via une pour éviter de réutiliser la même :
fonction non linéaire. Exemples : • X : 19 bits (x0, x1, x2, …, x18)
• Y : 22 bits (y0, y1, y2, …, y21)
• Générateurs de Geffe : • Z : 23 bits (z0, z1, z2, …, z22)
x y  y z  z ou x y  (x) z Sur chaque cycle d’horloge, un bit du flux
pseudo-aléatoire est produit :
• Fonction majorité x18  y21  z22

Les registres ‘stop and go’ A5/1

• Sur chaque cycle : m = maj(x8, y10, z10) x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 
• Si x8 = m, alors X se décale :
– t = x13  x16  x17  x18 
– Pour i = 17, 16, …. 0 : xi+1 = xi, puis x0 = t
17 16 y0 y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13 y14 y15 y16 y17 y18 y19 y20 y21
• Si y10 = m, alors Y se décale : 
– t = y20  y21
z0 z1 z2 z3 z4 z5 z6 z7 z8 z9 z10 z11 z12 z13 z14 z15 z16 z17 z18 z19 z20 z21 z22
– Pour i = 20, 19, …. 0 : yi+1 = yi, puis y0 = t
• Si z10 = m, alors Z se décale : 
– t = z7  z20  z21  z22
– Pour i = 21, 20, …. 0 : zi+1 = zi, puis z0 = t

A5/1 : exemple Chiffres basés sur les registres à

décalage à rétroaction linéaire
1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 1  • Solution facile à implémenter en matériel
(appréciée des électroniciens), plus difficile à
 réaliser en logiciel
0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 • Chiffrement rapide
p et efficace : un bit du flot
de clé est généré sur chaque cycle d’horloge

• Très utilisée historiquement : GSM…
1 1 1 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0
• Aujourd’hui, les processeurs sont plus
 rapides, et l’on peut réaliser plus facilement
les opérations de cryptographie au niveau
logiciel

Nicolas Pioch 3
Cryptographie symétrique 17 mars 2009

RC4 – ‘Rivest Cipher n°4’ RC4 et Arcfour – ‘Alleged RC4’

• Un algorithme à taille de clé variable inventé • Seul le nom ‘RC4’ est déposé – l’algorithme
en 1987 par Ron Rivest pour RSA Data est un secret industriel non breveté
Security Inc.
• Conçu
ç p pour une implémentation
p p
performante • Code source révélé anonymement en
en logiciel sur processeur 8 bits : les septembre 1994 sur la liste de diffusion
principales opérations sont des XOR et des Cypherpunk et reposté sur sci.crypt
permutations d’octets
• 10 fois plus rapide que DES : très populaire • Usage libre sous le nom ‘arcfour’ :
vers 1995 dans de nombreux logiciels et http://www.mozilla.org/projects/security/pki/n
protocoles tels que SSL, S/MIME, Acrobat… ss/draft-kaukonen-cipher-arcfour-03.txt

L’algorithme RC4 Taille de clé RC4

• Un tableau d’octets S[0…255] contenant • key_length = longueur de la clé key en octets

toujours une permutation de {0, 1, … 255}
• La clé (répétée autant de fois que • Peut valoir jusqu’à 256 octets, soit 2048 bits !
nécessaire)) sert à initialiser le tableau en
permutant les valeurs (octets) deux à deux
• Historiquement, de 5 ou 16 octets,
• À chaque itération, RC4 correspondant à des tailles de clés de 40 ou
– Permute deux valeurs dans la table 128 bits
– Sélectionne une autre valeur dans la table et
produit ainsi un octet pour le flot de clés

Initialisation RC4 à partir de la clé Génération du flot de clés RC4

for i from 0 to 255 i := 0

S[i] := i j := 0
K[i] := key[i mod key_length] while GeneratingOutput:
endfor i := (i + 1) mod 256
j := 0 j := (j + S[i]) mod 256
for i from 0 to 255 swap(S[i],S[j])
j := (j + S[i] + K[i]) mod 256 output S[(S[i] + S[j]) mod 256]
swap(S[i],S[j]) endwhile
endfor

Nicolas Pioch 4
Cryptographie symétrique 17 mars 2009

Représentation graphique Chiffrement des données avec RC4

• Octet par octet : chiffré = clair  flot de clé

• Par conséquent, chaque clé ne doit être
utilisée qu’une seule fois pour chiffrer un seul
message, g , sinon :
– le flot de clé peut être calculé par :
flot de clé = clair  chiffré
– On peut ainsi déchiffrer tout autre message
chiffré par la même clé
• Une telle clé à usage unique, pour chiffrer un
À chaque itération : on permute S[i] et S[j], et l’on produit un octet seul message, est appelée clé de session
pour le flot de clés : la valeur de la case d’indice S[i]+S[j] mod 256

Comment générer une clé de session Vulnérabilités de RC4

à usage unique ?
• Générer une clé de session aléatoire et • En 2001, Adi Shamir a montré que les
l’échanger via un cryptosystème à clé valeurs des premiers octets générés du flot
publique de clés RC4 ne sont pas équiprobables.
• Lorsqu’on
q p
partage
g déjà j une clé symétrique
y q • Il est désormais recommandé de « jjeter » les
avec le destinataire, la combiner avec un n premiers octets générés, afin d’augmenter
nonce à usage unique (‘number used once’) le nombre de permutations réalisées sur la
appelé également vecteur d’initialisation table S[] avant son utilisation.
– La clé de session est le résultat d’un hachage • De telles variantes de l’algorithme sont
cryptographique à sens unique de la clé appelées RC4-drop-n.
symétrique et du nonce
– Le nonce est transmis en clair au destinataire
• Une valeur extrêmement prudente pour n est
3072.

‘Wired Equivalent Privacy’ (WEP)

• Protocole mal conçu pour sécurisé les

réseaux WiFi (IEEE 802.11)
• Mécanisme d’intégrité (CRC32) non
yp g p q
cryptographique
• Mauvaise implémentation des vecteurs
d’initialisation, trop petits, sur 24 bits :
– 50% de chances de pouvoir mener une attaque
par clé liée après 5000 paquets (paradoxe des
anniversaires)
CHIFFRES PAR BLOC
• Remplacé par WPA2 (IEEE 802.11i, AES) ou (‘BLOCK CIPHERS’)
WPA (RC4)

Nicolas Pioch 5
Cryptographie symétrique 17 mars 2009

Principe d’un chiffre itéré par bloc Chiffre itéré

par bloc
• Le message en clair (ou le cryptogramme) On dérive n sous-clés
est découpé en blocs de taille fixe, par {k1, k2, …, kn} par
exemple 64, 128, ou 256 bits transformation de la
clé maîtresse initiale k
• On chiffre en itérant une fonction de ronde
sur un certain nombre d’étages Les paramètres de la
fonction de ronde à
• Un tel chiffre par itération est également l’itération n sont kn et
appelé chiffre par produit (‘product cipher’). le résultat de
l’exécution de la ronde
précédente

Sécurité et nombre d’étages Types de chiffres par itération

Chaque étage (ou ‘ronde’) est relativement • Si un étage n’utilise que des opérations de
faible cryptographiquement : substitution (‘S-box’) et de permutation
• C’est le chaînage répété qui confère la (‘P-box’), un tel chiffre itéré se nomme
robustesse au chiffre réseau de substitution-permutation
• Le nombre d’étages impacte la sécurité et la (‘SP-network’)
rapidité de chiffrement : il est compliqué de • On peut également mettre
concevoir un chiffre à la fois rapide et sûr en œuvre des opérations
• Lorsque les fonctions de ronde sont arithmétiques modulaires,
complexes, un faible nombre peut suffire (10 comme dans les chiffres
à 14 pour AES, 16 pour DES), sinon il faut de Horst Feistel
itérer un grand nombre de fois (64 pour TEA) (1915 – 1990)

Ronde d’un chiffre de Feistel Pour déchiffrer

• Le bloc en entrée est découpé en deux • Le bloc chiffré est (Ln, Rn)
moitiés (L0, R0) = M • On présente les sous-clés dans l’ordre
• F est la fonction inverse : {kn, …, k2, k1}
de ronde • On résout les équations précédentes :
• À chaque étape : Li  Ri 1   Ri 1  Li

– Li = Ri-1 Ri  Li 1  FRi 1 , ki   Li 1  Ri  FRi 1 , ki   Ri  FLi , ki 
– Ri = Li-1  F(Ri-1, ki)
• C’est la même formule avec R et L inversés
• Le bloc chiffré est et des indices décroissants
C = (Ln, Rn)
• À noter : F n’a pas besoin d’être inversible
– mais le chiffre n’est pas sûr pour toute fonction F

Nicolas Pioch 6
Cryptographie symétrique 17 mars 2009

Data Encryption Standard (DES) Caractéristiques de DES

• Appel d’offre du National Bureau of • Clé de 56 bits, chiffre par bloc de 64 bits
Standards (NBS, maintenant NIST) en 1973 • Chiffre de Feistel :
• Développé par IBM en 1975 (‘Lucifer’) – 16 étages relativement simples
– Conception secrète – F(Ri-1
i 1, ki) = P
P-box(S-boxes(Expand(R i 1)  ki))
box(S boxes(Expand(Ri-1
– Participation de la National Security Agency – Pour chaque étage, une sous-clé de 48 bits est
• Adopté comme standard du gouvernement dérivée de la clé maîtresse
américain (FIPS 46) en 1976 • La sécurité dépend principalement des
• Taille de clé désormais inadéquate : ne doit boîtes ‘S’, qui font correspondre 6 bits
plus être utilisé d’entrée à 4 bits en sortie.
http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf
• Remplacé par AES (FIPS 197) en 2001

Étage DES : Permutation expansive

DES
• Entrée 32 bits, qu’on numérotera ainsi :
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

• Sortie 48 bits :
31 0 1 2 3 4 3 4 5 6 7 8
7 8 9 10 11 12 11 12 13 14 15 16
15 16 17 18 19 20 19 20 21 22 23 24
23 24 25 26 27 28 27 28 29 30 31 0

DES : Permutation expansive (2/2) DES : boîtes S

• 8 boîtes de substitution : ‘S-box’

• Chacune prend 6 bits en entrée, et produit 4
bits en sortie bits 1, 2, 3, 4 :
• ‘S-box’
S box nn°1
1: 0 1 2 3 4 5 6 7 8 9 A B C D E F
00 E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7
bits 0, 5 : 01 0 F 7 4 E 2 D 1 A 6 C B 9 5 3 8
10 4 1 E 8 D 6 2 B F C 9 7 3 A 5 0
11 F C 8 2 4 9 1 7 5 B 3 E A 0 6 D
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
00 1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001 0000 0111
01 0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 1000
10 0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 1001 0111 0011 1010 0101 0000
11 1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 1101

Nicolas Pioch 7
Cryptographie symétrique 17 mars 2009

DES : boîtes P DES : génération des sous-clés

• Entrée 32 bits : Clé de 56 bits, numérotés 0, 1, 2, …, 55,

séparée en deux moitiés LK et RK :
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 LK : RK :
49 42 35 28 21 14 7 55 48 41 34 27 20 13

• Sortie 32 bits : 0 50 43 36 29 22 15 6 54 47 40 33 26 19

8 1 51 44 37 30 23 12 5 53 46 39 32 25
15 6 19 20 28 11 27 16 0 14 22 25 4 17 30 9
16 9 2 52 45 38 31 18 11 4 24 17 10 3
1 7 23 13 31 26 2 8 18 12 29 5 21 10 3 24

DES : génération des sous-clés Permutation-sélection compressive

des 48 bits de la sous-clé ki
Sur chaque étage • La partie gauche de la sous-clé ki est
i = 1, 2, …, 16 : composée des bits suivants de LK :
• Si i œ {1, 2, 9, 16}, (les bits 8, 17, 21 et 24 sont ignorés)
ri = 1, sinon ri = 2 13 16 10 23 0 4 2 27 14 5 20 9
• On
O décale
dé l lles bitbits d
de
22 18 11 3 25 7 15 6 26 19 12 1
LK circulairement à
gauche de ri positions • La partie droite de la sous-clé ki est
• On décale les bits de composée des bits suivants de RK :
RK circulairement à (les bits 6, 9, 14 et 25 sont ignorés)
gauche de ri positions
12 23 2 8 18 26 1 11 22 16 4 19

15 20 10 27 5 24 17 13 21 7 0 3

DES : détails Sécurité de DES (1/2)

• Une permutation initiale (‘IP’) avant le • La sécurité de DES dépend principalement

premier étage des boîtes S, car tout le reste est linéaire
• Les deux moitiés sont échangées après le • “We sent the S-boxes off to Washington.
g , afin de préparer
dernier étage, p p le They y came back and were all different.”
déchiffrement – Alan Konheim, un des concepteurs de DES
• Une permutation finale (‘FP’) inverse de ‘IP’ • “I would say that, contrary to what some
est appliquée à (R16, L16) people believe, there is no evidence of
• Tout ceci n’a aucune incidence sur la tampering with the DES so that the basic
sécurité de l’algorithme design was weakened.”
– Adi Shamir

Nicolas Pioch 8
Cryptographie symétrique 17 mars 2009

Sécurité de DES (2/2) DES 56-bits cryptanalysé

en 22h15 (janv. 1999)
• Plus de 30 ans de recherche intense n’ont • Juillet 1998 : “The Electronic Frontier
pas permis de révéler la présence de portes Foundation built a machine (‘Deep Crack’)
dérobées, en particulier dans la construction for $220,000 that took three days to crack
des mystérieuses ‘boîtes S’ the DES code. The previous record was 39
– Afin d’éviter de telles suspicions, les concepteurs days, according to the Foundation. The
de nouveaux chiffres utilisent des nombres ‘rien group's executives said that now that the
dans les manches’ pour initialiser les constantes research is done, a duplicate machine can
• Les attaques se font toujours en pratique par be built for as little as $50,000.”
balayage exhaustif de l’espace des clés • Janvier 1999 : DES-III Challenge : EFF
• Les concepteurs du DES savaient ce qu’ils ‘Deep Crack’ et distributed.net déchiffrent un
faisaient… avec 20 ans d’avance message DES en 22h15

DES n’est pas un groupe Double DES, C = E(E(M, k1), k2)

• Keith W. Campbell et Michael J. Wiener ont La sécurité réelle n’est pas de 2112 bits mais
démontré que DES n’était pas un groupe plutôt 257 car vulnérable (en théorie) à une
(Conférence CRYPTO 1992, p512-520) attaque à texte clair connu :
• Plus pprécisément,, l’ensemble kK Ek  • Pré-calculer et stocker les 256 valeurs
n’est pas stable pour la loi de possibles de E(M, k1) pour toute clé k1
composition des applications • Pour chaque clé k2, calculer D(C, k2) jusqu’à
• Si c’était le cas : trouver une valeur dans la table
(k1 , k 2 )  K 2 , k3  K , Ek3  Ek2  Ek1 • On a alors E(M, k1) = D(C, k2) et trouvé les
clés k1 et k2 puisque C = E(E(M, k1), k2)
(k1 , k 2 )  K 2 , k3  K , m  M , E (m, k3 )  E ( E (m, k1 ), k 2 )
• C’est une attaque ‘meet in the middle’.

Triple DES (3DES) Advanced Encryption Standard (AES)

• C = E(D(E(M, k1), k2), k1) • Appel d’offres du NIST en janvier 1997 pour
• M = D(E(D(C, k1), k2), k1) trouver un remplaçant à DES
Pourquoi utiliser E-D-E avec 2 clés ? – Une quinzaines de chiffres étudiés
– Participation
p p
publique
q de la NSA,, q
qui a déclaré
• Compatibilité avec DES si les deux clés sont que tous les algorithmes finalistes étaient
identiques : suffisamment sûrs pour chiffrer les informations
E(D(E(M, k), k), k) = E(M, k) non classifiées du gouvernement américain
• et 112 bits suffisent. • Rijndael sélectionné en nov. 2001 et publié
• Cela a permis de prolonger la durée utile de comme standard AES (FIPS 197)
DES jusqu’à la normalisation d’AES en 2001 – Inventé par deux cryptographes belges, Vincent
Toutefois : 3 fois plus lent que DES en logiciel ! Rijmen et Joan Daemen. Libre de droits.

Nicolas Pioch 9
Cryptographie symétrique 17 mars 2009

Adoption d’AES US National Policy on the use of AES

• Algorithme le plus intensément analysé “The design and strength of all key lengths of the
• Adi Shamir a déclaré à la conférence RSA AES algorithm (i.e., 128, 192 and 256) are sufficient
to protect classified information up to the SECRET
2002 que les données chiffrées avec AES et level. TOP SECRET information will require use of
une clé de 256-bits seraient « secure either the 192 or 256 key lengths.
lengths The
forever » quelles que soient les avancées en implementation of AES in products intended to
informatique. protect national security systems and/or information
• En 2003, AES est devenu le premier must be reviewed and certified by NSA prior to their
acquisition and use.”
algorithme de chiffrement ouvert approuvé -- National Policy on the Use of the Advanced
par la NSA pour le chiffrement d’informations Encryption Standard (AES) to Protect National
du gouvernement américain classées Security Systems and National Security Information
TOP SECRET http://www.cnss.gov/Assets/pdf/cnssp_15_fs.pdf

Fonctionnement d’AES Fonctionnement d’AES

• Réseau de substitution-permutation • Chaque étage met en œuvre 4 fonctions :

• Rijndael permet n’importe quelle taille de – SubBytes (substitution non-linéaire)
bloc et de clé indépendamment, de 128 et – ShiftRows (transposition linéaire)
256 bits ppar incrément de 32 bits – MixColumns ((mélangeg non-linéaire))
• AES ne conserve que le mode par bloc de – AddRoundKey (addition de la clé de ronde)
données de 128 bits http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf

• 3 tailles de clés : 128, 192 et 256 bits avec

10, 12 et 14 étages respectivement
• Possède une description mathématique sur
le corps fini GF(28) noté également  8
2

SubBytes pour l’octet {xy} : par exemple {53} devient {ed}

AES SubBytes x
y 0 1 2 3 4 5 6 7 8 9 a b c d e f
0 63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
1 ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
C’est la « S-box » d’AES 2 b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
3 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 72
4 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
5 53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
6 d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
7 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
8 cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
9 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
a e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
b e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
c ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
d 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
f 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16

Nicolas Pioch 10
Cryptographie symétrique 17 mars 2009

Origine de la table SubBytes (1/2) Origine de la table SubBytes (2/2)

SubBytes est la composition de deux • On applique ensuite la transformation affine

opérations inversibles : suivante sur GF(2) (avec ) au résultat :
• Un octet {a7, a6, a5, a4, a3, a2, a1, a0}, ai œ {0, 1} b0'  1 0 0 0 1 1 1 1 b0  1
 ' 
p
est interprété comme le p polynôme
y
 b1  1 1 0 0 0 1 1 1  b1  1
a7x7 + a6x6 + a5x5 + a4x4 + a3x3 + a2x2 + a1x + a0 b2'  1 1 1 0 0 0 1 1 b2  0
dans GF(28)  '     
• On calcule son inverse multiplicatif b3   1 1 1 1 0 0 0 1 b3  0

b '  1 1 1 1 1 0 0 0 b4  0
{b7, b6, b5, b4, b3, b2, b1, b0}, bi œ {0, 1}  4'       
modulo le polynôme irréductible b5  0 1 1 1 1 1 0 0 b5  1
m(x) = x8 + x4 + x3 + x + 1 via l’algorithme b '  0 0 1 1 1 1 1 0 b6  1
 6     
d’Euclide étendu b7'  0 0 0 1 1 1 1 1 b7  0

ShiftRows Mix
Columns
• Décalage cyclique vers la gauche dépendant
du numéro de ligne :

Chaque colonne est interprétée comme le

polynôme a(x) = a3x3 + a2x2 + a1x + a0 à
coefficients dans GF(28)
(attention, ici ce sont des octets !)
et est multipliée modulo x4 + 1 par le polynôme
c(x) = {03}x3 + {01}x2 + {01}x + {02}

Pour déchiffrer…

• AddRoundKey est son propre inverse

• MixColumns et SubBytes sont inversibles –
chiffrement et déchiffrement sont effectués
via une table
– Pour MixColumns, c’est lié au fait que le
polynôme choisi
c(x) = {03}x3 + {01}x2 + {01}x + {02} est
AddRoundKey inversible : c-1(x) = {0b}x3 + {0d}x2 + {09}x + {0e}
• ShiftRows est inversible par décalage à
droite

Nicolas Pioch 11
Cryptographie symétrique 17 mars 2009

Autres chiffres par bloc International Data Encryption

Algorithm (IDEA)
• IDEA • Développé à l’ETH Zürich en 1991 par Xuejia
Lai et James Massey
• Blowfish – Utilisé à l’origine par PGP : chiffre inventé en
Suisse, donc utilisable partout dans le monde et
i
importable
bl aux ÉÉtats-Unis,
U i alors
l que DES é
était
i
• RC6 interdit d’exportation
• Breveté : usage commercial non-libre
• TEA – Intéressant pour sa taille de clé (128 bits) avant
2000
– cet intérêt a disparu avec la normalisation d’AES,
qui est totalement libre de droits.

IDEA

• Optimisé pour les processeurs 16-bits

• Chiffre par bloc de 64-bits utilisant une clé de
128-bits
• 8 étages « et demi » : le dernier est tronqué
• Premier algorithme à mélanger les
opérations de trois groupes algébriques, une
approche courante aujourd’hui (AES) :
–  (addition modulo 2 ou XOR)
– Addition modulo 216
– Ÿ Multiplication de Lai-Massey: modulo 216 + 1,
avec 0 interprété comme étant égal à 216

Blowfish (1/2) Blowfish (2/2)

• Conçu en 1993 par Bruce Schneier • 16 étages

• Populaire et repris dans de nombreuses • Presque un réseau de Feistel
implémentations logicielles avant AES car – Ri = Li-1  ki
l’un des p
premiers algorithmes
g de i 1  F(Li-1
– Li = Ri-1 i 1  ki)
cryptographie ‘forte’ libres de droits • La fonction de ronde F utilise 4 boîtes ‘S’ qui
• L’auteur recommande désormais l’utilisation font correspondre 8 bits d’entrée à 32 bits en
de Twofish, l’un des 5 finalistes AES. sortie
• Blocs de 64-bits, clés de 32 à 448 bits par • Originalité : les boîtes ‘S’ sont calculées et
multiple de 8 bits dépendantes de la clé de chiffrement utilisée,
initialisées à partir des hexadécimales de 

Nicolas Pioch 12
Cryptographie symétrique 17 mars 2009

Étage Blowfish RC6

• Autre finaliste AES

• Tailles de bloc, de
clés et nombre
d’étages sont des
variables de
l’algorithme
• Particularité : met en
œuvre des rotations
qui dépendent des
données chiffrées
• Breveté par RSA
Security
Fonction de ronde F

Tiny Encryption Algorithm (TEA) TEA

• Publié en 1994 par David Wheeler et Roger • Usage libre (non breveté)
Needham (Cambridge Computer Lab) • Blocs de 64 bits, clé de 128 bits
• Remarquable par sa simplicité – tient en • Arithmétique sur 32-bits
quelques
q q lignes
g de code ! • Presque un réseau de Feistel :  est
• Implémentation logicielle simple et rapide, remplacé par l’addition modulo 232
consomme très peu de mémoire (Xbox) • Nombre d’étages variable : 64 recommandés
• Susceptible à une attaque par clés (32 ‘cycles’), car la fonction de ronde est
équivalentes, l’algorithme a été complexifié relativement simple
en eXtended TEA (XTEA) en 1997, puis • La constante est delta = 0x9e3779b9 = 232/,
Corrected block TEA (XXTEA) en 1998  étant le nombre d’or

Chiffrement TEA Déchiffrement TEA

(K[0],K[1],K[2],K[3]) = clé 128 bits (K[0],K[1],K[2],K[3]) = clé de 128 bits

(L,R) = bloc en clair de 64 bits (L,R) = bloc chiffré de 64 bits
sum = 0 sum = delta << 5
for i = 1 to 32 for i = 1 to 32
sum += delta R -= ((L<<4)+K[2])^(L+sum)^((L>>5)+K[3])
L += ((R<<4)+K[0])^(R+sum)^((R>>5)+K[1]) L -= ((R<<4)+K[0])^(R+sum)^((R>>5)+K[1])
R += ((L<<4)+K[2])^(L+sum)^((L>>5)+K[3]) sum -= delta
next i next i
Bloc chiffré = (L,R) Bloc en clair = (L,R)

Nicolas Pioch 13
Cryptographie symétrique 17 mars 2009

Comment chiffrer plusieurs blocs ?

On sait chiffrer un bloc de données par un

algorithme de chiffrement par bloc. Cependant,
comment chiffrer plusieurs blocs consécutifs ?
• Utiliser une nouvelle clé ppour chaqueq bloc
– Autant utiliser le masque à usage unique
• Utiliser la même clé pour chiffrer chaque bloc
MODES OPÉRATOIRES indépendamment
DES CHIFFRES PAR BLOC • Introduire une variabilité, par exemple en
fonction des blocs précédents ou d’un
compteur…

Modes opératoires Electronic Code Book (ECB)

Il existe de nombreux modes opératoires pour • Chaque clé k construit un livre de codage
les algorithmes de chiffrement par bloc. électronique
Les 3 les plus simples sont : • Chaque bloc est chiffré avec ce même livre
• Electronic Code Book (ECB) ( ) de codage
g :p pour un message
g m0, m1, …,, mn
– Chiffre chaque bloc indépendamment
Chiffrement Déchiffrement
– Ne pas utiliser !
• Cipher Block Chaining (CBC) c0 = E(m0, k) m0 = D(c0, k)
– Une méthode pour chaîner les blocs entre eux c1 = E(m1, k) m1 = D(c1, k)
• Counter Mode (CTR) … …
– Semblable à un chiffre en continu cn = E(mn, k) mn = D(cn, k)

Vulnérabilités du mode ECB

• Si mi = mj, alors ci = E(mi, k) = cj = E(mj, k)

• Savoir que ci = cj fournit de l’information à un
espion, même s’il ne connaît pas mi
Original ECB Autre mode

Nicolas Pioch 14
Cryptographie symétrique 17 mars 2009

Attaques actives sur ECB Cipher Block Chaining (CBC)

Un attaquant actif peut rejouer (réinjecter) des • On chaîne les blocs les uns aux autres
blocs chiffrés avec la même clé ci, ou modifier • Un vecteur d’initialisation (IV) aléatoire est
l’ordre des blocs chiffrés : attaque du ‘copier- nécessaire pour initier le processus. Il peut
coller’ : c0 c1 c2 c3 → c0 c3 c2 c3. Exemples : être transmis en clair.
• Modifier le montant d’un virement bancaire
en le remplaçant par un bloc chiffré extrait Chiffrement Déchiffrement
d’un autre endroit du message (RIB) c0 = E(IVm0, k) m0 = IVD(c0, k)
• Dans le jeu en ligne Phantasy Star Online: c1 = E(c0m1, k) m1 = c0D(c1, k)
Blue Burst, qui utilisait Blowfish en mode … …
ECB, les joueurs renvoyaient le message
correspondant à ‘Monster killed’ au serveur. cn = E(cn-1mn, k) mn = cn-1D(cn, k)

Intérêt du mode CBC

• Deux blocs identiques vont être chiffrés

différemment, car le bloc chiffré qui les
précède a peu de chances d’être identique
• L’attaque
q du ‘copier-coller’
p est toujours
j
possible, mais elle est plus compliquée, et
une partie du message sera corrompu
• Il y a récupération automatique sur erreur, ce
qui n’est pas forcément souhaitable
– Utiliser plutôt un code correcteur d’erreur si l’on
recherche un tel comportement sur les données

Propagation des erreurs, mode CBC Counter Mode (CTR)

Si l’on substitue x à cn : Le mode CTR transforme un chiffre par bloc en

• cn-1  D(x, k)  mn x  D(cn+1, k)  mn+1 chiffre en continu : on génère le flot de clés en
• cn+1 D(cn+2, k)  mn+2 cn+2 D(cn+3, k)  mn+3 chiffrant un vecteur d’initialisation incrémenté
de façon monotone.

Chiffrement Déchiffrement
c0 = m0  E(IV, k) m0 = c0  D(IV, k)
c1 = m1  E(IV+1, k) m1 = c1  D(IV+1, k)
… …
cn = mn  E(IV+n, k) mn = cn  D(IV+n, k)

Nicolas Pioch 15
Cryptographie symétrique 17 mars 2009

Avantages du mode CTR

• Permet un accès direct aux données

(mais CBC aussi)

• Permet de chiffrer plusieurs blocs en

parallèle : bien adapté aux machines
multiprocesseurs

• Fonctionne comme un chiffre en continu :

on peut transmettre des blocs incomplets
(pas de bourrage nécessaire)

Transmission d’un bloc incomplet

• Bourrage binaire (RFC 1321 § 3.1) :

– Rajouter obligatoirement un bit à ‘1’ suivi
d’autant de bits à ‘0’ que nécessaire (0 ou plus)
• Bourrage
g en octets :
– ANSI X.923 : ajouter des octets nuls sauf le
dernier qui indique le nombre d’octets de
bourrage : DD DD DD DD 00 00 00 04
– ISO 10126 : idem mais avec des octets
aléatoires sauf le dernier : DD DD 81 A6 23 04 INTÉGRITÉ
– PKCS#7, RFC 3852 § 6.3 : on répète le nombre
d’octets rajoutés : DD DD DD DD 04 04 04 04

Intégrité des données Message Authentication Code (MAC)

• Détecter toute modification non autorisée • Appelés également Message Integrity Code
des données (MIC)
• Plus important que la confidentialité dans • Doivent permettre de détecter toute
pp
certaines applications : virements bancaires modification du message g en clair :
• Les chiffres en continu ou les modes – Via une attaque à texte en clair choisi,
opératoires des chiffres par bloc peuvent être l’attaquant ne doit pas pouvoir trouver un autre
classés selon qu’ils amplifient ou minimisent message m’ tel que MAC(m) = MAC(m’)
le résultat d’une modification du • Le CBC-MAC (FIPS 113) est la méthode la
cryptogramme, mais le chiffrement seul est plus ancienne pour construire un MAC à
insuffisant pour garantir l’intégrité : partir d’un algorithme de chiffrement par bloc
il n’assure que la confidentialité. http://www.itl.nist.gov/fipspubs/fip113.htm

Nicolas Pioch 16
Cryptographie symétrique 17 mars 2009

Construction d’un CBC-MAC CBC-MAC : exemple

Calcul CBC-MAC • Alice veut envoyer à Bob le message

M = (m0, m1, m2, m3).
c0 = E(IVm0, k)
• Elle calcule : c0 = E(IV  m0, k),
c1 = E(c0m1, k) ( 0  m1, k),
c1 = E(c ( 1  m2, k),
), c2 = E(c ),
… c3 = E(c2  m3, k) = MAC
cn-1 = E(cn-2mn-1, k) = MAC • Alice envoie (IV, m0, m1, m2, m3, c3 = MAC)
• Supposons qu’un attaquant change m1 en x
• Le MAC est accolé à la fin du texte en clair
transmis au destinataire • Bob calcule : c0 = E(IVm0, k),
z1 = E(c0  x, k)  c1, z2 = E(z1  m2, k)  c2,
• Le destinataire refait le même calcul à partir z3 = E(z2  m3, k)  c3 = MAC
d’IV et de k, et vérifie le MAC

CBC-MAC

• L’erreur se propage dans un CBC-MAC…

contrairement au déchiffrement d’un
message en mode CBC !

• Un attaquant ne peut pas modifier tout ou

partie du message transmis
(IV, m0, m1, m2, …, mn-1, cn-1 = MAC),
car il ne sait pas recalculer le CBC-MAC
correspondant à son message modifié :
il ne dispose pas de la clé k
Contrairement au chiffrement en mode CBC, l’erreur se propage dans un CBC-MAC !

Intégrité et confidentialité Ne pas utiliser la même clé k pour

chiffrer (mode CBC) et un CBC-MAC!
• Il s’agit d’une somme de contrôle (checksum) • De manière générale, il ne faut pas utiliser la
cryptographique, accolée à la fin du même clé pour deux opérations
message en clair cryptographique différentes
• Ici,, cela équivaudrait
q à envoyer
y le dernier
• On n’obtient donc que l’intégrité, pas la bloc chiffré cn-1 = MAC deux fois… ce qui ne
confidentialité. peut pas améliorer le niveau de sécurité !
(IV, c0, c1, c2, …, cn-1, cn-1 = MAC)
• Pour obtenir confidentialité et intégrité, il faut • Si l’on fait cela, un attaquant peut modifier
impérativement utiliser deux clés différentes, tous les blocs ci sauf le dernier… puisqu’une
donc faire le double de calculs ! erreur sur un ci ne se propage qu’au bloc
immédiatement suivant !

Nicolas Pioch 17
Cryptographie symétrique 17 mars 2009

Restriction sur l’utilisation Les modes actuellement

des CBC-MAC recommandés par le NIST
Les CBC-MAC ne doivent être utilisés que sur • 5 modes pour la confidentialité :
des messages de taille fixe, car ils sont ECB (ne pas utiliser!), CBC, OFB, CFB, CTR
vulnérables aux attaques par concaténation : • Pour l’intégrité et l’authentification
• Si un attaquant
q connaît les deux messages
g seulement,, les CBC-MAC ont été remplacés
p
(x1, x2, …, xn, MAC(X)) et par un nouveau mode nommé « CMAC »
(y1, y2, …, yp, MAC(Y)), • Pour combiner chiffrement, intégrité et
alors il sait construire le message suivant authentification, deux modes existent :
dont le MAC est aussi MAC(Y) : – le mode CCM :
(x1, x2, …, xn, MAC(X), – Le mode GCM (Galois/Counter Mode) pour les
(MAC(X)  y1), y2, …, yp) implémentations matérielles à haut débit
• Les CBC-MAC sont obsolètes http://csrc.nist.gov/groups/ST/toolkit/BCM/current_modes.html

Conclusion

La cryptographie symétrique peut servir à :

• La confidentialité
– Transmission de données chiffrées à travers des
canaux de communication non sécurisés
– Au chiffrement de données stockées
(sauvegardes, archivage…)
• L’intégrité (MAC)
• L’authentification (Kerberos…)
• Remplacer les fonctions de hachage

Nicolas Pioch 18