Cryptographie

Cryptographie symétrique

Cryptographie symétrique

17 mars 2009

Terminologie Texte en clair (‘Cleartext’)

Nicolas Pioch 17 mars 2009

Texte chiffré ou cryptogramme (‘Ciphertext’)

Clé de chiffrement k1 (‘Encryption Key’)

Clé de déchiffrement k2 (‘Decryption Key’)

Taxinomie

Les chiffres symétriques

• Chiffres symétriques

• Les chiffres en continu

– La même clé est utilisée pour chiffrer et déchiffrer – Chiffres en continu ou par bloc

• Chiffres à clé publique – Deux clés distinctes : une clé publique pour chiffrer, et une clé privée pour déchiffrer

– Permet de réaliser des signatures digitales • Fonctions de hachage

Texte en clair (‘Cleartext’)

– Fonctionnement semblable à un masque à

usage unique, mais avec une clé de taille limitée

– La clé est « étirée » pour générer un long flux pseudo-aléatoire appelé ‘flot de clés’ (‘keystream’), qui est utilisé comme masque

• Les chiffres par bloc – Basés sur le concept du livre de codage – 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

LES CHIFFRES EN CONTINU (‘STREAM CIPHERS’)

Nicolas Pioch

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 même clé

1

Cryptographie symétrique

17 mars 2009

Les chiffres en continu synchrones

Les chiffres en continu qui s’autosynchronisent (‘self-synchronizing’)

• Le flot de clés est généré indépendamment

• ‘Self-synchronizing stream ciphers’,

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,

du message à chiffrer • Un caractère chiffré erroné transmis p q qu’un caractère du message g n’impacte déchiffré : cela rend ces chiffres plus vulnérables aux attaques actives • Le destinataire doit être ‘aligné’ sur l’émetteur pour décoder correctement le message : un protocole de resynchronisation peut être nécessaire en cas de perte ou d’insertion de caractère

à rétroaction linéaire • RC4

• Très utilisés historiquement en raison de

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

Les registres à décalage à rétroaction linéaire x0 x1 x2 x3 x4 x5 x6 x7 x8

 0 1 0 0 1 1 1 0

• ‘Linear Feedback Shift Register’ (LSFR) • Registre : suite binaire, initialisée à la valeur Sortie

x3  x6  x8 ö x0

Nicolas Pioch

appelée également ‘ou exclusif’ ou ‘XOR’ • Table de vérité :

Les registres à décalage à rétroaction linéaire

 Exemple de fonction de rétroaction :

‘asynchronous’, ou ‘ciphertext autokey’ (CTAK) • Ils utilisent les n pprécédents caractères chiffrés pour générer le flot de clés • Un caractère chiffré erroné transmis affecte n caractères déchiffrés au maximum • En cas d’insertion ou de perte de caractère chiffré, le destinataire se resynchronise automatiquement au bout de n caractères – exemple : une chiffre par bloc en mode CFB

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 • Cyclicité des clés produites : – La période vaut au maximum 2n-1 – On peut prédire les sorties après 2n bits

2

Cryptographie symétrique

17 mars 2009

Combinaisons non-linéaires de registres à décalage linéaires

Le chiffre A5 version 1 du GSM

Pour compenser la prédictibilité des registres à décalage linéaires, on peut en combiner plusieurs de taille différente (si possible relativement premières entre elles) via une fonction non linéaire. Exemples :

• Fonction majorité

A5/1 (inventé en 1989) utilise trois registres LSFR, initialisés par la clé de 64 bits ainsi que le numéro de trame TDMA (public) sur 22 bits pour éviter de réutiliser la même : • X : 19 bits (x0, x1, x2, …, x18) • Y : 22 bits (y0, y1, y2, …, y21) • Z : 23 bits (z0, z1, z2, …, z22) Sur chaque cycle d’horloge, un bit du flux pseudo-aléatoire est produit : x18  y21  z22

Les registres ‘stop and go’

A5/1

• Sur chaque cycle : m = maj(x8, y10, z10) • Si x8 = m, alors X se décale :

x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18

• Générateurs de Geffe :

x y  y z  z ou x y  (x) z



– t = x13  x16  x17  x18 – Pour i = 17, 17 16 16, …. 0 : xi+1 = xi, puis x0 = t • Si y10 = m, alors Y se décale : – t = y20  y21 – 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

y0 y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13 y14 y15 y16 y17 y18 y19 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



Chiffres basés sur les registres à décalage à rétroaction linéaire

A5/1 : exemple



1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 1

 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1

 1 1 1 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0



Nicolas Pioch



• Solution facile à implémenter en matériel

(appréciée des électroniciens), plus difficile à réaliser en logiciel • 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… • Aujourd’hui, les processeurs sont plus rapides, et l’on peut réaliser plus facilement les opérations de cryptographie au niveau logiciel

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 Security Inc. • Conçu ç p pour une implémentation p p performante en logiciel sur processeur 8 bits : les principales opérations sont des XOR et des permutations d’octets • 10 fois plus rapide que DES : très populaire vers 1995 dans de nombreux logiciels et protocoles tels que SSL, S/MIME, Acrobat…

est un secret industriel non breveté

• Code source révélé anonymement en

septembre 1994 sur la liste de diffusion Cypherpunk et reposté sur sci.crypt

• Usage libre sous le nom ‘arcfour’ :

http://www.mozilla.org/projects/security/pki/n 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 nécessaire)) sert à initialiser le tableau en permutant les valeurs (octets) deux à deux • À chaque itération, RC4 – Permute deux valeurs dans la table – Sélectionne une autre valeur dans la table et

• Peut valoir jusqu’à 256 octets, soit 2048 bits ! • Historiquement, de 5 ou 16 octets,

correspondant à des tailles de clés de 40 ou 128 bits

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 S[i] := i K[i] := key[i mod key_length] endfor j := 0 for i from 0 to 255 j := (j + S[i] + K[i]) mod 256 swap(S[i],S[j]) endfor

i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap(S[i],S[j]) output S[(S[i] + S[j]) mod 256] endwhile

Nicolas Pioch

4

Cryptographie symétrique

Représentation graphique

17 mars 2009

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 pour le flot de clés : la valeur de la case d’indice S[i]+S[j] mod 256

seul message, est appelée clé de session

Comment générer une clé de session à usage unique ?

Vulnérabilités de RC4

• 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é publique • Lorsqu’on q p partage g déjà j une clé symétrique y q avec le destinataire, la combiner avec un nonce à usage unique (‘number used once’) appelé également vecteur d’initialisation – La clé de session est le résultat d’un hachage cryptographique à sens unique de la clé symétrique et du nonce – Le nonce est transmis en clair au destinataire

valeurs des premiers octets générés du flot de clés RC4 ne sont pas équiprobables. • Il est désormais recommandé de « jjeter » les n premiers octets générés, afin d’augmenter le nombre de permutations réalisées sur la table S[] avant son utilisation. • De telles variantes de l’algorithme sont appelées RC4-drop-n. • 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)

• Remplacé par WPA2 (IEEE 802.11i, AES) ou WPA (RC4)

Nicolas Pioch

CHIFFRES PAR BLOC (‘BLOCK CIPHERS’)

5

Cryptographie symétrique

Principe d’un chiffre itéré par bloc • Le message en clair (ou le cryptogramme) est découpé en blocs de taille fixe, par exemple 64, 128, ou 256 bits

• On chiffre en itérant une fonction de ronde

17 mars 2009

Chiffre itéré par bloc On dérive n sous-clés {k1, k2, …, kn} par transformation de la clé maîtresse initiale k

• Un tel chiffre par itération est également

Les paramètres de la fonction de ronde à l’itération n sont kn et 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 faible cryptographiquement : • C’est le chaînage répété qui confère la robustesse au chiffre • Le nombre d’étages impacte la sécurité et la rapidité de chiffrement : il est compliqué de concevoir un chiffre à la fois rapide et sûr • Lorsque les fonctions de ronde sont complexes, un faible nombre peut suffire (10 à 14 pour AES, 16 pour DES), sinon il faut itérer un grand nombre de fois (64 pour TEA)

• Si un étage n’utilise que des opérations de

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) • On présente les sous-clés dans l’ordre

sur un certain nombre d’étages

appelé chiffre par produit (‘product cipher’).

moitiés (L0, R0) = M • F est la fonction de ronde • À chaque étape : – Li = Ri-1 – Ri = Li-1  F(Ri-1, ki) • Le bloc chiffré est C = (Ln, Rn)

Nicolas Pioch

substitution (‘S-box’) et de permutation (‘P-box’), un tel chiffre itéré se nomme réseau de substitution-permutation (‘SP-network’) • On peut également mettre en œuvre des opérations arithmétiques modulaires, comme dans les chiffres de Horst Feistel (1915 – 1990)

inverse : {kn, …, k2, k1}

• On résout les équations précédentes :

Li  Ri 1 Ri 1  Li    Ri  Li 1  FRi 1 , ki   Li 1  Ri  FRi 1 , ki   Ri  FLi , ki 

• C’est la même formule avec R et L inversés

et des indices décroissants • À noter : F n’a pas besoin d’être inversible – mais le chiffre n’est pas sûr pour toute fonction F

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 • Chiffre de Feistel :

• • • •

Standards (NBS, maintenant NIST) en 1973 Développé par IBM en 1975 (‘Lucifer’) – Conception secrète – Participation de la National Security Agency Adopté comme standard du gouvernement américain (FIPS 46) en 1976 Taille de clé désormais inadéquate : ne doit plus être utilisé Remplacé par AES (FIPS 197) en 2001

Étage DES

– 16 étages relativement simples – F(Ri-1 P-box(S-boxes(Expand(R box(S boxes(Expand(Ri-1 i 1, ki) = P i 1)  ki)) – Pour chaque étage, une sous-clé de 48 bits est dérivée de la clé maîtresse

• La sécurité dépend principalement des boîtes ‘S’, qui font correspondre 6 bits d’entrée à 4 bits en sortie.

http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf

DES : Permutation expansive • 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 7 15 23

DES : Permutation expansive (2/2)

0 8 16 24

1 9 17 25

2 10 18 26

4 12 20 28

3 11 19 27

3 11 19 27

4 12 20 28

5 13 21 29

6 14 22 30

7 15 23 31

8 16 24 0

DES : boîtes S • 8 boîtes de substitution : ‘S-box’ • Chacune prend 6 bits en entrée, et produit 4 bits en sortie

• ‘S-box’ S box n n°1 1: 00 bits 0, 5 : 01 10 11 00 01 10 11

Nicolas Pioch

0000 1110 0000 0100 1111

0001 0100 1111 0001 1100

0010 1101 0111 1110 1000

0011 0001 0100 1000 0010

0100 0010 1110 1101 0100

bits 1, 2, 3, 4 :

0 E 0 4 F

1 4 F 1 C

0101 1111 0010 0110 1001

2 D 7 E 8

0110 1011 1101 0010 0001

3 1 4 8 2

4 2 E D 4

0111 1000 0001 1011 0111

5 F 2 6 9

1000 0011 1010 1111 0101

6 B D 2 1

7 8 1 B 7

1001 1010 0110 1100 1011

8 3 A F 5

1010 0110 1100 1001 0011

9 A 6 C B

A 6 C 9 3

1011 1100 1011 0111 1110

B C B 7 E

1100 0101 1001 0011 1010

C 5 9 3 A

D 9 5 A 0

1101 1001 0101 1010 0000

E 0 3 5 6

1110 0000 0011 0101 0110

F 7 8 0 D 1111 0111 1000 0000 1101

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

• Sortie 32 bits : 15

6

19

20

28

11

27

16

0

14

22

25

4

17

30

9

1

7

23

13

31

26

2

8

18

12

29

5

21

10

3

24

DES : génération des sous-clés Sur chaque étage i = 1, 2, …, 16 : • Si i œ {1, 2, 9, 16}, ri = 1, sinon ri = 2 • On O décale dé l lles bit bits d de LK circulairement à gauche de ri positions • On décale les bits de RK circulairement à gauche de ri positions

LK :

RK :

49

42

35

28

21

14

7

55

48

41

34

27

20

13

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

16

9

2

52

45

38

31

18

11

4

24

17

10

3

Permutation-sélection compressive des 48 bits de la sous-clé ki • La partie gauche de la sous-clé ki est composée des bits suivants de LK : (les bits 8, 17, 21 et 24 sont ignorés) 13

16

10

23

0

4

2

27

14

5

20

9

22

18

11

3

25

7

15

6

26

19

12

1

• La partie droite de la sous-clé ki est

composée des bits suivants de RK : (les bits 6, 9, 14 et 25 sont ignorés) 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 • Les deux moitiés sont échangées après le g , afin de préparer p p le dernier étage, déchiffrement • Une permutation finale (‘FP’) inverse de ‘IP’ est appliquée à (R16, L16) • Tout ceci n’a aucune incidence sur la sécurité de l’algorithme

Nicolas Pioch

des boîtes S, car tout le reste est linéaire • “We sent the S-boxes off to Washington. y came back and were all different.” They – Alan Konheim, un des concepteurs de DES • “I would say that, contrary to what some people believe, there is no evidence of tampering with the DES so that the basic design was weakened.” – Adi Shamir

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 dérobées, en particulier dans la construction des mystérieuses ‘boîtes S’ – Afin d’éviter de telles suspicions, les concepteurs de nouveaux chiffres utilisent des nombres ‘rien dans les manches’ pour initialiser les constantes

• Les attaques se font toujours en pratique par balayage exhaustif de l’espace des clés

• Les concepteurs du DES savaient ce qu’ils faisaient… avec 20 ans d’avance

Foundation built a machine (‘Deep Crack’) for $220,000 that took three days to crack the DES code. The previous record was 39 days, according to the Foundation. The group's executives said that now that the research is done, a duplicate machine can be built for as little as $50,000.” • Janvier 1999 : DES-III Challenge : EFF ‘Deep Crack’ et distributed.net déchiffrent un 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 plutôt 257 car vulnérable (en théorie) à une attaque à texte clair connu : • Pré-calculer et stocker les 256 valeurs possibles de E(M, k1) pour toute clé k1 • Pour chaque clé k2, calculer D(C, k2) jusqu’à trouver une valeur dans la table • On a alors E(M, k1) = D(C, k2) et trouvé les clés k1 et k2 puisque C = E(E(M, k1), k2) • C’est une attaque ‘meet in the middle’.

démontré que DES n’était pas un groupe (Conférence CRYPTO 1992, p512-520) • Plus pprécisément,, l’ensemble kK Ek  n’est pas stable pour la loi de composition des applications • Si c’était le cas :

(k1 , k 2 )  K 2 , k3  K , Ek3  Ek2  Ek1 (k1 , k 2 )  K 2 , k3  K , m  M , E (m, k3 )  E ( E (m, k1 ), k 2 )

Triple DES (3DES)

Advanced Encryption Standard (AES)

• C = E(D(E(M, k1), k2), k1) • M = D(E(D(C, k1), k2), k1)

• Appel d’offres du NIST en janvier 1997 pour

Pourquoi utiliser E-D-E avec 2 clés ? • Compatibilité avec DES si les deux clés sont identiques : E(D(E(M, k), k), k) = E(M, k) • et 112 bits suffisent. • Cela a permis de prolonger la durée utile de DES jusqu’à la normalisation d’AES en 2001 Toutefois : 3 fois plus lent que DES en logiciel !

Nicolas Pioch

trouver un remplaçant à DES – Une quinzaines de chiffres étudiés – Participation p p publique q de la NSA,, q qui a déclaré

que tous les algorithmes finalistes étaient suffisamment sûrs pour chiffrer les informations non classifiées du gouvernement américain

• Rijndael sélectionné en nov. 2001 et publié

comme standard AES (FIPS 197) – Inventé par deux cryptographes belges, Vincent Rijmen et Joan Daemen. Libre de droits.

9

Cryptographie symétrique

17 mars 2009

Adoption d’AES

US National Policy on the use of AES

• Algorithme le plus intensément analysé • Adi Shamir a déclaré à la conférence RSA

“The design and strength of all key lengths of the

2002 que les données chiffrées avec AES et une clé de 256-bits seraient « secure forever » quelles que soient les avancées en informatique. • En 2003, AES est devenu le premier algorithme de chiffrement ouvert approuvé par la NSA pour le chiffrement d’informations du gouvernement américain classées TOP SECRET

AES algorithm (i.e., 128, 192 and 256) are sufficient to protect classified information up to the SECRET level. TOP SECRET information will require use of either the 192 or 256 key lengths. lengths The implementation of AES in products intended to protect national security systems and/or information must be reviewed and certified by NSA prior to their acquisition and use.” -- National Policy on the Use of the Advanced Encryption Standard (AES) to Protect National Security Systems and National Security Information http://www.cnss.gov/Assets/pdf/cnssp_15_fs.pdf

Fonctionnement d’AES

Fonctionnement d’AES

• Réseau de substitution-permutation • Rijndael permet n’importe quelle taille de

• Chaque étage met en œuvre 4 fonctions :

bloc et de clé indépendamment, de 128 et 256 bits p par incrément de 32 bits • AES ne conserve que le mode par bloc de données de 128 bits • 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

– SubBytes (substitution non-linéaire) – ShiftRows (transposition linéaire) – MixColumns ((mélange g non-linéaire)) – AddRoundKey (addition de la clé de ronde) http://www.csrc.nist.gov/publications/fips/fips197/fips-197.pdf

2

AES SubBytes C’est la « S-box » d’AES

Nicolas Pioch

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

y

0 1 2 3 4 5 6 7 8 9 a b c d e f

0 63 ca b7 04 09 53 d0 51 cd 60 e0 e7 ba 70 e1 8c

1 7c 82 fd c7 83 d1 ef a3 0c 81 32 c8 78 3e f8 a1

2 77 c9 93 23 2c 00 aa 40 13 4f 3a 37 25 b5 98 89

3 7b 7d 26 c3 1a ed fb 8f ec dc 0a 6d 2e 66 11 0d

4 f2 fa 36 18 1b 20 43 92 5f 22 49 8d 1c 48 69 bf

5 6b 59 3f 96 6e fc 4d 9d 97 2a 06 d5 a6 03 d9 e6

6 6f 47 f7 05 5a b1 33 38 44 90 24 4e b4 f6 8e 42

7 c5 f0 cc 9a a0 5b 85 f5 17 88 5c a9 c6 0e 94 68

8 30 ad 34 07 52 6a 45 bc c4 46 c2 6c e8 61 9b 41

9 01 d4 a5 12 3b cb f9 b6 a7 ee d3 56 dd 35 1e 99

a 67 a2 e5 80 d6 be 02 da 7e b8 ac f4 74 57 87 2d

b 2b af f1 e2 b3 39 7f 21 3d 14 62 ea 1f b9 e9 0f

c fe 9c 71 eb 29 4a 50 10 64 de 91 65 4b 86 ce b0

d d7 a4 d8 27 e3 4c 3c ff 5d 5e 95 7a bd c1 55 54

e ab 72 31 b2 2f 58 9f f3 19 0b e4 ae 8b 1d 28 bb

f 76 c0 15 72 84 cf a8 d2 73 db 79 08 8a 9e df 16

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 opérations inversibles : • Un octet {a7, a6, a5, a4, a3, a2, a1, a0}, ai œ {0, 1} p comme le p polynôme y est interprété a7x7 + a6x6 + a5x5 + a4x4 + a3x3 + a2x2 + a1x + a0 dans GF(28) • On calcule son inverse multiplicatif {b7, b6, b5, b4, b3, b2, b1, b0}, bi œ {0, 1} modulo le polynôme irréductible m(x) = x8 + x4 + x3 + x + 1 via l’algorithme d’Euclide étendu

• On applique ensuite la transformation affine suivante sur GF(2) (avec ) au résultat : b0'  1  '   b1  1 b2'  1  '  b3   1 b '  1  4'   b5  0 b '  0  6  b7'  0

0 0 0 1 1 1 1 b0  1 1 0 0 0 1 1 1  b1  1 1 1 0 0 0 1 1 b2  0     1 1 1 0 0 0 1 b3  0  1 1 1 1 0 0 0 b4  0      1 1 1 1 1 0 0 b5  1 0 1 1 1 1 1 0 b6  1     0 0 1 1 1 1 1 b7  0

Mix Columns

ShiftRows • 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

AddRoundKey

polynôme choisi c(x) = {03}x3 + {01}x2 + {01}x + {02} est 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

• Blowfish • RC6 • TEA

Lai et James Massey – 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 interdit d’exportation

• Breveté : usage commercial non-libre – 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 • Populaire et repris dans de nombreuses

• 16 étages • Presque un réseau de Feistel

implémentations logicielles avant AES car l’un des p premiers algorithmes g de cryptographie ‘forte’ libres de droits • L’auteur recommande désormais l’utilisation de Twofish, l’un des 5 finalistes AES. • Blocs de 64-bits, clés de 32 à 448 bits par multiple de 8 bits

Nicolas Pioch

– Ri = Li-1  ki – Li = Ri-1 i 1  F(Li-1 i 1  ki) • La fonction de ronde F utilise 4 boîtes ‘S’ qui font correspondre 8 bits d’entrée à 32 bits en sortie • Originalité : les boîtes ‘S’ sont calculées et dépendantes de la clé de chiffrement utilisée, initialisées à partir des hexadécimales de 

12

Cryptographie symétrique

Étage Blowfish

17 mars 2009

RC6 • Autre finaliste AES • Tailles de bloc, de

Fonction de ronde F

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

Tiny Encryption Algorithm (TEA)

TEA

• Publié en 1994 par David Wheeler et Roger

• • • •

Chiffrement TEA

Déchiffrement TEA

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

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

Needham (Cambridge Computer Lab) • Remarquable par sa simplicité – tient en quelques q q lignes g de code ! • Implémentation logicielle simple et rapide, consomme très peu de mémoire (Xbox) • Susceptible à une attaque par clés équivalentes, l’algorithme a été complexifié en eXtended TEA (XTEA) en 1997, puis Corrected block TEA (XXTEA) en 1998

Nicolas Pioch

Usage libre (non breveté) Blocs de 64 bits, clé de 128 bits Arithmétique sur 32-bits Presque un réseau de Feistel :  est remplacé par l’addition modulo 232 • Nombre d’étages variable : 64 recommandés (32 ‘cycles’), car la fonction de ronde est relativement simple • La constante est delta = 0x9e3779b9 = 232/,  étant le nombre d’or

13

Cryptographie symétrique

17 mars 2009

Comment chiffrer plusieurs blocs ?

MODES OPÉRATOIRES DES CHIFFRES PAR BLOC

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 chaque q bloc – Autant utiliser le masque à usage unique • Utiliser la même clé pour chiffrer chaque bloc indépendamment • 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 les algorithmes de chiffrement par bloc. Les 3 les plus simples sont : • Electronic Code Book (ECB) ( ) – Chiffre chaque bloc indépendamment – Ne pas utiliser ! • Cipher Block Chaining (CBC) – Une méthode pour chaîner les blocs entre eux • Counter Mode (CTR) – Semblable à un chiffre en continu

• Chaque clé k construit un livre de codage

électronique • Chaque bloc est chiffré avec ce même livre de codage g :p pour un message g m0, m1, …,, mn Chiffrement c0 = E(m0, k) c1 = E(m1, k) … cn = E(mn, k)

Déchiffrement m0 = D(c0, k) m1 = D(c1, 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

Nicolas Pioch

ECB

Autre mode

14

Cryptographie symétrique

17 mars 2009

Attaques actives sur ECB

Cipher Block Chaining (CBC)

Un attaquant actif peut rejouer (réinjecter) des blocs chiffrés avec la même clé ci, ou modifier l’ordre des blocs chiffrés : attaque du ‘copiercoller’ : c0 c1 c2 c3 → c0 c3 c2 c3. Exemples : • Modifier le montant d’un virement bancaire en le remplaçant par un bloc chiffré extrait d’un autre endroit du message (RIB) • Dans le jeu en ligne Phantasy Star Online: Blue Burst, qui utilisait Blowfish en mode ECB, les joueurs renvoyaient le message correspondant à ‘Monster killed’ au serveur.

• On chaîne les blocs les uns aux autres • Un vecteur d’initialisation (IV) aléatoire est

nécessaire pour initier le processus. Il peut être transmis en clair. Chiffrement c0 = E(IVm0, k) c1 = E(c0m1, k) … cn = E(cn-1mn, k)

Déchiffrement m0 = IVD(c0, k) m1 = c0D(c1, 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 : • cn-1  D(x, k)  mn x  D(cn+1, k)  mn+1 • cn+1 D(cn+2, k)  mn+2 cn+2 D(cn+3, k)  mn+3

Le mode CTR transforme un chiffre par bloc en chiffre en continu : on génère le flot de clés en chiffrant un vecteur d’initialisation incrémenté de façon monotone. Chiffrement c0 = m0  E(IV, k) c1 = m1  E(IV+1, k) … cn = mn  E(IV+n, k)

Nicolas Pioch

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

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 – 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É

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 • Plus important que la confidentialité dans pp : virements bancaires certaines applications • Les chiffres en continu ou les modes opératoires des chiffres par bloc peuvent être classés selon qu’ils amplifient ou minimisent le résultat d’une modification du cryptogramme, mais le chiffrement seul est insuffisant pour garantir l’intégrité : il n’assure que la confidentialité.

Nicolas Pioch

(MIC) • Doivent permettre de détecter toute g en clair : modification du message – Via une attaque à texte en clair choisi,

l’attaquant ne doit pas pouvoir trouver un autre message m’ tel que MAC(m) = MAC(m’)

• Le CBC-MAC (FIPS 113) est la méthode la

plus ancienne pour construire un MAC à partir d’un algorithme de chiffrement par bloc http://www.itl.nist.gov/fipspubs/fip113.htm

16

Cryptographie symétrique

Construction d’un CBC-MAC Calcul CBC-MAC c0 = E(IVm0, k) c1 = E(c0m1, k) … cn-1 = E(cn-2mn-1, k) = MAC

• Le MAC est accolé à la fin du texte en clair transmis au destinataire

• Le destinataire refait le même calcul à partir d’IV et de k, et vérifie le MAC

17 mars 2009

CBC-MAC : exemple • Alice veut envoyer à Bob le message • • • •

M = (m0, m1, m2, m3). Elle calcule : c0 = E(IV  m0, k), c1 = E(c ( 0  m1, k), ), c2 = E(c ( 1  m2, k), ), c3 = E(c2  m3, k) = MAC Alice envoie (IV, m0, m1, m2, m3, c3 = MAC) Supposons qu’un attaquant change m1 en x Bob calcule : c0 = E(IVm0, k), z2 = E(z1  m2, k)  c2, z1 = E(c0  x, k)  c1, z3 = E(z2  m3, k)  c3 = 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 message en clair

• On n’obtient donc que l’intégrité, pas la confidentialité.

• Pour obtenir confidentialité et intégrité, il faut

impérativement utiliser deux clés différentes, donc faire le double de calculs !

Nicolas Pioch

même clé pour deux opérations cryptographique différentes • Ici,, cela équivaudrait q à envoyer y le dernier bloc chiffré cn-1 = MAC deux fois… ce qui ne peut pas améliorer le niveau de sécurité ! (IV, c0, c1, c2, …, cn-1, cn-1 = MAC) • Si l’on fait cela, un attaquant peut modifier tous les blocs ci sauf le dernier… puisqu’une erreur sur un ci ne se propage qu’au bloc immédiatement suivant !

17

Cryptographie symétrique

17 mars 2009

Restriction sur l’utilisation des CBC-MAC

Les modes actuellement recommandés par le NIST

Les CBC-MAC ne doivent être utilisés que sur des messages de taille fixe, car ils sont vulnérables aux attaques par concaténation : • Si un attaquant q connaît les deux messages g (x1, x2, …, xn, MAC(X)) et (y1, y2, …, yp, MAC(Y)), alors il sait construire le message suivant dont le MAC est aussi MAC(Y) : (x1, x2, …, xn, MAC(X), (MAC(X)  y1), y2, …, yp) • Les CBC-MAC sont obsolètes

• 5 modes pour la confidentialité :

ECB (ne pas utiliser!), CBC, OFB, CFB, CTR • Pour l’intégrité et l’authentification p seulement,, les CBC-MAC ont été remplacés par un nouveau mode nommé « CMAC » • Pour combiner chiffrement, intégrité et authentification, deux modes existent : – le mode CCM : – Le mode GCM (Galois/Counter Mode) pour les implémentations matérielles à haut débit

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