AES & ECC

Ricardo BELIN et Mathieu ROMARY, EPITA spécialisation TCOM 2009 1

AES & ECCPrésentation des algorithmes de cryptographie

Groupe 10Présentation du

05/04/2008


Introduction


Introduction

Importance de la cryptographie aujourd’hui.

Société de plus en plus informatisée.

Loi de Moore: évolution de l’informatique et des technologies engendre une évolution des méthodes de sécurisation de celle-ci.

Mention AES et ECC dans la norme « Suite B » de la NSA publiée en février 2005.


Plan

Concepts Cryptographie symétrique AES

Historique Algorithme AES Usages & considérations économiques

Cryptographie asymétrique ECC

Historique Principe Usages & considérations économiques

Conclusion


ConceptsConcepts nécessaires à la compréhension du sujet


Concepts Cryptologie

Cryptologie « Science du

secret »Cryptographie

Discipline visant la protection de données axée

autour du concept de clé

Cryptanalyse Discipline opposée à la précédente basée sur le déchiffrement sans clé


Concepts Cryptographie

Cryptographie

SymétriqueChiffrement / Déchiffrement

AsymétriqueChiffreme

nt / Déchiffre

ment

Signature Numériqu

e

Echange de clé

Fonctions d’Agrégation (Hash)

Chiffrement à sens unique

AES ECC


ConceptsVocabulaire

Chiffrer : action de transcrire un message en un langage secret

Déchiffrer : Traduire en clair un message chiffré

Attention aux anglicismes « crypter » et « décrypter » basés sur le terme « encryption ».


ConceptsChiffrement par Blocs

Interprétation d’un flux ou d’un ensemble de données comme un flux de bits.

Découpage en segments, appelés blocs, d’un nombre de bits définis.

Permet donc de chiffrer « localement », de faire abstraction de l’ensemble.


Cryptographie symétriqueCryptographie à clé unique


TerminologieChiffrage Symétrique

Aussi dit « à clé secrète »

But: assurer la confidentialité de données Permet à partir d’une seul clé secrète de

chiffrer et de déchiffrer des données Problème de distribution des clés

Quelques exemples: Rot13 DES


Milieu non

sécurisé


BobAlice

Utilisation de la même clé de chiffrement par les deux

interlocuteurs



Exemple: ROT13 Décalage de chaque lettre de l’alphabet latin de 13

lettres

n o p k l m

t e a u

g r n h

a b c x y z

…

Message en clair

Clé de chiffrement

Message en chiffré

b a

on

z a bm n o

…b

t e a ua

Phase de chiffrage

Phase de déchiffrage


AESL’algorithme « Advanced Encryption Standard »


HistoriqueDES

DES pour « Data Encryption Standard ».

Introduit en 1977. Chiffrage symétrique par blocs Dérivé de l’algorithme Lucifer d’IBM

Fonctionne sur des blocs de 64 bits et des clés de 56 bits Adapté aux besoins techniques de l’époque. Aujourd’hui les

capacités et efficacités matérielles sont meilleures. Matériel spécialisé peut déterminer une clé DES 56 bits en

seulement quelques heures.

Besoin évident d’un nouveau standard de chiffrement.


HistoriqueLe concours AES

1997: NIST lance la sélection de l’Advanced Encryption Standard qui remplacera le DES

Sélection des algorithmes s’est faite par Sécurité prouvé contre des classes d’attaques Rapport coût-efficacité (matériel et logiciel) Architecture algorithmique Propriété intellectuelle

Présenté sous forme de concours: Deux tours de sélection 21 candidats (grandes entreprises, universitaires, et individus) 5 finalistes (MARS, RC6, Rijndael, Serpent, Twofish) Ouverture à la communauté par le biais de groupes de discussion

et de conférences





Présenté sous forme de concours de deux tours de sélection

21 candidats pour le premier tour de sélection

5 finalistes MARS proposé par IBM RC6 proposé par RSA Laboratories Rijndael proposé par Joan Daeman et Vincent Rijmen Serpent proposé par Ross Anderson, Eli Biham et

Lars Knudsen Twofish proposé par Bruce Schneier



MARS

RC6 Rijndael

Serpent

Twofish

Sécurité générale 3 2 2 3 3Implémentation de la sécurité

1 1 3 3 2

Performances logicielles

2 2 3 1 1

Performances carte à puce

1 1 3 3 2

Performances matérielles

1 2 3 3 2

Caractéristiques de l’architecture

2 1 2 1 3

Score total 10 9 16 14 13

“Rijndael provides consistently high-end performance for encryption, decryption and key setup, although performance decreases for the 192- and

256-bit key sizes.”

Source :

1 = mauvais2 = moyen3 = bon

Scores relatifs du deuxième tour de sélection:


AESL’algorithme de base: Rijndael

Concepteurs belges: Vincent Rijmen Joan Daeman

Publié en 1998 Chiffrage symétrique par blocs Dérivé de l’algorithme Square (des mêmes

concepteurs)

Le Rijndael: blocs de 128, 160, 192, 224 ou 256 bits, clé de 128, 160, 192, 224 ou 256 bits, et un nombre de rondes allant de 10 à 14. L’AES est un sous-ensemble: blocs de 128bits, clés de 128,

192, 256 bits, et 10, 12 ou 14 rondes.

Joan Daeman et Vincent Rijmen


AESL’algorithme de base: Rijndael

Taille clé

(bits)

Taille de bloc (bits)

128 192 256

128 10 12 14

192 12 12 14

256 14 14 14

Tableau de nombre de rondes pour le Rijndael, déterminé en fonction de la taille des blocs et de la taille de la clé

AES


AESComparatif DES AES

DES AES

Taille de clé 56 bits 128, 192 ou 256 bits

Type de chiffre Chiffre à bloc symétrique Chiffre à bloc symétrique

Taille de bloc 64 bits 128, 192 ou 256 bits

Resistance à la cryptanalyse Vulnérable à la cryptanalyse linéaire et différentielle; tables de substitution faibles

Résistant contre des attaques différentielles, linéaires et par interpolation.

Sécurité Prouvé comme inadéquat Considéré sécurisé

Clés possibles 256 2128,2192 ou 2256

Clés possibles composées de caractères ASCII affichables*

957 9516, 9524 ou 9532

Recherche sur toutes les clés possibles à 50 milliard de clés par seconde**

Pour une clé de 56 bits: 400 jours

Pour une clé de 128 bits: 5 x 1021 years

Source :* - Il y a 95 caractères ASCII affichables** - Temps affiché pour une recherche sur 100% des clés. ¨En théorie, une clé peut être trouvée après 50% de recherche.

23

AESAperçu général

AddRoundKey

SubBytes

ShiftRows

AddRoundKey

SubBytes

ShiftRows

MixColumns

AddRoundKey

12345678910

ronde

ronde initiale

9 rondes

ronde finale

0

Clé de chiffrage

Clé de ronde n

Clé de ronde 10

Le chiffrement se fait sur 10 rondescomposées de 4 étapes.

Ricardo BELIN et Mathieu ROMARY, EPITA spécialisation TCOM 2009

bloc départ

bloc arrivé

24

AESSubBytes

19 a0

3d f4

e3 e2

be 2b

9a e9

c6 f8

8d 48

2a 08

d4 e0

27 bf

11 98

ae f1

b8 1e

b4 41

5d 52

e5 30

19d4

S-BOX

Substituer chaque élément du bloc de données par l’élément correspondant dans la table de substitution (notée S-Box) telles que définie par Rijndael.


Animation basée sur une réalisation d’Enrique Zabala.

25

AESShiftRows

d4 e0 b8 1e

Décalage d’un octet

Décalage de 2 octets

Décalage de 3 octets

Effectuer un décalage cyclique sur chaque ligne en partant de la gauche, de 0 éléments pour la première ligne, puis 1 élément pour la deuxième, en

incrémentant le nombre d’élément à chaque ligne.



bf 4127 b4

11 98 5d 52

ae f1 e5 30

26

AESMixColumns

e0

b4

52

ae

b8

41

11

f1

1e

27

98

e5

=

04

66

81

e5

.d4

bf

5d

30

e0

cb

19

9a

48

f8

d3

7a

28

06

26

4c


Multiplier chaque colonne du bloc par un polynôme de degré 3 modulo un polynôme de degré 4 (tous deux constants et inversibles, tels que définis par

Rijndael), ce qui revient à faire une multiplication matricielle pour chacune des colonnes.


27

AESAddRoundKey

04

66

81

e5

e0

cb

19

9a

48

f8

d3

7a

28

06

26

4c

a0

fa

fe

17

88

54

2c

b1

23

a3

39

39

2a

6c

76

05

Clé de ronde

(XOR)

a4

9c

7f

f2

68

9f

35

2b

6b

5b

ea

43

02

6a

50

49


Application d’un XOR terme-à-terme avec la clé de ronde.


28

Clé de chiffrage

Clé de ronde 2

Clé de ronde 10

Clé de ronde 1

AESCréation des clés de rondes

…cf

09

ae f7

28

ab

7e

2b

4fd2

15

15

3c

a6

88

16

01000000

02000000

04000000

08000000

10000000

20000000

40000000

1b000000

80000000

36000000

fa

a0

fe

17

54

88

2cb1

a3

23

3939

6c

2a

7605

c2

f2

95

f2

96

7a

b943

a3

23

3939

59

73

f6

7f

14

d0

f9

a8

ee

c9

2589

3f

e1

0cc8

63

b6

0c

a6

09

cf

4f

3c

84eb01

7e

2b

1516

ae

28

d2a6

fa

a0

fe

17

54

88

2cb1

8a

cf

09

4f

3c

==


Tableau de constantes de rondes



AESUsages

Chiffrement de documents confidentiels L’algorithme AES est utilisé pour protéger des

documents confidentiels.

Voix sur IP: Skype “Skype uses AES (Advanced Encryption Standard),

[…] which is used by U.S. Government organizations to protect sensitive, information.”

WiFi: pour le WPA2 (norme IEEE 802.11i) Utilise l’algorithme AES plutôt que RC4 (utilisé par

WEP et WPA)

Compression de fichiers: WinRAR et WinZip

The Committee on National Security

Systems


AESAutres standards

NESSIE (New European Schemes for Signatures, Integrity and Encryption) Standard définit par l’Union

Européenne

CRYPTREC (Cryptography Research and Evaluation Committee) Standard japonais

Recommandent tous deux l’utilisation de l’AES


AESAttaques

Attaque exhaustive (brute force)

Attaques sur des versions simplifiée Certaines attaques effectuées avec succès en

réduisant le nombre de rondes à 7, 8, et 9 (en ajoutant une contrainte supplémentaire sur la clé) publiées en 2000

Attaques sur la version complète Méthode XSL a suscité un débat au sein de la

communauté de la cryptologie


AESAttaque par la méthode XSL

Publiée par Nicolas Courtois et Josef Pieprzyk en 2002 sous-entend pouvoir casser AES.

Attaque porte sur l’architecture de chiffrage du Rijndael.

Si possible, est une « certificational weakness »: requiert un nombre trop important de ressources, donc ne pose (actuellement) pas de problème à la sécurité réelle d’un système.

Démontré en 2004 par Claus Diem comme ne pouvant pas casser l’AES.


AESAttaque par la méthode XSL

En 2004, lors de la conférence AES 4 à Bonn Vincent Rijmen, co-concepteur du

Rijndael: "The XSL attack is not an attack. It is a dream.“

Nicolas Courtois, auteur de la méthode XSL, répond: "It will become your nightmare".

Sources :


AESSWOT

Strength Weaknesses

- Recommandé par la NIST- Performances fortes et indépendantes de la plateforme d’utilisation- Mise en place accessible

- Performances réduites avec des clés de 192 et 256 bits- Complexité algébrique relativement faible- Algorithme libre

Opportunities Threats

- Sécurité indépendante du matériel utilisé- Confidentialité pour cartes à puce- Besoin sans cesse croissant de sécurisation d’informations

-Application d’attaques à moyen terme (10 à 15 ans) encore théoriques aujourd’hui


Cryptographie asymétriqueCryptographie à double clés.


Chiffrage AsymétriqueIdée initiale

Initié dans les années 70 Whyfield Diffie Martin Hellman Ralph Merkle

But : Permettre les échanges chiffrés sans entente préalable sur une clé commune


Milieu non

sécurisé

Chiffrage AsymétriqueIdée initiale

A A BBA B

BobAlice


Chiffrage AsymétriquePrincipe

Basé sur une paire de clés (publique et privée)

Fonction mathématique « à sens unique » liant l’une à l’autre Multiplication vs. Factorisation Exponentiation vs. Logarithme

Plus dur est l’opération inverse (« reverse ») par rapport à l’opération de base (« forward »), plus l’algorithme peut être qualifié de sûr


Chiffrage AsymétriquePrincipe

Exemple Multiplication vs. Division : 165*285 = 47025 47025 = x * y ?

Exemple Exponentiation vs. Logarithme : 17^13 = 9904578032905937 logx 9904578032905937 = y ?


Chiffrage AsymétriqueUsages

3 utilisations : Chiffrage / déchiffrage Signature numérique (Digital Signature) Echange de clé (Key Exchange)

Garantie : Authentification Confidentialité Intégrité Non-répudiation


Chiffrage AsymétriqueUsages: Chiffrage / Déchiffrage

Clé publique de Bob Clé privée de Bob

Alice peut verrouiller un message avec le cadenas de Bob

Seul Bob peut ouvrir le cadenas


Chiffrage AsymétriqueUsages: Chiffrage / Déchiffrage

Source :


From:AliceBonjour

BobSignature

Chiffrage AsymétriqueUsages : Signature numérique

From:AliceBonjour

Bob

BobAlice

Signature

OK !


From:AliceBob, tu es renvoyé

Signature Eve

Chiffrage AsymétriqueUsages : Signature numérique

From:AliceBob, tu es renvoyé

Bob

Alice

Signature Eve

BAD!

Eve


Chiffrage AsymétriqueUsages : Echange de clé

Permet la discussion sans accord préalable sur une clé commune

Peut être utilisé pour communiquer une clé de chiffrage symétrique de façon confidentielle (algorithmes symétriques plus efficaces)


ECC« Elliptic Curve Cryptography »


Historique de l’ECC

Idée d’utiliser les courbes elliptiques pour la cryptographie née en 1985 Victor Miller (IBM) Neal Koblitz (University of Washington)

Libre, grand potentiel, mais trop lent Certicom

Société Canadienne crée en 1985 Nouvelles implémentations des algorithmes ECC Premier produit commercial basé sur ECC en 1997 Place prépondérante dans l’exploitation de l’ECC En relation avec N. Koblitz

N. Koblitz


Historique de l’ECC

Normalisé par IEEE, NESSIE, FIPS, ISO, ANSI X9F, …

Contrat de 25 million de dollars avec NSA en 2003 Licence d’utilisation pour toutes les

agences gouvernementales Licence d’utilisation pour les industries

travaillant pour l’état


ECCMathématiques

Les courbes elliptiques sont définies sur tous les ensembles possibles (réels, complexes, entiers, …)

Equation d’une courbe Elliptique: y² = x³ + ax + b


ECCMathématiques

Source :

Exemples de courbes :


ECCMathématiques

Source :

Exemples de courbes :


ECCUtilisation en cryptographie

Utilisé sur des groupes finis en cryptographie

Groupe mathématique doté de la loi +

Source :

P + Q = R(Addition)

2P= R(Doublement)



Ces opérations d’addition permettent l’utilisation de la multiplication kP = 2P + P + P + … + P

Méthode pas à pas sans intérêt Opération « reverse » aussi rapide que

« forward » Raccourcis mathématiques

nettement plus directs Proche temps constant pour un

ensemble donné



Source :

« Sur la courbe NIST 192 il est possible d’obtenir kP en un nombre d’opération quasi constant avec environ 38 additions et 192 doublements.

Calculer kP itérativement nécessiterait en moyenne 3.1057 opérations… »



Chiffrage / déchiffrage ECIES : Elliptic Curve Integrated Encryption

Scheme (El-Gamal ) Signature numérique (Digital Signature)

ECDSA : Elliptic Curve Digital Signature Algorithme

ECPVS : Elliptic Curve Pintsov Vanstone Signature ECNR: Elliptic Curve Nyberg Rueppel

Echange de clé (Key Exchange) ECDH : Elliptic Curve Diffie-Hellman ECMQV : Elliptic Curve Menezes-Qu-Vanstone


ECCExemple ECC-Diffie Hellman

P

BobAliceE(a,b,K)

kBPkA

PkA = 2

E(a,b,K)PkB = 3

kAPkB

PkA PkB

2P = PkA

3P = PkB

4P

5P

-6P

6P = kBPkA = kAPkB

PkA PkB

PirateE(a,b,K)PPkA

PkB

Clé ???

y

x

A et B s’accordent sur la courbe et le domaine utilisé pour l’échange.A et B s’accordent sur le point d’origine de l’échange.A et B choisissent au hasard une clé privée de x bits selon niveau de sécurité.

A et B calculent puis s’échangent leur clé publique Pk.

A et B calculent le produit de leur clé privée et de la clé publique de l’autre. Le résultat est identique pour A et B et sera utilisé comme clé pour l’échange.

Les valeurs utilisées ici sont très réduites afin de simplifier la compréhension et la lisibilité.


ECCRésistance aux attaques

Source :



La difficulté de casser l’algorithme est basée sur le problème des logarithmes discrets (DLP)

Pour l’ECC, rallonger la clé permet d’augmenter le temps de cassage de tn

En comparaison RSA (Factorisation), DSA (Petit Théorème de Fermat), Diffie-Hellman (DLP) le temps augmente de t√n



Symmetric Key Size

(bits)

RSA and Diffie-

HellmanKey Size

(bits)

Elliptic Curve Key

Size(bits)

80 1024 160

112 2048 224

128 3072 256

192 7680 384

256 15360 521

Source :


ECCThe Certicom ECC Challenge

Exercices 79-bit: Résolu en décembre 1997 89-bit: Résolu février 1998 97-bit: Résolu septembre 1999

Level 1 109-bit challenge Résolu en 2002* 131-bit challenge

Level 2 163-bit challenge

191-bit challenge239-bit challenge359-bit challenge

*10,000 ordinateurs549 jours de calcul


ECCAlgorithmes de cryptanalyse

Pollard-Rho (le plus efficace) Baby-step giant-step Pohlig Hellman’s reduction Xedni Attaque exhaustive (Brute force)


Considérations économiquesBenchmarks

Temps de traitement réduit de 25 à 85%

Sources :



De 30 à 270% de requêtes gérées en plus

Sources :



ECC-224 plus rapide que RSA-1024

Sources :


ECCProblématique des brevets

Majoritairement détenu par Certicom Brevet sur le protocole ECMQV

(protocole d’authentification basée sur DH et ECC)

Propriétaires de méthodes d’optimisation des multiplications

Grande quantité de courbes brevetées (les plus robustes)

Au total plus de 130 brevets


ECCUsages

Parfait pour périphériques mobiles Facile à gérer en hardware Clés réduites, réduit bande passante Faible consommation (chaleur, batterie)

Intérêts serveurs Faible consommation de ressource

système (plus de requêtes satisfaites) Consommation électrique réduite

Cryptographie conçue pour durer


ECCUsages

Motorola

Alcatel-Lucent :Certicom's technology enables operators to offer virtual private network (VPN) solutions to the growing base of DSL users

RIM : large-scale deployment of Certicom's high-performance, highly efficient ECC within its secure wireless devices

NSA


ECCUsages

Le « ECC/TLS Interoperability Forum » a été créé en 2006 pour promouvoir l’usage de l’ECC dans le cadre du protocole HTTPS. Les membres actuels sont des représentants de Apache/OpenSSL, Certicom, IBM, Microsoft, Mozila/Firefox, NSA, Red Hat, RSA, Sun et Verisign.


ECCSWOT

Strength Weaknesses

- Recommandé par la NIST- Robuste- Clé réduites- Temps de calculs réduits

- Majoritairement la propriété de la société Certicom- Met en jeu des notions mathématiques complexes

Opportunities Threats

- Le RSA devient très lourd- Explosion du nombre et du périmètre des périphériques mobiles

- Sécurité basée sur un domaine des mathématiques encore jeune


Conclusion


MerciFin de présentation.

Documents

AES & ECC