Fonctions de hachage cryptographiques

Dans cette leçon, nous allons examiner les fonctions de hachage cryptographiques qui sont largement utilisées pour la validation rapide et l'authentification.

À la fin de la leçon, nous aurons abordé :

• Ce que sont les fonctions de hachage cryptographiques
• Des exemples de code Python illustrant l'utilisation des fonctions de hachage
• Un aperçu des applications du hachage cryptographique
• La sécurité du hachage cryptographique
• Les menaces pesant sur ces algorithmes, tant du côté des ordinateurs classiques que quantiques

Introduction au hachage cryptographique

Les fonctions de hachage constituent un outil précieux en cryptographie, car elles permettent la validation tout en garantissant la confidentialité. À ce titre, elles forment un composant important des mécanismes d'authentification et d'intégrité des données, tels que les codes d'authentification de message basés sur le hachage (HMAC) et les signatures numériques. Cet article présente les idées fondamentales et les considérations de sécurité qui sous-tendent les fonctions de hachage cryptographiques, ainsi que les vulnérabilités potentielles liées à l'émergence de l'informatique quantique.

Principe de base et conception des fonctions de hachage

Il existe de nombreuses situations où l'authentification et la vérification d'intégrité doivent être réalisées efficacement, sans révéler d'informations privées à la partie effectuant la validation.

Par exemple, lors du téléchargement d'un logiciel depuis un serveur distant, un mécanisme efficace est nécessaire pour vérifier que le logiciel téléchargé n'a pas été modifié depuis sa création par l'auteur original. De même, lors de l'authentification des utilisateurs d'applications web, il serait souhaitable d'utiliser un mécanisme qui n'implique pas de stocker ou de transmettre les mots de passe en clair, ce qui pourrait compromettre leur confidentialité.

Les fonctions de hachage cryptographiques (FHC) répondent à ces besoins de manière efficace et sécurisée.

Fondamentalement, une fonction de hachage cryptographique prend une entrée (ou message) de longueur arbitraire et retourne une chaîne de n bits de taille fixe en sortie. La sortie d'une FHC est également appelée condensat (ou digest). Une FHC utile doit satisfaire plusieurs propriétés clés :

1. Uniformité : Les condensats produits par une FHC doivent être distribués uniformément et avoir l'air aléatoires. L'objectif est de s'assurer que la sortie ne révèle aucune information sur l'entrée.
2. Déterminisme : Pour une entrée donnée, une FHC doit toujours produire le même condensat, c'est-à-dire qu'elle doit être déterministe.
3. Irréversibilité : Une FHC est une fonction à sens unique : étant donné un condensat, il doit être impossible en pratique d'inverser le hachage pour retrouver l'entrée.
4. Injectivité approximative : Bien que les FHC soient des fonctions plusieurs-à-un, elles doivent paraître être des fonctions un-à-un. Cela est obtenu en combinant un espace de sortie de taille immense avec l'effet avalanche, par lequel de minuscules modifications de l'entrée entraînent des condensats radicalement différents. Cette caractéristique est connue sous le nom d'injectivité approximative.

Cela permet de valider une donnée par rapport à l'original en comparant le condensat de la donnée au condensat de l'original.

• Si les deux condensats correspondent, on peut affirmer avec une forte probabilité que la donnée est identique à l'original.
• Si les condensats diffèrent, on peut être certain que la donnée a été altérée ou qu'elle n'est pas authentique.

Comme les condensats d'une FHC ne révèlent pas le contenu réel des données ou de l'original, ils permettent la validation tout en préservant la confidentialité.

Mathematical description

Une fonction de hachage $H$ peut être définie comme :

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

où $Σ^*$ est l'ensemble de toutes les chaînes possibles, que l'on peut considérer comme des chaînes binaires de longueur quelconque.

Le fait que la taille du domaine d'entrée $Σ^*$ de $H$ soit illimitée, tandis que celle du codomaine $\{0,1\}^n$ est bornée, implique que $H$ est nécessairement une application plusieurs-à-un, faisant correspondre une infinité d'entrées à toute chaîne de n bits.

Les propriétés d'uniformité et de déterminisme sont bien encapsulées dans le modèle de l'oracle aléatoire du hachage cryptographique.

Exemple de hachage cryptographique en Python avec SHA-256

Cet exemple simple illustre le hachage cryptographique à l'aide du populaire algorithme SHA-256 fourni par la bibliothèque Python cryptography. On montre d'abord comment une légère différence dans les textes en clair entraîne une très grande différence dans les condensats.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

# Begin by importing some necessary modules
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes

# Helper function that returns the number of characters different in two strings
def char_diff(str1, str2):
    return sum(str1[i] != str2[i] for i in range(len(str1)))

# Messages to be hashed
message_1 = b"Buy 10000 shares of WXYZ stock now!"
message_2 = b"Buy 10000 shares of VXYZ stock now!"

print(f"The two messages differ by { char_diff(message_1, message_2)} characters")

The two messages differ by 1 characters

Les deux messages diffèrent par exactement un caractère.

Ensuite, on instancie des objets hash pour activer le processus de hachage, qui implique des appels à deux méthodes : update et finalize.

On constate que, grâce à l'effet avalanche dans la FHC SHA-256, une différence d'un caractère dans les messages d'entrée produit deux condensats très différents.

# Create new SHA-256 hash objects, one for each message
chf_1 = hashes.Hash(hashes.SHA256(), backend=default_backend())
chf_2 = hashes.Hash(hashes.SHA256(), backend=default_backend())

# Update each hash object with the bytes of the corresponding message
chf_1.update(message_1)
chf_2.update(message_2)

# Finalize the hash process and obtain the digests
digest_1 = chf_1.finalize()
digest_2 = chf_2.finalize()

# Convert the resulting hash to hexadecimal strings for convenient printing
digest_1_str = digest_1.hex()
digest_2_str = digest_2.hex()

# Print out the digests as strings
print(f"digest-1: {digest_1_str}")
print(f"digest-2: {digest_2_str}")

print(f"The two digests differ by { char_diff(digest_1_str, digest_2_str)} characters")

digest-1: 6e0e6261b7131bd80ffdb2a4d42f9d042636350e45e184b92fcbcc9646eaf1e7
digest-2: 6b0abb368c3a1730f935b68105e3f3ae7fd43d7e786d3ed3503dbb45c74ada46
The two digests differ by 57 characters

Applications du hachage cryptographique

Les propriétés uniques des FHC les rendent adaptées à un large éventail d'applications :

• Vérification de l'intégrité des données : Les fonctions de hachage peuvent être utilisées pour créer une somme de contrôle pour un ensemble de données. Toute modification des données, intentionnelle ou non, entraînera une somme de contrôle différente, alertant les systèmes ou les utilisateurs du changement. La somme de contrôle est également généralement bien plus compacte que les données originales, ce qui rend les comparaisons de sommes de contrôle très rapides.

Figure 1. Hachage sécurisé pour la vérification de l'intégrité des données

• Signatures numériques : Les hachages cryptographiques sont essentiels au fonctionnement des signatures numériques, car ils impliquent la comparaison de messages hachés cryptographiquement pour établir l'authenticité et l'intégrité tout en préservant la confidentialité.

Figure 2. Signatures numériques

• Blockchain et cryptomonnaies : Les cryptomonnaies comme Bitcoin s'appuient fortement sur les FHC, notamment pour assurer l'intégrité des transactions et permettre des mécanismes de consensus comme la preuve de travail (proof of work).

Sécurité du hachage cryptographique

La sécurité d'une FHC est généralement évaluée en fonction de sa résistance à deux types d'attaques : les attaques par pré-image et les attaques par collision.

Résistance aux attaques par pré-image

La résistance aux attaques par pré-image signifie que, étant donné un condensat, il doit être impossible en pratique de retrouver l'entrée.

Cela est lié à la propriété de sens unique des FHC.

Une bonne FHC est conçue de telle sorte qu'un attaquant souhaitant mener une attaque par pré-image n'a pas d'autre option qu'une approche par force brute, dont la complexité temporelle est $2^n$.

mathematical details

Étant donnés une FHC $H$ et un condensat $g$, il doit être computationnellement impossible de trouver une entrée $m$ appartenant à la pré-image de $g$ telle que $H(m) = g$.

Résistance aux collisions

La résistance aux collisions signifie qu'il est difficile de trouver deux entrées différentes qui produisent le même condensat.

Une collision de hachage cryptographique se produit lorsque deux entrées produisent le même condensat. Bien que les collisions existent inévitablement compte tenu de la nature plusieurs-à-un des FHC, une bonne FHC rend néanmoins impossible de les localiser à volonté.

La résistance aux collisions est cruciale pour des applications comme les signatures numériques et les certificats, où il serait désastreux qu'un acteur malveillant soit capable de créer un faux qui produit le même hachage.

mathematical details of hash collisions

$m_1, m_2$ peuvent être trouvés tels que $H(m_1) = H(m_2)$.

Longueur du hachage

La résistance aux collisions est une exigence plus stricte que la résistance aux attaques par pré-image et nécessite des longueurs de sortie deux fois plus grandes que celles nécessaires pour la résistance aux pré-images. Cela est dû au fait qu'une attaque par force brute connue sous le nom d'attaque des anniversaires, qui peut être utilisée pour identifier des collisions de hachage, a une complexité temporelle de $2^{n/2}$.

En l'absence de faiblesses cryptanalytiques, la sécurité d'une fonction de hachage est donc principalement influencée par sa longueur. Plus le hachage est long, plus il est sécurisé, car il devient plus difficile de mener des attaques par force brute.

Fonctions de hachage cryptographiques couramment utilisées

Le tableau suivant liste certaines fonctions de hachage cryptographiques couramment utilisées, avec leurs longueurs de sortie et leurs principaux domaines d'application :

Fonction de hachage	Longueur de sortie (bits)	Applications courantes
MD5	128	Vérification d'intégrité de fichiers, anciens systèmes, usages non-crypto
SHA-1	160	Systèmes legacy, Git pour le contrôle de version
SHA-256	256	Cryptomonnaies (Bitcoin), signatures numériques, certificats
SHA-3	Variable (jusqu'à 512)	Diverses applications cryptographiques, successeur de SHA-2
Blake2	Variable (jusqu'à 512)	Cryptographie, remplacement de MD5/SHA-1 dans certains systèmes
Blake3	Variable (jusqu'à 256)	Cryptographie, hachage de fichiers, intégrité des données

• MD5 et SHA-1, bien qu'encore utilisés dans des applications moins sensibles, sont considérés comme obsolètes en termes de résistance aux collisions et ne sont pas recommandés pour les nouveaux systèmes. SHA-256, qui fait partie de la famille SHA-2, est largement utilisé et actuellement sécurisé pour la plupart des applications.
• SHA-3 est une norme plus récente qui a été sélectionnée par le NIST en 2015 comme vainqueur de la compétition de fonctions de hachage du NIST. Il est conçu pour être un remplacement direct de SHA-2, mais il présente également des caractéristiques internes différentes et est résistant à certains types d'attaques qui pourraient être efficaces contre SHA-2.
• Blake2 et Blake3 sont des fonctions de hachage cryptographiques plus rapides que MD5, SHA-1, SHA-2 et SHA-3, tout en étant au moins aussi sécurisées que la dernière norme, SHA-3. Elles sont de plus en plus utilisées dans les nouveaux systèmes, notamment là où la vitesse est importante.

Risques quantiques pour le hachage cryptographique traditionnel

La principale menace quantique pour le hachage cryptographique vient des attaques par force brute.

Étant donné un condensat particulier, un attaquant va essayer des entrées aléatoires jusqu'à en trouver une qui produit le même condensat.

Avec $n$ bits dans l'entrée, il y a $2^n$ valeurs possibles. L'attaquant doit donc essayer environ $2^{n-1}$ entrées pour avoir plus de 50 % de chances de succès.

L'algorithme de Grover

Pour un tel contexte de recherche non structurée, l'algorithme de Grover peut fournir une accélération quadratique grâce à une technique connue sous le nom d'amplification d'amplitude quantique, réduisant la complexité temporelle d'une attaque par pré-image à $2^{n/2}$.

En termes pratiques, cela signifie qu'une FHC de 256 bits, actuellement considérée comme sécurisée contre les attaques par pré-image par les ordinateurs classiques, offrirait le même niveau de sécurité qu'une FHC de 128 bits face à un attaquant quantique utilisant l'algorithme de Grover.

L'algorithme de Grover seul n'est pas connu pour fournir des accélérations quantiques supplémentaires en ce qui concerne les attaques par collision, au-delà de la limite fixée par l'attaque des anniversaires, qui peut être menée sur des ordinateurs classiques. Puisque l'attaque des anniversaires classique oblige déjà les FHC à utiliser des longueurs de hachage deux fois plus grandes que nécessaire pour la résistance aux pré-images, le fait que la recherche de Grover divise effectivement par deux la longueur du hachage pour les attaques par pré-image ne constitue pas une menace pratique.

Par exemple, dans le cas de SHA-256, effectuer de l'ordre de $2^{128}$ opérations pour exécuter une attaque par pré-image assistée par Grover resterait impossible dans un avenir prévisible.

L'algorithme BHT

Un algorithme quantique qui combine des aspects de l'attaque des anniversaires et de la recherche de Grover a été proposé en 1997 par Brassard, Høyer et Tapp (BHT) et permet une mise à l'échelle théorique de $O(2^{n/3})$ pour trouver des collisions de hachage. Cependant, cette mise à l'échelle améliorée est conditionnée à l'existence de la technologie de mémoire quantique à accès aléatoire QRAM, qui n'existe pas encore à ce jour.

Sans QRAM, la mise à l'échelle réalisable est $\tilde{O}(2^{2n/5})$ et, pour les longueurs de hachage actuellement en usage, cette amélioration marginale de la capacité à trouver des collisions par rapport à l'attaque des anniversaires ne représente pas une menace critique.

Résumé

Les fonctions de hachage cryptographiques sont un composant essentiel pour garantir l'intégrité et la confidentialité des données dans les systèmes d'information numériques, et elles sont largement utilisées dans de nombreux contextes.

Les exigences de sécurité des FHC sont principalement comprises en termes de résistance aux attaques par pré-image et aux collisions. Pour les FHC bien conçues, la longueur du hachage est un bon indicateur du niveau de sécurité.

Bien que l'avènement des ordinateurs quantiques exécutant les algorithmes de Grover et BHT affecte en théorie la résistance aux pré-images et aux collisions des FHC traditionnelles, les longues longueurs de hachage déjà utilisées aujourd'hui signifient que les algorithmes de hachage cryptographique modernes, comme SHA-3, resteront probablement sécurisés, sauf découverte d'attaques cryptanalytiques encore inconnues.

L'importance des FHC réside dans leur rôle de brique fondamentale pour les schémas cryptographiques résistants aux attaques quantiques, garantissant que l'information numérique reste sécurisée même face aux avancées futures potentielles des algorithmes et technologies informatiques quantiques.