Cryptographie - Crypto-reduit.pdf PDF

LA CRYPTOGRAPHIE Anas ABOU EL KALAM ENSEEIHT  Plan du cours ⚫ Confidentialité – Introduction : utilité, définitions, historique – Chiffrement symétrique : transpositions, substitutions – Chiffrement asymétrique – le futur : courbes elliptiques, cryptographie quantique...

LA CRYPTOGRAPHIE Anas ABOU EL KALAM ENSEEIHT  Plan du cours ⚫ Confidentialité – Introduction : utilité, définitions, historique – Chiffrement symétrique : transpositions, substitutions – Chiffrement asymétrique – le futur : courbes elliptiques, cryptographie quantique ⚫ Authentification – Introduction : objectifs, définitions – Fonction de hashage – Signatures digitales et certificats ⚫ Applications – PAP, CHAP, NTLM – TLS, Kerberos Anas Abou El Kalam 2 Crypto : définitions – cryptosystème : mécanisme permettant de camoufler des messages I.e., de le rendre incompréhensible pour quiconque n’est pas autorisé – cryptographie : art de créer et utiliser des cryptosystèmes – cryptanalyse : art de “casser” des cryptosystèmes – cryptologie : étude de la cryptographie + cryptanalyse À PROSCRIRE : cryptage, encryptage, chiffrage, chiffration !!!!! Convention secrète chiffrement Texte en Texte chiffré clair (cryptogramme) déchiffrement cryptanalyse (espions) Anas Abou El Kalam 3 Crypto : historique ⚫ "FD PDUFKH" ❖ inconvénient ⚫ totalement symétrique ⚫ calculer fréquences d'apparition lettres dans message codé... Anas Abou El Kalam 11  Substitution monoapphabétique(Exemple …) ❖Comment ? ⚫ chaque caractère du texte en clair est remplacé par un caractère correspondant dans le texte chiffré. ⚫ Les exemples les plus célèbres sont les algorithmes cesar, rotl3, morse ❖Exemple ? AB CD E F G H I J K LMN O PQ R S T UVW XYZ D E F G H I J K LM N O P Q RS TUVW XYZ ABC ❖ Clair : LANCE LES MISSILES ❖ Chiffré : ODQFH OHV PLVVLHV ⚫ Mais : cryptanalyse statistique (Freqce lettres) Anas Abou El Kalam 12 Chiffrement par symboles de substitution A B C J N O P W D E F K L Q R S X Y G H I M T U V Z message : LANCELESMISSILES message chiffré : Anas Abou El Kalam 13 La Substitution homophonique ❖Comment ? ⚫ comme pour le principe précédent, sauf qu’à un caractère du texte en clair on fait correspondre plusieurs caractères dans le texte chiffré. ⚫ Par exemple, " A " peut correspondre à 5, 13, 25 ou 56 ; " B " 7, 19, 31, ou 42 ; etc. Anas Abou El Kalam 14 La Substitution polyalphabétique ❖remplacer chaque lettre du message en clair par une nouvelle lettre prise dans un ou plusieurs alphabets aléatoires associés ❖ On choisit une clé qui sert d’entrée dans la grille ❖ Chaque caractère de la clé désigne une lettre dans la grille ❖Chiffrement : lire le caractère correspondant du texte en clair en utilisant la grille et le mot clé associé ❖on répète la clé si sa longueur est inférieure à celle du texte de départ 15 Anas Abou El Kalam Le carré de Polybe (~150 av JC) Principe ⚫ Chaque lettre est codée par deux chiffres : coordonnées dans matrice Exemple ⚫ X=53 1 2 3 4 5 1 A B C D E 2 F G H I-J K 3 L M N O P 4 Q R S T U 5 V W X Y Z Anas Abou El Kalam 16 Substitution par Carré polybique Mot clé secret est utilisé pour construire un alphabet dans un tableau. Transcrire le message en chiffres : coordonnées (lignes, colonne) des lettres du clair Deux lignes de chiffres : une pour les absices, l'autre pour les ordonnés Ces deux coordonnées sont ensuite transposées en les recombinant par deux sur la ligne ainsi obtenue. Anas Abou El Kalam 17 Substitution : chiffrement de vigenère Quoi ? ⚫ Utilise matrice ⚫ Le chiffré d'une caractère est différents à chaque fois Pourquoi ? ⚫ pallier pblme de César: une lettre puisse être codée d'une seule façon. Chiffrement ⚫ A chacune des lettres du message, ajouter lettre d'un autre mot appelé clé ⚫ Les deux lettres forment une entrée à la matrice de vigenère ⚫ Remarque : La clé est ajoutée indéfiniment en vis-à-vis avec texte clair Anas Abou El Kalam 18 Crypto-système de vigenère Anas Abou El Kalam 19 Crypto-système de Vigenère (…) Keyword: RELATIONS Plaintext: TO BE OR NOT TO BE THAT IS THE QUESTION Chiffrement Keyword: RELAT IONSR ELATI ONSRE LATIO NSREL Plaintext: TOBEO RNOTT OBETH ATIST HEQUE STION Ciphertext:KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY Déchiffrement Keyword: RELAT IONSR ELATI ONSRE LATIO NSREL Ciphertext: KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY Plaintext: TOBEO RNOTT OBETH ATIST HEQUE STION Anas Abou El Kalam 20 Crypto-système de vigenère... Anas Abou El Kalam 21 Crypto-système de vigenère... Anas Abou El Kalam 22 Le chiffre de Hill ❖ idée ⚫ Ne plus coder lettres par lettres, mais de coder simultanément des groupes de m lettres! ⚫ Plus m est grand, plus les analyses statistiques deviennent difficiles ! ❖ Comment ? ⚫ Remplacer chaque lettre par son ordre dans l'alphabet-1 : ⚫ A devient 0, B devient 1, C devient 2, … ⚫ grouper les nombres ainsi obtenus par m (prenons par exemple m=2). ⚫ Pour chaque bloc de m nombres à coder x1x2...xm, on calcule le texte codé en effectuant des combinaisons linéaires (ici m=2) : ⚫ y1=ax1+bx2 ⚫ y2=cx1+dx2 ⚫ Le choix de la clé correspond ici au choix d'un nombre m, et au choix des combinaisons linéaires à effectuer (ce sont toujours les mêmes de blocs en blocs). Anas Abou El Kalam 23 Le chiffre de Hill : exemple ❖coder le mot ELECTION avec le chiffre de Hill ⚫ Clé : m=2, a=3, b=5, c=1 et d=2. ⚫ Etape 1 : Découpage en blocs de 2 : EL | EC | TI | ON ⚫ Etape 2 : remplacer lettres par leur nombre associé : 4-11 | 4-2 | 19-8 | 14-13 ⚫ Etape 3 : combinaisons linéaires pour chaque bloc. ⚫ E.g., pour le 1er bloc (x =4, x =11) 1 2 y1=ax1+bx ⚫ 2 Y1= 3×4 + 5×11 = 67 ⚫ Y2= 1×4 + 2×11 = 26 y2=cx1+dx2 De même, y3=22, y4=8, y5=97, y6=35, y7=107, y8=40. ⚫ Etape 4 : restes modulo 26: z1=15, z2=0, z3=22, z4=8, z5=19, z6=9, z7=3, z8=14. ⚫ Etape 5 : On reconvertit en lettres ==> Chiffré : PAWITDJO. Anas Abou El Kalam 24 Le chiffre de Hill ❖Remarques : ⚫ le premier E de ELECTION est transformé en P, ⚫ tandis que le second est transformé en W. ⚫ Le critère des chiffrements polyalphabétique est bien respecté : ⚫ les analyses statistiques directes sur la fréquence des lettres sont impossibles. ❖Déchiffrement ⚫ Découper message en blocs de m lettres, ⚫ inverser relations données par les combinaisons linéaires : si un système donne y 1 et y2 en fonction de x1 et x2, il faut pouvoir l'inverser et exprimer y1 et y2 en fonction de x1 et x2 Anas Abou El Kalam 25  D.E.S, Triple D.E.S, A.E.S, IDEA ⚫ D.E.S – Inventé par IBM sous le nom de Lucifer (1976) – Adopté comme standard de chiffrement aux USA en 1977 – Blocs de 64 bits, clés de 56 bits (+8 bits de parité) – Grand succès (anciens systèmes UNIX, beaucoup d’applications…) ⚫ Triple D.E.S – Utilise 2 ou 3 clés différentes de 56 bits chacune – Modes : EEE3, EDE3, EEE2, EDE2 ; une préférence pour le EDE3. ⚫ A.E.S – Concours lancé par le NIST (National Institute of Standards and Technology ) – 15 participants – Octobre 2000 : gagnant RIJNDAEL Vincent Rijmen et Joan Daemen Algorithme de chiffrement par blocs. Anas Abou El Kalam 26  DES Chiffrement par blocs ⚫ Découpe le texte clair en blocs de 64 bits (8 octets) ⚫ Code les blocs séparément, ⚫ Les concatène. Algorithme assez simple ⚫ ne combine que des permutations et des substitutions Algorithme à clef secrète ⚫ La clef sert à la fois à chiffrer et à déchiffrer message ⚫ Longueur de 64 bits (8 caractères), ⚫ mais seulement 56 bits sont utilisés. Anas Abou El Kalam 27  DES Fractionnement du texte en blocs de 64 bits (8 octets) Permutation initiale des blocs Découpage des blocs en deux parties: G et D Permutations et substitutions répétées 16 fois (rondes) Recollement des parties gauche et droite Permutation initiale inverse Anas Abou El Kalam 28  DES La clef K (64 bits) est utilisée pour générer 16 autres clefs de 48 bits chacune (K0,.., K15) 16 étapes / itérations / roundes : ⚫ Ki est utilisée à l’itérations i (rounde). Ces clefs sont les mêmes  le bloc qu'on code dans un message. La sécurité de DES repose sur ses tables de substitutions Nombre de clefs possibles est (256=7,2*1016) Algorithme relativement facile à réaliser matériellement ⚫ certaines puces chiffrent jusqu'à 1 Go de données /s Anas Abou El Kalam 29  Permutations initiales 58 50 42 34 26 18 10 2 ⚫ Chaque bit d'un bloc est 60 52 44 36 28 20 12 4 soumis à la permutation 62 54 46 38 30 22 14 6 initiale, pouvant être représentée par une matrice 64 56 48 40 32 24 16 8 PI ⚫ Exemple : 57 49 41 33 25 17 9 1 – le 58ème bit du bloc de texte 59 51 43 35 27 19 11 3 de 64 bits se retrouve en première position, le 50ème en 61 53 45 37 29 21 13 5 seconde position et ainsi de suite. 63 55 47 39 31 23 15 7 Anas Abou El Kalam 30  Scindement en blocs 58 50 42 34 26 18 10 2 ⚫ Une fois la permutation initiale 60 52 44 36 28 20 12 4 réalisée, le bloc de 64 bits est G0 scindé en deux blocs de 32 bits, 62 54 46 38 30 22 14 6 notés respectivement G0 et D0 64 56 48 40 32 24 16 8 – G0 contient tous les bits possédant une position paire dans le message initial, 57 49 41 33 25 17 9 1 – D0 contient les bits de position impaire. 59 51 43 35 27 19 11 3 D0 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 Anas Abou El Kalam 31  Rondes ⚫ Les blocs Gn et Dn sont soumis à un ensemble de transformation itératives appelées rondes Dn+1 = Gn  EKn(Dn) Ronde n Gn+1 = Dn Anas Abou El Kalam 32  Génération des clefs ⚫ Initialement les 64 bits de la clef DES sont réduits à 56 bits (ignorer bits parité) ⚫ Une clé de 48 bits différentes est engendrée pour chaque ronde du DES – D’abord la clé de 56 bits est divisée en 2 moitiés de 28 bits – Ensuite les moitiés sont décalées vers la gauched’une ou deux positions en fonction de la ronde – Le nombre de bits de décalage est donné par le tableau Ronde 1 2 3 4 5 6 7 8 9 10 1 1 13 1 1 1 2 5 6 Nbre décalage 1 1 2 2 2 2 2 2 1 2 2 2 2 2 1 ⚫ Après avoir été décalés, 48 bits parmi les 56 sont sélectionnés ⚫ Cette opération fourni un sous ensemble de bits qui a la même taille que la sortie de la permutation expansive Anas Abou El Kalam 33  Permutation expansive ⚫ La moitié droite est étendue de 32 à 48 bits – Change l’ordre de certains bits et répète certains bits ⚫ Pourquoi ? – Le résultat à la même taille que la clé pour le ou exclusif – Fournit un résultat plus long qui pourra être comprimé pendant l’opération de substitution 32 1 2 3 4 5 4 5 6 7 8 9 le dernier bit de D0 (32ème) devient le premier, 8 9 10 11 12 13 le premier devient le second, … les bits 1,4,5,8,9,12,13,16,17,20, 21, 24,25,28 12 13 14 15 16 17 et 29 de D0 sont dupliqués et disséminés dans la E 16 17 18 19 20 21 matrice ⚫ par ex : Le premier bits sera copié dans le 20 21 22 23 24 25 deuxième et le 64ème bits 24 25 26 27 28 29 28 29 30 31 32 1 Anas Abou El Kalam 34 Permutation expansive 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 32 48 1 2 3 4 5 6 7 8 9 10 11 121314151617 18 19 20 21 22 23 Anas Abou El Kalam 35  Substitution par tables-S ⚫ Après que la clef comprimée a été combinée par ou exclusif avec le bloc expansé, le résultat de 48 bits est soumis à une opération de substitution ⚫ Ces substitutions sont réalisées à l’aide de 8 tables de substitutions ⚫ Chaque table-S a 6 bits d’entrée et 4 de sortie ⚫ Les 48 bits d’entrée sont divisés en blocs de 6 bits ⚫ Chaque bloc est manipulé séparément par une table-S différente Entrée de 48 bits Table S-1 Table S-2..... Table S-8 Sortie de 32 bits 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 Exemple de Table-S : S-6 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 Anas Abou El Kalam 36  DES, suite … ⚫ Fonction de substitution – D0 est scindé en 8 blocs de 6 bits, noté D0i. Chacun de ces blocs passe par des fonctions de sélection (boîtes de substitution ou fonctions de compression), notées généralement Si. – Chaque bloc de 6 bits est ainsi substitué en un bloc de 4 bits. Ces bits sont regroupés pour former un bloc de 32 bits. ⚫ Permutation – Le bloc de 32 bits obtenu est enfin soumis à une permutation P ⚫ OU Exclusif – Les résultats en sortie de P est soumis à un OU Exclusif avec le G0 de départ pour donner D1, tandis que le D0 initial donne G1 ⚫ Itération (16 fois) ⚫ Permutation initiale inverse – A la fin des itérations, les deux blocs G16 et D16 sont "recollés, puis soumis à la permutation initiale inverse Anas Abou El Kalam 37 Les caractéristiques du DES. 1. Tous les bits de C dépendent de tous les bits de M 2. Effet d'avalanche ⚫ Légère modification de M ==> grande modification de C ⚫ (en moy. 32 bits différents/bit de M modifié). Le même effet est obtenu en modifiant la clé. Anas Abou El Kalam 38 Les modes du DES ❖ Le DES est un algorithme de chiffrement par blocs ❖ L'opération de chiffrement s'effectue sur des blocs de texte clair (ex: pour le DES -blocs de 64 bits) ❖ Dans le cadre d'une implémentation pratique, l'algorithme 'pur' est combiné à une série d'opérations simples en vue d'améliorer la sécurité sans pour autant pénaliser l'efficacité de l'algorithme. ❖ Cette combinaison est appelée un mode cryptographique. Anas Abou El Kalam 39 Les modes du DES (…) Sécurité: - Effacement des formats standards (ex. l'introduction d'un texte). - Protection contre la modification de C. - Chiffrement de plusieurs messages avec la même clé. Efficacité: - L'utilisation d'un mode cryptographique ne doit pas pénaliser l'efficacité du cryptosystème. - Limitation de la propagation des erreurs qui apparaissent dans M ou C. Anas Abou El Kalam 40 A quel point le DES est sûr ? 1993 : Une attaque par une machine spécialement conçue (1M$) prend 3-5 heures en moyenne Difficile de résister à une technique de cryptanalyse différentielle lorsque le texte clair est chiffré avec la même clé W. Schwartau a écrit que la NSA a construit une machine CRAY 1980 basée sur des algorithmes statistiques, clés probables (3-15mn) Recommandation : utiliser des tables S-Box dépendant de la clé Anas Abou El Kalam 41  Le triple DES : pourquoi ? Faiblesses du DES Les S-boxes qui pourraient contenir des failles. La taille de la clé ⚫ 1990 : Eli Biham et Adi Shamir ont mis au point la cryptanalyse différentielle qui recherche des paires de texte en clair et des paires de texte chiffrées. ⚫ Cette méthode marche jusqu'à un nombre de rondes < 15 ⚫ ++ processeurs permettent de calculer plus de 106 clés par seconde ⚫ utilisés parallèlement sur un très grand nombre de machines, il devient possible de trouver la bonne clé... Anas Abou El Kalam 42  Le triple DES : pourquoi ? Augmenter la sécurité du DES sans réécrire un nouvel algorithme Une attaque brutale devrait tester 2 112 clés possibles 3DES : chaîner trois chiffrement DES à l'aide de deux clés de 56 bits (clé de 112 bits) ➔ Augmenter sécurité – Mais demande également plus de ressources pour les chiffrement et le déchiffrement ⚫ On distingue plusieurs types de chiffrement triple DES : – DES-EEE3 : 3 chiffrements DES avec 3 clés différentes ; – DES-EDE3 : une clé différente pour chacune des 3 opérations DES (chiffrement, déchiffrement, chiffrement) ; – DES-EEE2 et DES-EDE2 : une clé différente pour la seconde opération (déchiffrement). Anas Abou El Kalam 43 Diffie - Hellmann Anas Abou El Kalam 44 Idée Diffie- Hellmann Anas Abou El Kalam 45  Diffie - Hellmann (1) ⚫ Algorithme à clé publique inventé en 1976 ⚫ Objectif : Permet l’échange d’une clé secrète sur un domaine non sécurisé, sans disposer au préalable de secret ⚫ Utilisation : entre autres, dans SSL/TLS (Netscape) ⚫ Repose sur : – connaissant ga mod p et gb mod p, il est très difficile d’en déduire a et b. Anas Abou El Kalam 46  Diffie - Hellmann (2) ⚫ Privé : - Algorithme - – a pour Alice n,1np−1,k/gk =nmod p – b pour Bob Alice génère p−1etcalcule a(privé) ga mod p(public) Bob génère p-1etcalcule b(privé) gb mod p(public) ⚫ Public : – p : nbre premier Echange des clés publiques – G: appelé générateur – clé publique d’Alice Alice (gb)a mod calcule p – clé publique de Bob Bob (ga)b mod calcule p p=(ga)b mod (gb)a mod p=gabmod p=k(secret partag Anas Abou El Kalam 47  DH : un exemple Alice Bob p = nombre premier arbitraire g = nombre aléatoire inférieur à p Ax = nombre aléatoire (privé) Bx = nombre aléatoire (privé) Ay = g ^ Ax % p By = g ^ Bx % p Ay Ay By By s = By ^ Ax % p Échange données s = Ay ^ Bx % p Chiffrées avec s Anas Abou El Kalam 48  DH : un exemple Alice Bob p = nombre premier arbitraire = 419 g = nombre aléatoire Ax = nombre aléatoire (privé) inférieur à p = 7 Bx = nombre aléatoire (privé) 178 344 Ay = 7 ^ 178 %419 By = 7 ^ 344 %419 = 351 181 181 351 351 s = 351 ^ 178 % 419 Échange données s = 181 ^ 344 % 419 = 493 Chiffrées avec = 493 s NB : Contrairement à RSA, il ne permet pas de signer des documents. Diffie-Hellman est souvent associé à DSS 49 Anas Abou El Kalam  Diffie - Hellmann (3) ⚫ Attaque “sandwich” (man-in- the-middle attack) : Bob gb mod p – Carole intercepte le message d’Alice et remplace ga mod p par sa propre clé publique gc mod p, et ga mod p l’envoie à Bob. gc mod p Alice – Carole intercepte la réponse de Bob, et remplace gb mod p par gc mod p, et l’envoie à Alice. gc mod p Carole – Alice et Bob croient converser entre eux, alors que tout passe par ga mod p Carole ! gb mod p Anas Abou El Kalam 50 Algorithme R.S.A (1) ⚫ Inventé en 1977 par Rivest, Shamir et Adleman ⚫ Utilise une fonction à brèche secrète – factorisation de nombres premiers. ⚫ Parmi les plus utilisés ⚫ Sécurité : – Le RSA à clé de 512 bits a récemment été cassé, mais ce n’est pas à la portée de tout le monde. – Incassable actuellement sur du 768 ou 1024 bits. Anas Abou El Kalam 51  Algorithme R.S.A (2) Algorithme de chiffrementt : ⚫ p et q deux nombres e m mod n = c premiers distincts ⚫ Modulo : Euclide (Algo PGCD) : – n=pq d tq ed mod( p −1)(q −1) =1 ⚫ Exposant public : Théorème d' Euler : – e premier avec (p-1)(q-1) m,0  m  n, med mod n = m ⚫ Clés : – clé publique : (n,e) Algorithme de déchiffrement : – clé privée : (n,d) cd mod n = m p, q restent secrets, ils permettent de calculer d Anas Abou El Kalam 52  RSA : un exemple ⚫ 2 nombres premiers au hasard: p = 29, q = 37 ⚫ calcul n = pq = 29 * 37 = 1073 ⚫ choisir e au hasard tq e n'ai aucun facteur commun avec (p-1)(q-1) = 1008 ⚫ On prend e = 71 ⚫ On choisit d tel que 71*d mod 1008 = 1 ➔ d = 1079 On a maintenant nos clés : ⚫ La clé publique est (e, n) = (71,1073) (=clé de chiffrement) ⚫ La clé privée est (d, n) = (1079,1073) (=clé de déchiffrement) Anas Abou El Kalam 53  RSA : Chiffrer « hello » ⚫ Prendre le code ASCII des caractères m = 72 69 76 76 79 ⚫ Découper m en blocs qui comportent - de chiffres que n. (n comporte 4 chiffres), ⚫ Découper m en blocs de 3 chiffres: 726 976 767 900 (on complète avec zéros) ⚫ Chiffrer chacun de ces blocs: « c = Me mod(n) » 726^71 mod 1073 = 436 976^71 mod 1073 = 822 767^71 mod 1073 = 825 900^71 mod 1073 = 552 Le message chiffré est 436 822 825 552. Déchiffrer (avec d) : M = Me*d mod(n) = cd mod(n) 436^1079 mod 1073 = 726 822^1079 mod 1073 = 976 825^1079 mod 1073 = 767 552^1079 mod 1073 = 900 ➔ 726976767900. ➔retrouver notre message en clair 72 69 76 76 79 : 'HELLO'. Anas Abou El Kalam 54  Algorithme R.S.A (3) ⚫ Cryptanalyse (on connaît n et e) : – arriver à factoriser n en facteurs premiers. – ou calculer la racine eième de c … ⚫ Choix de p et q : – p et q doivent être voisins – la factorisation en nombre premiers est d’autant plus difficile que (p-1) et (p+1) ont des facteurs premiers élevés. – Il n’y a aucun risque de tomber à court de nombres premiers ⚫ Longueurs de clés : – ne pas comparer avec les longueurs de clés d’algorithmes à clés secrètes. Anas Abou El Kalam 55  Exemple RSA ⚫ Décomposition d'un nombre à 155 chiffres (512 bits) en produit de deux nombres premiers de 78 chiffres : ⚫ Août 1999 ⚫ 300 PCs et stations ⚫ 12 sites dans 6 pays. RSA-155 = 109417386415705274218097073220403576120037329454492059909 138421314763499842889347847179972578912673324976257528997 81833797076537244027146743531593354333897 écrit comme le produit de deux nombres premiers de 78 chiffres: 102639592829741105772054196573991675900716567808038066803 341933521790711307779 * 106603488380168454820927220360012878679207958575989291522 270608237193062808643 Anas Abou El Kalam 56 El Gamal ⚫ Publié par El Gamal en 1987 (Cf. gnuPG) ⚫ Clé privée (secrète) : s ⚫ Clé publique : (p, g, y) – p, entier premier de grande taille. – g, entier premier avec p. – y = gs mod p,. ⚫ Chiffrer ⚫ Découper message en blocs compris entre 0 et p-1. ⚫ Chaque bloc est un entier M, ⚫ Générer au hasard k premier avec p - 1 ⚫ Calculer a = gk mod p et b= M yk mod p ⚫ Message chiffré = (a, b) ⚫ Déchiffrer b M y kmodp Mg sk s = s = sk = M a a g 57 Anas Abou El Kalam El Gamal: un exemple ⚫ Le destinataire, Bob, possède deux clés : – clé privée (secrète) : un entier s. – clé publique (p, a, Y) tel que a premier avec p ; Y=as mod p. ⚫ Chiffrer ⚫ tirer au hasard un nombre k, ⚫ calculer : C1=ak mod p, et C2=MYk mod p. ⚫ Le message chiffré est le couple (C1,C2), ⚫ Déchiffrer ⚫ calculer R1=C1s mod p=ask mod p=Yk mod p. ⚫ retrouver Yk, ⚫ diviser Yk par C2 ⚫ retrouver M. Anas Abou El Kalam 58 El Gamal: robustesse Pour retrouver M, un attaquant doit pouvoir calculer Y k, connaissant Y, a et ak. Il doit donc découvrir k, ⚫ Problème du logarithme discret !! Point - ❖le message chiffré est deux fois plus long que le message original Point + ❖Le fait d'utiliser un paramètre aléatoire k est un plus en termes de sécurité ⚫ le même message M chiffré à 2 moments différents donnera deux messages codés distincts! Anas Abou El Kalam 59  Chiffrement hybride ⚫ Chiffrement à clé secrète (symétrique) : – Rapides – Problème de distribution de clés ⚫ Chiffrement à clé publique (asymétrique) : – Plus lents – Utilisés pour : transmettre des clés secrètes de session (Diffie-Hellmann) ou signer (DSA) – Quelques rares algorithmes permettent de faire les deux : RSA, El Gamal, Rabin... Anas Abou El Kalam 60  Chiffrement :hybride Chiffrement Génération clé session Chiffrement clé session avec Kpub destinataire Chiffrer message avec clé session Déchiffrement Déchiffrement clé session par Kpriv destinataire Déchiffrement message avec clé session Anas Abou El Kalam 61  Algo de chiffrement cassés Année Nom Taille Année de Par qui ? d'apparition cassage 1974 RSA 560 2003 équipe internationale de chercheurs 1976 DES 56 1997 Internet (Distributed.net et Electronic Frontier Foundation) 1985 ECC 109 1997 Internet (Ecc2.com ) 1987 RC4 40 1995 Adam Back, Eric Young et David Byers Anas Abou El Kalam 62  Législation ❖ Les logiciels de chiffrement ne sont pas libres d'utilisation en France. ❖Deux décrets fixent l'utilisation des moyens de cryptographie en France: ⚫ décret 99-200 du 17 mars 1999 sur les moyens de cryptographie dispensés de toute formalité préalable pour l'utilisateur (pas de demande d’autorisation) ⚫ logiciels dont l'algo utilise une la clé de session inférieure à 40bits ⚫ logiciels dont l'algo utilise une clé inférieure à 128 bits à condition que: ⚫ l'éditeur du logiciel ait fait une déclaration ou ⚫ logiciels utilisés dans un cadre privé exclusivement ⚫ décret 99-199 du 17 mars 1999 sur les moyens de cryptographie nécessitant un déclaration préalable auprès des autorités compétentes. ⚫ logiciels dont l'algo utilise une clé inférieure à 128 bits ⚫ non déclarés par l'éditeur et utilisés dans un cadre non-privé (commercial, entreprise,...). Anas Abou El Kalam 63  Législation : conclusions ❖ il est interdit en France de se servir des logiciels qui utilisent une clé de session supérieure à 128bits. ❖ Dans le cadre privé, vous pouvez utiliser n'importe quel logiciel, déclaré ou non par l'éditeur, dès lors que la clé de session ne dépasse pas 128bits. ❖ Dans le cadre de l'entreprise, vous pouvez utiliser les logiciels commerciaux de cryptographie déclarés en France, ⚫ liste sur le site du DCSSI ❖ Les restrictions ne concernent que la clé qui chiffre les données et donc garantit la confidentialité des données, ❖ Pas de limites pour tout ce qui concerne les fonctions de signature et d'intégrité des données. Anas Abou El Kalam 64 Protocoles cryptographiques Dès que plusieurs entités sont impliquées dans un échange de messages sécurisés, des règles doivent déterminer l'ensemble des opérations cryptographiques à réaliser, leur séquence, afin de sécuriser la communication: C'est ce que l'on appelle les protocoles cryptographiques. Les propriétés fondamentales Que signifie sécuriser - Confidentialité un échange? - Authentification -Intégrité -Non répudiation Anas Abou El Kalam 65  Introduction à l’authentification ⚫ La notion de confidentialité ne suffit ? pas forcément : – qui m’a réellement envoyé ce message ? Authenticité – quelqu’un a-t-il pu usurper émetteur !! son identité ? + – ai-je bien reçu le message Intégrité complet ? + – quelqu’un a-t-il pu remplacer Non répudiation !! ? le message initial par un Authenticité autre ? message !! La confidentialité ne répond pas à ces questions ! Anas Abou El Kalam 66  Définitions ⚫ Intégrité – on assure que le message n’a pas été modifié – exemple : une lettre scellée. Si une tierce personne ouvre l’enveloppe et remplace la lettre par une autre, le sceau sera forcément rompu – attaque : la substitution (remplacer le message originel par un autre) ⚫ Authenticité – on garantit la provenance du message – l’authentification, c’est le procédé qui permet de prouver et valider l’authenticité. – exemple : le message provient d’Alice. – attaque : la mascarade (espérer que le message forgé sera considéré comme authentique) ⚫ Non répudiation – propriété rendant impossible de nier toute action qui a été effectuée Anas Abou El Kalam 67  Fonctions de hashage ⚫ Dans la pratique, un sceau, signature, c’est petit! – On condense le texte avant de le sceller ou de le signer – La fonction qui effectue ce “résumé” est appelée fonction de hashage ⚫ Choix des algorithmes de hachage – Une fonction de hachage "H" transforme une entrée d'une dimension variable "m" et donne comme résultat une sortie de données inférieure et fixe "h ⚫ il doit être impossible de trouver m à partir de h. ➔ fonction de hachage doit remplir conditions : ➔ L'entrée peut être de dimension variable. ➔ La sortie doit être fixe. ➔ H(m) doit être relativement facile à calculer. ➔H(m) doit être une fonction à sens unique. impossible de trouver m à partir de h. ➔ H(m) doit être "sans collision". M1  M2  H(M1)  H(M2) Anas Abou El Kalam 68  Contrôler l’intégrité Document Transmission du document Document Algorithme de hashage à Hashage Hashage sens unique, résistant aux collisions Empreinte Empreinte (2) Transmission de comparaison ? l’empreinte Empreinte (1) Attention: résout l’intégrité… mais pas l’authenticité de l’émetteur ! Anas Abou El Kalam 69  Message Authentication Code Document MAC Algo. Authentifiant Clé secrète ⚫ Objectif : Intégrité et authenticité ⚫ Algorithmes de MAC : – Fonction de hashage compression et facilité de calcul. – Convenir au préalable d’une clé sécrète. – Pas (ou très très peu) de collisions – sans connaître la clé. ⚫ Exemples : DES-CBC, HMAC … Résout l’intégrité et l’authenticité (à condition que la clé soit bien secrète) MAIS pas de non répudiation (quelqu’un d’autre pourrait posséder la même clé). Anas Abou El Kalam 70  Aperçu du SHA-1 (1) ⚫ Historique – conçu en 1995 Mise en forme du texte – Adopté comme algorithme standard de hashage par le gouvernement américain Calculs sur 5 registres – Décrit dans le FIPS 180-1 ⚫ Objectifs Obtention du résultat – fonction de hashage qui retourne toujours un résumé sur 20 octets, quelque soit la taille du texte en entrée – conçu pour des machines 32 bits Anas Abou El Kalam 71  SHA 2 : le successeur de SHA-1 ⚫ Rappel – but d'un haché : être le plus court possible, tout en gardant ses propriétés. problème des collisions (paradoxe des anniversaires) !! – il faut 2n/2 essais pour trouver une collision au hasard – Empreinte de128 bits (n/2=64) ne représentent plus une sécurité à moyen terme ⚫ Pourquoi SHA-2 ? – SHA-1 ne peut produire que des hash de 160 bits ➔ pas plus de 80 bits de sécurité contre les collisions. – AES (Advanced Encryption Standard), qui utilise des clés de taille128, 192 ou 256-bit ⚫ SHA-2 – SHA-2 algorithm contient SHA-256, SHA-384 et SHA-512 Produit un hash de 256, 384 ou 512-bits ➔ avec un niveau de protection (contre les collision) de 128, 192 ou 256-bits. Anas Abou El Kalam 72 1. Confidentialité Cryptosystème à clés symétriques (K) Cryptosystème à clés publiques (PKA/SKA, PKB/SKB) Anas Abou El Kalam 73 1. Confidentialité (…) A l'aide de cryptosystèmes hybrides. Cryptosystème à clés publiques pour l'échange confidentiel de la clé (de session) K. Cryptosystème à clés symétriques pour l'échange confidentiel du message. Anas Abou El Kalam 74 2. Intégrité du message Vérification qu ’un message n ’a pas été altéré durant la communication. A cette fin, on utilise les fonctions de hashage. Anas Abou El Kalam 75 3. Authentification des acteurs. Protocole question réponse RA Chaîne aléatoire de A A l ’aide d’un cryptosystème à RB Chaîne aléatoire de B clés symétriques. Si on suppose que A et B partagent une même clé secrète K A B RA Génération RA EK(RA,B) DK(EK(RA,B)) EK(RA,B) , RB Génération RB EK(RB,A) EK(RB,A) DK(EK(RB,A)) Anas Abou El Kalam 76 3. Authentification des acteurs (…) A l ’aide d’un cryptosystème à clés publiques. Chaque partie possède une paire de clés publique/privée (PKA/SKA, PKB/SKB). Anas Abou El Kalam 77 3. Authenticité du message A l ’aide d’un MAC (Message Authentication Code). Un MAC peut être généré de deux manières: 1. A l'aide d ’un cryptosystème symétrique. 2. A l'aide d ’une fonction de hashage. Anas Abou El Kalam 78 3. Authenticité du message (…) 1. A l'aide d ’un cryptosystème symétrique Authentification grâce à K Par ex le triple DES Anas Abou El Kalam 79 3. Authenticité du message (…) 2. A l'aide d ’une fonction de hashage. Une clé secrète K est partagée entre A et B Authentification grâce à K + Intégrité. Anas Abou El Kalam 80  Signatures (1) ⚫ Il n’est pas forcément facile de s’échanger une clé secrète auparavant ⚫ Solution : – utiliser des algorithmes à clé publique. – Alice envoie un document à Bob. – Elle décide alors de signer le document : elle condense le document (fonction de hashage) puis le “chiffre” avec sa clé privée, cela constitue une signature. ⚫ Vérification : – Bob possède la clé publique d’Alice. Il peut donc déchiffrer (=vérifier) la signature. – Si le message est altéré en cours de route, la signature ne correspondra plus !!! – Si la clé utilisée pour le chiffrement n'est pas la clé privée d'Alice alors la vérification va échouer 81 Anas Abou El Kalam  Signatures (3) Alice Bob Document Transmission du document Document Hashage à sens unique Hashage à sens unique Document condensé (1) Document condensé ? Document condensé (2) Algorithme à Clé privée Clé publique Algorithme à clé publique d’Alice d’Alice clé publique chiffrement déchiffrement Transmission de la signature Signature Signature Anas Abou El Kalam 82 Signature (2) : un exemple Anas Abou El Kalam 83  Algorithmes de signatures ⚫ Digital Signature Millisecondes / opération Algorithm (1994) : Sur un Celeron 850Mhz sous – Utilise un algorithme à clé Windows 2000 avec l’API publique Crypto++ – Repose sur le problème des 12 logarithmes discrets – Ne peut être utilisé que pour 10 effectuer des signatures (pas pour le chiffrement) 8 ⚫ Comparaison avec RSA : 6 Signature – La génération de la signature en DSA est plus rapide que 4 Vérification sa vérification – Le RSA peut servir au 2 chiffrement et aux signatures. 0 DSA RSA 1024 1024 Anas Abou El Kalam 84 4. Non répudiation A l'aide d’une signature Seul A a pu composer Sign. digitale. Anas Abou El Kalam 85 4. Non répudiation + confidentialité A l'aide d’une signature et Authentification + d'un chiffrement Confidentialité Anas Abou El Kalam 86  Certificats : pourquoi ? ⚫ chiffrement & signatures supposent l’authenticité des clés publiques, disponibles sur un annuaire ou un serveur web – signature garantit que le message provient bien du détenteur de la clé privée … mais … A qui appartient clé privée/publique ? – Chiffrement garantit que le message ne pourra être déchiffré que par le détenteur de la clé privée (associée à la clé publique utilisée lors du chiffrement) … mais A qui appartient cette clé publique ? ⚫ Est-on sûr qu’il ne s’agit pas d’un usurpateur ? Anas Abou El Kalam 87  Certificats : pourquoi ? ⚫Scénario : ⚫ Alice et Marie veulent s’envoyer des messages ⚫ Bob = pirate Bob ⚫ modifie l’annuaire ou le serveur web qui héberge les clés publiques ⚫ remplace clé publique d’Alice par la sienne. ⚫ Bob peut mnt lire les courriers destinés à Alice et signer des message en se faisant passer pour Alice !! ⚫ si Marie envoie message « M » chiffré à Alice, – Marie va chiffrer M avec clé publique de Bob (croyant que c’est la clé d’Alice). ⚫ Bob pourra – déchiffrer les messages destinés à Alice avec sa clé privée, – lire ainsi le courrier confidentiel d’Alice. Les signatures et les MACs ne résolvent pas entièrement le problème de l’authenticité. On introduit alors la notion de certificat ! Anas Abou El Kalam 88  Certificats : quoi ? ⚫ permet de proouver l'authenticité d'une clé publique ==> établir un environnement de confiance entre deux entités distantes ayant besoin de communiquer entre elles et de s’échanger des informations : non-répudiables (nécessité de signature) ou confidentielles (application de chiffrement). ⚫ certificat : vise à effectuer un lien entre une identité (d'une personne) et une bi-clé (privé/publique) – Il est délivré par une autorité de certification (AC) – Il est nominatif – Il est destiné à un usage unique (signature OU chiffrement) – Il a une durée de validité donnée – Il est certifié par l’AC – Il est révocable ⚫ X.509 : norme proposée par l’ISO (et la plus répandue) 89 Anas Abou El Kalam  Demande de certificat (3) ⚫ Processus de certification : M. Bidon génère son bi-clé (publique/privé) Je, soussigné M. Documents demandés Bidon, demande par l’autorité de un certificat... certification : Clé publique fiche d’état civil... Avec sa clé Signature privée Autorité de certification Anas Abou El Kalam 90 Certificats : exemple ⚫ Structure du certificat X.509v3 Version du certificat Numéro de série du certificat Algo.de signature de l’AC Nom de l’AC ayant délivré le certificat Période de validité Nom du propriétaire du certificat Clé publique Algo. à utiliser avec la clé publique Identification de l’AC (opt) Identification du propriétaire (opt) Extensions (opt) Signature de l’AC Anas Abou El Kalam 91  Certificats : vérification ⚫ Vérification certificat Autorit éde certification ACBob : Empreinte 1 Hachage Pr é nom: Bob Nom: Dupond Email: dupond @entreprise. bob. fr Certificat valid Si oui Egalit é ? Cl épublique de Date é de :Duvalidit 01/10/93 au Bob Dupond : 01/10/94 A5:3F:F9: … E2 Cl épublique ’ autorit é de l Cl épublique: …E2 A5:3F:F9: de certification …. D é Empreinte 2 chiffrement Signature: 9B:C5:11:..:F5 Anas Abou El Kalam 92  Infrastructure de gestion de clés ⚫ IGC ou PKI (Public Key Infrastructure) recouvre les services mis en œuvre pour assurer la gestion des clés publiques – enregistrement des utilisateurs – vérification des attributs, – génération de certificats, – publication des certificats valides et révoqués, – identification et authentification des utilisateurs, – archivage des certificats, etc. ⚫ Composants fondamentaux d’une IGC ⚫ l’autorité de certification ; ⚫ l’autorité d’enregistrement, ⚫ un service de publication ou autorité de validation ; ⚫ l’annuaire qui contient les clés publiques, les certificats distribués, ainsi que les listes de certificats révoqués. Anas Abou El Kalam 93  Les acteurs de la certification ⚫ Le porteur – Il est référencé par le certificat – Il est le seul à posséder la clé privée associée ⚫ L’utilisateur – Il utilise le certificat Il vérifie que l’identité indiquée par le certificat est bien son interlocuteur Il vérifie que le certificat n’est pas révoqué (en consultant des listes de certificats révoqués - CRL) Il vérifie que l’utilisation qu’il veut faire du certificat est conforme à son usage (chiffrement, signature, …) authentifie et vérifie l’intégrité du certificat à l’aide de la clé publique de l’AC ⚫ L’autorité de certification (AC) ⚫ Elle émet le certificat ⚫ Elle a la confiance des utilisateur ⚫ diffuse la valeur de sa clé publique auprès des structures qu’elle connaît et des annuaires (e.g., LDAP « Light Directory Access Protocol ») ; ⚫ Elle peut optionnellement créer des clés Anas Abou El Kalam 94  Les acteurs de la certification ⚫L’autorité d’enregistrement (AE) ⚫ Elle dépend de l’AC ⚫ Elle s’occupe des aspects administratifs : ⚫ réception utilisateurs ⚫ Vérification de l’identité du demandeur ⚫ Vérification que le demandeur est habilité à recevoir les droits indiqués dans le certificat ⚫ s’assure que celui-ci possède bien un couple de clés privée-publique, ⚫ Obtention la clé publique ⚫ Transmission de la demande à l’AC ⚫ Traitement les demandes de révocation, suspension ou activitation d ’un certificat ⚫ L’AE est le point faible du système (affaire Microsoft/Verisign) Anas Abou El Kalam 95  Les acteurs de la certification ⚫ En janvier 2001, Verisign a délivré deux certificats à la société Microsoft … mais le porteur du certificat n’était pas affilié à Microsoft http://www.amug.org/~glguerin/opinion/revocati on.html ⚫ Verisign, suite à un audit de sécurité (6 semaines après), annonce que les deux certificats sont révoqués ⚫ Microsoft publie un patch pour ne plus accepter ces certificats Anas Abou El Kalam 96  Les acteurs de la certification ⚫ Le répertoire (e.g., LDAP) – Il contient les certificats et est consultable par le public ⚫ Des acteurs annexes peuvent exister – L’autorité d’approbation des politiques : elle spécifie les règles selon lesquelles l’AC est autorisée à délivrer des certificats – L’autorité d’horodatage : elle délivre des marques de temps qui sont signées – Autorité d’attributs : elle délivre des « sous-certificats » temporaires (comme par exemple des délégation de signature) – Service de validation : il valide des certificats déjà existants pour les utilisateurs de ces certificats – Service de séquestre et de recouvrement des clés : il stocke la clé privée associée au certificat et peut donc répondre en cas de perte de cette clé par le porteur du certificat Anas Abou El Kalam 97  Les acteurs de la certification Infrastructure de confiance Autorité de certification Création Demande de création Consultation, modification Autorité d ’enregistrement Demande de Répertoire création, suspension, révocation ou réactivation Consultation Porteur Utilisateur Echange sécurisé Anas Abou El Kalam 98  Les étapes de la certification ⚫ La création du certification – La création passe par les étapes suivantes : Le porteur fait une demande à l’autorité d’enregistrement (AE) l’AE authentifie et vérifie le bien fondé de la demande du porteur – Vérification éventuelle de la possession de la clé privée – Le « sérieux » de l’authentification indique le degré de confiance à placer dans le certificat [on peut le voir dans l’autre sens également] l’AE transmet la demande à l’AC l’AC génère le certificat – Une stratégie de nommage évitant les doublons doit être utilisée – Si il y a stockage (service de séquestre) de la clé privée, on peut utiliser, par ex., des cartes à puce Le certificat est publié – La publication d ’un certificat de signature n’est pas forcément utile (car le certificat correspondant est toujours joint avec la signature) – On utilise des mécanismes d ’annuaire (ex: LDAP, X.500) Le certificat est transmis à l’AE par l’AC Le certificat est délivré au porteur Anas Abou El Kalam 99  Les étapes de la certification ⚫ L’utilisation du certificat – L’étape la plus importante dans l’utilisation du certificat est sa validation Vérification de l’intégrité du certificat – Chaque certificat est signé par l’AC – Chaque AC possède donc un certificat appelé certificat racine et qui est « bien connu » » Il faut vérifier le certificat racine également (peut impliquer n étapes si le certificat racine appartient à une AC fililale) Vérification de la validité du certificat – Cela implique de vérifier que le certificat n’a pas expiré ou qu’il n’a pas été révoqué – On peut faire appel à une service de validation pour simplifier le travail Vérification de l’adéquation d’usage du certificat – Note : tous les logiciels ne mettent pas en œuvre l’entièreté de ces étapes !!! Anas Abou El Kalam 100  Les étapes de la certification ⚫ La révocation du certificat – Un certificat est révoqué car : Il a expiré Les clés secrètes ont été perdues ou compromises Le porteur à fait un usage illégal du certificat Il est non valide – Chaque AC publie périodiquement une liste des certificats révoqués (CRL) – Cette liste pouvant être volumineuse, on procède En publiant des delta (modifications incrémentales) En découpant la CRL en partition. Chaque certificat contient un pointeur vers la partition où il devrait se trouver Anas Abou El Kalam 101  Les étapes de la certification ⚫ La révocation du certificat – La CRL peut être obtenue, A partir d’un URL accessible publiquement (et bien connue) Ex : http://crl.verisign.com/Class3SoftwarePublishers.crl Manuellement (en téléchargeant une liste des certificats révoqués) A partir d’une URL contenue dans le certificat racine (celui de l’AC) A partir d’une URL contenue dans le certificat – La polémique de l’affaire Microsoft/Verisign porte sur l’absence d’une infrastructure de révocation Anas Abou El Kalam 102  Chaîne de certification (5) Autorité racine ⚫ La confiance est Clés déplacée vers l’autorité de certification ⚫ Des autorités peuvent en certifier d’autres : on Autorité A aboutit à une chaîne de certification – à la racine, on a forcément un certificat “racine” auto-certifié… Clés – si on ne fait pas confiance à cette autorité racine, toute la chaîne de certification ne sert à rien Émis Clés – généralement, il s’agit d’une par A organisation très réputée Anas Abou El Kalam 103  Conclusion Intégrité Authenticité Non répudiation Empreinte digitale MAC Voir note 1 Signature Voir note 2 digitale Signature Voir note 3 digitale + certificat Note 1. Impossible d’identifier précisément l’émetteur si la clé secrète est partagée entre plusieurs personnes. Note 2. On garantit que l’émetteur possède la clé privée, mais A retenir pas l’identité effective de l’émetteur. Note 3. Ne pas oublier de vérifier la validité (date, répudiation…) du certificat. Anas Abou El Kalam 104