Eléments de
Cryptoanalyse
Roumen Andonov, Nadia Bennani,
Didier Donsez
Université de Valenciennes
Institut des Sciences et Techniques de Valenciennes
e-mail : {andonov,nbennani,donsez}@[Link]
1
Sommaire
n Rappel sur la Cryptographie
n Chiffrage à clé symétrique (clé secrète) - DES
n Chiffrage à clé asymétrique (clé publique) - RSA
n Eléments de cryptoanalyse
• Fonction de hachage à sens unique
• Attaque d ’un chiffrage
• longueur des clés secrètes
• longueur des clés publiques
n Rudiments mathématiques - théorie de la complexité
, 1999
Eléments de Cryptoanalyse, 2
le Chiffrage (Cryptage)
n algorithme public
• connu de tous
• le secret est maintenue
tant que la clé n’est pas connu
• qui peut être propriétaire : royalties
n chiffrage à clé symétrique
• (clé secrète)
n chiffrage à clé asymétrique
• (clé publique / clé privée)
, 1999
Eléments de Cryptoanalyse, 3
le Chiffrage à clé symétrique
(clé secrète)
n 1 seule clé pour chiffrer et déchiffer
K K
opération overlord E #~»{tyt|`@à^`\^= D opération overlord
Le Gentil Le Méchant L’ami du Gentil
Le Truand Les Gentils Un Comparse du Truant
n DES (Data Encryption Standard - IBM 1977), IDEA
, 1999
Eléments de Cryptoanalyse, 4
DES
(Decryption Encryption Standard)
n Principe
– Succession de Rouleaux de Permutation
• Machine ENIGMA
n DES
• 56 bits
• Triple-DES (3*56 bits)
n Limite de DES
• DES56 « cassable »
• Juillet 98 : 56 heures par une machine à 250 000 $
[Link]
• Appel d ’offre du NIST pour un remplacant
• AES (Advanced Encryption Standard)
, 1999
Eléments de Cryptoanalyse, 5
le Chiffrage à clé asymétrique
(clé publique / clé privée)
n 2 clés K1 et K2
• si chiffrage par K1, déchiffrage par K2
• si chiffrage par K2, déchiffrage par K1
Remarque : on ne peut pas trouver une clé à partir de l’autre
K1 K2
opération overlord E #~»{tyt|`@à^`\^= D opération overlord
Le Gentil Le Méchant L’ami du Gentil
Le Truand Les Gentils Un Comparse du Truant
n RSA (Rivest Shamir Adelman)
, 1999
Eléments de Cryptoanalyse, 6
RSA (Rivest Shamir Adelman)
Génération des Clés de B
Privé
B sélectionne 2 nb. premiers p et q •p, q nombres premiers
B tire la clé publique Kpub •Kpriv une clé secrète
tq pgcd(Kpub, (p-1)(q-1))=1 Public
B calcule la clé privée Kpriv •N =p*q
Kpriv * Kpub = 1 (mod((p-1)(q-1) ) •Kpub une clé publique
(par l ’alg. d’Euclide étendu )
Chiffrage Déchiffrage
M C = MKpub (mod N) C M = CKpriv (mod N) M
, 1999
Eléments de Cryptoanalyse, 7
RSA - Exemple
Génération des Clés de B
B sélectionne p=47 et q=71, alors N=pq=3337
(p-1)(q-1)=46*70=3220
B tire aléatoirement la clé publique Kpub=79
B calcule la clé privée Kpriv
Kpriv =79-1 (mod(3220) => Kpriv=1019
B publie n et Kpub, garde Kpriv secret et jette p et q
Chiffrage Déchiffrage
688 1570 M=15701019 (mod 3337) 688
C = 68879 (mod 3337)
, 1999
Eléments de Cryptoanalyse, 8
Chiffrements par bloc et en continu
n Chiffrement par bloc
• Principe:
• le message est découpé en blocs (de 1,8,32 ou 64 bits)
• chaque bloc est chiffré indépendamment
de la valeur des autres blocs
• Algo : DES, RSA, IDEA, RC2
n Chiffrement en continu
• Principe:
• le message est un flot de texte ou de données binaires
découpé en blocs (de 1,8,32 ou 64 bits)
• chaque bloc est chiffré en fonction de la valeur de la clé
mais aussi de la valeur du bloc précédent (et/ou suivant)
• Algo : RC4, SEAL, WAKE
, 1999
Eléments de Cryptoanalyse, 9
La CryptoAnalyse
n Attaque d’un chiffrage
• l’attaquant cherche à connaître
• le texte en clair
• la clé « secrète ou privée » utilisée
• à partir d’un texte encodé : très difficile
• Paul Leyland et 1600 machines relèvent le Défi [1994]
RSA : 129-digits (430 bits) -> 5000 Mips - Year
« THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE »
• à partir du texte clair et du texte encodé : faisable
Attention aux en-têtes de formulaires !!!!
, 1999
Eléments de Cryptoanalyse, 10
Validité d’un Chiffrage
• dépendant de la nature de la donnée à protéger
transaction bancaire
» quelques minutes
secret d’état, signature de contrat à long terme
» 50 ans
• dimension de la clé
plus la clé est grande, elle est difficile à casser
n Réponse : augmentation de la dimension de la clé
• Même algorithme mais agrandi (TripleDES)
• Surchiffrement (avec 2 ou 3 clés) (xDES)
• pas de changement du programme ou du hardware
• Nouveau algorithmes
, 1999
Eléments de Cryptoanalyse, 11
Génération des Clés
n DES
• Clé Secrête : un nombre quelconque
• hormis certains 0, …
• tirage aléatoire sécurisé
• surtout non reproductible
(car il permettrait aux crypto-analyses le limite de domaine de recherche
des clés)
n RSA
• 2 nombres premiers p et q très grands
, 1999
Eléments de Cryptoanalyse, 12
Système Cryptographie
n Fonction
• Authentification
• Confidentialité
• Non Répudiation
n Outils à assembler
• Algorithme de Chiffrage à Clé Symétrique
• Algorithme de Chiffrage à Clés Asymétriques
• Fonction de Hachage
• Générateur de Nombres Aléatoires
• Générateur de Nombres Premiers
• ...
, 1999
Eléments de Cryptoanalyse, 13
Théorie de la complexité
n La complexité est mesurée par 2 paramètres
• T: complexité en temps
• S: complexité en espace (mémoire)
n T et S sont exprimés en fonction de n (taille du pb.)
n Classes d ’équivalence
• Polynomiaux : (linéaire, quadratique, cubique, etc)
• Exponentiels : O(t f(n)) où t est const et f(n) est fonction polynomiale de n
• Super-polynomiaux : O(t f(n) ) où f(n) est plus qu’une const. mais moins
que linéaire
, 1999
Eléments de Cryptoanalyse, 14
Complexité des problèmes
n Pbs. Solubles - qui peuvent être résolus avec des algs.
polynomiaux
n Pbs. Non-solubles - qui ne peuvent pas être résolus en
temps polynomial (pbs. difficiles)
n Pbs. indécidables - impossible de concevoir un algorithme
pour la résolution du problème
, 1999
Eléments de Cryptoanalyse, 15
Classes de complexité
n P : pbs. qui peuvent être résolus en temps polynomial
n NP:pbs. qui peuvent être résolus en temps polynomial sur
une machine de Turing non déterministe
n NP-complets:pbs aussi difficile que tout autre pb dans NP
n PSPACE: pbs. qui peuvent être résolus en espace
polynomial mais pas nécessairement en temps polynomial
n PSPACE-complets:
• si n ’importe lequel d ’entre eux est dans NP => PSAPCE=NP;
• si l ’un d ’entre eux est dans P =>PSPACE=P
n EXPTIME: pbs. solubles en temps exponential
n EXPTIME-complets: pbs. qui nepeuvent pas être résolus
en temps déterministe polynomial (P not = EXPTIME)
, 1999
Eléments de Cryptoanalyse, 16
Fonction de hachage à sens unique
n h=H(M) où
• M est de longueur arbitraire
• la valeur de hachage h est de longueur fixe
n + les caractéristiques suivantes:
• Etant donné M, il est facile de calculer h;
• Etant donné h, il est difficile de calculer M;
• Etant donné M, il est difficile de trouver un autre message M ’, tq H(M ’)=H (M);
n + résistance à la collision
• Il est difficile de trouver 2 messages aléatoires M et M ’ tq H(M ’)=H (M);
n Examples: il est facile de multiplier deux grands nombres premiers,
mais il est difficile de factoriser leur produit
• multiplication de un l-bits par un k-bits se fait en O(kl);
• factorisation de nombre n se fait en e(1+0(1))(ln n)1/2 (ln(ln n))2/3;
, 1999
Eléments de Cryptoanalyse, 17
Force et Faiblesse
d ’un Système Cryptographie
n Force d ’un système cryptographique
• = Force du composant le plus faible
B. Schneier, « Cryptographic Design Vulnerabilities », Computer, 09/98
[Link]
n Exemple
• Syst. = Protocole d ’échange sécurisé
Protocole d ’échange sécurisé
RSA (authentification)
Faiblesses
Point d ’Attaque
•espace des clés limités
•la 1ère clé détermine
Générateur Aléatoire (5 clés sessions)
• les 4 suivantes
xDES (session chiffrée à x=5)
, 1999
Eléments de Cryptoanalyse, 18
Longueur des clés secrètes
n La sécurité d ’un cryptosystème à clé secrète doit résider dans la clé et
non pas dans les détails de l ’algorithme !
n Hypothèse: la solidité de l ’alg. est parfaite (l ’attaque exhaustive est le
seul moyen possible de casser le cryptosystème). On connaît un bout
de texte chiffré et du texte en clair correspondant.
n Estimation du temps et du coût d ’une attaque exhaustive de DES
• machines dédiées
• 1977 la machine de Diffie et Hellman
106 proc. chaque teste 106 clés/sec. => 2 64 clés en 214 jours
• 1993 la machine de Wiener (puces et cartes spécialisées)
coût 106 $, 2 56 clés en 3h30 en moyen
• généralisation de ces résultats sur tab. 7.1
• Rappel de loi de Moore: la puissance de calcul double tous le 18 mois (le coût
est divisé par 10 tous les 5 ans)
• méthodes logicielles : 1000 fois plus lentes mais « gratuites »
• Le Peer-to-Peer
, 1999
• 10000 PC sur le Web se partage l’espace de recherche
Eléments de Cryptoanalyse, 19
• Une applet dans la page de garde d’un site hacké et visité comme Google !
Longueur des clés publiques
n La cryptographie à clé publique est basée sur utilisation des fonctions
à sens unique
• factorisation des grands nombres qui sont le produit de deux grands nombres
premiers.
• Problème logarithmique discret
n Les records de factorisation sur tab 7.3 .
• Attention: Factoriser 512 bits est dans le domaine de possible!!!
n Mesure utilisée : mips-an 3*1013 instr. (106 instr./sec. pendant 1 an)
• ex. Pentium 100 MHz est de 50 mips
n Algs. utilisés: le crible quadratique, le crible général sur corps
numérique, le crible spécial sur corps numérique
n Récommandations:
• un module de 1024 bits devrait être suffisant jusqu’au 2005
• pour les 20 prochaines années 1024 bits seront insuffisant
• La longueur doit être adaptée au niveau de sécurité de votre clé. Tab 7.6
, 1999
Eléments de Cryptoanalyse, 20
Bibliographie
Cryptographie Appliquée, Bruce Schneier (Wiley), 1996,
ISBN 0-471-59756-2 (ISBN 2-84180-036-9 en VF)
, 1999
Eléments de Cryptoanalyse, 21
