Hachage
Signature utilisable seulement pour des petis messages.
Solution naïve : découper le message à signer en blocs (de
160 bits) et signer chaque bloc.
Plusieurs problèmes :
Hachage et certification • taille de la signature
• lenteur des algos de signatures
Contenu Solution par le hachage
Utiliser une fonction de hachage cryptographique, rapide à
calculer, qui transforme un message de longueur arbitraire en
une empreinte numérique de taille fixe. On signe l’empreinte :
message m longueur arbitraire
Hachage #
empreinte z = h(m) 160 bits
#
signature s = sigsk (z) 320 bits
Certification
Principe : Bob signe m :
• il calcule l’empreinte z = h(m)
• signe en s = sigsk (z) et transmet (m, s).
N’importe qui vérifie (m, s) en recalculant l’empreinte ẑ = h(m)
puis en utilisant le procédé de vérification de verpk (ẑ, s).
Conditions à satisfaire Q Q
On approche ki=11 1 ni par ki=11 e n car
2
i
x3
e x = 1 x + x2! 3! · · · , donc e
x ⇡1 x si x est petit (ce
Une fonction de hachage h calcule i i
qui est notre cas). Donc 1 n ⇡e n .
z = h(m)
Q Q i 1 Pk 1 (k 1)k
pour m message de taille arbitraire et z, empreinte de taille fixe. q = ki=11 1 ni ⇡ ki=11 e n =e n i=1 i
=e 2n
On veut que h soit être à sens unique, i.e. ln q ⇡ (k 2n1)k
2n ln( q1 ) ⇡ k 2
• h(m) doit être facile à calculer à partir de m q
• z doit être difficile à inverser. 2n ln( 1 1 p ) ⇡ k
Collision de h : couple de mots distincts (x, x 0 ) tq h(x) = h(x 0 ). p
p = 1/2, proba d’avoir au moins une collision pour k ⇡ 2n ln 2
h est
• faiblement résistante aux collisions si, pour un x donné, il Exemple : n = 365, k = 23 personnes ; on a plus d’une chance
est difficile de calculer une collision. sur deux que deux personnes aient le même jour anniversaire.
• fortement résistante aux collisions s’il est difficile de Utilité : trouver la taille n de l’image parpla fonction de hachage
calculer la moindre collision (x, x 0 ). pour éviter les collisions. On a k en O( n).
Paradoxe des anniversaires Attaque basée sur le paradoxe
Donnée : B = (b1 , . . . , bk ) 2 {1, 2, . . . , n}k . Calculer et trier autant de couples (x, h(x)) que possible. Détecter
Problème : proba p d’avoir 2 éléments de B identiques ? une (ou plusieurs) collisions.
On prend k messages mi tirés aléatoirement avec i 2 [1, k ] et Il y a 2n valeurs qui correspondent aux «jours anniversaires» ; .
on étudie la proba pour que deux mi aient la même image. On suppose que les images par h suivent une distribution uniforme.
zi = h(mi ). En considérant k entrées on a plus d’une chance sur deux d’avoir
n
Complémentaire= Proba que les zi soient tous différents : une collision avec k ⇡ 2 2 . En passant au logarithme,
k 1 kY1 ✓ ◆ ✓ ◆ ✓ ◆ n 50 100 150 200
1 Y i 1 k 1 log2 k 25, 24 50, 24 75, 24 100, 24
1 p=q= (n i) = 1 =1 1 ··· 1
nk n n n
i=0 i=1
Ainsi, en calculant un peu plus que 2n/2 images par h, on trouve une
collision avec une probabilité > 1/2.
Où 1 est la proba de tirer z1 , (1 n1 ) celle de tirer z2 6= z1 (car il
Pour h fortement résistante, on choisit n pour que le calcul de 2n/2
y a une chance sur n que z1 = z2 ),. . . , (1 ni ) celle de tirer
images par h soit irréaliste. A ce jour, n 160.
zi 6= z1 , . . . , zi 1 .
Hachage par compression Fonction de compression
A partir de ek : {0, 1}n ⇥ {0, 1}n ! {0, 1}n
on construit g, fonction de compression
Dans MD5, SHA, découper m en n blocs de longueur fixe puis :
g : {0, 1}n ⇥ {0, 1}n ! {0, 1}n pour n 2 N
message
dont la taille de l’image par la fonction de hachage est n.
bloc 1 bloc 2 bloc n La fonction de chiffrement est utilisée soit directement si elle
est résistante aux collisions soit en la «perturbant» :
valeur valeur
initiale MD5 MD5 MD5 hachée
g(k , x) = ek (x) x
g(k , x) = ek (x) x k
g(k , x) = ek (x k ) x
g(k , x) = ek (x k ) x k
Construire une fonction de hachage Fonction de hachage
Merkle : construction de fonction de hachage à partir d’une
fonction de compression g : {0, 1}m ! {0, 1}n .
Partir de ek , chiffre sym., construire une fonction de Soit r = m n > 1. On veut construire h : {0, 1}? ! {0, 1}n .
compression Soit x 2 {0, 1}? et ` sa longueur en binaire.
• compléter x avec des "0" : u = 0i x t.q. |u| ⌘ 0 mod r
m n
g : {0, 1} ! {0, 1} pour m, n 2 N, m>n compléter ` avec des "0" : y = 0j ` t.q. |y | ⌘ 0 mod r
• 1
On utilise g pour construire une fonction de hachage : • découper y en blocs de r 1 bits et ajouter un "1" au
début de chacun des blocs pour former le mot v
h : {0, 1}? ! {0, 1}n pour n 2 N • construire w = u0r v composé de t blocs de longueur r .
Exemple : r = 4, x = 11101, ` = 101. u = 0001 1101, v = 1101.
Proposition
h est résistante aux collisions si g l’est aussi. w = 0001 1101 0000 1101 = w1 w2 w3 w4 (t = 4)
H définie ind. : H0 = 0n et Hi = g(Hi 1 wi ), 1i t
h(x) = Ht
Fonctions de hachage efficaces Plan de l’exposé
Les fonctions de hachages utilisées en pratique sont
construites comme précédemment. Les plus courantes : Hachage
nom bits tours⇥étapes vitesse relative
MD5 128 4⇥16 1
SHA 160 4⇥20 0,28 Certification
Application à DSA Certificat de clé publique
Un certificat de clé publique de B garantit la relation entre IdB
et pkB , signée par un tiers de confiance, Ivan.
Utilité : déjouer l’attaque de l’homme du milieu
Un certificat de la clé publique de B contient
Digital Signature Algorithm : standard de signature qui combine
une fonction de hachage (SHA) et DSS, qui améliore le schéma • sa clé publique
de signature d’El Gamal (en travaillant dans un sous-groupe). • des infos concernant B (nom, e-mail. . . )
• la signature d’un tiers de confiance Ivan
Ivan signe à la fois
• la clé
• les infos concernant B
Ivan certifie la relation entre la clé publique et l’identité de B.
Réalisation «asymétrique» Certification & Vérification
IdS,PKS hachage SignAC SignAC(h(IdS,PKS))
h
Certification réalisée au moyen d’un schéma de signature.
IdS,PKS
Celui-ci consiste en [1] : AC Clé de S
IdS,PKS certifiée par AC SignAC(h(IdS,PKS))
• une signature après hachage cryptographique
• une opération de vérification correspondant à la signature.
Exemple : si le contenu du message est celui décrit par la
norme X509, on fournit de cette manière un identificateur IdS,PKS hachage h(IdS,PKS)
h
numérique ou Digital ID, sorte de carte d’identité numérique. AC Clé de S
IdS,PKS certifiée par AC
Algorithme public
SignAC(h(IdS,PKS)) VerAC de vérification de AC
oui/non
Certificat (X.509) Paradoxe
Associe une clé publique à l’identité d’un sujet ; comprend :
• Subject : Nom Distingué, Clé publique
• Issuer : Nom Distingué, Signature
• Period of Validity : date de début, date de fin Comment connaît-on l’algorithme de vérification
de l’autorité de certification ?
• Administrative Information : version, numéro de série
Quel est le modèle de confiance ?
• Extended Information :
L’information « Nom Distingué » comprend : • confiance directe
• Common Name : nom à certifier Bruno Martin • confiance hiérarchique (le plus utilisé)
• Organization| Company : contexte U. Côte d’Azur • toile de confiance (web of trust)
• Organizational Unit : contexte spécifique Deptinfo
• City/Locality : ville Sophia Antipolis
• State/Province : pour US PACA
• Country : code pays fr
Chaîne de certification Rupture dans la chaîne
ACr
IdACr,KACr
AC peut aussi fournir un
certificat à une autre AC. ACr
IdB,cléB
ACr
IdAC1,KAC1
ACr
IdC,cléC
Alice peut ainsi remonter
une chaîne de certification
AC1
jusqu’à trouver une AC en IdAC,KAC
qui elle a confiance.
AC
IdS,PKS
Mauvaise AC : attaques possibles (2011 : DigiNotar)
Création d’une AC «racine» Toile de confiance
Tentative de concilier les modes directs et hiérarchiques.
La confiance est accordée par l’utilisateur selon le principe que
Problème des chaînes de certification : il faut une AC «racine». plus on dispose d’information, meilleure est la confiance. On
Celle-ci ne peut se faire certifier. Dans ce cas, le certificat est accorde sa confiance directement ou au moyen d’une chaîne
auto-signé par l’AC racine. L’entité qui délivre le certificat est de certification qui remonte jusqu’à un tiers connu selon le
identique au sujet certifié. La confiance réside dans une large principe :
distribution de la clé publique de l’AC.
• Jean signe l’identifiant Paul dans le certificat de Paul ;
Les systèmes d’exploitation sont configurés pour faire
• lorsque Marie veut vérifier que Jean a signé Paul, elle
confiance à certaines AC par défaut, comme CertiSign ou utilise la clé publique de Jean pour vérifier sa signature
VeriSign utilisés par des autorités intermédiaires comme dans le certificat de Paul ;
Let’s Encrypt.
Ces sociétés proposent des techniques pour demander des • Marie fait confiance à Jean. Elle reçoit un message signé
de Paul. Elle vérifie la validité de la signature de Paul (clé
certificats, ont des procédures de vérification de l’information,
récupérée depuis un serveur de clés). Comme elle fait
délivrent et gèrent des certificats.
pleinement confiance à Jean, elle valide de plus le fait que
c’est bien Paul qui a signé ce message.
C’est le système utilisé par OpenPGP, GnuPG ou PGP.
Bibliographie
RSA Laboratories.
PKCS ]1 v2.0, RSA cryptography standard.
Technical report, RSA Data Security, 1998.
