Fonction de compression unidirectionnelle - One-way compression function

En cryptographie , une fonction de compression unidirectionnelle est une fonction qui transforme deux entrées de longueur fixe en une sortie de longueur fixe. La transformation est "à sens unique" , ce qui signifie qu'il est difficile, étant donné une sortie particulière, de calculer les entrées qui se compressent à cette sortie. Les fonctions de compression unidirectionnelle ne sont pas liées aux algorithmes de compression de données conventionnels , qui peuvent être inversés exactement (compression sans perte) ou approximativement (compression avec perte) aux données d'origine.

Une fonction de compression unidirectionnelle

Les fonctions de compression à sens unique sont par exemple utilisées dans la construction Merkle-Damgård à l' intérieur des fonctions de hachage cryptographiques .

Les fonctions de compression à sens unique sont souvent construites à partir de chiffrements par blocs . Certaines méthodes pour transformer n'importe quel chiffrement par bloc normal en une fonction de compression à sens unique sont Davies-Meyer , Matyas-Meyer-Oseas , Miyaguchi-Preneel (fonctions de compression à longueur de bloc unique) et MDC-2/Meyer-Schilling , MDC-4 , Hirose (fonctions de compression à longueur de bloc double). Ces méthodes sont décrites en détail plus loin. ( MDC-2 est aussi le nom d'une fonction de hachage brevetée par IBM .)

Compression

Une fonction de compression mélange deux entrées de longueur fixe et produit une seule sortie de longueur fixe de la même taille que l'une des entrées. Cela peut également être vu comme le fait que la fonction de compression transforme une grande entrée de longueur fixe en une sortie de longueur fixe plus courte.

Par exemple, l' entrée A peut être de 128 bits, l' entrée B de 128 bits et ils sont compressés ensemble en une seule sortie de 128 bits. Cela équivaut à avoir une seule entrée de 256 bits compressée en une seule sortie de 128 bits.

Certaines fonctions de compression ne compressent pas de moitié, mais plutôt par un autre facteur. Par exemple, l' entrée A peut être de 256 bits et l' entrée B de 128 bits, qui sont compressés en une seule sortie de 128 bits. C'est-à-dire qu'un total de 384 bits d'entrée sont compressés ensemble en 128 bits de sortie.

Le mélange est effectué de manière à obtenir un effet d'avalanche complet . C'est-à-dire que chaque bit de sortie dépend de chaque bit d'entrée.

Une manière

Une fonction à sens unique est une fonction facile à calculer mais difficile à inverser. Une fonction de compression unidirectionnelle (également appelée fonction de hachage) doit avoir les propriétés suivantes :

• Facile à calculer : si vous avez des entrées, il est facile de calculer la sortie.
• Résistance à la préimage : si un attaquant ne connaît que la sortie, il devrait être impossible de calculer une entrée. En d'autres termes, étant donné une sortie , il devrait être impossible de calculer une entrée telle que .${\style d'affichage h}$${\style d'affichage m}$${\displaystyle \operatorname {hash} (m)=h}$
• Deuxième résistance à l'image : étant donné une entrée dont la sortie est , il devrait être impossible de trouver une autre entrée qui a la même sortie , c'est-à-dire .${\style d'affichage m_{1}}$${\style d'affichage h}$${\style d'affichage m_{2}}$${\style d'affichage h}$${\displaystyle \operatorname {hash} (m_{1})\neq \operatorname {hash} (m_{2})}$
• Résistance aux collisions : il devrait être difficile de trouver deux entrées différentes qui compressent vers la même sortie, c'est-à-dire qu'un attaquant ne devrait pas être en mesure de trouver une paire de messages tels que . En raison du paradoxe de l' anniversaire (voir aussi l' attaque d'anniversaire ), il y a 50% de chances qu'une collision se produise à peu près où se trouve le nombre de bits dans la sortie de la fonction de hachage. Une attaque sur la fonction de hachage ne devrait donc pas être capable de trouver une collision avec moins de travail.${\displaystyle m_{1}\neq m_{2}}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$${\style d'affichage 2^{n/2}}$${\style d'affichage n}$${\style d'affichage 2^{n/2}}$

Idéalement, on aimerait que "l'infaisabilité" de la résistance de préimage et de la seconde résistance de préimage signifie un travail d'environ où est le nombre de bits dans la sortie de la fonction de hachage. Cependant, en particulier pour la résistance à la seconde préimage, c'est un problème difficile. ${\style d'affichage 2^{n}}$${\style d'affichage n}$

La construction Merkle-Damgård

La construction de hachage Merkle-Damgård. Les cases étiquetées [f] sont une fonction de compression à sens unique.

Une utilisation courante des fonctions de compression à sens unique est dans la construction Merkle-Damgård à l'intérieur des fonctions de hachage cryptographiques. Les fonctions de hachage les plus largement utilisées, y compris MD5 , SHA-1 (qui est obsolète) et SHA-2 utilisent cette construction.

Une fonction de hachage doit être capable de traiter un message de longueur arbitraire en une sortie de longueur fixe. Ceci peut être réalisé en divisant l'entrée en une série de blocs de taille égale et en les exploitant en séquence à l'aide d'une fonction de compression unidirectionnelle. La fonction de compression peut être soit spécialement conçue pour le hachage, soit construite à partir d'un chiffrement par bloc.

Le dernier bloc traité doit également être rembourré en longueur , ceci est crucial pour la sécurité de cette construction. Cette construction est appelée la construction Merkle-Damgård . Les fonctions de hachage les plus largement utilisées, y compris SHA-1 et MD5 , prennent cette forme.

Lorsque le remplissage de longueur (également appelé renforcement MD) est appliqué, les attaques ne peuvent pas trouver de collisions plus rapidement que le paradoxe d'anniversaire ( , étant la taille de bloc en bits) si la fonction utilisée est résistante aux collisions. Par conséquent, la construction de hachage Merkle-Damgård réduit le problème de trouver une fonction de hachage appropriée à la recherche d'une fonction de compression appropriée. ${\style d'affichage 2^{n/2}}$${\style d'affichage n}$${\style d'affichage f}$

Une deuxième attaque de préimage (étant donné un message qu'un attaquant trouve un autre message à satisfaire peut être effectuée selon Kelsey et Schneier pour un message -message-block in time . Notez que la complexité de cette attaque atteint un minimum de pour les messages longs quand et approche quand les messages sont courts. ${\style d'affichage m_{1}}$${\style d'affichage m_{2}}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$${\displaystyle 2^{k}}$${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$${\style d'affichage 2^{3n/4+2}}$${\displaystyle k=2^{n/4}}$${\style d'affichage 2^{n}}$

Construction à partir de chiffrements par blocs

Un chiffrement par bloc moderne typique

Les fonctions de compression à sens unique sont souvent construites à partir de chiffrements par blocs.

Les chiffrements par bloc prennent (comme les fonctions de compression à sens unique) deux entrées de taille fixe (la clé et le texte en clair ) et renvoient une seule sortie (le texte chiffré ) qui est de la même taille que le texte en clair d'entrée.

Cependant, les chiffrements par blocs modernes ne sont que partiellement à sens unique. Autrement dit, étant donné un texte en clair et un texte chiffré, il est impossible de trouver une clé qui chiffre le texte en clair en texte chiffré. Mais, étant donné un texte chiffré et une clé, un texte clair correspondant peut être trouvé simplement en utilisant la fonction de déchiffrement du chiffrement par bloc. Ainsi, pour transformer un chiffrement par bloc en une fonction de compression unidirectionnelle, certaines opérations supplémentaires doivent être ajoutées.

Certaines méthodes pour transformer n'importe quel chiffrement par bloc normal en une fonction de compression à sens unique sont Davies-Meyer, Matyas-Meyer-Oseas, Miyaguchi-Preneel (fonctions de compression à longueur de bloc unique) et MDC-2, MDC-4, Hirose (double -fonctions de compression de longueur de bloc).

Les fonctions de compression de longueur de bloc unique produisent le même nombre de bits que ceux traités par le chiffrement par bloc sous-jacent. Par conséquent, les fonctions de compression à double longueur de bloc produisent deux fois plus de bits.

Si un chiffrement par bloc a une taille de bloc de, disons, 128 bits, les méthodes de longueur de bloc unique créent une fonction de hachage qui a une taille de bloc de 128 bits et produit un hachage de 128 bits. Les méthodes à double longueur de bloc créent des hachages avec une taille de hachage double par rapport à la taille de bloc du chiffrement par bloc utilisé. Ainsi, un chiffrement par bloc de 128 bits peut être transformé en une fonction de hachage de 256 bits.

Ces méthodes sont ensuite utilisées dans la construction Merkle-Damgård pour construire la fonction de hachage réelle. Ces méthodes sont décrites en détail plus bas.

L'utilisation d'un chiffrement par bloc pour créer la fonction de compression unidirectionnelle pour une fonction de hachage est généralement un peu plus lente que l'utilisation d'une fonction de compression unidirectionnelle spécialement conçue dans la fonction de hachage. Ceci est dû au fait que toutes les constructions sécurisées connues effectuent l' ordonnancement des clés pour chaque bloc du message. Black, Cochran et Shrimpton ont montré qu'il est impossible de construire une fonction de compression à sens unique qui ne fait qu'un seul appel à un chiffrement par bloc avec une clé fixe. En pratique, des vitesses raisonnables sont atteintes à condition que l'ordonnancement des clés du chiffrement par bloc sélectionné ne soit pas une opération trop lourde.

Mais, dans certains cas, c'est plus facile car une seule implémentation d'un chiffrement par bloc peut être utilisée à la fois pour un chiffrement par bloc et une fonction de hachage. Il peut également économiser de l' espace de code dans de très petits systèmes embarqués comme par exemple des cartes à puce ou des nœuds dans des voitures ou d'autres machines.

Par conséquent, le taux de hachage ou le taux donne un aperçu de l'efficacité d'une fonction de hachage basée sur une certaine fonction de compression. Le taux d'une fonction de hachage itéré décrit le rapport entre le nombre d'opérations de chiffrement par bloc et la sortie. Plus précisément, le débit représente le rapport entre le nombre de bits d'entrée traités , la longueur en bits de sortie du chiffrement par bloc, et les opérations de chiffrement par bloc nécessaires pour produire ces bits de sortie. Généralement, l'utilisation de moins d'opérations de chiffrement par bloc entraîne une meilleure performance globale de l'ensemble de la fonction de hachage, mais elle conduit également à une valeur de hachage plus petite qui pourrait être indésirable. Le taux est exprimé par la formule : ${\style d'affichage m}$${\style d'affichage n}$${\style d'affichage s}$${\style d'affichage n}$

${\displaystyle R_{h}={\frac {\left|m_{i}\right|}{s\cdot n}}}$

La fonction de hachage ne peut être considérée comme sécurisée que si au moins les conditions suivantes sont remplies :

• Le chiffrement par bloc n'a pas de propriétés particulières qui le distinguent des chiffrements idéaux, tels que des clés faibles ou des clés qui conduisent à des chiffrements identiques ou apparentés (points fixes ou collisions de clés).
• La taille de hachage résultante est assez grande. Selon l' attaque d'anniversaire, un niveau de sécurité de 2 ⁸⁰ (généralement supposé impossible à calculer aujourd'hui) est souhaitable, la taille de hachage doit donc être d'au moins 160 bits.
• Le dernier bloc est correctement rembourré de longueur avant le hachage. (Voir la construction Merkle–Damgård .) Le remplissage de longueur est normalement implémenté et géré en interne dans des fonctions de hachage spécialisées comme SHA-1, etc.

Les constructions présentées ci-dessous : Davies-Meyer, Matyas-Meyer-Oseas, Miyaguchi-Preneel et Hirose se sont avérées sûres selon l' analyse de la boîte noire . Le but est de montrer que toute attaque qui peut être trouvée est au plus aussi efficace que l' attaque d'anniversaire sous certaines hypothèses. Le modèle de boîte noire suppose qu'un chiffrement par bloc est utilisé qui est choisi au hasard dans un ensemble contenant tous les chiffrements par bloc appropriés. Dans ce modèle, un attaquant peut chiffrer et déchiffrer librement n'importe quel bloc, mais n'a pas accès à une implémentation du chiffrement par bloc. Les fonctions de chiffrement et de déchiffrement sont représentées par des oracles qui reçoivent une paire soit d'un texte en clair et d'une clé, soit d'un texte chiffré et d'une clé. Les oracles répondent ensuite avec un texte en clair ou un texte chiffré choisi au hasard, si la paire a été demandée pour la première fois. Ils partagent tous deux une table pour ces triplets, une paire de la requête et de la réponse correspondante, et renvoient l'enregistrement, si une requête a été reçue pour la deuxième fois. Pour preuve, il existe un algorithme de recherche de collisions qui envoie des requêtes choisies au hasard aux oracles. L'algorithme renvoie 1, si deux réponses entraînent une collision impliquant la fonction de hachage qui est construite à partir d'une fonction de compression appliquant ce chiffrement par bloc (0 sinon). La probabilité que l'algorithme renvoie 1 dépend du nombre de requêtes qui déterminent le niveau de sécurité.

Davies-Meyer

La fonction de compression unidirectionnelle Davies-Meyer

La fonction de compression de longueur de bloc unique de Davies-Meyer alimente chaque bloc du message ( ) en tant que clé d'un chiffrement par bloc. Il alimente la valeur de hachage précédente ( ) en tant que texte en clair à chiffrer. Le texte chiffré de sortie est ensuite également XORé (⊕) avec la valeur de hachage précédente ( ) pour produire la valeur de hachage suivante ( ). Au premier tour, lorsqu'il n'y a pas de valeur de hachage précédente, il utilise une valeur initiale constante pré-spécifiée ( ). ${\style d'affichage m_{i}}$${\style d'affichage H_{i-1}}$${\style d'affichage H_{i-1}}$${\style d'affichage H_{i}}$${\style d'affichage H_{0}}$

En notation mathématique, Davies-Meyer peut être décrit comme :

${\displaystyle H_{i}=E_{m_{i}}{(H_{i-1})}\oplus {H_{i-1}}}$

Le schéma a le taux (k est la taille de clé) :

${\displaystyle R_{DM}={\frac {k}{1\cdot n}}={\frac {k}{n}}}$

Si le chiffrement par bloc utilise par exemple des clés de 256 bits, alors chaque bloc de message ( ) est un morceau de 256 bits du message. Si le même chiffrement par bloc utilise une taille de bloc de 128 bits, les valeurs de hachage d'entrée et de sortie à chaque tour sont de 128 bits. ${\style d'affichage m_{i}}$

Des variantes de cette méthode remplacent XOR par toute autre opération de groupe, telle que l'addition sur des entiers non signés 32 bits.

Une propriété notable de la construction Davies-Meyer est que même si le chiffrement par bloc sous-jacent est totalement sécurisé, il est possible de calculer des points fixes pour la construction : pour tout , on peut trouver une valeur de telle que : il suffit de définir . C'est une propriété que les fonctions aléatoires n'ont certainement pas. Jusqu'à présent, aucune attaque pratique n'a été basée sur cette propriété, mais il faut être conscient de cette "fonctionnalité". Les points fixes peuvent être utilisés dans une seconde attaque de préimage (étant donné un message , l'attaquant trouve un autre message à satisfaire de Kelsey et Schneier pour un message -message-block dans le temps . Si la construction ne permet pas de créer facilement des points fixes (comme Matyas–Meyer–Oseas ou Miyaguchi–Preneel) alors cette attaque peut se faire dans le temps. Notez que dans les deux cas la complexité est supérieure mais inférieure lorsque les messages sont longs et que lorsque les messages deviennent plus courts la complexité de l'attaque se rapproche . ${\style d'affichage m}$${\style d'affichage h}$${\displaystyle E_{m}(h)\oplus h=h}$${\displaystyle h=E_{m}^{-1}(0)}$${\style d'affichage m_{1}}$${\style d'affichage m_{2}}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$${\displaystyle 2^{k}}$${\displaystyle 3\times 2^{n/2+1}+2^{n-k+1}}$${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$${\style d'affichage 2^{n/2}}$${\style d'affichage 2^{n}}$${\style d'affichage 2^{n}}$

La sécurité de la construction Davies-Meyer dans le modèle de chiffrement idéal a été prouvée pour la première fois par R. Winternitz.

Matyas–Meyer–Oseas

La fonction de compression unidirectionnelle Matyas-Meyer-Oseas

La fonction de compression unidirectionnelle Matyas-Meyer-Oseas à longueur de bloc unique peut être considérée comme le double (le contraire) de Davies-Meyer.

Il alimente chaque bloc du message ( ) en tant que texte en clair à chiffrer. Le texte chiffré de sortie est ensuite également XOR (⊕) avec le même bloc de message ( ) pour produire la prochaine valeur de hachage ( ). La valeur de hachage précédente ( ) est fournie comme clé du chiffrement par bloc. Au premier tour, lorsqu'il n'y a pas de valeur de hachage précédente, il utilise une valeur initiale constante pré-spécifiée ( ). ${\style d'affichage m_{i}}$${\style d'affichage m_{i}}$${\style d'affichage H_{i}}$${\style d'affichage H_{i-1}}$${\style d'affichage H_{0}}$

Si le chiffrement par bloc a des tailles de bloc et de clé différentes, la valeur de hachage ( ) aura la mauvaise taille pour être utilisée comme clé. Le chiffrement peut également avoir d'autres exigences particulières sur la clé. Ensuite, la valeur de hachage est d'abord transmise à la fonction à convertir/remplir pour s'adapter comme clé pour le chiffrement. ${\style d'affichage H_{i-1}}$${\style d'affichage g}$

En notation mathématique, Matyas-Meyer-Oseas peut être décrit comme :

${\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus m_{i}}$

Le régime a le taux:

${\displaystyle R_{MMO}={\frac {n}{1\cdot n}}=1}$

Une deuxième attaque de préimage (étant donné un message qu'un attaquant trouve un autre message à satisfaire ) peut être effectuée selon Kelsey et Schneier pour un message -message-block in time . Notez que la complexité est supérieure mais inférieure lorsque les messages sont longs, et que lorsque les messages deviennent plus courts, la complexité de l'attaque approche . ${\style d'affichage m_{1}}$${\style d'affichage m_{2}}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$${\displaystyle 2^{k}}$${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$${\style d'affichage 2^{n/2}}$${\style d'affichage 2^{n}}$${\style d'affichage 2^{n}}$

Miyaguchi–Preneel

La fonction de compression unidirectionnelle Miyaguchi-Preneel

La fonction de compression unidirectionnelle à un seul bloc de Miyaguchi-Preneel est une variante étendue de Matyas-Meyer-Oseas. Il a été proposé indépendamment par Shoji Miyaguchi et Bart Preneel .

Il alimente chaque bloc du message ( ) en tant que texte en clair à chiffrer. Le texte chiffré de sortie est ensuite XORé (⊕) avec le même bloc de message ( ) puis également XORé avec la valeur de hachage précédente ( ) pour produire la valeur de hachage suivante ( ). La valeur de hachage précédente ( ) est fournie comme clé du chiffrement par bloc. Au premier tour, lorsqu'il n'y a pas de valeur de hachage précédente, il utilise une valeur initiale constante pré-spécifiée ( ). ${\style d'affichage m_{i}}$${\style d'affichage m_{i}}$${\style d'affichage H_{i-1}}$${\style d'affichage H_{i}}$${\style d'affichage H_{i-1}}$${\style d'affichage H_{0}}$

Si le chiffrement par bloc a des tailles de bloc et de clé différentes, la valeur de hachage ( ) aura la mauvaise taille pour être utilisée comme clé. Le chiffrement peut également avoir d'autres exigences particulières sur la clé. Ensuite, la valeur de hachage est d'abord transmise à la fonction à convertir/remplir pour s'adapter comme clé pour le chiffrement. ${\style d'affichage H_{i-1}}$${\style d'affichage g}$

En notation mathématique, Miyaguchi-Preneel peut être décrit comme :

${\displaystyle H_{i}=E_{g(H_{i-1})}(m_{i})\oplus H_{i-1}\oplus m_{i}}$

Le régime a le taux:

${\displaystyle R_{MP}={\frac {n}{1\cdot n}}=1}$

Les rôles de et peuvent être intervertis, de sorte qu'ils sont chiffrés sous la clé , faisant ainsi de cette méthode une extension de Davies-Meyer à la place. ${\style d'affichage m_{i}}$${\style d'affichage H_{i-1}}$${\style d'affichage H_{i-1}}$${\style d'affichage m_{i}}$

Une deuxième attaque de préimage (étant donné un message qu'un attaquant trouve un autre message à satisfaire ) peut être effectuée selon Kelsey et Schneier pour un message -message-block in time . Notez que la complexité est supérieure mais inférieure lorsque les messages sont longs, et que lorsque les messages deviennent plus courts, la complexité de l'attaque approche . ${\style d'affichage m_{1}}$${\style d'affichage m_{2}}$${\displaystyle \operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})}$${\displaystyle 2^{k}}$${\displaystyle k\times 2^{n/2+1}+2^{n-k+1}}$${\style d'affichage 2^{n/2}}$${\style d'affichage 2^{n}}$${\style d'affichage 2^{n}}$

Hirose

La fonction de compression à double longueur de bloc Hirose

La fonction de compression unidirectionnelle à double longueur de bloc Hirose consiste en un chiffrement par bloc plus une permutation . Il a été proposé par Shoichi Hirose en 2006 et est basé sur une œuvre de Mridul Nandi . ${\style d'affichage p}$

Il utilise un chiffrement par bloc dont la longueur de clé est supérieure à la longueur du bloc et produit un hachage de taille . Par exemple, l'un des candidats AES avec une clé de 192 ou 256 bits (et un bloc de 128 bits). ${\style d'affichage k}$${\style d'affichage n}$${\style d'affichage 2n}$

Chaque tour accepte une partie du message qui est bits de long, et l' utilise pour mettre à jour les deux valeurs d'état de bits et . ${\style d'affichage m_{i}}$${\displaystyle kn}$${\style d'affichage n}$${\style d'affichage G}$${\style d'affichage H}$

Tout d'abord, est concaténé avec pour produire une clé . Ensuite, les deux valeurs de retour sont mises à jour en fonction de : ${\style d'affichage m_{i}}$${\style d'affichage H_{i-1}}$${\displaystyle K_{i}}$

• ${\displaystyle G_{i}=E_{K_{i}}(G_{i-1})\oplus G_{i-1}}$
• ${\displaystyle H_{i}=E_{K_{i}}(p(G_{i-1}))\oplus p(G_{i-1})}$

${\style d'affichage p(G_{i-1})}$est une permutation arbitraire sans point fixe sur une valeur -bit, généralement définie comme pour une constante arbitraire non nulle (tous les uns peuvent être un choix pratique). ${\style d'affichage n}$${\style d'affichage p(x)=x\oplus c}$${\style d'affichage c}$

Chaque cryptage ressemble à la construction Davies-Meyer standard. L'avantage de ce schéma par rapport aux autres schémas proposés à double longueur de bloc est que les deux cryptages utilisent la même clé, et ainsi l'effort de planification de clé peut être partagé.

La sortie finale est . Le schéma a le taux relatif au chiffrement du message avec le chiffrement. ${\displaystyle H_{t}||G_{t}}$${\textstyle R_{Hirose}={\frac {kn}{2n}}}$

Hirose fournit également une preuve dans le modèle de chiffrement idéal.

Construction en éponge

La construction en éponge peut être utilisée pour créer des fonctions de compression à sens unique.

Voir également

• Whirlpool — Une fonction de hachage cryptographique construite à l'aide de la construction Miyaguchi-Preneel et d'un chiffrement par bloc similaire à Square et AES .
• CBC-MAC , OMAC et PMAC — Méthodes pour transformer les chiffrements par blocs en codes d'authentification de message (MAC).

Les références

Citations

Sources