Audit et Sécurité Informatique

15 / 66

RSA

RSA

Developpé en 1977 au MIT par Ron Rivest, Adi Shamir & Len

Adleman

le plus utiisé des alg à clé publique

c’est un alg dont le plaintext et le ciphertext sont des entiers entre

0 et n-1.

n est un nombre de taille 1024 bits ou 309 digit décimal

16 / 66

Algorithme RSA

RSA

le plaintext est crypté en blocs, chaque bloc a une valeur

inférieure à n

Cryptage d’un bloc de plaintext est comme suit :

C = M e mod n

décryptage est comme suit :

M = Cd mod n = (M e)d mod n = M ed mod n

émetteur et récepteur connaissent la valaur de n

L’émetteur connait la valeur de e

seulement le récepteur connaît la valeur de d

la clé publique est la paire (e, n)

la clé privée est la paire (d, n)

17 / 66

Génération des clés

RSA

chaque utilisateur génère ses propres clés (privée et publique)

par :

selectionner deux grands nombres premiers p et q

calculer n = p × q

calculer φ(n) = (p − 1) × (q − 1)

sélectionner aléatoirement un nombre e avec : 1 < e < φ(n) et

GCD(e, φ(n)) = 1

résoudre cette équation pour trouver d avec 0 ≤ d ≤ n :

e × d = 1 mod φ(n)

publier la paire PU = {e, n} comme clé publique

garder en secret la paire PR = {d, n} comme clé privée

18 / 66

exemple

RSA

1 Sélectionner les nb premiers : p = 17 & q = 11

2 Calculer n = p × q = 17 × 11 = 187

3 Calculer φ(n) = (p − 1) × (q − 1) = 16 × 10 = 160

4 Sélectionner e : gcd(e, 160) = 1 ; choisir e = 7

5 Déterminer d tel que d × e = 1 mod 160 et d < 160 : la valeur est

d = 23 puisque 23 × 7 = 161 = 10 × 160 + 1

6 Publier la clé publique PU = {7, 187}

7 Garder en secret la clé privée PR = {23, 187}

19 / 66

Exemple RSA

RSA

20 / 66

Exemple RSA avec un long message

RSA

21 / 66

Exponentiation dans RSA

RSA

le cryptage et le decryptage manipule des exponentiations de

grand nombres modulo n

on peut utiliser des propriétés de l’arithmetique modulaire :

(a mod n) × (b mod n) = (a × b) mod n

il faut chercher aussi à faire l’exponentiation le plus vite possible

on prend rendre l’exponentiation en O(log2n) multiplications pour

un nombre n

ex1 : 75 = 74 × 71 = 3 × 7 = 10 mod 11 =⇒ log25 = 3

multiplications

ex2 : 3129 = 3128 × 31 = 5 × 3 = 4 mod 11 =⇒ log2129 = 8

multiplications

22 / 66

Calcul de ab mod n

RSA

avec b est un entier converti en binaire en bk bk −1 . . . b0

Ex de calcul de ab mod n, pour a = 7, b = 560 = (1000110000)2, et

n = 561

23 / 66

Attaque sur RSA ?

RSA

Trois approches pour attaquer RSA :

Factoriser n en deux nombres premiers p et q. Ceci va mener à

trouver φ(n) = (p − 1)(q − 1) ce qui mène à déterminer

d = e−1 mod φ(n)

déterminer φ(n) directement sans trouver p et q, ce qui mène à

déterminer d = e−1 mod φ(n)

Déterminer directement d sans déterminer φ(n)

24 / 66

Partage de clé de Diffie-Hellman

Plan

1 Principes de la Cryptographie asymétrique

2 RSA

3 Partage de clé de Diffie-Hellman

4

Les fonctions de Hachage

5 Problèmes et contre-mesure des problèmes de sécurité

6 MAC

7 Signature numérique

25 / 66

Partage de clé de Diffie-Hellman

Échange de clé de Diffie-Hellman

Premier alg à clé publique

un très grand nombre de produit commercial utilisent ce protocole

But : permettre à deux utilisateurs d’échanger en toute sécurité

une clé qui peut par la suite être utilisée pour le chiffrement

symétrique de messages

Son efficacité est liée à la difficulté de calculer des logarithmes

discrets

26 / 66

Partage de clé de Diffie-Hellman

Échange de clé de Diffie-Hellman

27 / 66

Partage de clé de Diffie-Hellman

Échange de clé de Diffie-Hellman

La clé partagée entre deux entités A et B, est KAB

KAB = axA×xB mod q

= y xB

= y xA

A mod q ( calcul par B )

B mod q ( calcul par A )

KAB est utilisée comme clé de session dans un alg symétrique

entre A et B

si Alice et Bob continuent à communiquer, ils auront la même clé

comme avant, à moins qu’ils ne choisissent de nouvelles clés

publiques

un adversaire doit résoudre le problème du logarithme discret

pour compromettre cet algorithme (difficile)

28 / 66

Partage de clé de Diffie-Hellman

Exemple

Alice et Bon veulent partager une clé

Ils partagent un nombre premier q=353 et un nombre a=3

choisir des nombres aléatoires secrètement : XA = 97, XB = 233

calculer les clés publiques respectives :

yA = 397 mod 353 = 40 (Alice)

yB = 3233 mod 353 = 248 (Bob)

calculer la clé de session partagée KAB :

KAB = y xA

B mod 353 = 24897 = 160 (Alice)

KAB = y xB

A mod 353 = 40233 = 160 (Bob)

29 / 66

Partage de clé de Diffie-Hellman

Man-in-the-Middle Attack

1 Darth se prépare en créant 2 clés privée/publique

2 Alice transmet sa clé publique à Bob

3 Darth intercepte cette clé et transmet sa première clé publique à

Bob. Darth calcule alors la clé partagée K2 avec Alice.

4 Bob reçoit la clé publique et calule la clé partagée K1 (avec Darth

au lieu de la faire avec Alice !)

5 Bob transmet sa clé publique à Alice

6 Darth intercepte ce message et transmet sa seconde clé publique

à Alice. Darth calcule alors la clé partagée K1 avec Bob.

7 Alice reçoit la clé et calcule la clé partagée K2 avec Darth (au lieu

de Bob)

8 Darth peut alors intercepter, déchiffrer, re-chiffrer, transmettre tous

les messages entre Bob et Alice.

30 / 66

Partage de clé de Diffie-Hellman

31 / 66

Plan

Les fonctions de Hachage

1 Principes de la Cryptographie asymétrique

2 RSA

3 Partage de clé de Diffie-Hellman

4

Les fonctions de Hachage

5 Problèmes et contre-mesure des problèmes de sécurité

6 MAC

7 Signature numérique

32 / 66

Les fonctions de Hachage

Les fonctions de Hachage

Une fonction de hachage accepte une entrée de longueur variable

et fait sortir un condensé ou empreinte de longueur fixe

h = H(M)

Son principal but est la vérification d’intégrité

Une fonction de hachage cryptographique est un algorithme dont

il est mathématiquement difficile de :

Trouver une entrée qui donne un condensé bien spécifié

(Propriété : fonction à sens unique)

trouver deux entrées qui donne le même condensé (Propriété :

Sans collision)

33 / 66

Fonction de hachage cryptographique h=H(M)

Les fonctions de Hachage

34 / 66

Le condensé du message (digest)

Les fonctions de Hachage

Le condensé du message est son empreinte digitale

Beaucoup plus petit que le message original

facile à calculer

impossible de retrouver le message depuis le condensé

Changer le message fait automatiquement changer le condensé

35 / 66

Les fonctions de Hachage

36 / 66

Authentification du message

Les fonctions de Hachage

Vérifier l’intégrité du message

S’assurer que les données reçues sont exactement comme

envoyés

S’assurer que l’identité de l’expéditeur est valide

Exemple 1 : Chiffrer le message et son condensé par un

cryptosystème symétrique

37 / 66

Authentification du message

Les fonctions de Hachage

Exemple 2 : Chiffrer seulement le condensé du message

ça permet de réduire la complexité de calcule si la confidentialité

n’est pas sollicitée

38 / 66

Authentification du message

Les fonctions de Hachage

Exemple 3 : Un secret partagé est haché

Pas de besoin de cryptage

39 / 66

Authentification du message

Les fonctions de Hachage

Exemple 4 : Un secret partagé combiné avec confidentialité

40 / 66

D’autres Utilisations des fonctions de hachage

Les fonctions de Hachage

Utilisée pour créer les fichiers de mots de passe

Lorsqu’un utilisateur tape un mot de passe, le condensé du

password est comparé au condensé enregistré pour vérification

Cette approche est utilisée par la majorité des systèmes

d’exploitation

utilisé pour détecter les intrusions et les virus

enregistrer le H(f) de chaque fichier dans le disque

l’antivirus peut vérifier par la suite si le fichier a été altéré ou non en

recalculant son condensé H(f)

Un intrus essayera de changer F sans changer H(f) : très difficile !

peut être utilisé pour construire des générateurs de séquences

pseudo-aléatoires PRNG

générer des keystreams, des clés secrètes

41 / 66

Exigences d’une fonction de hachage

Les fonctions de Hachage

Entrée de longueur variable

Sortie de longueur fixe

Efficacité : étant donnée x, il est facile de générer le condensé

H(x) en s/w ou h/w

Fonction à sens unique (Preimage resistant) : Pour un condensé

donné h, il est impossible de trouver y tel que H(y ) = h

Pas de collision en sens large (Second preimage resistant : weak

collision resistant) : Quelque soit x donnée, il est impossible de

trouver y (cid:54)= x tel que H(y ) = H(x)

Pas de collision au sens strict (collision resistant : Strong collision

resistant) : il est impossible de trouver une paire (x, y ) tel que

H(x) = H(y )

Critère aléatoire : La sortie de H doit être aléatoire selon les tests

standards (NIST : 16 tests du critère aléatoire)

NB : "impossible" = "mathématiquement ou par calcul difficile"

42 / 66

Exigences des applications d’intégrité

Les fonctions de Hachage

43 / 66

Paradoxe d’anniversaire

Les fonctions de Hachage

Dans une classe, quelle est la probabilité pour que 2 élèves fêtent leurs anniversaires le

même jour ?

Avec 365 jours par an, une trentaine d’élèves dans la classe, on se dit qu’elle doit être

faible...

On va calculer la probabilité pour que, dans un groupe de k personnes, ces personnes

aient toutes un jour d’anniversaire différent :

Si on a 2 personnes, la première peut avoir son anniversaire

n’importe quand, la seconde n’importe quel autre jour. on a donc :

p2 = 364

si mnt on a k personnes : p3 = (1 − 1

ds un groupe de k personnes, pk = (1 − 1

365 = 1 − 1

365 )

365 )(1 − 2

365 ) . . . (1 − k −1

365 )

365 )(1 − 2

365

=⇒ Il ne faut donc que 23 personnes pour qu’il y ait plus d’une chance sur 2 (chance > 0.5) pour

que 2 personnes aient leur anniversaire le même jour.

44 / 66

Les attaques basés sur le paradoxe d’anniversaire

Les fonctions de Hachage

Dans une attaque qui cherche des collisions, l’adversaire veut trouver 2 messages qui

donnent le meme condensé.

Dans une classe de 23 étudiants la probabilité de trouver 2 étudiants ayant le meme

anniversaire est > 0.5

Si le condensé est codé sur b bits, il y a 2b empreinte possibles.

si on prend k msg différents, la probabilité de trouver 2 msg ayant le meme condensé est :

p = 1 − (1 −

k − 1

2

1

2b

2b

2b

2b ) . . . (1 − k −1

2b ) ≤ 1

2b )(1 − 2

2 , il suffit que p = (1 − 1

) . . . (1 −

)(1 −

)

2

pour que p ≥ 1

on a (1 − j

2b ) ∼ e

on a alors (1 − 1

(− j

2b )

il faut donc que e

2b ) . . . (1 − k −1

2b ) ∼ e

2b )(1 − 2

(− k (k−1)

2b+1 )

≤ 1

2

(− k (k−1)

2b+1 )

45 / 66

Paradoxe d’anniversaire et sécurité wifi (WEP)

Les fonctions de Hachage

la clé de 104 bits est tapé manuellement (13 caractères). La clé

est fixe

ce qui varie est le vecteur d’initialisation (24 bits) échangé entre le

point d’accès et le PC.

il ya 224 possibilités du IV. presque 16 millions possibilités

Par le paradoxe des anniversaires, il suffit d’à peu près 4824

échanges pour qu’il y ait plus d’une chance sur deux pour que le

même IV soit utilisé.

Ainsi, la sécurité d’une clé de 104 bits n’était que virtuelle dans

WEP. La vraie sécurité était sur 24 bits seulement !

WEP est remplacé par WPA (utilise RC4 mais change IV à

chaque paquet) et WPA2 (utilise AES).

46 / 66

Structure générale d’une fonction de hachage

Les fonctions de Hachage

47 / 66

Secure Hash Algorithm (SHA)

Les fonctions de Hachage

SHA a été conçu par "National Institute of Standards and

Technology (NIST)" et publié comme "federal information

processing standard" (FIPS 180) en 1993

a été revisé en 1995 comme SHA-1

Basé sur la fonction de hachage MD4

Produit un condensé de taille 160-bit

En 2002 NIST produit une version révisée du standard pour

définir 3 autres de SHA avec des longueurs 256, 384, and 512

Connus comme SHA-2

48 / 66

Comparaison des versions de SHA

Les fonctions de Hachage

49 / 66

SHA-512

Les fonctions de Hachage

50 / 66

SHA-512 : traitement d’un bloc de 1024-Bit

Les fonctions de Hachage

51 / 66

SHA-512 : Mise à jour des buffers

Les fonctions de Hachage

52 / 66

SHA-512 : traitement du message Mi

Les fonctions de Hachage

53 / 66

Problèmes et contre-mesure des problèmes de sécurité

Plan

1 Principes de la Cryptographie asymétrique

2 RSA

3 Partage de clé de Diffie-Hellman

4

Les fonctions de Hachage

5 Problèmes et contre-mesure des problèmes de sécurité

6 MAC

7 Signature numérique

54 / 66

Problèmes et contre-mesure des problèmes de sécurité

Différents types d’attaques/problèmes ds un réseau

Divulgation des messages =⇒ Sol : cryptage

Analyse de trafic =⇒ Sol : cryptage

Mascarade : insertion de message depuis une source frauduleuse

=⇒ Sol : Authentification du message

modification de contenu : insertion, suppression, transposition et

modification =⇒ Sol : Authentification du message

modification en temps : retard ou rediffusion (replay) de message

=⇒ Sol : Authentification du message

Répudiation de la source : Déni de transmission du message par

la source =⇒ Sol : Signature numérique

Répudiation de la destination : Déni de réception du message par

le destinataire =⇒ Sol : Signature numérique

55 / 66

Problèmes et contre-mesure des problèmes de sécurité

Les techniques d’authentification de message

1 Les fonction de hachages : une fonction qui accepte comme

entrée n message de longueur variable et fait sortir un condensé

de longueur fixe. Le condensé est l’authentificateur du message

(déjà vu)

2 Le cryptage du message : le ciphertext du message constitue son

authentificateur

3 Le MAC (Message authentication code) : une fonction du

message et d’une clé secrète qui produisent une sortie de

longueur fixe MAC ce qui constitue l’authentificateur du message

56 / 66

Problèmes et contre-mesure des problèmes de sécurité

plusieurs scénarios d’utilisation du cryptage

57 / 66

Plan

MAC

1 Principes de la Cryptographie asymétrique

2 RSA

3 Partage de clé de Diffie-Hellman

4

Les fonctions de Hachage

5 Problèmes et contre-mesure des problèmes de sécurité

6 MAC

7 Signature numérique

58 / 66

MAC

MAC

Connu aussi par fonction de hachage à clé

utilisé lorsque deux entités partageant la même clé pour

authentifier l’information échangée entre eux

Prend comme entrée une clé secrète K et un bloc de donnée M et

produit un MAC=C(K,M)

le MAC est associé au message lors de son envoi

Si l’intégrité du message doit être vérifié, la fonction MAC est

appliqué au message et le résultat est comparé au MAC associé

(reçu)

un hacker qui veut modifier le message sera incapable de modifier

le MAC sans la connaissance de la clé secrète.

Le MAC n’est pas une signature numérique

59 / 66

Utilisations basiques du MAC

MAC

60 / 66

Cryptage authentifié

MAC

Protèger la confidentialité et fournir l’authentification en meme

temps

Différent approches :

Hash-then-encrypt : E(K , (M||H(M))

MAC-then-encrypt : E(K 2, (M||MAC(K 1, M))

Encrypt-then-MAC : C = E(K 2, M), T = MAC(K 1, C)

Encrypt-and-MAC : C = E(K 2, M), T = MAC(K 1, M)

decryptage et la vérification est facile

61 / 66

Plan

Signature numérique

1 Principes de la Cryptographie asymétrique

2 RSA

3 Partage de clé de Diffie-Hellman

4

Les fonctions de Hachage

5 Problèmes et contre-mesure des problèmes de sécurité

6 MAC

7 Signature numérique

62 / 66

Signature numérique

Signature numérique

Similaire qu’au MAC

le condensé du message est chiffré par la clé privée de l’émetteur

du message

N’importe quelle personne connaissant la clé publique de

l’émetteur peut vérifier l’intégrité du message

un hacker qui veut modifier le message a besoin de connaître la

clé privée de l’émetteur

3 propriétés :

elle doit vérifier l’auteur, le temps et la date du document signé

elle doit authentifier le contenu au temps de la signature

elle doit être vérifiée par une tierce partie pour résoudre les

disputes

63 / 66

Modèle général de la signature numérique

Signature numérique

64 / 66

Modèle détaillé de la signature numérique

Signature numérique

65 / 66

2 approches de la signature numérique

Signature numérique

66 / 66