Algorithmes de hachage

„ On constate des similitudes dans l'évolution des

Algorithmes de hachage fonctions de hachage et les chiffrements
symétriques
‰ Puissance croissante des attaques par force brute
‰ Ce qui pousse à l'évolution dans les algorithmes
‰ du DES à l’AES dans des chiffrements symétriques
‰ de MD4 et de MD5 à Sha - 1 et à Ripemd - 160 dans des
algorithmes de hachage
„ Ces algorithmes ont tendance à employer la même
structure itérative (Feistel) que les chiffrements
symétriques

1 Cryptographie - 2
 MD5 - présentation
„ conçu par Ronald Rivest (le R dans RSA)
MD5 „ Le dernier d’une série (MD2, MD4)
„ produit un condensé de 128 bits
„ était jusqu’à récemment l'algorithme de hachage le
plus largement répandu
‰ La cryptanalyse et l’attaque par force brute l’on affaibli

„ Spécification Internet : RFC 1321

3 Cryptographie - 4
MD5 - Vue d'ensemble MD5 – Vue d’ensemble
1. Complétion : 4. Calcul itératif :
‰ ajout de padding si nécessaire afin que le message ait ‰ traiter le message par blocs de 512 bits
une longueur de 448 mod 512 ‰ 4 rondes de 16 opérations fonction du bloc (512), des
buffers et de fonctions primitives
2. Ajout de la longueur :
‰ Le résultat (4*32 bits) est utilisé pour l’initialisation des
‰ on ajoute la longueur réelle du message (sur 64 bits)
registres suivants
après les 448 bits ! 512 bits

3. Initialisation : 5. Le résultat final est obtenu en additionnant

A,B,C,D
‰ initialiser 4 buffers de 32 bits chacun (A,B,C,D)

Hachage et signatures - 5 Hachage et signatures - 6

MD5 – Vue d’ensemble MD5 - Rondes

Hachage et signatures - 7 Hachage et signatures - 8

MD5 - fonction de compression MD5 - Algorithme
„ chaque ronde a 16 itérations de la forme : „ CV0 = IV
‰ a = b+((a+g(b, c, d)+X[k]+T[i])<<<s) „ CVq+1=∑32[CVq, RFI (Yq,RFH(Yq, RFG(Yq, RFF(Yq, CVq))))]
‰ a, b, c, d se rapportent aux 4 buffers, mais sont utilisés „ MD = CVL-1
selon des permutations variables
„ Note : cela ne met à jour qu’un seul des buffers (de 32 bits)
„ Où :
„ Après 16 étapes, chaque buffer a été mis à jour 4 fois ‰ IV : valeur initiale des registres ABCD
‰ Yq : le qe bloc de 512 bits du message
‰ g(b, c, d) est une fonction non
- linéaire différente dans
‰ L : le nombre de blocs de 512 bits dans le message
chaque ronde (F,G, H, I)
‰ CVq : variable chainée obtenue par la manipulation du qe bloc
‰ T[i ] est une valeur constante dérivée de sin
‰ RFx : fonction primitive dépendante de la ronde en cours
‰ <<< s : décalage circulaire à gauche (pour chaque buffer ‰ MD : résultat final
séparément) de s bits ‰ ∑32 : addition modulo 232

Hachage et signatures - 9 Hachage et signatures - 10

MD5 - Opération élémentaire MD5 - Calculs des valeurs
„ Valeurs initiales des registres : „ Valeurs pour X[k]
‰ A : 01 23 45 67 ‰ i = itération, k=
‰ B : 89 AB CD EF ‰ ρ1(i) = i
‰ C : FE DC BA 98 ‰ ρ2(i) = (1+5i) mod 16
‰ D : 76 54 32 10 ‰ ρ3(i) = (5+3i) mod 16
„ Primitives : ‰ ρ4(i) = 7i mod 16
‰ F(b,c,d) = (b ∧ c) ∨ (¬ b ∧ d)
‰ G(b,c,d) = (b ∧ d) ∨ (c ∧ ¬ d)
‰ H(b,c,d) = b ⊕ c ⊕ d
‰ I(b,c,d) = c ⊕ (b ∨ ¬ d)

Hachage et signatures - 12

Hachage et signatures - 11
MD4 - comparaison Force du MD5
„ précurseur du MD5 „ Le condensé MD5 dépend de tous les bits du
message → avalanche
„ produit également des condensés de 128 bits
„ Rivest prétend que La sécurité est aussi bonne
„ a 3 rondes de 16 étapes contre 4 dans MD5 que possible
„ buts de conception : „ Les attaques connues sont :
‰ Résistant aux collisions (difficile de trouver des collisions) ‰ Berson 92, Den Boer et Bosselaers 93, Dobbertin 96
‰ sécurité directe (aucune dépendance envers des ‰ Présence de collision, attaque sur une ronde
problèmes math.) ‰ Pas d’attaque concrète mais de plus en plus de
‰ rapide, simple, compact faiblesses trouvée

‰ Favorise les systèmes « little endian » (exple : les PCs) „ Conclusion : MD5 sera bientôt vulnérable

Hachage et signatures - 13 Hachage et signatures - 14

 Le Secure Hash Algorithm (SHA-1)
„ SHA a été conçu par NIST et NSA en 1993, révisé 1995
SHA-1 (Secure hash algorithm) „ Standard US pour usage avec le schéma de signature DSA
‰ norme : FIPS 180-1 (1995), Internet RFC3174
‰ l'algorithme est SHA, la norme est SHS (secure hash standard)

„ produit des valeurs condensées de 160 bits

„ actuellement l'algorithme généralement préféré pour le
hachage
„ basé sur le design du MD4 avec quelques différences

15 Hachage et signatures - 16
SHA - Vue d'ensemble
1. Complétion :
‰ le message condensé doit être de longueur 448 mod 512
2. Ajout de la longueur
‰ une valeur codée sur 64 bits
3. Initialisation
‰ Initialiser 5 buffers de 32 bits (= 160 bits) – A,B,C,D,E
4. Calcul itératif :
‰ 4 rondes de 20 itérations chacune
‰ Les rondes ont une structure similaire mais utilisent des fonction
primitives différentes (f1,f2,f3,f4)
‰ Utilisation de constante additives Kt (0 · t · 79)
‰ Le résultat est utilisé pour initialiser les buffers du bloc suivant.
5. Le condensé final constitue le condensé attendu

Hachage et signatures - 17 Hachage et signatures - 18

SHA - Fonction de compression SHA - Fonction de compression
„ chaque ronde a 20 étapes qui manipulent ainsi les 5
registres :
„ (A,B,C,D,E) ← (E + f(t,B,C,D) + (A<<5) + Wt + Kt), A,
(B<<30), C, D)
„ Où :
‰ A,B,C,D,E se rapportent aux 5 registres
‰ t est le numéro de l'étape
‰ f(t, B, C, D) est une fonction primitive non-linéaire de la ronde pour
l’étape t
‰ Wt est dérivé du bloc de message(32 bits)
‰ Kt est une valeur additive

Hachage et signatures - 19 Hachage et signatures - 20

SHA - Fonction de compression SHA - Calcul de Wt
„ Fonctions primitives
‰ Travaille sur 32 bits et fournit un résultat sur 32 bits
‰ 0 · t · 19 f1=f(t,B,C,D) (B∧ C)∨(¬ B ∧ D)
‰ 20 · t · 39 f2=f(t,B,C,D) B ⊕ C ⊕ D
‰ 40 · t · 59 f3=f(t,B,C,D) (B∧ C)∨(B∧ D)∨(C∧ D)
‰ 60 · t · 79 f4=f(t,B,C,D) B ⊕ C ⊕ D

„ Wt
‰ 0 · t · 15 : les 16 premières valeurs du bloc
‰ 16 · t : Wt = ((Wt-16 ⊕ Wt-14 ⊕ Wt-8 ⊕ Wt-3)<<<1)

Hachage et signatures - 21 Hachage et signatures - 22

SHA - Valeurs initiales SHA-1 vs MD5
„ Registre : „ l'attaque par force brute est plus difficile (160
‰ A = 67452301 contre 128 bits pour MD5)
‰ B = efcdab89
‰ C = 98badcfe „ non vulnérable à toutes les attaques connues
‰ D = 10325476 (comparées à MD4/5)
‰ E = c3d2e1f0
„ un peu plus lent que MD5 (80 contre 64 étapes)
„ Kt
‰ 0· t ·19 – Kt=5a827999 „ conçu comme simple et compact
‰ 20· t · 39 – Kt=6ed9eba1
„ optimisé pour CPU's big-endian (contre MD5 qui
‰ 40· t · 59 – Kt=8f1bbcdc
est optimisé pour CPU's little-endian)
‰ 60· t · 79 – Kt=ca62c1d6

Hachage et signatures - 23 Hachage et signatures - 24

SHA-1 vs MD5 Revised Secure Hash Standard
„ Le NIST a publié une révision : FIPS 180-2
„ Ajout de 3 algorithmes additionnels de hachage
„ Sha-256, Sha-384, Sha-512
„ Conçu pour la compatibilité avec la sécurité accrue
a fourni par le chiffrement AES
„ La structure et le détail est semblable à Sha-1
„ Par conséquent l'analyse devrait être semblable

Hachage et signatures - 25 Hachage et signatures - 26

Comparaison des propriétés de SHA

Algorithmes pour les MACs

1. Toutes les tailles sont mesurées en bits.

2. La sécurité se rapporte au fait qu’une attaque d'anniversaire sur un
condensé de message de taille n produit une collision avec un
facteur d'approximativement 2n/2.

Hachage et signatures - 27 28
Fonction de hachage pour le calcul de MAC Cahier des charges
„ Désire de créer des MACs à partir de fonction de „ Utiliser , sans modifications, des fonctions de
hachage plutot que de chiffrement par bloc hachage existantes
‰ Fonctions de hachage généralement plus rapide
„ Permettre un remplacement aisé de la fonction de
‰ Non limitées par les contrôles à l’exportation hachage au cas où des fonctions plus rapides ou
„ Hachage incluant une clef avec le message plus sures seraient trouvées ou exigées

„ Proposition originale : „ Préserver les performances initiales de la fonction

‰ HashSur = Hash(clé|Message)
de hachage
‰ Quelques faiblesses ont été trouvées dans ce schéma „ Employer et manipuler les clefs de manière simple
„ A mené au développement de HMAC

Hachage et signatures - 29 Hachage et signatures - 30

Correspondance avec ce CCH Principe de l’algorithme
„ HMAC traites les fonctions de hachage comme des „ Soient :
‘black box’. ‰ H : la fonction de hachage
‰ La fonction de hachage devient un module ‰ IV : un vecteur d’initialisation
‰ Pas de modification à apporter à la fonction ‰ M : le message (+ padding)
‰ Yi : ieme bloc de M
‰ L : le nombre de blocs de M
‰ b : le nombre de bits dans un bloc
‰ n : la longueur du condensé produit
‰ K : la clé
‰ K+ : la clé ‘paddée’ à une longueur b
‰ ipad : 0x36 (répété b/8 fois)- opad : 0x5C (répété b/8 fois)

Hachage et signatures - 31 Hachage et signatures - 32

Principe de l’algorithme
„ HMAC :
‰ HMACk (M) = H[(K+ ⊕ opad) || H[(K+ ⊕ ipad) || M]]
„ En bref :
1. Padding de la clé :
Ajout de 0 à gauche de K pour créer un flux de b bits (K+)
2. XOR de K+ et ipad pour produire Si (longueur b bits)
3. Ajout de M à Si
4. Application de H à ce flux
5. XOR de K+ et opad pour produire So (longueur b bits)
6. Ajoute du hash (etape 4) avec So
7. Application de H au résultat de l’étape 6

Hachage et signatures - 33 Hachage et signatures - 34

Optimisations
„ Possibilité de préprocessing :
‰ f(IV, (K+ ⊕ ipad))
‰ f(IV, (K+ ⊕ opad))
‰ f
„ fonction de compression utilisée pour hacher
„ Prend en argument une variable chaînée de n bits et un bloc de b
bits
„ Produit une variable chaînée de n bits
‰ Ces quantités ne sont calculée qu’à l’initialisation et
quand la clé change
‰ Ces quantités se substituent à IV dans la fonction de
hachage

Hachage et signatures - 35 Hachage et signatures - 36

Sécurité de HMAC
„ La sécurité de HMAC est directement liée à la
fonction de hachage sous-jacente Signatures digitales
„ Attaquer HMAC exige
‰ Soit une attaque de force brutale sur la clef utilisée (2n
essais)
‰ Soit une attaque d'anniversaire (2n/2mais puisque utilisé
avec une clé, on devrait observer un nombre très grand
de messages)
„ Choisir la fonction de hachage à utiliser en se
basant sur des contraintes de sécurité et de
vitesse

Hachage et signatures - 37 38
Signatures Digitale Propriétés des signatures digitales
„ On a regardé l'authentification de message „ Doit dépendre du message signé
‰ mais n'aborde pas les questions de manque de confiance „ Doit employer une information unique propre à l'expéditeur
‰ pour empêcher la contrefaçon et le démenti
„ Les signatures numériques permettent de :
„ Doit être relativement facile produire
‰ vérifier l'auteur, la date et l'heure de la signature
‰ authentifier le contenu de message „ Doit être relativement facile reconnaître et vérifier
‰ être vérifié par des tiers pour résoudre des conflits „ Doit être mathématiquement infaisable à forger
‰ avec de nouveau message pour une signature numérique existante
„ Par conséquent, elles incluent la fonction ‰ avec une signature numérique frauduleuse pour un message donné
d'authentification avec des possibilités
„ Doit être pratique à stocker
additionnelles

Hachage et signatures - 39 Hachage et signatures - 40

Signatures Digitales Directes Signatures digitales arbitrées
„ Implique uniquement l'expéditeur et le récepteur „ comporte l'utilisation d’un arbitre A
„ Suppose que le récepteur dispose de la clé publique de „ Il valide n'importe quel message signé
l'expéditeur „ Le date et l’envoie au destinataire

„ Signature numérique faite par l'expéditeur signant le „ exige un niveau approprié de confiance en l'arbitre
message entier ou le condensé avec sa clé privée
„ peut être mis en application avec des algorithmes
„ peut être chiffrée en utilisant la clé publique des récepteurs
symétriques ou à clés publiques
„ Il est important de signer d’abord et de chiffrer ensuite le
message et la signature „ l'arbitre peut ou ne peut pas voir le message
„ La sécurité dépend de la clé privée de l'expéditeur

Hachage et signatures - 41 Hachage et signatures - 42

Techniques

Algorithmes de signatures

Hachage et signatures - 43 44
 El Gamal : principe El Gamal : exemple
„ Clé publique : „ p = 11, g = 2, x = 8
‰ p premier, g < p
„ y = gx mod p = 28 mod 11 = 3 PK = (3,2,11)
‰ y = gx mod p → (y,g,p)
„ Authentification : M = 5 , k=9 (9,10)=1 (ok)
„ Clé privée
‰ a = gk mod p = 29 mod 11 = 6
‰ x<p
‰ Par Euclide :
„ Signature „ M = (ax + bk) mod (p-1)
‰ K tel que (k,p-1)=1 „ 5 = (8*6 + 9*b) mod 10
„ b=3 → signature = (a,b) = (6,3)
‰ a = gk mod p
‰ b tel que M = (xa + kb) mod (p-1) „ Vérification :
‰ yaab mod p = gM mod p
„ Vérification :
‰ 3663 mod 11 = 25 mod 11
‰ La signature est valide si yaab mod p = gM mod p

Hachage et signatures - 45 Hachage et signatures - 46

Un nouveau k à chaque signature ou chiffrement

Si plusieurs fois le même k : retrouver x aisément
Digital Signature Standard (DSS) DSA – description de l’algorithme
„ Schéma de signature FIPS
- 186 approuvé par le govt US „ p : p = 2L : nbre premier de L bits (512<L<1024)
„ Emploie l'algorithme de hachage SHA „ q : facteur premier de p-1, 160 bits
„ Conçu par le NIST et la NSA dans le début des années 90
„ g : g = h(p-1)/q mod p
„ Le DSS est la norme, DSA est l'algorithme
‰ h : h < -p 1et h(p-1)/q > 1
„ Variante d'ElGamal et de Schnorr
„ x:x<q
„ Crée une signature de 320 bits, mais avec une sécurité
équivalentes à un chiffrement 512
- 1024 bits „ y : y = gx mod p
„ La sécurité dépend de la difficulté de calculer des „ H(x) : fonction de hachage à sens unique (SHA)
logarithmes discrets
„ Pk : y et Sk = x

Hachage et signatures - 47 Hachage et signatures - 48

p doit également être un multiple de 64

DSS - signature DSS - vérification
„ Alice engendre k tq k < q „ Bob vérifie la signature en calculant
‰ k doit être aléatoire, détruit après utilisation, jamais ‰ w = s-1 mod q
réutilisé ‰ u1 = (H(M) * w) mod q
„ Alice engendre ‰ u2 = rw mod q
‰ r = (gk mod p) mod q ‰ v = ((gu1 * gu2) mod p) mod q
‰ s = (k-1(H(M) + xr)) mod q „ Si v = r, alors la signature est vérifiée
„ r et s forment la signature
„ Alice envoie (r, s) à Bob

Hachage et signatures - 49 Hachage et signatures - 50

Comparaison des approches Questions
„ Expliquer
‰ MD5 et/ou SHA + comparaisons
‰ HMAC
‰ Signatures digitales : principes
‰ Signatures ElGamal et/ou DSS

Hachage et signatures - 51 Hachage et signatures - 52

Références
„ http://www.secure
- hash
- algorithm
- md5- sha
- 1.co.uk/
„ http://www.bibmath.net/crypto/moderne/sigelec.php3
„ http://www.securiteinfo.com/crypto/hash.shtml
„ http://www.ssh.fi/support/cryptography/introduction/signatur
es.html

„ [schneier] – ch 2, 18, 20
„ [stallings] – ch 12,13

Hachage et signatures - 53