Introduction

Les chiffrements en bloc et les fonctions de compression sont des blocs de construction qui peuvent être utilisés pour fabriquer des applications cryptographiques.  Nous allons explorer quelques de ces applications.  Il faut se souvenir qu'essentiellement, un chiffrement en bloc est une implémentation algorithmique d'une fonction f tel que X = f(C,K) avec X et C des nombres naturels tirés du même sous-ensemble {0, 1, 2, ... 2N - 1}, où N est le nombre de bits du texte en clair et aussi le nombre de bits du texte chiffré, K est un nombre tiré du sous-ensemble de nombres {0, ... , 2M - 1} où M est le nombre de bits dans la clé, tel qu'une fonction inverse g existe avec une implémentation algorithmique: C = g(X,K), mais qu'il n'est pas possible dans la pratique de trouver une implémentation d'une fonction qui calcule K si on possède plusieurs pairs (C,X).  Une fonction de compression est essentiellement la même chose, sauf qu'on appelle (C,K) simplement B de longueur N + M bits et il n'y a pas nécessairement une fonction inverse g.

Considérons quelques exemples.

Messagerie secrète symmétrique

La messagerie secrète est probablement l'application originale de la cryptographie et la cryptographie est toujours très associée à la messagerie secrète.  L'application est la suivante:  deux "amis" A et B veulent échanger des messages dont ils ne veulent pas que les "ennemis" E puissent les lire à travers un canal non sure, c'est à dire, un canal qui pourra transférer le message de A vers B, mais qui pourra aussi être vu (et éventuellement modifié) par E.  On peut s'imaginer que E est le messager, et que A et B ne veulent pas que leur messager puisse lire ce que A veut raconter à B.  Ce qui distingue amis d'ennemis en cryptographie, c'est la possession d'une clé secrète.   Il faut donc qu'A et B puissent partager une clé secrète sans qu'E puisse connaître cette clé.  Ainsi, A et B doivent générer cette clé ensemble, un des deux (disons, A) doit générer cette clé et la communiquer à B, ou un troisième parti de confiance doit générer une clé et la communiquer à A et à B.  Il va de soi que ce transport de clé secrète doit être sûr.  Si le transport de cette clé est compromis, alors l'ancien ennemi E peut devenir cryptographiquement un "ami" et il n'y a plus de secrets pour lui.

Mais cela pose la question: s'il y a un canal sûr qui peut transporter la clé, pourquoi on n'utilise pas ce canal pour transporter le message en premier lieu ?

Seulement si on peut répondre de façon pertinente à cette question, la messagerie secrète symétrique a un sens.  La réponse est souvent que les entités A et B peuvent se rencontrer physiquement à un moment en temps et seront séparés par une distance plus tard quand ils devront utiliser un moyen de communication non sûr.  Une autre réponse que nous verrons plus tard est qu'on peut mettre en place un canal de communication sûr, mais qui demande beaucoup d'efforts de calcul.  Il peut être utile d'utiliser ce canal pour établir la clé, et en suite, on peut utiliser un canal non sûr pour communiquer des messages beaucoup plus longs en utilisant la cryptographie symétrique.   Il est cependant nécessaire de se poser cette question avant de mettre en place une messagerie secrète.

Il semble que les chiffrements par bloc ont étés conçus exactement à cette fin, et c'est effectivement le cas, mais nous allons voir que l'utilisation simple de chiffrements en bloc peut être problématique.  Il s’avérera que la fonction inverse du chiffrement en bloc n'est pas indispensable dans tous les cas.

Sécuriser un stockage de données.

Un cas spécifique de la messagerie secrète est quand l'émetteur et le récepteur sont la même personne ou entité.  Il peut sembler bizarre à première vue de vouloir s'envoyer des messages secrètes sur un canal non sûr.  Mais c'est en fait exactement la situation du stockage d'informations sensibles.  Le porteur d'information (un disque dur, une clé USB, un téléphone mobile) peut être considéré non sûr s'il peut être accédé par d'autres, copié par d'autres, ou volé.  Ainsi, il peut être intéressant de garder l'information sur un porteur d'information en forme de texte chiffré.  Quand on veut utiliser les données, on peut fournir une clé qui permet de décrypter les données et accéder aux données en clair.  Bien sûr, de la même façon que pendre la clé de la porte d'entrée à une ficelle devant celle-ci n'est pas une bonne idée, c'est une mauvaise idée de garder la clé de chiffrement avec le porteur de données cryptées.  Aussi, quand la clé est appliquée au porteur, qui est "ouvert", les données sont vulnérables et peuvent être accédées.   Le chiffrement des porteurs de données est une application très importante de la cryptographie symétrique, qui gagne de plus en plus d'importance.  La façon de s'y prendre a beaucoup de similitudes avec la messagerie secrète, mais on prend en compte la spécificité de l'application.

La question à considérer est: s'il y a une façon sûre de conserver la clé secrète, pourquoi on l'utilise pas pour stocker les données à protéger ?

La génération de nombres pseudo aléatoires

La possibilité de partager une série de nombres "aléatoires" parmi des amis peut avoir plusieurs applications.  Cela permet à des amis d'avoir des flux de données quasi illimités et parfaitement corrélés mais qui semblent totalement aléatoires pour des ennemis.  Ils sont basés sur le partage d'une clé commune, mais ne nécessitent pas d'autre forme de communication.  Cela permet des actions corrélés parmi des amis qui sont inimitables par des ennemis.  Une application est du "spectre étalé" en communication radio: l'émetteur et le récepteur ont des générateurs de nombres "aléatoires" synchronisés qui indiquent quelles sont les fréquences successives sur lesquelles on communique ; mais pour l'ennemi, ces sauts aléatoires des fréquences de communication ressemble à du bruit.  C'est la corrélation parfaite entre l'émetteur et le récepteur qui permet de distinguer un flux de bruit d'un signal de communication compréhensible.

Une autre application est la preuve d'identité souvent utilisée par des banques pour permettre à leurs clients de s'identifier.   A un moment, le client doit être présent physiquement chez le banquier, de telle façon que la banque puisse avoir confiance dans l'identité légitime du client.  Alors, la banque partage une clé secrète avec le client (souvent cette clé n'est jamais visible par le client, mais incorporée dans un logiciel ou un appareil donné au client).  Cette clé sert à générer un bloc "aléatoire" après n itérations, qui sera le même chez le banquier et chez le client, sans nécessité de communication supplémentaire.  Le nombre d'itérations peut dépendre du temps (disons, une itération tous les 30 secondes depuis un moment fixé dans le passé).  Quand le client doit prouver son identité à la banque à un moment futur, l'application ou l'appareil vont calculer le bon nombre d'itérations en fonction de la date et l'heure, et calculera le bloc de nombres "aléatoires" correspondant à cette itération.  En envoyant ce bloc de données à la banque qui peut faire exactement le même calcul, la banque sait que le client ne peut être que le client légitime.  30 secondes plus tard, cette identification ne marche plus, donc quelqu'un qui aurait écouté cette preuve ne peut plus rien en faire 30 secondes plus tard.

Une autre application de nombres pseudo aléatoires par des techniques cryptographiques est la vérifiabilité d'un tirage au sort équitable.  Considérons une loterie.   L'idée de base d'une loterie est que le tirage au sort est "juste", c'est à dire, que personne ne pouvait déterminer le tirage ; ou que personne ne pouvait prédire le tirage en avance.   Il y a deux aspects: "ne pas être en mesure d'influencer le résultat pour obtenir un résultat voulu" et "ne pas savoir à l'avance ce que sera le résultat".   Dépendant du type de loterie, l'un ou l'autre aspect sera le plus important pour que la loterie sera acceptée comme équitable.  Si les participants ne peuvent pas choisir leur lot (par exemple, c'est leur date d'anniversaire), alors le plus important est que celui qui tire le résultat ne puisse pas le déterminer à sa guise.  Si les participants peuvent choisir leur lot, alors il faut que personne ne puisse connaître le résultat du tirage avant d'avoir déterminé son lot.  Bien sûr, un tirage par un vrai générateur aléatoire avec une source d'entropie est la meilleure solution, mais il est difficile de prouver la nature véritable d'un tel tirage quand on ne dispose que du résultat. 

Hashage et MAC

Il peut être utile de pouvoir générer une empreinte de petite taille d'un jeu de données potentiellement très grand qui constitue une "preuve portable d'authenticité".  Il y a deux types d'empreintes: ceux qui peuvent être générées par tout le monde, et ceux qui ne peuvent être générées par des "amis".  La première classe s'appelle des hash, la deuxième un MAC (Message Authentication Code).

La plupart des applications cryptographiques consistent en utilisant l'empreinte afin de vérifier l'authenticité de données qui ne sont pas, elles-mêmes, des secrets.  On veut juste vérifier qu'ils n'ont pas étés modifiés, et sont bien les données d'origine.  Si cette vérification doit être publique, il nous faut utiliser un hash (il y a une autre solution avec de la cryptographie asymmétrique).  Si cette vérification n'a de l'importance que parmi des amis, alors on peut utiliser un MAC.

Une application typique d'un hash est la vérification d'un logiciel téléchargé.  Effectivement, quand on télécharge un logiciel, on prend toujours le risque de télécharger une version modifiée, compromise, contenant des virus, des espions, .... .  Si on peut obtenir un hash du logiciel, il suffit de calculer le hash du fichier téléchargé, et s'il est identique, c'est que le logiciel est bien l'original, non modifié.... sauf si le hash a été modifié aussi.  Cela nous mène à la question:

s'il faut un canal sûr pour avoir un hash non-modifié, alors pourquoi ne pas utiliser ce canal pour télécharger le logiciel ?

Le hash étant bien plus petit que le fichier à télécharger, il est souvent plus facile de donner une façon sûre d'obtenir la valeur du hash.  Le logiciel même à télécharger peut se trouver sur un serveur puissant mais potentiellement non sûr, et le hash peut se trouver sur une page web bien plus sécurisée mais avec moins de puissance de distribution.  Aussi, plusieurs sources peuvent donner le hash, ce qui rend la tâche pour l'ennemi bien plus difficile: il faut corrompre toutes ces sources pour modifier le hash.

La difficulté de devoir posséder un canal sûr pour transmettre une empreinte correcte d'un jeu de données disparaît avec l'utilisation du MAC.  Un MAC ne peut être généré (mais aussi, ne peut être vérifié) que par des amis qui partagent une clé secrète.  Cela pose maintenant le problème du partage de la clé par un canal sûr et nous avons à nous poser de nouveau cette question existentielle du canal sûr...

On peut voir un MAC comme un "hash crypté".  Techniquement ce n'est pas comme ça qu'on le fait, mais il n'y a pas de danger qu'un ennemi qui ne possède pas la clé, puisse générer un faux MAC, correspondant à un fichier modifié.  Par contre, seulement les amis peuvent vérifier le MAC.  Le MAC peut donc être distribué par un canal non sûr.  Le MAC peut en fait faire partie du jeu de données et être communiqué de la même façon.  Quand un jeu de données contient un MAC qui se vérifie, alors c'est la preuve que ce MAC est généré par une personne en possession de la clé, et en utilisant le même jeu de données.

Si des amis partageant une clé secrète veulent s'échanger des données sûrs, ils peuvent aussi les crypter avec la clé.  Mais dans la mesure où les données ne sont pas des secrets et que la seule chose que ces personnes veulent, c'est de s'assurer que les données sont authentiques, alors un MAC convient parfaitement et il n'est pas nécessaire de crypter l'ensemble des données.

Preuve de connaissance

Parfois il est utile pour deux personnes d'établir s'ils sont des amis ou non, ce qui veut dire dans un sens cryptographique, s'ils partagent une clé secrète.  Il se peut que cela ne doit marcher que dans un sens, mais il se peut que ça doit marcher dans les deux sens.  Par exemple, vous partagez peut-être une clé avec votre frère qui est en voyage.  Quand vous communiquez par un canal non sûr, comment est-ce que vous et votre frère puissent vérifier que c'est bien vous et votre frère ?  Si vous demandez de voir la clé secrète l'autre personne ne peut plus vérifier que vous êtes bien ce que vous prétendez être.

Une façon de vérifier que l'autre personne connaît la clé secrète sans la révéler est de fournir des données aléatoires à l'autre personne, et lui demander de fournir un MAC de ces données.  Seulement une personne en possession de la clé peut faire cela.  En suite, l'autre personne vous fait le même genre de défi.  Cela prouve que vous possédez donc tous les deux la clé, sans la révéler.

Preuve de travail

Parfois on veut "ralentir" certaines choses suffisamment car si des personnes peuvent le faire trop vite, cela pose un problème comme une surcharge d'un système, une tricherie, ou une autre défaillance dans un système.  Par exemple, on pourrait vouloir limiter le nombre d'accès par minute d'une personne à un serveur pour des raisons différentes.  Peut-être qu'on veut limiter la surcharge du serveur (une protection contre une attaque DoS par exemple).  Peut-être que vous voulez mettre à disposition quelques fichiers au choix, mais que vous ne voulez pas que quelqu'un télécharge systématiquement tout.  Il peut y avoir plusieurs raisons pour limiter l'accès par personne.  La façon classique, de vérifier l'identité et de compter un nombre de fois qu'une identité accède au système, ne marche pas bien sur internet, où il est facile de se procurer des milliers d'identités (y compris des numéros IP, des comptes e-mail...).  Une façon évidente de limiter cet accès est de rendre l'accès payant.  Une entité qui voudra accéder souvent, va devoir payer beaucoup.  Mais parfois on veut mettre quelque chose en accès libre, mais limité.  Alors il faut trouver un moyen équivalent de "payer" mais d'une façon non-monétaire.

Une façon de rendre un accès "cher" est de le rendre cher en temps de calcul.  Chaque fois que quelqu'un veut accéder au service, on lui fournit un puzzle à résoudre qui prendra une quantité de calcul importante.  Ce n'est que quand le puzzle est résolu, qu'il peut accéder une seule fois.  S'il veut accéder de nouveau, il lui faudra résoudre un autre puzzle.  Si ce puzzle est du genre de prendre 5 minutes de calcul pour trouver la solution sur un PC normal, alors la plupart des personnes possédant un PC pourront accéder chaque 5 minutes.  S'ils possèdent 5 PC, ils pourront accéder chaque minute.  Mais s'ils veulent accéder 10 fois par seconde, il leur faudra la puissance de calcul de 3000 PC.  Le nombre de personnes pouvant mettre à leur disposition cette puissance de calcul est limitée et devient chère.  Donc votre protection marche: vous n'allez pas être submergé par des demandes d'accès répétées par la même personne en grande quantité.

La façon classique de fournir une preuve de travail consiste à procurer un hash d'une pièce de données, dont la première partie est fournie par celui qui veut voir la preuve, et la deuxième partie est la "solution" tel que le hash fasse partie d'un sous-ensemble des valeurs possibles.   La seule façon pour la partie adverse de trouver cette solution, est d'essayer une solution, de calculer le hash, de vérifier s'il est dans le sous-ensemble, et de recommencer.  En moyenne, il faudra calculer un nombre de hash grosso modo égal au rapport de la taille de l'ensemble des hash possibles, sur la taille du sous-ensemble exigé.  En fournissant une solution, on prouve donc qu'on a calculé un tel nombre de hash.

Modes d'opération d'un chiffrement par bloc pour le chiffrage des textes

Supposons que nous voulons une fonction de chiffrement F tel que XX = F(CC,K).  Cela ressemble fortement à la fonction de chiffrement en bloc X = f(C,K), sauf que nous avons un texte en clair CC et un texte chiffré XX bien plus grand que C et X de la fonction de chiffrement en bloc. Nous voulons construire F à partir de f.  Nous allons couper CC en n blocs de longueur 2N que nous appellerons Ci.  De la même façon, le texte chiffré sera composé de blocs Xi.  La question est: comment utiliser f ?  Les façons de faire s'appellent des modes d'opération du chiffrement en bloc.

Electronic Codebook mode (ECB)

La façon la plus évidente d'utiliser f pour construire F est bien sûr:

Xi = f(Ci , K)

Le déchiffrement correspondant est: Ci = g(Xi , K)

Simple, évident et trivial que cela peut sembler, il y a plusieurs problèmes avec cette approche.  Le problème le plus important est que la fonction f étant déterministe, si le bloc de texte en clair se répète, alors le bloc chiffré correspondant se répétera.  Ainsi, une information potentiellement importante du texte en clair fuite dans le texte chiffré.  En chiffrant des images par exemple, cet effet est même dramatique: des zones de couleur uniforme dans l'image sont chiffrés de façon uniforme, et on voit dans l'image chiffré tous les contours des zones à couleur uniforme !  Cela peut trahir l'essentiel de l'image.

Un autre aspect de ce mode de chiffrement, qui peut être un avantage ou un désavantage, dépendant de l'application, est qu'on puisse remplacer des parties du texte chiffré, sans affecter le reste du texte chiffré.  C'est un problème quand on considère que le canal de communication peut dédoubler, enlever, ou modifier l'ordre des blocs.  C'est aussi un problème quand l'ennemi mélange différents textes chiffrés avec la même clé.  Mais c'est un avantage quand on considère le chiffrement d'un porteur de données: la corruption d'une partie du porteur n'empêche pas le déchiffrement du reste.

Le mode ECB est aussi intéressant car il peut être exécuté en parallèle.

Cypher block chaining mode (CBC)

Pour pallier aux faiblesses du mode ECB, principalement le fait que le même bloc en clair se traduira en un même bloc chiffré, le mode CBC exige un bloc d'initialisation I de la même longueur que les blocs de texte en clair et de texte chiffré.  Il faudra transmettre ce bloc d'initialisation en clair avec le message chiffré pour permettre le déchiffrage.

Le cryptage en mode CBC se fait ainsi:

X1 = f(C1 xor I , K)

Xi = f(Ci xor Xi-1 , K)

Il faut noter que même si tous les blocs Ci sont les mêmes, aucun bloc chiffré Xi ne sera le même.  Le décryptage se fait comme ceci:

C1 = g(X1 , K) xor I

Cj = g( Xj , K) xor Xj-1

Cette technique a aussi l'avantage que, si un des blocs chiffrés est endommagé pendant la transmission, cela ne rendra illisible que deux blocs de texte en clair pendant le déchiffrage.  La sécurité du mode CBC vient de l'hypothèse que le bloc d'initialisation I est différent pour chaque chiffrement.  Si on réutilise I pour deux chiffrements, et l'ennemi est au courant de cela, et possède le premier texte en clair, le mode CBC devient non sûr.  Le mode CBC n'est pas entièrement protégé contre une attaque de substitution, car seulement quelques blocs seront illisibles.   Un désavantage du mode CBC est qu'il ne peut pas être exécuté en parallèle.

Output feedback mode (OFB)

Le mode OFB est intéressant, car nous n'avons pas besoin de la fonction inverse de la fonction de chiffrement par bloc, g.  Ainsi, toute la difficulté et aussi la source de beaucoup de vulnérabilités du chiffrement par bloc traditionnel, à savoir la nécessité d'avoir une fonction inverse g, n'a plus lieu d'être.  Essentiellement, le mode OFB utilise le chiffrement en bloc comme un générateur de nombres pseudo-aléatoires qui serviront comme "clé" dans un chiffrement par masque jetable.  Il est extrêmement important d'avoir un bloc de démarrage (à transférer avec le texte chiffré) à utiliser une seule fois, car la "clé" (le masque) est vite trouvé par un ennemi qui possède le texte en clair et le texte chiffré.

Nous avons:

R1 = f(I , K)

Ri = f(Ri-1 , K)

comme les blocs du "masque jetable".  Le chiffrement et le déchiffrement se font alors ainsi:

Chiffrement: Xi = Ci xor Ri

Déchiffrement: Ci = Xi xor Ri

Le mode OFB ne peut pas être exécuté en parallèle, mais les blocs R peuvent être calculés à l'avance (par les deux parties si le récepteur possède déjà le bloc d'initialisation I).  Une propriété de ce mode est que si une partie du texte chiffré est endommagée, cela n'a d'implication que sur la partie du texte en clair correspondant.  Le reste peut être déchiffré sans problèmes.

Counter mode (CTR)

Le mode compteur (counter mode en anglais) est très semblable au mode OFB, mais permet le chiffrement et le déchiffrement en parallèle.  Au lieu de chaîner les calculs des blocs R, on propose que les blocs d'entrée consistent en une combinaison d'un bloc d'initialisation I et d'un compteur qui compte les blocs (donc, l'index i).

Ii = composition de I et de i

Ri = f( Ii , K)

Le chiffrement et le déchiffrement sont identiques au mode OFB.

Cypher feedback mode (CFB)

Le mode CFB a quelques similitudes avec le mode OFB, mais le texte chiffré est pris lui-même comme "masque jetable".

Chiffrement:

X1 = f (I , K) xor C1

Xi = f(Xi-1 , K) xor Ci

Déchiffrement:

C1 = f(I, K) xor X1

Ci = f(Xi-1 , K) xor Xi

Ce mode ne peut ni être exécuté en parallèle, ni être calculé à l'avance.

Modes d'opération de chiffrement de texte en clair avec authentification

Dans ce qui précède, nous avons discuté comment éteindre le concept de chiffrement en bloc au chiffrage de long textes.  Cependant, certains modes étaient vulnérables à la modification du texte chiffré quand celui-ci est transmis par un canal non sûr.  Bien que certains modes sont plus robustes contre cette difficulté que d'autres (on verrait qu'il y ait au moins un bloc déchiffré bizarre), maintenant on considère que la fonction de chiffrement afin de préserver le secret (la confidentialité) et l'authentification sont deux applications cryptographiques différentes et que l'authentification doit être assuré d'une autre façon que de "détecter du texte en clair bizarre" pendant le déchiffrage.  La façon la plus simple pour obtenir une authentification sûre est d'ajouter un MAC au texte chiffré.  Cependant, calculer un MAC de façon indépendante est presque aussi lourd que chiffrer le texte.  Ainsi, il y a des modes spécifiques qui calculent en même temps le texte chiffré, et un MAC associé afin d'utiliser les ressources de calcul de façon plus efficace.  Nous allons seulement considérer le mode le plus célèbre: le Galois Counter Mode (GCM).

Le chiffrement en mode GCM est le même qu'en mode compteur (CTR), sauf qu'on "saute un coup": on calcule R0 = f(I0,K), et ce n'est que R1 = f(I1 , K) qui servira à crypter C1.

Nous calculons simultanément un MAC, de la manière suivante.  L'utilisateur doit aussi faire un bloc de texte d'authentification qui sera transféré en clair avec le texte chiffré.  Il peut contenir par exemple de l'information sur une adresse réseau qui ne pourra pas être falsifiée.  Appelons ce bloc AAD.

Nous calculons H = f(0, K).

Avec AAD et le bloc H, on calcule g0 = AAD  × H,où la multiplication est celle du champs Galois d'ordre de la taille du bloc.  Ce champs fait partie de la spécification du chiffrement.  Un standard connu est celui avec la taille de 128 bits (donc l'ordre égal à 2128) avec le polynôme irréducible P(x) = x128 + x7 + + x2 + x + 1.  Mais on peut spécifier un autre champs Galois si on veut.

On calcule le MAC de façon récursive des blocs chiffrés:

gi = ( gi-1 xor Ci ) × H

Finalement, le dernier gn est utilisé pour calculer le MAC: MAC = (gn × H) xor f (I0 , K)

La multiplication Galois étant bien plus légère à calculer qu'un chiffrement complet d'un bloc, ce calcul d'un MAC ne rajoute que très peu de charge supplémentaire à la procédure de chiffrement.  Le prix à payer est bien sûr que ce calcul ne peut être fait en parallèle, ce qui est inévitable avec un MAC.

Pour le déchiffrement, c'est la même chose que le CTR.  Le calcul du MAC est identique à la procédure pendant le chiffrement.  En comparant le calcul local du MAC avec le MAC reçu, on peut s'assurer de l’authenticité du texte chiffré et du bloc d'authentification AAD.

Authentification sans cryptage en utilisant le chiffrement par bloc

Une application spécifique du mode CBC est la génération d'un MAC sans considérer le chiffrement.  On peut simplement chiffrer le texte en clair en utilisant le mode CBC.  Le dernier bloc chiffré peut être considéré comme un MAC.   Si on envoie le texte en clair avec juste le dernier bloc chiffré, cela fonctionne comme un MAC.  Cette technique est appelée CBC-MAC.

Le GTR peut aussi être utilisé simplement pour générer un MAC.  C'est appelé le GMAC.  On ne transmet pas le texte chiffré, mais le texte en clair, et le MAC du GTR.

Nombres aléatoires de chiffrements par bloc

Les modes OFB et CTR illustrent déjà la production de séries de nombres pseudo-aléatoires cryptographiquement sûres.

Fonctions de hachage de chiffrements par bloc et de fonctions de compression

La fonction de compression primitive standard d'une application de hachage est tel que nous avons une fonction H = h(B) où B est plus grand en taille que H.  If B est de taille N bits, et H est de taille M bits, alors N > M pour une vraie fonction de compression.  Nous pouvons utiliser un chiffrement par bloc à la place d'une fonction de compression.  Dans ce cas, nous avons H = h(C,K), et B est vu comme la composition de C et de K.

La construction Merkle-Damgård

Si nous devons calculer le hash avec une longueur de M bits d'un grand jeu de données (ce qui est l'application essentielle de hachage) à partir d'une fonction de compression h, alors la construction standard est la suivante:

Le grand jeu de données est coupé en morceaux de taille (N - M): x1 x2 x3 ... xn

Nous choisissons un bloc d'initialisation I de taille M, qui peut être une constante spécifiée dans la description de l'application de hachage, ou il peut être dépendant de l'implémentation.  De toute façon, ce bloc d'initialisation doit être connu publiquement.  Alors nous calculons:

H1 = h( I // x1)

Hi = h(Hi-1 // xi )

Hn est finalement le hash du jeu de données.

La construction Davies-Meyer

La construction Davies-Meyer est adaptée à l'utilisation d'un chiffrement par bloc dans une application de hachage, car dans un chiffrement par bloc, il y a une entrée de taille exactement celle de la sortie: l'entrée du texte en clair.  L'autre entrée, la clé secrète, a potentiellement une autre longueur.

Ainsi, un jeu de données coupé en blocs de taille K, la longueur de clé, donne: x1 x2 x3 ... xn

De la même façon que dans la construction Merkle-Damgard, un bloc d'initialisation publiquement connu I est nécessaire, de taille M.

Maintenant, on calcule:

H1 = I xor f(x1 , I)

Hi = Hi-1 xor f(xi , Hi-1)

De nouveau, le dernier Hn sera le hash du jeu de données.

La construction Matyas-Meyer-Oseas

Cette construction ne tient pas compte du fait que l'entrée du texte en clair est de la même taille que la sortie.   Les données sont coupés en morceaux de taille M (la taille de la sortie).  Maintenant, il nous faut une fonction u(H) qui modifie un bloc de taille M en un bloc de taille K (que K soit plus grand ou plus petit que M).  Il n'y a pas d'exigences spéciales pour cette fonction de compression ou d'expansion.

Nous avons de nouveau un bloc d'initialisation I de taille M.   Nous calculons:

H1 = f(x1 , u(I) ) xor x1

Hi = f(xi , u(Hi-1) ) xor xi

La différence avec la construction avec la construction Davies-Meyer est que maintenant, les données à hacher entrent par l'entrée "texte en clair" et dans l'autre construction (D.M.) elles entrent par l'entrée "clé" du chiffrement en bloc.  La contre-réaction de la sortie entre dans l'entrée "clé" dans notre cas (et doit donc adapter sa longueur) tandis que dans l'autre construction (D.M.) cette sortie entre par l'entrée "texte en clair" de la même taille.

Il y a d'autres constructions encore, comme Miyaguchi-Preneel et Hirose.

Une propriété typique de ces constructions récursives est que, pour ajouter des données au jeu de données, le hash peut être calculé à partir du hash du jeu d'origine, et les données supplémentaires.  Il ne faut plus boucler sur le texte d'origine.  Cela vient du fait que Hn+1 ne dépend que de Hn et des blocs supplémentaires xn+1.  Pour les applications standard des fonctions de hachage, cela ne pose aucun problème, mais quand on veut utiliser des fonctions de hachage dans d'autres applications cryptographiques, il faut en tenir compte.

La construction éponge

Une approche totalement différente de construction de fonction de hachage est la construction éponge.  Elle consiste en un "régistre" S de taille s bits, dont les r premiers (r < s) sont "entrée" ou "sortie" ;  et une fonction de "compression" 1-1 qui peut projeter un bloc de s bits en un autre bloc de s bits, T = f(S).

Les données d'entrée sont coupés en blocs de taille r: x1 x2 x3 ... xn

On initialise S à 0 (tous les bits de S sont mis à 0).

L'algorithme suivant est répété n fois (le nombre de blocs d'entrée):

  1. R, la partie des r premiers bits, est XORé avec xi et le résultat est placé de nouveau dans R
  2. S est remplacé par f(S) (contenant le morceau R)

Quand on veut obtenir une sortie de longueur k r, alors on répète k fois l'algorithme suivant:

  1. R est lu, donnant les r bits suivants de la sortie
  2. S est remplacé par f(S)

Comme normalement, S est bien plus grand que R (r << s), on considère que S est un "réservoir d'entropie" qui est "rempli" pendant la phase du cycle d'entrée, et qui est "vidé" pendant la phase de lecture.  Il faut remarquer que cette construction n'a pas la propriété qu'on peut calculer le hash d'un jeu de données agrandi à partir du hash du jeu original et des nouvelles données: il faut re-passer sur le jeu d'origine.

Des MAC obtenu à partir de fonctions de hachage.

Il y a quelques constructions vaines utilisant une fonction de hachage pour produire un MAC qui sont vulnérables si la fonction de hachage peut être "continuée" avec les nouvelles données (ceci n'est pas le cas d'une construction d'éponge).  Effectivement, si Hn+1 peut être calculé à partir de Hn il peut parfois être possible d'ajouter du texte (ou du code !) à un texte donné, et de produire un nouveau MAC valide à partir du MAC d'origine, sans devoir connaître la clé.

La construction la plus évidente, à première vue, d'un MAC, est de prendre un hash des données, et de crypter ce hash avec un chiffrement en bloc.  Seulement, il faut être très vigilant quand on fait cela, car une telle construction n'est pas nécessairement sûre.  Par exemple, si on utilise le mode CTR, et on chiffre le hash, comme le texte en clair et le texte chiffré (le MAC) est connu par l'ennemi, il peut facilement calculer le "masque jetable".  Il suffit alors de calculer le XOR avec le hash du nouveau texte, et il a obtenu un MAC valide pour n'importe quel autre texte.  Il y a des façons d'utiliser un chiffrement d'un hash pour obtenir un MAC sûr, mais on dépend de propriétés du chiffrement qui ne sont pas toujours évidentes.

C'est de nouveau un exemple de la mauvaise idée de "fabriquer de la cryptographie dans sa cave".  Il y a des façons sûrs de fabriquer un MAC à partir d'une fonction de hachage.  C'est HMAC.

HMAC

Si on a une clé secrète K (de la même longueur qu'un bloc de fonction de hachage) dont on peut produire deux clés auxiliaires Ki et Ko de la façon suivante:

Ki = K xor (une succession de "00110110")

Ko = K xor (une succession de "01011100")

Si C est le texte en clair long et h est l'application de hachage qui peut prendre un texte de longueur arbitraire, alors:

HMAC(C, K)  = h( Ko // h( Ki // C) )

ou il faut comprendre // comme une concaténation.

La construction HMAC nécessite peu de calculs supplémentaires comparé à un simple calcul de hachage d'un texte: le deuxième hash est un hachage d'un tout petit texte.

Padding

Une considération pratique pour toute cryptographie basée sur des blocs est que le texte en clair doit être coupé en blocs de longueur M, ce qui veut dire qu'on ne peut considérer que des textes en clair de longueur un multiple de M.  Dans la pratique, bien sûr, cela n'est pas le cas, et il faut donc rallonger un texte pour qu'il ait une longueur qui est un multiple de M.  Cette procédure est appelée le "padding".

La plupart des standards cryptographiques spécifient exactement comment il faut faire ce padding.  La façon triviale est d'ajouter des bits "0" au texte en clair jusqu'à ce que la bonne longueur est atteinte.  Cela a cependant le désavantage qu'on ne sait plus quels bits "0" appartenaient à la fin du texte en clair, et lesquels sont des ajouts du padding.  C'est pourquoi une technique populaire consiste à ajouter un 1, suivi d'autant de 0 qu'il faut pour obtenir la bonne longueur.  S'il le faut, c'est à dire, quand le texte en clair était de la bonne longueur, il faut ajouter un bloc complet consistant d'un seul un et de M-1 zéros.

Le protocol SHA-1 modifie ce padding en ajoutant, à la fin, un mot de 64 bits qui représente un entier non-signé spécifiant la longueur du texte en clair.

Le protocol SHA-3 (Keccak) modifie ce padding d'une autre façon: le padding consiste à ajouter un "01", suivi d'un 1, et d'un nombre de 0, pour finir en un 1.  La longueur du texte en clair n'est pas ajouté.