Exercices - Chapitre 3: Fonction de hash

Solution

Partie A : Calcul de valeurs de hash

import hashlib

def calculate_hashes(input_string):
    """Calcule les hashes d'une chaîne avec différents algorithmes."""
    # Convertir la chaîne en bytes
    data = input_string.encode('utf-8')
    
    # Calculer les différents 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()
    
    # Afficher les résultats
    print(f"Input: '{input_string}'")
    print(f"MD5: {md5_hash}")
    print(f"SHA-1: {sha1_hash}")
    print(f"SHA-256: {sha256_hash}")
    print(f"SHA3-256: {sha3_256_hash}")
    print("-" * 80)

# Tester avec différentes entrées
inputs = ["Bonjour monde", "Bonjour monde.", "bonjour monde"]
for input_str in inputs:
    calculate_hashes(input_str)
                    

Résultats attendus :

Input: 'Bonjour monde'
MD5: 30e98d1eb94bb9680a81a793d81374d7
SHA-1: 95917401a9def8eed262cb43dadd6a8d28eaf8fd
SHA-256: 16b6977f2b76c97e847d8132ef3c081f7bbfb7338db8ebe147d13e8e5499f449
SHA3-256: e840deb4f5519e9862c9038752df33ff5f8c8ee433109e8ee0e5a5c6d4594927
--------------------------------------------------------------------------------
Input: 'Bonjour monde.'
MD5: d6a80ccdee29d4191a18462b9d741a96
SHA-1: 32a7f798a0d90c586cf1fd02e1daab18adcd1fad
SHA-256: 0baa9c3a81271a3ef05f7700627daa0d4bc361745d35db5ed4596999c1f0ac5f
SHA3-256: 196dbeb965a5f3cf02a233232aec306da39c37b6963ecbabbbcb974a932a1ed8
--------------------------------------------------------------------------------
Input: 'bonjour monde'
MD5: 82b8ba522941a5b308c6c1a3183dceac
SHA-1: b3ad5ac954d937c8e0da98f2f70c3e7fa4c42a82
SHA-256: b5cb660fd566e17a33914954a8542e66ab8a36f9e3bca57ab30f339caf004155
SHA3-256: c5bf3e46a5db2b9ddd699c46ea13b4bdd7ce46e5aa35e608de24744d5bfb6fe5
--------------------------------------------------------------------------------
                        

Observations :

• Même l'ajout d'un simple point (comparaison entre "Bonjour monde" et "Bonjour monde.") change complètement toutes les valeurs de hash
• La modification de la casse d'une seule lettre (comparaison entre "Bonjour monde" et "bonjour monde") produit également des hashes totalement différents
• Cette propriété, appelée "effet d'avalanche", est essentielle pour les fonctions de hash cryptographiques
• On observe également que la longueur du hash dépend de l'algorithme utilisé (MD5: 32 caractères hexadécimaux, SHA-256: 64 caractères hexadécimaux, etc.)

Partie B : Propriétés des fonctions de hash

1. Effet d'avalanche

Importance : L'effet d'avalanche garantit qu'une modification minime dans les données d'entrée (même un seul bit) entraîne un changement radical dans la valeur de hash. Cette propriété rend impossible la prédiction de la façon dont une modification des données affectera le hash résultant.

Exemple concret : Dans les systèmes de stockage de mots de passe, l'effet d'avalanche assure qu'un attaquant ne peut pas déduire d'informations sur un mot de passe similaire à partir d'un hash connu. Si quelqu'un connaît le hash de "password123" et tente de deviner des variations comme "Password123" ou "password124", les hashes correspondants seront complètement différents, ne donnant aucune indication sur la proximité avec le mot de passe original.

2. Résistance à la préimage

Importance : La résistance à la préimage signifie qu'il est pratiquement impossible, à partir d'une valeur de hash, de retrouver le message original qui a produit ce hash. C'est une propriété à sens unique essentielle pour la sécurité.

Exemple concret : Dans les bases de données de mots de passe, on stocke uniquement les hashes, pas les mots de passe en clair. Même si un attaquant obtient accès à la base de données et voit la valeur du hash, la résistance à la préimage garantit qu'il ne pourra pas calculer directement le mot de passe original. L'attaquant serait contraint d'essayer des mots de passe candidats (attaque par force brute ou dictionnaire), de calculer leur hash, et de vérifier s'ils correspondent au hash stocké.

3. Résistance aux collisions

Importance : La résistance aux collisions garantit qu'il est extrêmement difficile de trouver deux messages différents qui produisent la même valeur de hash. Cette propriété est cruciale pour l'intégrité des données et l'authenticité.

Exemple concret : Dans les signatures numériques, le document est généralement haché, puis le hash est signé avec la clé privée du signataire. Si un attaquant pouvait trouver une collision (un document frauduleux avec le même hash que le document légitime), il pourrait substituer le document frauduleux tout en conservant la signature valide. La résistance aux collisions empêche ce scénario, garantissant que seul le document original correspondra au hash signé.

Partie C : Détection de modifications

Choix de l'algorithme :

Pour vérifier l'intégrité d'un fichier important téléchargé par de nombreux utilisateurs, je choisirais SHA-256 pour les raisons suivantes :

• Sécurité : SHA-256 n'a pas de vulnérabilités connues (contrairement à MD5 et SHA-1) et offre une résistance robuste aux collisions
• Équilibre performance/sécurité : SHA-256 offre un bon compromis entre performance et sécurité pour la vérification d'intégrité de fichiers
• Adoption répandue : SHA-256 est largement supporté par les systèmes d'exploitation et les outils de sécurité, ce qui facilite son utilisation par les utilisateurs finaux
• Adéquation à l'usage : Pour la vérification d'intégrité de fichiers, SHA-256 offre une sécurité largement suffisante sans le surcoût de performance des fonctions de hash plus lourdes comme SHA-512

Processus complet :

1. Création du hash :
   • Après la finalisation du fichier et avant sa mise à disposition, calculer le hash SHA-256 du fichier
   • Documenter cette valeur de hash avec la version exacte du fichier
   • Stocker le hash dans un fichier texte signé numériquement (par exemple, "checksums.txt") ou dans une base de données sécurisée
2. Distribution du fichier et du hash :
   • Mettre le fichier principal à disposition sur les serveurs de téléchargement
   • Publier le hash sur le site web officiel via HTTPS
   • Inclure le hash dans la documentation et les annonces de publication
3. Vérification par l'utilisateur :
   • L'utilisateur télécharge le fichier et la valeur de hash publiée
   • En utilisant un outil standard (comme shasum, certutil, ou Get-FileHash), l'utilisateur calcule localement le hash SHA-256 du fichier téléchargé
   • L'utilisateur compare ce hash calculé avec la valeur publiée
   • Si les hashes correspondent, le fichier a été téléchargé intégralement et sans altération
   • Si les hashes diffèrent, le fichier a été corrompu ou modifié et l'utilisateur doit réessayer le téléchargement ou signaler le problème

Distribution sécurisée des valeurs de hash :

La sécurité du processus repose sur la distribution sécurisée des valeurs de hash. Voici comment je gérerais cet aspect :

1. Publication multi-canal :
   • Publier les hashes sur le site web officiel via HTTPS (avec certificat SSL/TLS valide)
   • Inclure les hashes dans les annonces par email (signées avec DKIM)
   • Partager les hashes via les réseaux sociaux officiels
   • Fournir les hashes dans les dépôts Git/GitHub (signés avec GPG)
2. Signature numérique :
   • Signer numériquement le fichier de hashes avec la clé GPG de l'organisation
   • Publier la signature numérique aux côtés des hashes
   • Maintenir la clé publique GPG sur des serveurs de clés et sur le site web de l'organisation
3. Vérification de l'authenticité de la source :
   • Encourager les utilisateurs à vérifier le certificat SSL/TLS du site web
   • Documenter comment vérifier l'empreinte de la clé GPG utilisée pour signer les hashes
   • Établir un processus pour que les utilisateurs puissent signaler des incohérences
4. Transparence et auditabilité :
   • Conserver un historique public de toutes les versions de fichiers et leurs hashes correspondants
   • Documenter tout changement ou mise à jour des fichiers
   • Permettre à des tiers de vérifier indépendamment les hashes publiés

Cette approche multicouche garantit que même si un canal de distribution est compromis, les utilisateurs ont d'autres moyens de vérifier l'authenticité des hashes, renforçant ainsi considérablement la sécurité du processus de vérification d'intégrité.

Solution

Partie A : Identification des problèmes

Problème 1 : Stockage des mots de passe en clair

• Description : Les mots de passe sont stockés tels quels dans la base de données, sans aucun chiffrement ou hachage.
• Exploitation possible : Si un attaquant obtient un accès à la base de données (via une injection SQL, une vulnérabilité de l'application, une sauvegarde non sécurisée, etc.), il aura immédiatement accès à tous les mots de passe des utilisateurs.
• Impact : L'attaquant peut usurper l'identité de n'importe quel utilisateur sur le système. De plus, comme beaucoup d'utilisateurs réutilisent leurs mots de passe, l'attaquant pourrait accéder à leurs comptes sur d'autres services.

Problème 2 : Vulnérabilité à l'injection SQL

• Description : Bien que le code utilise des requêtes paramétrées, ce qui est une bonne pratique, la structure de la requête dans la fonction authenticate permet des attaques de type "time-based blind SQL injection".
• Exploitation possible : Un attaquant pourrait potentiellement extraire des informations en mesurant le temps de réponse des requêtes modifiées. De plus, si d'autres parties du code utilisent des requêtes non paramétrées, des attaques par injection SQL classiques seraient possibles.
• Impact : Un attaquant pourrait contourner l'authentification, extraire des données sensibles ou même modifier la structure de la base de données.

Problème 3 : Absence de validation et de sanitisation des entrées

• Description : Le code ne vérifie pas la validité des noms d'utilisateur et des mots de passe avant de les insérer dans la base de données ou de les utiliser pour l'authentification.
• Exploitation possible : Un attaquant pourrait créer des utilisateurs avec des noms spéciaux qui pourraient causer des problèmes (par exemple, des noms très longs, contenant des caractères spéciaux ou des séquences d'échappement).
• Impact : Cela pourrait conduire à des problèmes de fonctionnement, des dénis de service, ou potentiellement d'autres types d'exploitation.

Problème 4 : Pas de gestion de l'unicité des noms d'utilisateur

• Description : Le code ne vérifie pas si un nom d'utilisateur existe déjà avant d'en créer un nouveau.
• Exploitation possible : Un attaquant pourrait créer plusieurs comptes avec le même nom d'utilisateur, ce qui pourrait perturber la logique d'authentification.
• Impact : Confusion des utilisateurs, possibilité d'usurpation d'identité ou de contournement de certaines mesures de sécurité basées sur les noms d'utilisateur.

Problème 5 : Absence de limitation des tentatives et de journalisation

• Description : Il n'y a pas de mécanisme pour limiter le nombre de tentatives d'authentification échouées ou pour journaliser les activités suspectes.
• Exploitation possible : Un attaquant peut effectuer des attaques par force brute sans être détecté ni ralenti.
• Impact : Les attaques par force brute ou par dictionnaire deviennent beaucoup plus faciles à réaliser et peuvent rester non détectées pendant longtemps.

Partie B : Implémentation sécurisée

import sqlite3
import hashlib
import os
import re
from hmac import compare_digest
import time

# Essayer d'utiliser Argon2 si disponible (meilleure option actuelle)
try:
    from argon2 import PasswordHasher
    from argon2.exceptions import VerifyMismatchError
    USE_ARGON2 = True
except ImportError:
    USE_ARGON2 = False
    print("Argon2 non disponible. Utilisation de PBKDF2 comme alternative.")

def is_valid_username(username):
    """Vérifie si le nom d'utilisateur est valide."""
    # Limiter la longueur et les caractères autorisés
    if not isinstance(username, str) or len(username) < 3 or len(username) > 30:
        return False
    # Autoriser uniquement des caractères alphanumériques et quelques symboles
    return bool(re.match(r'^[a-zA-Z0-9_.-]+$', username))

def is_valid_password(password):
    """Vérifie si le mot de passe est suffisamment fort."""
    if not isinstance(password, str) or len(password) < 8:
        return False
    # Au moins une lettre majuscule, une minuscule, un chiffre et un caractère spécial
    has_upper = any(c.isupper() for c in password)
    has_lower = any(c.islower() for c in password)
    has_digit = any(c.isdigit() for c in password)
    has_special = any(not c.isalnum() for c in password)
    return has_upper and has_lower and has_digit and has_special

def hash_password_argon2(password):
    """Hache un mot de passe avec Argon2."""
    ph = PasswordHasher()
    return ph.hash(password)

def hash_password_pbkdf2(password):
    """Hache un mot de passe avec PBKDF2."""
    # Générer un sel aléatoire de 16 octets
    salt = os.urandom(16)
    # 100 000 itérations de PBKDF2 avec SHA-256
    key = hashlib.pbkdf2_hmac('sha256', password.encode('utf-8'), salt, 100000)
    # Stocker le sel avec le hachage
    return salt.hex() + '$' + key.hex()

def verify_password_argon2(stored_hash, provided_password):
    """Vérifie un mot de passe avec Argon2."""
    ph = PasswordHasher()
    try:
        ph.verify(stored_hash, provided_password)
        return True
    except VerifyMismatchError:
        return False

def verify_password_pbkdf2(stored_hash, provided_password):
    """Vérifie un mot de passe avec PBKDF2."""
    salt_hex, key_hex = stored_hash.split('$')
    salt = bytes.fromhex(salt_hex)
    key = bytes.fromhex(key_hex)
    new_key = hashlib.pbkdf2_hmac('sha256', provided_password.encode('utf-8'), salt, 100000)
    # Utiliser compare_digest pour une comparaison sécurisée (résistante aux attaques temporelles)
    return compare_digest(key, new_key)

class FailedAttemptsTracker:
    """Classe pour suivre et limiter les tentatives d'authentification échouées."""
    def __init__(self, max_attempts=5, lockout_time=300):  # 5 tentatives, 5 minutes de verrouillage
        self.attempts = {}
        self.max_attempts = max_attempts
        self.lockout_time = lockout_time
    
    def record_attempt(self, username, success):
        """Enregistre une tentative d'authentification."""
        current_time = time.time()
        
        # Nettoyer les anciennes entrées
        self.attempts = {u: (count, timestamp) for u, (count, timestamp) in self.attempts.items()
                       if current_time - timestamp < self.lockout_time}
        
        if not success:
            if username in self.attempts:
                count, _ = self.attempts[username]
                self.attempts[username] = (count + 1, current_time)
            else:
                self.attempts[username] = (1, current_time)
        else:
            # Réinitialiser le compteur en cas de succès
            self.attempts.pop(username, None)
    
    def is_locked_out(self, username):
        """Vérifie si un utilisateur est verrouillé."""
        if username not in self.attempts:
            return False
        
        count, timestamp = self.attempts[username]
        current_time = time.time()
        
        # Vérifier si le temps de verrouillage est écoulé
        if current_time - timestamp >= self.lockout_time:
            self.attempts.pop(username, None)
            return False
        
        return count >= self.max_attempts

# Initialiser le tracker de tentatives
attempts_tracker = FailedAttemptsTracker()

def init_database():
    """Initialise la base de données avec le schéma correct."""
    conn = sqlite3.connect('users.db')
    cursor = conn.cursor()
    cursor.execute('''
    CREATE TABLE IF NOT EXISTS users (
        id INTEGER PRIMARY KEY AUTOINCREMENT,
        username TEXT UNIQUE,
        password_hash TEXT,
        created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP
    )
    ''')
    
    # Table pour les journaux d'authentification
    cursor.execute('''
    CREATE TABLE IF NOT EXISTS auth_logs (
        id INTEGER PRIMARY KEY AUTOINCREMENT,
        username TEXT,
        success BOOLEAN,
        ip_address TEXT,
        timestamp TIMESTAMP DEFAULT CURRENT_TIMESTAMP
    )
    ''')
    
    conn.commit()
    conn.close()

def create_user(username, password):
    """Crée un nouvel utilisateur avec des vérifications de sécurité."""
    # Valider les entrées
    if not is_valid_username(username):
        raise ValueError("Nom d'utilisateur invalide")
    
    if not is_valid_password(password):
        raise ValueError("Mot de passe trop faible")
    
    conn = sqlite3.connect('users.db')
    cursor = conn.cursor()
    
    try:
        # Vérifier si l'utilisateur existe déjà
        cursor.execute('SELECT username FROM users WHERE username = ?', (username,))
        if cursor.fetchone():
            conn.close()
            raise ValueError(f"L'utilisateur {username} existe déjà")
        
        # Hacher le mot de passe
        if USE_ARGON2:
            password_hash = hash_password_argon2(password)
        else:
            password_hash = hash_password_pbkdf2(password)
        
        # Insérer le nouvel utilisateur
        cursor.execute('INSERT INTO users (username, password_hash) VALUES (?, ?)',
                      (username, password_hash))
        conn.commit()
        
        print(f"Utilisateur {username} créé avec succès")
        return True
    
    except Exception as e:
        conn.rollback()
        print(f"Erreur lors de la création de l'utilisateur: {e}")
        raise
    
    finally:
        conn.close()

def log_authentication_attempt(username, success, ip_address="127.0.0.1"):
    """Enregistre une tentative d'authentification dans les logs."""
    conn = sqlite3.connect('users.db')
    cursor = conn.cursor()
    cursor.execute(
        'INSERT INTO auth_logs (username, success, ip_address) VALUES (?, ?, ?)',
        (username, success, ip_address)
    )
    conn.commit()
    conn.close()

def authenticate(username, password, ip_address="127.0.0.1"):
    """Authentifie un utilisateur avec des mesures de sécurité renforcées."""
    # Vérifier le format du nom d'utilisateur
    if not is_valid_username(username):
        log_authentication_attempt(username, False, ip_address)
        return False
    
    # Vérifier si l'utilisateur est verrouillé
    if attempts_tracker.is_locked_out(username):
        print(f"Utilisateur {username} verrouillé en raison de trop nombreuses tentatives échouées")
        log_authentication_attempt(username, False, ip_address)
        return False
    
    conn = sqlite3.connect('users.db')
    cursor = conn.cursor()
    
    try:
        # Récupérer le hash stocké
        cursor.execute('SELECT password_hash FROM users WHERE username = ?', (username,))
        result = cursor.fetchone()
        
        if not result:
            # Prendre un temps constant même si l'utilisateur n'existe pas (protection contre les attaques temporelles)
            time.sleep(0.5)
            attempts_tracker.record_attempt(username, False)
            log_authentication_attempt(username, False, ip_address)
            return False
        
        stored_hash = result[0]
        
        # Vérifier le mot de passe
        if USE_ARGON2:
            success = verify_password_argon2(stored_hash, password)
        else:
            success = verify_password_pbkdf2(stored_hash, password)
        
        # Enregistrer la tentative
        attempts_tracker.record_attempt(username, success)
        log_authentication_attempt(username, success, ip_address)
        
        return success
    
    finally:
        conn.close()

# Initialisation
init_database()

# Exemple d'utilisation
try:
    create_user("admin", "SecureP@ss123")
    is_valid = authenticate("admin", "SecureP@ss123")
    print(f"Authentification réussie: {is_valid}")
except ValueError as e:
    print(e)
                    

Explications des améliorations :

1. Utilisation de fonctions de hachage adaptées :
   • Le code essaie d'abord d'utiliser Argon2, qui est actuellement considéré comme le meilleur algorithme pour le hachage de mots de passe
   • En fallback, il utilise PBKDF2 avec SHA-256, qui est également sécurisé
   • Ces algorithmes sont spécifiquement conçus pour être lents à calculer, ce qui rend les attaques par force brute beaucoup plus difficiles
2. Salage des mots de passe :
   • Chaque mot de passe est salé avec une valeur aléatoire unique (générée avec os.urandom)
   • Le sel est stocké avec le hash pour permettre la vérification ultérieure
   • Cela protège contre les attaques par tables précalculées (rainbow tables) et garantit que deux utilisateurs avec le même mot de passe auront des hashes différents
3. Mécanismes anti-force brute :
   • Implémentation d'un système de verrouillage temporaire après un certain nombre de tentatives échouées
   • Temps constant pour les vérifications, même pour les utilisateurs inexistants (protection contre les attaques temporelles)
4. Validation des entrées :
   • Vérification de la validité des noms d'utilisateur (longueur, caractères autorisés)
   • Exigences de complexité pour les mots de passe
5. Gestion de base de données améliorée :
   • Structure de table appropriée avec contrainte d'unicité sur les noms d'utilisateur
   • Journalisation des tentatives d'authentification
   • Gestion des erreurs avec des messages appropriés
6. Vérification sécurisée :
   • Utilisation de compare_digest pour une comparaison résistante aux attaques temporelles

Partie C : Scénario d'attaque

Supposons qu'un attaquant ait obtenu un accès en lecture à notre base de données d'utilisateurs. Voici comment se comparent les différentes méthodes de stockage face aux types d'attaques courants :

Analyse détaillée :

1. Stockage en texte clair

C'est la pire méthode possible, offrant zéro protection. Un attaquant qui a accès à la base de données obtient immédiatement tous les mots de passe sans avoir à faire le moindre effort. Cela compromet non seulement votre système, mais potentiellement tous les autres services où vos utilisateurs pourraient avoir réutilisé les mêmes mots de passe.

2. Simple hash MD5

MD5 a été conçu pour être rapide, ce qui est exactement l'opposé de ce que l'on souhaite pour le hachage de mots de passe. Avec du matériel moderne, on peut calculer des milliards de hashes MD5 par seconde. De plus :

• Des bases de données de millions de hashes MD5 précalculés existent en ligne
• MD5 a des vulnérabilités cryptographiques connues
• Des mots de passe identiques produisent des hashes identiques, révélant des motifs

Un attaquant pourrait récupérer la plupart des mots de passe dans un délai très court, particulièrement les plus communs.

3. Hash SHA-256 avec sel

Cette approche est nettement meilleure que les précédentes :

• SHA-256 est cryptographiquement plus sûr que MD5
• Le sel unique empêche l'utilisation de rainbow tables
• Deux utilisateurs avec le même mot de passe auront des hashes différents

Cependant, SHA-256 reste relativement rapide à calculer, ce qui permet encore des attaques par force brute à haute vitesse si l'attaquant dispose de ressources informatiques suffisantes.

4. Solution de la partie B (Argon2 ou PBKDF2)

Cette solution offre la meilleure protection :

• Argon2 est spécifiquement conçu pour le hachage de mots de passe et a gagné la compétition Password Hashing Competition en 2015. Il utilise non seulement du temps (itérations) mais aussi de la mémoire, ce qui le rend particulièrement résistant aux attaques utilisant des GPU ou des ASIC.
• PBKDF2 avec 100 000 itérations ralentit considérablement les attaques, obligeant l'attaquant à investir des ressources importantes pour tester chaque mot de passe candidat.
• Le sel aléatoire unique protège contre les rainbow tables et les motifs de reconnaissance.
• Les mécanismes supplémentaires (verrouillage après échecs, validation de complexité) ajoutent des couches de défense.

Avec cette solution, même avec un accès à la base de données, un attaquant aurait besoin d'un temps considérable et de ressources importantes pour récupérer des mots de passe, surtout s'ils sont complexes.

Conclusion :

La différence de sécurité entre ces méthodes est énorme. Alors qu'un stockage en texte clair ou un simple hash MD5 peut conduire à une compromission immédiate ou en quelques heures, une solution moderne utilisant Argon2 ou PBKDF2 correctement configuré pourrait résister pendant des années aux tentatives de récupération des mots de passe, même avec un accès direct à la base de données.

C'est pourquoi les standards modernes recommandent fortement l'utilisation d'algorithmes adaptés au hachage de mots de passe comme Argon2, bcrypt, ou PBKDF2 avec un nombre élevé d'itérations et un sel unique par utilisateur.

Solution

Partie A : Principe et implémentation

Principe de fonctionnement d'un arbre de Merkle :

Un arbre de Merkle (ou arbre de hachage) est une structure de données en arbre dans laquelle :

1. Chaque feuille (nœud terminal) contient le hash d'un bloc de données
2. Chaque nœud interne contient le hash de la concaténation des hashes de ses nœuds enfants
3. La racine (sommet de l'arbre) contient un seul hash qui représente de manière unique tout l'ensemble de données

Construction d'un arbre de Merkle :

1. On calcule d'abord le hash de chaque élément de données, formant les feuilles de l'arbre
2. Si le nombre de feuilles est impair, on duplique généralement la dernière feuille
3. On combine les hashes par paires (concaténation puis hachage) pour former le niveau supérieur
4. On répète ce processus jusqu'à obtenir un seul hash (la racine de Merkle)

Implémentation en Python :

import hashlib
from math import ceil, log2

def hash_data(data):
    """Calcule le hash SHA-256 des données fournies."""
    if isinstance(data, str):
        data = data.encode('utf-8')
    return hashlib.sha256(data).digest()

def build_merkle_tree(data_list):
    """
    Construit un arbre de Merkle à partir d'une liste de données.
    
    Args:
        data_list: Liste des éléments de données (chaînes ou bytes)
    
    Returns:
        Un tuple (racine_merkle, nœuds_par_niveau) où nœuds_par_niveau est un dictionnaire
        contenant les hashes à chaque niveau de l'arbre
    """
    if not data_list:
        raise ValueError("La liste de données ne peut pas être vide")
    
    # Calculer les hashes des feuilles (niveau 0)
    leaf_hashes = [hash_data(data) for data in data_list]
    
    # Nous allons stocker tous les nœuds de l'arbre, niveau par niveau
    nodes_by_level = {0: leaf_hashes}
    
    # Construire l'arbre niveau par niveau
    current_level = 0
    current_nodes = leaf_hashes
    
    while len(current_nodes) > 1:
        current_level += 1
        next_level_nodes = []
        
        # Traiter les nœuds par paires
        for i in range(0, len(current_nodes), 2):
            # Si nous avons un nombre impair de nœuds, dupliquer le dernier
            if i + 1 >= len(current_nodes):
                pair = current_nodes[i] + current_nodes[i]
            else:
                pair = current_nodes[i] + current_nodes[i + 1]
            
            # Calculer le hash de la paire
            next_level_nodes.append(hash_data(pair))
        
        # Stocker les nœuds de ce niveau
        nodes_by_level[current_level] = next_level_nodes
        current_nodes = next_level_nodes
    
    # La racine est le seul nœud du dernier niveau
    merkle_root = current_nodes[0]
    
    return merkle_root, nodes_by_level

def get_merkle_root(data_list):
    """Version simplifiée qui renvoie uniquement la racine de Merkle."""
    merkle_root, _ = build_merkle_tree(data_list)
    return merkle_root

# Exemple d'utilisation
def example_merkle_tree():
    # Données d'exemple
    data = ["Transaction 1", "Transaction 2", "Transaction 3", "Transaction 4", "Transaction 5"]
    
    # Construire l'arbre de Merkle
    merkle_root, nodes_by_level = build_merkle_tree(data)
    
    # Afficher l'arbre niveau par niveau
    print("Arbre de Merkle:")
    for level, nodes in sorted(nodes_by_level.items()):
        print(f"Niveau {level}:")
        for i, node in enumerate(nodes):
            # Afficher seulement les 10 premiers caractères du hash en hexadécimal pour la lisibilité
            print(f"  Nœud {i}: {node.hex()[:10]}...")
    
    print(f"\nRacine de Merkle: {merkle_root.hex()}")
    
    return merkle_root, nodes_by_level

# Exécuter l'exemple
merkle_root, nodes_by_level = example_merkle_tree()
                    

Cette implémentation construit un arbre de Merkle complet et retourne à la fois la racine et tous les nœuds intermédiaires organisés par niveau. Cela sera utile pour la partie B où nous devrons générer des preuves d'inclusion.

Partie B : Preuve d'inclusion

Qu'est-ce qu'une preuve d'inclusion ?

Une preuve d'inclusion (ou preuve de Merkle) est un ensemble minimal de hashes qui permet à quelqu'un de vérifier qu'un élément spécifique fait partie d'un ensemble de données, sans avoir besoin de connaître tous les éléments de cet ensemble. La preuve consiste en :

1. Le hash de l'élément concerné
2. Un ensemble de hashes "frères" le long du chemin de l'élément jusqu'à la racine
3. Des informations sur la position (gauche/droite) de chaque hash frère

Avec ces informations et l'élément original, on peut recalculer la racine de Merkle et la comparer avec la racine connue pour vérifier l'inclusion.

Implémentation de la génération de preuve :

def generate_merkle_proof(data_list, target_data_index):
    """
    Génère une preuve d'inclusion pour un élément spécifique dans l'arbre de Merkle.
    
    Args:
        data_list: Liste des éléments de données
        target_data_index: Index de l'élément pour lequel générer la preuve
    
    Returns:
        Un tuple (merkle_root, proof) où proof est une liste de tuples (hash, position)
        position est 'left' ou 'right' indiquant si le hash doit être combiné à gauche ou à droite
    """
    if target_data_index < 0 or target_data_index >= len(data_list):
        raise ValueError("Index cible hors limites")
    
    # Construire l'arbre complet
    merkle_root, nodes_by_level = build_merkle_tree(data_list)
    
    # Initialiser la preuve
    proof = []
    
    # Déterminer la position de l'élément cible à chaque niveau
    current_index = target_data_index
    
    for level in range(len(nodes_by_level) - 1):  # Tous les niveaux sauf le dernier (racine)
        current_level_nodes = nodes_by_level[level]
        is_right_node = current_index % 2 == 1
        
        if is_right_node:
            # Si l'élément cible est à droite, nous avons besoin du hash à gauche
            sibling_index = current_index - 1
            sibling_position = 'left'
        else:
            # Si l'élément cible est à gauche, nous avons besoin du hash à droite
            sibling_index = current_index + 1
            # Si c'est le dernier élément et qu'il n'a pas de frère, on utilise lui-même
            if sibling_index >= len(current_level_nodes):
                sibling_index = current_index
            sibling_position = 'right'
        
        # Ajouter le hash frère à la preuve
        proof.append((current_level_nodes[sibling_index], sibling_position))
        
        # Passer au niveau suivant (parent)
        current_index = current_index // 2
    
    return merkle_root, proof

def verify_merkle_proof(target_data, proof, merkle_root):
    """
    Vérifie une preuve d'inclusion pour un élément donné.
    
    Args:
        target_data: L'élément de données à vérifier
        proof: La preuve générée par generate_merkle_proof
        merkle_root: La racine de Merkle connue
    
    Returns:
        True si la preuve est valide, False sinon
    """
    # Calculer le hash initial de la donnée cible
    current_hash = hash_data(target_data)
    
    # Reconstruire le chemin jusqu'à la racine
    for sibling_hash, position in proof:
        if position == 'left':
            # Le hash frère va à gauche
            combined = sibling_hash + current_hash
        else:
            # Le hash frère va à droite
            combined = current_hash + sibling_hash
        
        # Calculer le hash parent
        current_hash = hash_data(combined)
    
    # Vérifier si le hash final correspond à la racine de Merkle
    return current_hash == merkle_root

# Exemple d'utilisation des preuves
def example_merkle_proof():
    # Données d'exemple
    data = ["Transaction 1", "Transaction 2", "Transaction 3", "Transaction 4", "Transaction 5"]
    
    # Générer une preuve pour la Transaction 3 (index 2)
    target_index = 2
    merkle_root, proof = generate_merkle_proof(data, target_index)
    
    print(f"Preuve pour '{data[target_index]}':")
    for i, (hash_value, position) in enumerate(proof):
        print(f"  Niveau {i}: {hash_value.hex()[:10]}... (position: {position})")
    
    # Vérifier la preuve
    is_valid = verify_merkle_proof(data[target_index], proof, merkle_root)
    print(f"\nVérification de la preuve: {'Succès' if is_valid else 'Échec'}")
    
    # Tester avec des données modifiées
    modified_data = "Transaction 3 modifiée"
    is_valid_modified = verify_merkle_proof(modified_data, proof, merkle_root)
    print(f"Vérification avec données modifiées: {'Succès' if is_valid_modified else 'Échec, comme attendu'}")
    
    return merkle_root, proof

# Exécuter l'exemple
example_merkle_proof()
                    

Explication de la génération de preuve :

1. Pour générer une preuve, nous déterminons d'abord la position de l'élément cible dans l'arbre
2. Nous remontons l'arbre niveau par niveau, en collectant à chaque fois le "hash frère" (le nœud avec lequel notre élément se combine)
3. Nous enregistrons également la position (gauche ou droite) de chaque hash frère pour permettre une reconstruction correcte du chemin

Explication de la vérification de preuve :

1. Nous commençons par calculer le hash de l'élément cible
2. Nous utilisons les hashes frères fournis dans la preuve pour recalculer les nœuds parents, niveau par niveau
3. Si la racine calculée correspond à la racine de Merkle connue, alors l'élément fait bien partie de l'ensemble original

Partie C : Application à la blockchain

Utilisation des arbres de Merkle dans les blockchains :

Dans les blockchains comme Bitcoin, chaque bloc contient un grand nombre de transactions (plusieurs centaines voire milliers). Au lieu de stocker simplement une liste de toutes ces transactions, les blockchains utilisent un arbre de Merkle pour créer un résumé cryptographique compact de toutes les transactions du bloc.

Fonctionnement dans Bitcoin :

1. Chaque transaction est hachée pour former une feuille de l'arbre de Merkle
2. Les hashes sont combinés par paires jusqu'à obtenir une racine unique (appelée "merkle root")
3. Cette racine est incluse dans l'en-tête du bloc, qui est lui-même haché dans le processus de minage
4. Lorsqu'un nouveau bloc est ajouté à la blockchain, son en-tête inclut le hash du bloc précédent, formant une chaîne de blocs liés cryptographiquement

Avantages des arbres de Merkle dans les blockchains :

1. Vérification efficace des transactions (SPV - Simplified Payment Verification) :
   • Les clients légers (comme les portefeuilles mobiles) n'ont pas besoin de télécharger l'intégralité de la blockchain
   • Ils peuvent vérifier qu'une transaction spécifique est incluse dans un bloc en demandant uniquement une preuve de Merkle
   • Cette preuve est de taille logarithmique (O(log n)) par rapport au nombre de transactions, au lieu de linéaire (O(n))
   • Exemple : Pour vérifier 1 transaction parmi 1 million, il suffit d'environ 20 hashes (~640 octets) au lieu de 32 Mo de données
2. Intégrité des données :
   • Une modification de n'importe quelle transaction dans le bloc changerait la racine de Merkle
   • Cela changerait l'en-tête du bloc, ce qui modifierait son hash
   • Ce changement invalidrait la chaîne, car chaque bloc contient le hash du bloc précédent
   • Pour falsifier une transaction, un attaquant devrait recalculer tous les blocs suivants (ce qui nécessiterait plus de puissance de calcul que le reste du réseau combiné)
3. Réduction de l'espace de stockage :
   • Les nœuds complets peuvent "élaguer" (pruning) certaines parties de l'arbre une fois qu'elles ont été validées
   • Seuls les en-têtes de blocs et les branches pertinentes peuvent être conservés
4. Parallélisation :
   • La construction et la vérification des arbres de Merkle peuvent être parallélisées efficacement
   • Différentes branches de l'arbre peuvent être traitées simultanément

Comparaison avec une simple liste de hashes :

Exemple concret dans Bitcoin :

Prenons l'exemple d'un portefeuille Bitcoin léger qui veut vérifier si une transaction le concernant est incluse dans la blockchain :

1. Le portefeuille possède les en-têtes des blocs (environ 80 octets chacun, incluant la racine de Merkle)
2. Pour vérifier une transaction, il demande à un nœud complet la transaction elle-même et sa preuve de Merkle
3. Avec environ 20 hashes (pour un bloc de ~1 million de transactions), le portefeuille peut vérifier que la transaction est dans le bloc
4. Le portefeuille n'a pas besoin de télécharger ou de vérifier les autres transactions du bloc (potentiellement des gigaoctets de données)

Cette efficacité est cruciale pour permettre l'utilisation de Bitcoin sur des appareils à ressources limitées, comme les smartphones, sans compromettre la sécurité fondamentale du système.

Conclusion :

Les arbres de Merkle sont une composante fondamentale qui rend les blockchains pratiques et évolutives. Leur capacité à fournir des résumés cryptographiques compacts et des preuves d'inclusion efficaces est essentielle pour concilier la sécurité, la décentralisation et l'efficacité des systèmes blockchain.

Solution

Partie A : Définition et propriétés

Définition d'une fonction de hachage à sens unique avec trappe :

Une fonction de hachage à sens unique avec trappe est une fonction mathématique qui :

1. Est facile à calculer dans un sens (le sens direct)
2. Est extrêmement difficile à inverser (calculer dans le sens inverse) si l'on ne dispose pas d'une information secrète
3. Devient facile à inverser si l'on possède une information particulière appelée "trappe" ou "porte dérobée"

Différences avec les fonctions de hachage cryptographiques standards :

Propriétés essentielles d'une bonne fonction à sens unique avec trappe :

1. Efficacité calculatoire dans le sens direct : La fonction doit être rapide à calculer pour tous les utilisateurs.
2. Difficulté d'inversion sans la trappe : Sans la trappe, inverser la fonction doit être calculatoirement infaisable, même avec des ressources informatiques importantes.
3. Efficacité d'inversion avec la trappe : Avec la connaissance de la trappe, l'inversion doit être rapide et précise.
4. Sécurité de la trappe : Il doit être impossible ou extrêmement difficile de déduire la trappe à partir de la description publique de la fonction.
5. Robustesse : La fonction doit résister aux avancées en cryptanalyse et aux améliorations algorithmiques au fil du temps.
6. Distribution uniforme : L'image de la fonction doit être uniformément distribuée dans l'espace de sortie pour maximiser l'entropie.

Partie B : Applications

1. Chiffrement à clé publique (comme RSA)

Les systèmes de chiffrement à clé publique comme RSA sont directement basés sur des fonctions à sens unique avec trappe :

• Fonction directe : Le chiffrement, qui utilise la clé publique pour transformer un message clair en message chiffré.
• Trappe : La clé privée, qui permet de déchiffrer efficacement le message.
• Intérêt pratique : Permet l'échange sécurisé d'informations sans partage préalable de secret, fondement du e-commerce et des communications sécurisées sur Internet.

Exemple concret : Lorsque vous vous connectez à un site web en HTTPS, votre navigateur utilise la clé publique du serveur (fournie dans son certificat) pour chiffrer la clé de session. Seul le serveur, possédant la trappe (clé privée), peut déchiffrer cette clé et établir une communication sécurisée.

2. Signatures numériques

Les signatures numériques utilisent les fonctions à sens unique avec trappe de manière inversée :

• Fonction directe modifiée : Le calcul de la signature utilise la clé privée (la trappe) pour signer un message ou son hash.
• Vérification : N'importe qui peut vérifier la signature avec la clé publique, mais ne peut pas la produire sans la clé privée.
• Intérêt pratique : Garantit l'authenticité et la non-répudiation des documents électroniques, essentiel pour les contrats, les certificats, les mises à jour logicielles, etc.

Exemple concret : Les mises à jour d'applications sur smartphone sont signées par les développeurs avec leur clé privée. Votre téléphone vérifie cette signature avec la clé publique correspondante avant d'installer la mise à jour, garantissant qu'elle provient bien de la source officielle.

3. Certificats numériques et infrastructures à clés publiques (PKI)

Les certificats numériques, qui lient une identité à une clé publique, reposent sur les signatures numériques et donc sur les fonctions à sens unique avec trappe :

• Création : Une autorité de certification (CA) utilise sa clé privée pour signer un certificat contenant une clé publique et des informations d'identité.
• Vérification : Tout le monde peut vérifier l'authenticité du certificat avec la clé publique de la CA.
• Intérêt pratique : Permet d'établir une chaîne de confiance pour authentifier les entités sur les réseaux, fondement de la sécurité des navigateurs web et de nombreux protocoles sécurisés.

Exemple concret : Quand vous visitez un site web sécurisé, votre navigateur vérifie que le certificat du site a été signé par une autorité de certification reconnue, garantissant ainsi l'identité du site.

4. Systèmes de preuves à connaissance nulle (Zero-Knowledge Proofs)

Certains systèmes de preuves à connaissance nulle utilisent des fonctions à sens unique avec trappe pour permettre à une partie de prouver qu'elle connaît un secret sans révéler ce secret :

• Engagement : Le prouveur utilise une fonction à sens unique pour créer un engagement basé sur sa connaissance secrète.
• Vérification : Grâce à des protocoles d'interaction, le vérificateur peut s'assurer que le prouveur connaît la trappe sans que celle-ci ne soit révélée.
• Intérêt pratique : Permet l'authentification préservant la vie privée, les transactions confidentielles dans les blockchains, et diverses applications où la confidentialité est cruciale.

Exemple concret : Les crypto-monnaies axées sur la confidentialité comme Zcash utilisent des preuves à connaissance nulle pour permettre des transactions vérifiables tout en préservant l'anonymat des participants.

5. Cryptographie post-quantique à base de treillis

Face à la menace des ordinateurs quantiques, certains systèmes post-quantiques sont basés sur de nouvelles fonctions à sens unique avec trappe :

• Fonction directe : Des opérations sur des treillis ou d'autres structures mathématiques complexes.
• Trappe : Des informations sur la structure spécifique du treillis ou d'autres paramètres secrets.
• Intérêt pratique : Fournit une alternative aux systèmes comme RSA qui seraient vulnérables face à un ordinateur quantique suffisamment puissant.

Exemple concret : NTRU et CRYSTALS-Kyber, des finalistes de la standardisation post-quantique du NIST, utilisent des fonctions à sens unique avec trappe basées sur des problèmes de treillis considérés résistants aux attaques quantiques.

Partie C : Exemple mathématique

La factorisation comme fonction à sens unique avec trappe :

La multiplication de deux grands nombres premiers est rapide à calculer, mais la factorisation du produit obtenu est extrêmement difficile sans information supplémentaire :

• Fonction directe : Multiplier deux grands nombres premiers p et q pour obtenir n = p × q
• Problème inverse : Étant donné n, trouver ses facteurs premiers p et q
• Trappe : La connaissance préalable de p et q

Exemple simple de RSA :

Voici un exemple très simplifié de RSA utilisant de petits nombres (dans la pratique, on utilise des nombres de plusieurs centaines de chiffres) :

1. Génération des clés :
   • Choisir deux nombres premiers : p = 11 et q = 13
   • Calculer n = p × q = 11 × 13 = 143
   • Calculer φ(n) = (p-1) × (q-1) = 10 × 12 = 120
   • Choisir e tel que 1 < e < φ(n) et e est premier avec φ(n), par exemple e = 7
   • Calculer d tel que (d × e) mod φ(n) = 1, ici d = 103 (car 7 × 103 = 721 = 1 + 6 × 120)
   • Clé publique : (n=143, e=7)
   • Clé privée (trappe) : (n=143, d=103)
2. Chiffrement :
   • Pour un message m = 9 :
   • Chiffré c = m^e mod n = 9^7 mod 143 = 4782969 mod 143 = 48
3. Déchiffrement :
   • Avec la clé privée (la trappe) : m = c^d mod n = 48^103 mod 143
   • Ce calcul est complexe à la main, mais avec la trappe, on trouve m = 9

Comment la fonction à sens unique avec trappe fonctionne dans RSA :

1. Fonction directe : Le chiffrement (élévation à la puissance e modulo n) est facile à calculer même pour de très grands nombres.
2. Difficulté d'inversion sans la trappe : Sans connaître d (qui dépend de la factorisation de n), il est extrêmement difficile de retrouver m à partir de c.
3. Trappe : La connaissance de d (ou de la factorisation de n en p et q) permet de calculer facilement m à partir de c.

Relation avec la factorisation :

La sécurité de RSA repose sur la difficulté de factoriser n. Si un attaquant pouvait factoriser n pour obtenir p et q, il pourrait :

1. Calculer φ(n) = (p-1) × (q-1)
2. Calculer d = e^(-1) mod φ(n) (l'inverse modulaire de e)
3. Utiliser d pour déchiffrer n'importe quel message

C'est pourquoi dans RSA pratique, on utilise des nombres premiers p et q de taille suffisante (généralement 1024 bits chacun ou plus) pour rendre la factorisation infaisable avec les moyens de calcul actuels.

Exemple de calcul pas à pas :

Pour illustrer la simplicité des calculs avec la trappe et la difficulté sans celle-ci, prenons un chiffrement et un déchiffrement avec de petits nombres :

Conclusion :

Les fonctions à sens unique avec trappe, comme celle utilisée dans RSA, sont au cœur de la cryptographie asymétrique. Elles permettent de créer des systèmes où :

• Tout le monde peut chiffrer des messages (ou vérifier des signatures) facilement
• Seul le détenteur de la clé privée (la trappe) peut déchiffrer (ou créer des signatures)
• La sécurité repose sur des problèmes mathématiquement difficiles, comme la factorisation de grands nombres

Cette asymétrie fondamentale entre le coût calculatoire des opérations avec et sans la trappe est ce qui rend possibles de nombreuses applications cryptographiques modernes.