Plateforme de Cryptographie Par Kaci AMAOUCHE

Chapitre 3: Fonction de hash

Algorithmes et applications pratiques

Chapitre 3/5 Durée estimée: 2h

Introduction aux fonctions de hachage

Les fonctions de hachage cryptographiques constituent un pilier fondamental de la sécurité informatique moderne. Ces algorithmes transforment des données de taille arbitraire (comme un fichier, un message ou un mot de passe) en une chaîne de caractères de taille fixe, appelée "empreinte", "condensat" ou "hash". Cette transformation est conçue pour être rapide à calculer dans un sens, mais pratiquement impossible à inverser, créant ainsi une sorte d'"empreinte digitale" unique pour chaque ensemble de données.

Contrairement aux algorithmes de chiffrement, les fonctions de hachage sont des fonctions à sens unique qui ne nécessitent pas de clé et ne sont pas conçues pour être inversées. Cette propriété les rend particulièrement utiles pour de nombreuses applications de sécurité, notamment l'intégrité des données, l'authentification et les signatures numériques.

Formellement, une fonction de hachage cryptographique \(H\) est une fonction qui transforme une entrée \(m\) de taille variable en une sortie \(h\) de taille fixe :

$$H: \{0,1\}^* \rightarrow \{0,1\}^n$$

où \(\{0,1\}^*\) représente l'ensemble de toutes les chaînes binaires de longueur arbitraire et \(\{0,1\}^n\) représente l'ensemble des chaînes binaires de longueur fixe \(n\).

Applications courantes des fonctions de hachage

  • Stockage sécurisé des mots de passe : Au lieu de stocker les mots de passe en clair, les systèmes stockent leur hachage
  • Signatures numériques : Le hachage du document est signé plutôt que le document entier, pour des raisons d'efficacité
  • Vérification d'intégrité : Pour s'assurer qu'un fichier n'a pas été modifié durant son transfert ou son stockage
  • Structures de données : Tables de hachage, arbres de Merkle et blockchain
  • Dérivation de clés : Génération de clés cryptographiques à partir de mots de passe
  • Identifiants uniques : Création d'identifiants pour des objets de grande taille

3.1. Propriétés des fonctions de hachage

Une fonction de hachage cryptographique doit satisfaire plusieurs propriétés fondamentales pour garantir sa sécurité et son utilité. Ces propriétés peuvent être divisées en propriétés de base et propriétés de sécurité.

Propriétés de base

  • Déterminisme : La même entrée produira toujours la même sortie. Formellement, pour toute entrée \(x\), \(H(x)\) donne toujours le même résultat.
  • Efficacité de calcul : Le calcul de \(H(x)\) doit être rapide pour toute entrée \(x\) de taille raisonnable, permettant des traitements en temps réel même sur de grands volumes de données.
  • Effet d'avalanche : Une modification minime de l'entrée (même d'un seul bit) doit entraîner une modification significative et imprévisible de la sortie. Idéalement, chaque bit de sortie a une probabilité de 50% de changer quand un bit d'entrée est modifié.
  • Distribution uniforme : Les valeurs de hachage doivent être distribuées uniformément dans l'espace de sortie, sans concentration ou motifs prévisibles, minimisant ainsi les risques de collision naturelle.

Propriétés de sécurité

  • Résistance à la préimage (one-way property) : Étant donné un hachage \(h\), il doit être calculatoirement infaisable de trouver une entrée \(x\) telle que \(H(x) = h\). Cette propriété garantit qu'on ne peut pas "inverser" la fonction pour retrouver l'entrée à partir de la sortie.

    Formellement, pour presque tout \(y \in \{0,1\}^n\), il est computationnellement infaisable de trouver \(x\) tel que \(H(x) = y\).

  • Résistance à la seconde préimage (weak collision resistance) : Étant donné une entrée \(x_1\), il doit être calculatoirement infaisable de trouver une entrée différente \(x_2 \neq x_1\) telle que \(H(x_1) = H(x_2)\). Cette propriété prévient la substitution frauduleuse de données.

    Formellement, pour tout \(x_1\), il est computationnellement infaisable de trouver \(x_2 \neq x_1\) tel que \(H(x_1) = H(x_2)\).

  • Résistance aux collisions (strong collision resistance) : Il doit être calculatoirement infaisable de trouver deux entrées différentes \(x_1 \neq x_2\) telles que \(H(x_1) = H(x_2)\). Cette propriété est plus forte que la résistance à la seconde préimage car l'attaquant est libre de choisir les deux entrées.

    Formellement, il est computationnellement infaisable de trouver n'importe quelle paire \(x_1, x_2\) telle que \(x_1 \neq x_2\) et \(H(x_1) = H(x_2)\).

Note sur le paradoxe des anniversaires

La résistance aux collisions est souvent liée au "paradoxe des anniversaires" en mathématiques. Ce paradoxe montre qu'avec seulement 23 personnes dans une pièce, la probabilité que deux d'entre elles partagent le même anniversaire dépasse 50%.

De manière similaire, pour une fonction de hachage produisant des sorties de n bits, la théorie des probabilités suggère qu'après environ \(2^{n/2}\) entrées aléatoires (et non \(2^n\) comme on pourrait intuitivement le penser), la probabilité de trouver une collision devient significative.

C'est pourquoi les fonctions de hachage modernes comme SHA-256 (256 bits) nécessiteraient environ \(2^{128}\) opérations pour trouver une collision par force brute, ce qui reste infaisable avec la technologie actuelle.

Données d'entrée (taille variable) Ex: "Bonjour monde!" Fonction de hash Valeur de hash (taille fixe) Ex: "5d41402abc..."

3.2. Principaux algorithmes de hachage

MD5 (Message Digest 5)

Développé par Ronald Rivest en 1991, MD5 produit un hash de 128 bits (16 octets). Bien que rapide, il n'est plus considéré comme sécurisé en raison de ses vulnérabilités aux collisions découvertes en 2004. Son utilisation est déconseillée pour les applications de sécurité.

SHA-1 (Secure Hash Algorithm 1)

Développé par la NSA, SHA-1 produit un hash de 160 bits (20 octets). En 2017, Google a réussi à démontrer une collision concrète, rendant cet algorithme non sécurisé pour les signatures numériques et les certificats.

SHA-2

Famille d'algorithmes incluant SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 et SHA-512/256. SHA-256 (32 octets) est l'un des plus utilisés et considéré comme sécurisé à ce jour.

SHA-3

Standardisé en 2015, SHA-3 est basé sur l'algorithme Keccak. Contrairement à SHA-1 et SHA-2, il utilise une construction en éponge (sponge function) complètement différente, ce qui le rend résistant aux attaques qui pourraient affecter SHA-2.

BLAKE2 et BLAKE3

Alternatives à SHA-3, ces algorithmes sont optimisés pour la vitesse tout en offrant un haut niveau de sécurité. BLAKE3, publié en 2020, est particulièrement efficace pour des applications à haut débit.

Algorithme Taille de sortie Statut de sécurité Vitesse relative
MD5 128 bits Non sécurisé Très rapide
SHA-1 160 bits Non sécurisé Rapide
SHA-256 256 bits Sécurisé Modéré
SHA-3-256 256 bits Sécurisé Modéré
BLAKE2b jusqu'à 512 bits Sécurisé Rapide
BLAKE3 256 bits Sécurisé Très rapide
Exemple de valeurs de hash pour la chaîne "Bonjour monde!"
  • MD5: c0fb20d14291b9041fccaea66c94d6bc
  • SHA-1: a9d4c2c3be59eed265fc9e3eb6a9b943dd7a3ad3
  • SHA-256: 7f83b1657ff1fc53b92dc18148a1d65dfc2d4b1fa3d677284addd200126d9069
  • SHA-3-256: 2a6485680c98dc17ca5e864c3d50a5e23e2acac5d83f1fbe2959694000d9cee3

Notez comment une petite modification du message (par exemple, changer "Bonjour monde!" en "Bonjour monde.") changerait complètement toutes ces valeurs de hash.

3.3. Fonctionnement interne

La plupart des fonctions de hachage cryptographiques fonctionnent selon un modèle similaire :

  1. Prétraitement : Le message est padded (complété) pour atteindre une taille qui est un multiple de la taille de bloc
  2. Initialisation : Un état initial est défini
  3. Traitement par blocs : Le message est traité bloc par bloc, chaque bloc modifiant l'état
  4. Finalisation : L'état final est transformé en valeur de hash

Construction de Merkle-Damgård

Utilisée par MD5, SHA-1 et SHA-2, cette construction divise le message en blocs qui sont traités séquentiellement, chaque bloc modifiant l'état interne en utilisant une fonction de compression.

Construction en éponge

Utilisée par SHA-3 (Keccak), cette construction alterne entre l'absorption des blocs du message et le pressage (squeezing) pour produire la sortie. Elle offre plus de flexibilité et de sécurité théorique.

3.4. Applications des fonctions de hachage

Vérification d'intégrité des données

Les hashes sont utilisés pour vérifier qu'un fichier n'a pas été modifié durant le transfert ou le stockage. Par exemple, les téléchargements de logiciels sont souvent accompagnés de checksums (valeurs de hash) que l'utilisateur peut vérifier.

Stockage sécurisé des mots de passe

Une des applications les plus importantes des fonctions de hachage est le stockage sécurisé des mots de passe dans les systèmes d'authentification. Au lieu de stocker les mots de passe en texte clair, les systèmes stockent leur empreinte cryptographique (hash). Lorsqu'un utilisateur tente de se connecter, le système calcule le hash du mot de passe fourni et le compare au hash stocké, sans jamais avoir à manipuler ou stocker le mot de passe original.

Cette approche présente plusieurs avantages de sécurité :

  • Même les administrateurs système ou les attaquants ayant accès à la base de données ne peuvent pas lire les mots de passe originaux
  • En cas de violation de données, les attaquants n'obtiennent que des hashes, pas les mots de passe réels
  • La propriété de non-réversibilité des fonctions de hachage empêche la récupération directe des mots de passe

Cependant, les hachages simples des mots de passe présentent des vulnérabilités, notamment aux attaques par dictionnaire et aux tables arc-en-ciel (rainbow tables). Pour renforcer la sécurité, plusieurs techniques sont employées :

  • Salage (Salting) : Ajout d'une valeur aléatoire unique (sel) à chaque mot de passe avant le hachage. Cette technique prévient les attaques utilisant des tables précalculées et garantit que deux utilisateurs ayant le même mot de passe auront des hashes différents.

    $$\text{storedHash} = \text{Hash}(\text{salt} + \text{password})$$

  • Fonctions de dérivation de clé (KDF) : Algorithmes spécialement conçus pour le hachage des mots de passe, comme bcrypt, scrypt ou Argon2. Ces fonctions sont délibérément lentes et gourmandes en ressources pour rendre les attaques par force brute coûteuses.
  • Étirement de clé (Key Stretching) : Technique consistant à appliquer la fonction de hachage de manière répétée, typiquement des milliers ou des millions de fois, pour augmenter le coût computationnel des attaques.

    $$\text{hash}_0 = \text{password}$$

    $$\text{hash}_{i+1} = \text{Hash}(\text{hash}_i)$$

    $$\text{finalHash} = \text{hash}_n \text{ (après } n \text{ itérations)}$$

  • Poivrage (Peppering) : Ajout d'une valeur secrète constante (poivre), stockée séparément de la base de données, à tous les mots de passe. Contrairement au sel qui est public, le poivre est une clé secrète qui ajoute une couche de sécurité supplémentaire.
Exemple d'implémentation avec bcrypt

Bcrypt est l'une des fonctions de hachage les plus recommandées pour les mots de passe. Elle intègre automatiquement un sel aléatoire et permet de configurer un facteur de coût qui détermine la lenteur de l'algorithme.


import bcrypt

# Hachage d'un mot de passe (lors de l'enregistrement d'un utilisateur)
def hash_password(password):
    # Génère un sel aléatoire et hache le mot de passe
    # Le facteur de coût (12) détermine la complexité du hachage
    password_bytes = password.encode('utf-8')
    salt = bcrypt.gensalt(rounds=12)
    hashed = bcrypt.hashpw(password_bytes, salt)
    return hashed

# Vérification d'un mot de passe (lors de la connexion)
def check_password(password, stored_hash):
    password_bytes = password.encode('utf-8')
    # bcrypt compare le hash du mot de passe avec le hash stocké
    # en tenant compte du sel qui est stocké avec le hash
    return bcrypt.checkpw(password_bytes, stored_hash)

# Exemple d'utilisation
user_password = "MotDePasse123!"
stored_hash = hash_password(user_password)
print(f"Hash stocké: {stored_hash}")

# Simulation de connexion
is_valid = check_password("MotDePasse123!", stored_hash)  # Retourne True
is_invalid = check_password("MauvaisMotDePasse", stored_hash)  # Retourne False

Signatures numériques

Les fonctions de hash sont utilisées dans les algorithmes de signature numérique. Au lieu de signer directement un message (ce qui serait inefficace pour les grands messages), on signe son hash.

Structures de données

Les hashes sont à la base de structures comme les tables de hachage, les arbres de Merkle et les blockchains.

Arbre de Merkle (Merkle Tree)

Structure de données en arbre où chaque nœud est étiqueté par le hash de ses enfants. Les arbres de Merkle permettent de vérifier efficacement l'intégrité de grandes quantités de données.

Hash racine Hash 1-2 Hash 3-4 Hash 1 Hash 2 Hash 3 Hash 4 Données 1 Données 2 Données 3 Données 4
Blockchain

Les fonctions de hash sont essentielles pour les blockchains, où elles sont utilisées pour :

  • Créer des identifiants uniques pour les blocs
  • Lier les blocs entre eux (chaque bloc contient le hash du bloc précédent)
  • Implémenter les mécanismes de preuve de travail (proof-of-work)
  • Créer des adresses à partir de clés publiques

HMAC (Hash-based Message Authentication Code)

Les HMAC combinent une fonction de hachage avec une clé secrète pour produire un code d'authentification de message. Ils sont utilisés pour vérifier à la fois l'intégrité et l'authenticité des données.

$$HMAC(K, m) = H((K' \oplus opad) \| H((K' \oplus ipad) \| m))$$

Où \(H\) est la fonction de hash, \(K\) est la clé, \(K'\) est la clé dérivée, \(opad\) et \(ipad\) sont des constantes, et \(\|\) représente la concaténation.

Chapitre précédent: Chiffrement symétrique et asymétrique Chapitre suivant: Cryptographie quantique

Dans ce chapitre

Exercices associés

Mettez en pratique les concepts de ce chapitre avec les exercices dédiés.

Accéder aux exercices

Exemple de code (Python)


import hashlib
import hmac
import os

# Exemple de calcul de hash
def calculate_hashes(data):
    """Calcule différents hashes pour les données fournies."""
    # Convertir la chaîne en bytes si nécessaire
    if isinstance(data, str):
        data = data.encode('utf-8')
    
    # Calcul des hashes
    md5_hash = hashlib.md5(data).hexdigest()
    sha1_hash = hashlib.sha1(data).hexdigest()
    sha256_hash = hashlib.sha256(data).hexdigest()
    sha3_256_hash = hashlib.sha3_256(data).hexdigest()
    
    return {
        'MD5': md5_hash,
        'SHA-1': sha1_hash,
        'SHA-256': sha256_hash,
        'SHA3-256': sha3_256_hash
    }

# Exemple d'utilisation du salage pour les mots de passe
def hash_password_with_salt(password):
    """Hache un mot de passe avec un sel aléatoire."""
    if isinstance(password, str):
        password = password.encode('utf-8')
    
    # Génération d'un sel aléatoire
    salt = os.urandom(16)  # 16 octets = 128 bits
    
    # Hachage du mot de passe avec le sel
    # Utilise PBKDF2 avec HMAC-SHA256, 100000 itérations
    key = hashlib.pbkdf2_hmac('sha256', password, salt, 100000)
    
    # Stocker le sel et le hash ensemble
    storage = salt + key
    
    return storage.hex()

# Exemple de HMAC
def create_hmac(key, message):
    """Crée un HMAC pour le message avec la clé donnée."""
    if isinstance(key, str):
        key = key.encode('utf-8')
    if isinstance(message, str):
        message = message.encode('utf-8')
    
    h = hmac.new(key, message, hashlib.sha256)
    return h.hexdigest()

# Exemples d'utilisation
data = "Bonjour monde!"
print("Hashes pour:", data)
hashes = calculate_hashes(data)
for algo, value in hashes.items():
    print(f"{algo}: {value}")

password = "mot_de_passe_secret"
hashed_password = hash_password_with_salt(password)
print(f"\nMot de passe haché avec sel: {hashed_password}")

secret_key = "ma_clé_secrète"
message = "Message à authentifier"
message_hmac = create_hmac(secret_key, message)
print(f"\nHMAC pour '{message}': {message_hmac}")