11/18/2024

Fonctions de Hachage

Fonction de Hachage
• Fonction de hachage (cryptographique) : mappe un
message de longueur arbitraire à une condensé court et de
longueur fixe.

• On peut définir des fonctions de hachage avec ou sans clé.

• Les fonctions de hachage sans clé sont les plus utilisées.

• Leur sécurité est liée à la notion de collision.

1
 11/18/2024

Résistance à la collision
Soit H: M  T une fonction de hachage ( |M| >> |T| ). Les m dans
M sont de longueurs arbitraires. Les empreintes h = H(m) dans T sont toutes
de longueur fixe. Par exemple: SHA-256: {0,1}*  {0,1}256

Une collision de H est une pair m0 , m1  M (m0  m1) vérifiant:

H(m0) = H(m1)

H est résistante à la collision (RC) si pour tout algorithme A

“explicite” et “efficace” :
AvRC[A,H] = Pr[ A retourne une collision de H] est “négligeable”

Vérification d’intégrité
Progiciels: Espace
Nom du logiciel Nom du logiciel Nom du logiciel
public en
F1 F2 Fn lecture seule
H(F1) H(F2)
H(Fn)

•Un utilisateur qui télécharge un logiciel peut vérifier son intégrité.

•H résistante aux collisions ⇒ l‘adversaire ne peut pas modifier le
contenu sans détection.
•Moyen efficace de vérifiabilité publique sans clé, mais nécessitant
un espace public en lecture seule.

2
 11/18/2024

Attaque “générique”
• Par définition, une attaque “générique” sur une méthode
s’applique quelque soit la spécificité de la méthode attaquée .

• Par exemple, une attaque “générique” sur une fonction de

hachage H: M  {0,1} l est de choisir x1, …, xN + 1 éléments
distincts de M avec N = 2l . En calculant H(x1), …, H(xN + 1), on
est sûr de trouver une collision.
– Est-il possible de faire mieux?

Attaque générique basée sur le

“Paradoxe de l’Anniversaire”
• Choisir au hasard x1, …, x2l/2 éléments et calculer H(x1), …, H(x2l/2)
– Quelle est la probabilité d’une collision?

• Cette probabilité est liée au fameux “paradoxe de l’anniversaire”

– Quel est le nombre minimal de personnes, choisies au hasard,
pour que, au moins, 2 d’entre eux aient la même date
d’anniversaire avec une probabilité de 50% ?

3
 11/18/2024

Bines: jours de l’année (N=365) Bines: valeurs de T = {0,1}l (N=2l)

Boules: personnes Boules: nombre de calculs de H

Quel est le nombre minimal de boules

pour provoquer une collision avec 50% de chance de succès ?

Paradoxe de l’anniversaire
• Théorème: Soient r1, …, rn ∈ {1,…,N} des entiers
indépendants et identiquement distribués (i.i.d).
Si n = 1.2 × N1/2 alors P = Pr[ ∃i≠j: ri = rj ] ≥ 1/2

• Application: Des boules tirées au hasard, en nombre suffisant,

de l’ordre de O(N1/2) génèrent une collision dans 50% des cas.
– Anniversaires (N = 365)  23 personnes suffisent!
– Evaluations de H (N = 2l)  O(2l/2) évaluations

4
 11/18/2024

Preuve du Paradoxe
• Soient r1, …, rn (ind. unif. dis.), on veut calculer P = Pr[ ∃i≠j: ri = rj ] :
• P = 1 - Pr[ i≠j: ri ≠ rj ]
• P = 1 - Pr(r2r1)* . Pr(r3r1 et r3r2). … . Pr(rnr1 et … et rnrn-1)
• = 1 - [(N-1)/N] . [(N-2/N)] . … . [N-(n-1)/N]
• = 1 - (1-1/N) (1-2/N) … (1-(n-1)/N)
•x, 0 x 1, on a 1-x  e-x  P  1- e-1/N e-2/N …e-(n-1)/N = 1- e-n(n-1)/2N
•  P  1- e-n2/2N
• Si n = 1.2 × N1/2  P  1- e-0.72 = 0.513. c.q.f.d
*Pour que r2r1 (r1 fixé ), (N-1) choix restants pour r2  Pr(r2r1) = (N-1)/N

Algorithme de l’attaque générique

H: M  {0,1} l . Algorithme de recherche de collision :

1. Choisir 2l/2 éléments au hasard dans M : m1, …, m2l/2

2. Pour i = 1, …, 2l/2 calculer ti = H(mi) ∈ {0,1} l
3. Détecter une collision (ti = tj). Sinon, retour à l’étape 1.

Nombre d'itérations moyen ≈ 2

Temps d'exécution : O(2n/2) (espace mémoire O(2n/2) )

5
 11/18/2024

Fonctions de hachage usuelles

• MD5 (hors service)
– Développée en 1991
– Empreintes de taille: 128-bits
– N’est pas RC: Collisions détectées en 2004
• SHA-1 (hors service)
– Introduite en 1995
– Empreintes de taille: 160-bits
– N’est pas RC: Collisions détectées en 2017

Fonctions de hachage usuelles

• SHA-2 (toujours en service)
– Empreintes de tailles 256-bits ou 512-bits
– Pas de vulnérabilités connues

• SHA-3/Keccak (toujours en service)

– Résultat d’une compétition publique de 2008-2012
– Une conception très différente de la famille SHA
– Empreintes de tailles: 224, 256, 384, et 512-bits

6
 11/18/2024

Fonctions de hachage usuelles Crypto++ 5.6.0 [ Wei Dai ]

AMD Opteron, 2.2 GHz ( Linux)

temps
fonction valeur (bits) Vitesse (MB/sec) d’attaque
NIST standards

SHA-1* 160 153 280

SHA-256 256 111 2128
SHA-512 512 99 2256

Whirlpool 512 57 2256

* SHA-1 définitivement cassée

Construction des
Fonctions de Hachage

7
 11/18/2024

Principe de construction
• But: construire une fonction de hachage, anticollision (R.C.), pour des
messages de taille arbitraires.

• Principe de construction:
1. Construire une fonction de hachage, anticollision, pour de courts
message de taille fixe: h: T × X ⟶ T (fonction de compression)
• X = {0,1}s : Espace des messages courts.
• T = {0,1}n : Espace des empreintes
2. Utiliser le schéma de Merkle-Damgard pour générer à partir de h,
une fonction de hachage, anticollision, pour de longs messages : H:
X≤L ⟶ T
• X≤L : Espace des messages longs (jusqu’à L blocs de X)

Itération de Merkle-Damgard
m[0] m[1] m[2] m[3] ll PB

IV H(m)
(fixe) h h h h
H0 H1 H2 H3 H4

Etant donnée h: T × X ⟶ T (fonction de compression)

On obtient H: X≤L T Hi - variables en chaine

Si l’espace est insuffisant

PB: Padding Bloc = 1000…0 ll taille msg pour PB, ajouter un dummy bloc
64 bits

8
 11/18/2024

Est-ce MD anticollision?
Théorème: si h est RC alors H sera RC.
Preuve: par contradiction: collision de H ⇒ collision de h
Soient M  M’ et H(M) = H(M’). Construisons une collision pour h.

IV = H0 , H1 , … , Ht , Ht+1 = H(M)

IV = H0’ , H1’ , … , H’r, H’r+1 = H(M’)

 h( Ht, Mt ll PB) = Ht+1 = H’r+1 = h(H’r, M’r ll PB’)

Si Ht, Mt ll PB  H’r, M’r ll PB’  Collision pour h

Sinon Ht = H’r Mt = M’r PB = PB’  r = t

Alors: h( Ht-1, Mt-1) = Ht = H’t = h(H’t-1, M’t-1 )

Si (Ht-1, Mt-1)  (H’t-1, M’t-1)  Collision pour h

Sinon Ht-1 = H’t-1 Mt = M’t-1

Itérant vers le haut, à un moment donné on aura pour un certain i:

h( Hi, Mi) = Hi+1 = H’i+1 = h(H’i, M’i)

avec (Ht-1, Mt-1)  (H’t-1, M’t-1)  Collision pour h

Sinon H0 = H’0 et M0 = M’0  M = M’ (impossible)

9
 11/18/2024

Construire des Fonctions

de Compression

Itération MD (revisitée)
m[0] m[1] m[2] m[3] ll PB

IV H(m)
(fixe) h h h h

Théorème: h anti-collision ⇒ H anti-collision

But: construire des fonctions de compression h: T × X ⟶ T

10
 11/18/2024

Fonc. Compr. Davies-Meyer

Soit E: K× {0,1}n ⟶ {0,1}n une PPA, par exemple, un bloc-cipher (E,D).

La fonction de compression de Davies-Meyer:

h: {0,1}n × K ⟶ {0,1}n

h(H, m) = E(m, H)⨁H

mi
>
E h(Hi, mi) = E(mi,Hi)Hi
Hi

Fonc. Compr. Davies-Meyer

Théorème: Si E est un chiffrement idéal (collection de |K|
permutations aléatoires). Alors, Détecter une collision h(H,m) =
h(H’,m’) nécessite O(2n/2) évaluations de (E,D).

mi
>
E h(Hi, mi) =
Hi E(mi,Hi)Hi

On ne peux pas faire mieux !!

11
 11/18/2024

Mauvais exemple
Supposons que nous définissions h (H, m) = E (m, H)
m
H >
E h

Pensez-vous que le h résultant est résistant aux collisions?

Si non, étant donné le triplet (H, m, m’), comment choisir H’
pour construire une collision (H, m)  (H’, m’)?
 H’ = D(m’, E(m, H))
 H’ = E(m’, D(m, H))
 H’ = E(m’, E(m, H))
 H’ = D(m’, D(m, H))

Mauvais exemple
Supposons que nous définissions h (H, m) = E (m, H)
m
H >
E h

Étant donné le triplet (H, m, m’), une collision (H, m)  (H’, m’)
est telle que:

 H’ = D(m’, E(m, H)) (En effet, E(m’, H’) = E(m, H))

 H’ = E(m’, D(m, H))

 H’ = E(m’, E(m, H))
 H’ = D(m’, D(m, H))

12
 11/18/2024

Autres constructions
Soit E: {0,1}n × {0,1}n ⟶ {0,1}n pour simplifier

Miyaguchi-Preneel: h(H, m) = E(m, H)⨁H⨁m (Whirlpool)

h(H, m) = E(H⨁m, m)⨁m
total de 12 variantes similaires

D’autres variantes naturelles ne sont pas sûres: Par exemple,

h(H, m) = E(m, H)⨁m (vu en TD)

Étude de cas: SHA-256

• Construction de Merkle-Damgard
• Fonction de compression de Davies-Meyer
– Chiffrement par bloc: SHACAL-2

clé :512-bit

>
SHACAL-2 bloc: 256-bit
bloc : 256-bit

13
 11/18/2024

Fonction de compression prouvable

Choisissez un premier p aléatoire de 2000 bits et deux nombres
aléatoire 1 ≤ u, v ≤ p.
Pour m, H ∈ {0,…, p-1} définir h(H,m) = uH ⋅ vm (mod p)

Théorème: trouver une collision pour h est aussi difficile que de

résoudre le problème du logarithme discret modulo p.

Inconvénient: lente  rarement utilisée.

14