L3 informatique, Sécurité
Appliquée
Fonctions de hachage
Jean-François Couchot
Université de Franche-Comté, UFR-ST
Plan
Introduction
Théorie
Constructions
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 2
Plan
Introduction
Applico crypto. : l’intégrité
Applico crypto. : hachage de mots de passe
Applico crypto. : code d’Authentification de Message
Applico non crypto. : pseudonymisation
Théorie
Constructions
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 3
Plan
Introduction
Applico crypto. : l’intégrité
Applico crypto. : hachage de mots de passe
Applico crypto. : code d’Authentification de Message
Applico non crypto. : pseudonymisation
Théorie
Constructions
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 4
Objectif d’intégrité : vérifier l’égalité m1 = m2
Pour ne pas analyser tous les bits de m1 et m2 (fastidieux)
▶ Souhait : une fonction H
▶ Réduisant m à son empreinte H(m) de taille fixe
▶ Implantant l’effet d’avalanche : même si m1 et m2 ne diffèrent que
d’1 bit ⇝ H(m1 ) et H(m2 ) complètement différents
▶ Reproductible : H(m) ne change pas au cours du temps
Exécution de la fonction sha256 sur 2 messages proches
import hashlib
txt1 = " L3 sécurité: indispensable".encode('utf-8')
print(txt1,'\n',hashlib.sha256(txt1).hexdigest())
txt2 = " L2 sécurité: indispensable".encode('utf-8')
. print(txt2,'\n',hashlib.sha256(txt2).hexdigest())
b' L3 s\xc3\xa9curit\xc3\xa9: indispensable'
6794435c2ea132b2a695e3308e64134c18fdc2854841d626612fba3cd6f1efb2
b' L2 s\xc3\xa9curit\xc3\xa9: indispensable'
25d5b973843a25c6634bba79109f389e8eb1519441c1cd76740837d6ae449768
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 5
Plan
Introduction
Applico crypto. : l’intégrité
Applico crypto. : hachage de mots de passe
Applico crypto. : code d’Authentification de Message
Applico non crypto. : pseudonymisation
Théorie
Constructions
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 6
Mot de passe : jamais stocké en clair !
Hachage de mots de passe
Le hachage de mots de passe est un cas particulier très usuel d’utilisation des
fonctions de hachage. L’idée principale :
1. Utilisateur ou utilisatrice : définit son mot de passe m ;
2. Système : enregistre une empreinte h = H(m) du mot de passe ;
3. Lors d’une connexion : mot de passe m′ saisi ;
4. Système : calcule l’empreinte h′ = H(m) du mot de passe puis,
comparaison avec h.
Stockage de mot de passe dans une base
CREATE TABLE ETUDIANT INSERT INTO ETUDIANT
(Numero INTEGER PRIMARY KEY, VALUES (32823,'Marche','Claire',
Nom VARCHAR(50) NOT NULL, '1998-10-01','cmarche',
Prenom VARCHAR(50) NOT NULL, SHA2('@L1Sc1enc3!',512))-- a discuter
DateNaissance DATE NOT NULL,
Login CHAR(8) NOT NULL UNIQUE,
MotDePasse BINARY(64) NOT NULL) -- a discuter
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 7
Hachage de mots de passe : attaques
▶ l’espace de recherche est-il suffisamment grand ?
▶ la fonction de hachage utilisée est-elle rapide ?
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 8
Espace de recherche
Espace de recherche
Ce paramètre dépend de l’utilisateur. Si l’utilisateur utilise un mot du
dictionnaire, l’espace de recherche est ridiculement faible !
▶ mots du dictionnaire : 130000 ≈ 217
▶ deux mots du dictionnaire : 234
▶ trois mots du dictionnaire : 251
Ordres de grandeur
Règles en vigueur sur l’ENT : a minima Longueur 6 7 8 9 10
▶ 8 caractères a-z (26) 228 232 237 242 247
▶ 1 caractère spécial (parmi 26) a-zA-Z (52) 234 239 245 251 257
a-zA-Z0-9 (62) 235 241 247 253 259
▶ 2 chiffres + [punct] (94) 239 245 252 258 265
▶ 1 caractère alphabétique ENT - - 248 255 261
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 9
Vitesse de la fonction de hachage
Vitesse de la fonction de hachage
▶ Une fonction de hachage est normalement destinée à être rapide pour être
capable de hacher de grandes quantité de données.
▶ Pour limiter la portée d’une attaque sur des mots de passe, on a intérêt à
ce que la fonction de hachage soit la plus lente possible.
→ On n’utilise pas les mêmes fonctions de hachages pour les mots de passe et
pour les autres utilisations cryptographiques
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 10
Hachage cryptographique pour les mots de passe
Généralités
Dans les fonctions suivantes, on peut souvent régler :
▶ le temps d’exécution
▶ l’espace mémoire utilisé
Hachage cryptographique de mots de passe
▶ bcrypt, 1999, basé sur Blowfish
▶ PBKDF2, 2000
▶ scrypt, 2012
▶ Argon2, 2015, gagnant du Password Hashing Competition
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 11
Plan
Introduction
Applico crypto. : l’intégrité
Applico crypto. : hachage de mots de passe
Applico crypto. : code d’Authentification de Message
Applico non crypto. : pseudonymisation
Théorie
Constructions
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 12
Code d’Authentification de Message
Définition (Code d’Authentification de Message (MAC))
Un Message Authentication Code (MAC) est une association entre une fonction
de compression et une clef secrète permettant de vérifier à la fois l’intégrité et
l’authenticité des données reçues.
Utilisation
1. Alice veut envoyer un message m à Bob
2. Elle calcule le MAC avec une clef secrète K qu’elle partage avec Bob
3. Elle envoie son message et le MAC à Bob
4. Bob recalcule le MAC et vérifie qu’il est identique à celui d’Alice
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 13
Hash-based Message Authentication Code (HMAC)
Hash-based Message Authentication Code (HMAC)
▶ Utilisé dans IPSec et TLS
▶ HMAC(K , m) = H ((K ⊕ opad) || H ((K ⊕ ipad) || m))
▶ H est une fonction de hachage cryptographique
▶ K est la clef secrète
▶ opad = 0x5c5c5c. . . 5c5c
▶ ipad = 0x363636. . . 3636
▶ || est la concaténation
▶ Plusieurs variantes suivant H : HMAC-MD5 (possible, mais cata !),
HMAC-SHA-256
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 14
Plan
Introduction
Applico crypto. : l’intégrité
Applico crypto. : hachage de mots de passe
Applico crypto. : code d’Authentification de Message
Applico non crypto. : pseudonymisation
Théorie
Constructions
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 15
Pseudonymiser un attribut identifiant
Pseudonymiser n’est pas anonymiser
▶ Remplacer la valeur d’un attribut “identifiant” par un pseudonyme.
▶ Pseudonyme peut être dérivé de la valeur identifiante (par exemple, en
appliquant une fonction de hachage).
▶ Risque de mise en corrélation de données avec l’identité originale d’un
sujet : réduit mais possible
▶ ré-identification indirecte possible en utilisant les autres attributs⇝ Pas
une méthode d’anonymisation.
Pseudonymiser un attribut avec pandas
import pandas as pd
import hashlib
df = pd.read_csv('[Link]',
usecols=['CLIENTNUM', 'Customer_Age','Total_Trans_Amt'])
df['CLIENTNUM'] = df['CLIENTNUM'].astype(str)
df['CLIENTNUM_HASH'] = df['CLIENTNUM'].apply(lambda x:
hashlib.sha256([Link]('utf-8'))
.hexdigest())
[Link](['CLIENTNUM'],inplace=True)
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 16
Plan
Introduction
Théorie
Formalisation
Recherche de collisions
Constructions
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 17
Plan
Introduction
Théorie
Formalisation
Recherche de collisions
Constructions
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 18
Définitions
Définition (Fonction de hachage H : B∗ → Bn )
Fonction qui transforme un message m de taille quelconque en une valeur
h = H(m) de taille fixe n.
▶ h : appelé.e empreinte, le résumé ou la somme de contrôle de m
▶ m : appelé.e l’antécédent ou la préimage de h
Définition (Collision)
Il y a collision entre m1 et m2 , m1 ̸= m2 si H(m1 ) = H(m2 )
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 19
Propriétés pour H : B∗ → Bn
Définition (Résistance à la préimage)
Pour toute empreinte h, il est difficile de trouver m tel que H(m) = h.
Conséquences :
▶ Difficile de retrouver un mdp m étant donnée une empreinte h stockée
▶ On parle de fonction à sens unique
Définition (Résistance à la seconde préimage)
Pour tout m1 , il est difficile de trouver m2 ̸= m1 tel que H(m1 ) = H(m2 ).
Remarque : on a ici une connaissance supplémentaire qui est m1
Définition (Résistance aux collisions)
Il est difficile de trouver m1 et m2 ̸= m1 tels que H(m1 ) = H(m2 ).
Remarque : comme H : B∗ → Bn , il y a nécessairement des collisions
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 20
Plan
Introduction
Théorie
Formalisation
Recherche de collisions
Constructions
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 21
#tirages avant une collision avec une proba. p ?
Proba. d’une coll. en tirant au hasard k éléments parmi n distincts ?
1. 1er tirage : il y a n valeurs différentes parmi lesquelles choisir.
n−1
2. Proba. que les deux 1ers tirages soient ̸= : n
.
n−1
3. Proba. que les trois 1ers tirages soient ̸= : n
× n−2
n
n n−1 n−(k−1)
4. . . . Proba. que les k 1ers tirages soient ̸= : n n
× ··· × n
.
⇒ Proba. p d’obtenir au moins une coll. sur k tirages :
k(k−1)
p =1− n!
(n−k)!
· 1
nk
≈ 1 − e− 2n croissante en en fct. de k
⇒ [Link] de tirages suffisants pour avoir une une coll. avec une proba. p :
1
k≈ 2 · n ln 1−p
Applications
▶ Paradoxe des anniversaires : nbre. suffisant de personnes pour que la proba.
qu’au moins deux aient leur anniversaire le même jour soit sup. à 21 ? 23.
▶ Conséquences pour H sur n bits : collision avec une probabilité supérieure
√ n
à 12 en O( 2n ) = O(2 2 ) : seulement n2 bits de sécurité.
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 22
Plan
Introduction
Théorie
Constructions
Fonctions de hachage issues de Merkle-Damgård
SHA-3
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 23
Plan
Introduction
Théorie
Constructions
Fonctions de hachage issues de Merkle-Damgård
SHA-3
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 24
Construction de Merkle-Damgård
Idées principales
▶ On découpe le message m en blocs mi de taille égale
▶ On utilise une fonction de compression f : h0 = IV , hi+1 = f (mi , hi )
▶ Propriété : si f est résistante aux collisions, alors la construction l’est
▶ Appliquées dans MD5, SHA-1, SHA-2..... . .
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 25
MD5
Aperçu général
Généralités
▶ Inventé par Ronald Rivest en 1991
▶ Amélioration de MD4
▶ Bloc de 512 bits
▶ Empreinte de 128 bits
▶ 64 rondes (ou itérations)
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 26
MD5
Description d’une itération
Description d’une itération
▶ Dans l’image Mi est un bloc mi du
message
▶ Les constantes Ki sont fixées
▶ État : A, B, C , D
▶ Fonctions F :
▶ F1 (B, C , D) = (B ∧ C ) ∨ (¬B ∧ D)
▶ F2 (B, C , D) = (B ∧ D) ∨ (C ∧ ¬D)
▶ F3 (B, C , D) = B ⊕ C ⊕ D
▶ F4 (B, C , D) = C ⊕ (B ∨ ¬D)
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 27
MD5
pas résistance à la préimage
Historique
▶ 2009 : Attaque en 2123.4
Attaque hashcat de [Link] stockant des empreintes MD5 (-m 0)
▶ hashcat -m 0 -a 0 [Link] [Link] -r [Link] --show
Avec un dictionnaire (-a 0 [Link]) et des règles (-r
[Link]) ⇝ 646 mdp reconstruits en qques. secondes
▶ hashcat -m 0 -a 3 [Link]
Brute force (-a 3) ⇝ 1700 mdp reconstruits en qques. heures
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 28
MD5
pas résistante aux collisions
Historique ⇝ MD5 n’est plus une fonction cryptographiquement sûre
▶ 1996 : une faille est trouvée dans la fonction de compression
▶ 2004 : premières collisions générées
Code de collision
import hashlib
from array import array
input1 = array('I', [1634021390, 2275908181, 4156951504, 889109771, 1694748420, 2236575902,
4212113460, 2269944933, 798280768, 362884587, 1544942755, 1225230011,
1835370099, 2754879357, 2413254944, 4023487834])
input2 = array('I', [1634021390, 2275908181, 4156951504, 889109771, 1694748420, 2236576926,
4212113460, 2269944933, 798280768, 362884587, 3692426403, 1225230011,
1835370099, 2754879357, 2413254944, 4023487834])
print(""+str(input1[5])+" vs "+ str(input2[5]))
print(""+str(input1[10])+" vs "+ str(input2[10]))
print(hashlib.md5(input1).hexdigest())
print(hashlib.md5(input2).hexdigest())
2236575902 vs 2236576926
1544942755 vs 3692426403
cee9a457e790cf20d4bdaa6d69f01e41
cee9a457e790cf20d4bdaa6d69f01e41
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 29
SHA-1
Aperçu général et attaques
Algorithme similaire à MD-5, mais
▶ 1995 : complexification de SHA-0
▶ Empreinte de 160 bits
▶ 80 rondes (ou itérations)
Attaques
▶ 2005 : construction d’une attaque théorique en 269 (comparer à 280 )
▶ 2017 : attaque de la seconde préimage réaliste (Google, vue en TD)
▶ 2020 : construction d’une attaque théorique 263 opérations.
▶ Déconseillées depuis 2010, mais :
▶ Signatures SHA-1 (vues plus tard) : encore acceptées dans TLS. . .
▶ HMAC-SHA-1 : dans plus de 8% des 1M de serveurs Alexa (2020)
▶ Il est important que vous ne l’utilisiez plus !
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 30
SHA-256
Aperçu général
Algorithme similaire à SHA-1, mais
▶ 2002 : création par la National Security Agency
▶ Empreinte de 256 bits
▶ 64 rondes (ou itérations)
Attaques
▶ Aucune connue ! A utiliser (et sa version SA-512)
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 31
Plan
Introduction
Théorie
Constructions
Fonctions de hachage issues de Merkle-Damgård
SHA-3
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 32
SHA-3 Keccak : construction éponge
Intuition
▶ Absorption : blocs mi intégrés successivement par XOR dans l’état interne
et application de f
▶ Essorage : r premiers bits évacués puis application de f
L3 informatique, Sécurité Appliquée Fonctions de hachage | Jean-François Couchot | 33
