Rembourrage (cryptographie)

En cryptographie , le remplissage est l'une des nombreuses pratiques distinctes qui consistent toutes à ajouter des données au début, au milieu ou à la fin d'un message avant le chiffrement. En cryptographie classique, le remplissage peut consister à ajouter des phrases absurdes à un message pour masquer le fait que de nombreux messages se terminent de manière prévisible, par exemple « Cordialement » .

Les messages officiels commencent et se terminent souvent de manière prévisible : « Mon cher ambassadeur », « Bulletin météo », « Cordialement » , etc. L'utilisation principale du remplissage avec les chiffrements classiques est d'empêcher le cryptanalyste d'utiliser cette prévisibilité pour trouver un texte en clair connu qui l'aiderait à casser le chiffrement. Le remplissage de longueur aléatoire empêche également un attaquant de connaître la longueur exacte du message en clair.

Un exemple célèbre de ce type de « rembourrage classique » qui a causé un grand malentendu est l' incident des « merveilles du monde », qui a presque causé une perte alliée lors de la bataille de Samar pendant la Seconde Guerre mondiale , une partie de la plus grande bataille du golfe de Leyte . Dans cet exemple, l'amiral Chester Nimitz , commandant en chef de la flotte américaine du Pacifique pendant la Seconde Guerre mondiale, a envoyé le message suivant à l'amiral Bull Halsey , commandant de la Force opérationnelle 34 (la principale flotte alliée) lors de la bataille du golfe de Leyte, le 25 octobre 1944 :

Où est, je répète, où est la Force opérationnelle trente-quatre ?

Avec le remplissage (en gras) et les métadonnées ajoutées, le message est devenu :

TURKEY TROTS TO WATER GG FROM CINCPAC ACTION COM THIRD FLEET INFO COMINCH CTF SEVENTY-SEVEN X WHERE IS RPT WHERE IS TASK FORCE THIRTY FOUR RR THE WORLD WONDERS

L'opérateur radio de Halsey a confondu une partie du remplissage avec le message et l'amiral Halsey a fini par lire le message suivant :

Où est, je répète, où est la Force opérationnelle 34 ? Le monde s'interroge

L'amiral Halsey a interprété la phrase de remplissage « les merveilles du monde » comme une réprimande sarcastique, ce qui lui a valu une explosion émotionnelle et l'a ensuite enfermé dans son pont et boudé pendant une heure avant de déplacer ses forces pour aider à la bataille de Samar. L'opérateur radio de Halsey aurait dû être averti par les lettres RR que « les merveilles du monde » était un remplissage ; tous les autres opérateurs radio qui ont reçu le message de l'amiral Nimitz ont correctement supprimé les deux phrases de remplissage.

De nombreux chiffrements classiques organisent le texte en clair selon des modèles particuliers (par exemple, des carrés, des rectangles, etc.) et si le texte en clair ne correspond pas exactement, il est souvent nécessaire d'ajouter des lettres supplémentaires pour compléter le modèle. L'utilisation de lettres sans sens à cette fin présente l'avantage de rendre certains types de cryptanalyse plus difficiles.

La plupart des fonctions de hachage cryptographiques modernes traitent les messages en blocs de longueur fixe. Toutes, à l'exception des plus anciennes, incluent une sorte de schéma de remplissage. Il est essentiel que les fonctions de hachage cryptographiques utilisent des schémas de terminaison qui empêchent un hachage d'être vulnérable aux attaques par extension de longueur .

De nombreux schémas de remplissage sont basés sur l'ajout de données prévisibles au bloc final. Par exemple, le remplissage peut être dérivé de la longueur totale du message. Ce type de schéma de remplissage est couramment appliqué aux algorithmes de hachage qui utilisent la construction Merkle–Damgård comme MD-5 , SHA-1 et la famille SHA-2 comme SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 et SHA-512/256

Le mode de chaînage de blocs de chiffrement (CBC) est un exemple de mode de fonctionnement de chiffrement par blocs . Certains modes de chiffrement par blocs (CBC et PCBC essentiellement) pour les algorithmes de chiffrement à clé symétrique nécessitent une entrée de texte brut qui est un multiple de la taille du bloc, de sorte que les messages peuvent devoir être complétés pour les amener à cette longueur.

Il y a actuellement un changement pour utiliser le mode de fonctionnement en streaming au lieu du mode de fonctionnement en bloc. Un exemple de chiffrement en mode streaming est le mode de fonctionnement compteur . Les modes de fonctionnement en streaming peuvent chiffrer et déchiffrer des messages de toute taille et ne nécessitent donc pas de remplissage. Des méthodes plus complexes pour terminer un message, telles que le vol de texte chiffré ou la terminaison de bloc résiduel, évitent le besoin de remplissage.

L'inconvénient du remplissage est qu'il rend le texte brut du message vulnérable aux attaques de type oracle de remplissage . Les attaques de type oracle de remplissage permettent à l'attaquant d'obtenir des informations sur le texte brut sans attaquer la primitive de chiffrement par bloc elle-même. Les attaques de type oracle de remplissage peuvent être évitées en s'assurant qu'un attaquant ne puisse pas obtenir d'informations sur la suppression des octets de remplissage. Cela peut être accompli en vérifiant un code d'authentification de message (MAC) ou une signature numérique avant la suppression des octets de remplissage, ou en passant à un mode de fonctionnement en continu.

Le remplissage de bits peut être appliqué à des messages de n'importe quelle taille.

Un seul bit « 1 » est ajouté au message, puis autant de bits « 0 » que nécessaire (éventuellement aucun) sont ajoutés. Le nombre de bits « 0 » ajoutés dépend de la limite du bloc auquel le message doit être étendu. En termes de bits, cela correspond à « 1000 ... 0000 ».

Cette méthode peut être utilisée pour remplir des messages dont la longueur est de n'importe quel nombre de bits, pas nécessairement d'un nombre entier d'octets. Par exemple, un message de 23 bits complété avec 9 bits afin de remplir un bloc de 32 bits :

... | 1011 1001 1101 0100 0010 011 1 0000 0000 | 

Ce remplissage est la première étape d'un schéma de remplissage en deux étapes utilisé dans de nombreuses fonctions de hachage, notamment MD5 et SHA . Dans ce contexte, il est spécifié par l'étape 3.1 de la RFC1321.

Ce schéma de remplissage est défini par la norme ISO/IEC 9797-1 comme méthode de remplissage 2.

Le remplissage d'octets peut être appliqué aux messages qui peuvent être codés sous la forme d'un nombre entier d' octets .

Dans la norme ANSI X9.23, entre 1 et 8 octets sont toujours ajoutés en guise de remplissage. Le bloc est complété avec des octets aléatoires (bien que de nombreuses implémentations utilisent 00) et le dernier octet du bloc est défini sur le nombre d'octets ajoutés.

Exemple : Dans l'exemple suivant, la taille du bloc est de 8 octets et un remplissage est requis pour 4 octets (au format hexadécimal).

... | JJ DD DD DD DD DD DD DD | JJ JJ JJ JJ 00 00 00 04 | 

La norme ISO 10126 (retirée, 2007 ) spécifie que le remplissage doit être effectué à la fin de ce dernier bloc avec des octets aléatoires, et la limite de remplissage doit être spécifiée par le dernier octet.

Exemple : Dans l'exemple suivant, la taille du bloc est de 8 octets et un remplissage est requis pour 4 octets

... | JJ DD DD DD DD DD DD DD | DD DD DD DD 81 A6 23 04 | 

PKCS#7 est décrit dans la RFC 5652.

Le remplissage est en octets entiers. La valeur de chaque octet ajouté est le nombre d'octets ajoutés, c'est-à-dire N octets, chacun de valeur N étant ajouté. Le nombre d'octets ajoutés dépendra de la limite du bloc auquel le message doit être étendu.

Le rembourrage sera l'un des suivants :

01 02 02 03 03 03 04 04 04 04 05 05 05 05 05 06 06 06 06 06 06 etc. 

Cette méthode de remplissage (ainsi que les deux précédentes) est bien définie si et seulement si N est inférieur à 256.

Exemple : Dans l'exemple suivant, la taille du bloc est de 8 octets et un remplissage est requis pour 4 octets

... | JJ DD DD DD DD DD DD DD | JJ JJ JJ JJ 04 04 04 04 | 

Si la longueur des données d'origine est un multiple entier de la taille du bloc B , alors un bloc supplémentaire d'octets avec la valeur B est ajouté. Cela est nécessaire pour que l'algorithme de déchiffrement puisse déterminer avec certitude si le dernier octet du dernier bloc est un octet de remplissage indiquant le nombre d'octets de remplissage ajoutés ou une partie du message en clair. Considérons un message en clair qui est un multiple entier de B octets avec le dernier octet de texte en clair étant 01. Sans information supplémentaire, l'algorithme de déchiffrement ne sera pas en mesure de déterminer si le dernier octet est un octet de texte en clair ou un octet de remplissage. Cependant, en ajoutant B octets chacun de valeur B après l' octet de texte en clair 01 , l'algorithme de déchiffrement peut toujours traiter le dernier octet comme un octet de remplissage et retirer le nombre approprié d'octets de remplissage de la fin du texte chiffré ; ledit nombre d'octets à retirer étant basé sur la valeur du dernier octet.

Le remplissage PKCS#5 est identique au remplissage PKCS#7, à ceci près qu'il n'a été défini que pour les chiffrements par blocs qui utilisent une taille de bloc de 64 bits (8 octets). En pratique, les deux peuvent être utilisés de manière interchangeable.

La taille maximale du bloc est de 255, car c'est le plus grand nombre qu'un octet peut contenir.

La norme ISO/IEC 7816-4 :2005 est identique au schéma de remplissage de bits, appliqué à un texte brut de N octets. Cela signifie en pratique que le premier octet est un octet obligatoire de valeur '80' (hexadécimal) suivi, si nécessaire, de 0 à N − 1 octets définis sur '00', jusqu'à ce que la fin du bloc soit atteinte. La norme ISO/IEC 7816-4 elle-même est une norme de communication pour les cartes à puce contenant un système de fichiers et ne contient en elle-même aucune spécification cryptographique.

Exemple : Dans l'exemple suivant, la taille du bloc est de 8 octets et un remplissage est requis pour 4 octets

... | JJ DD DD DD DD DD DD DD | JJ JJ JJ JJ 80 00 00 00 | 

L'exemple suivant montre un remplissage d'un seul octet

... | JJ DD DD DD DD DD DD DD | JJ DD DD DD DD DD DD 80 | 

Tous les octets qui doivent être complétés sont complétés par des zéros. Le schéma de remplissage par zéros n'a pas été normalisé pour le chiffrement, bien qu'il soit spécifié pour les hachages et les MAC comme méthode de remplissage 1 dans les normes ISO/IEC 10118-1 et ISO/IEC 9797-1 .

Exemple : Dans l'exemple suivant, la taille du bloc est de 8 octets et un remplissage est requis pour 4 octets

... | JJ DD DD DD DD DD DD DD | JJ JJ JJ JJ 00 00 00 00 | 

Le remplissage par des zéros peut ne pas être réversible si le fichier d'origine se termine par un ou plusieurs octets nuls, ce qui rend impossible la distinction entre les octets de données en texte clair et les octets de remplissage. Il peut être utilisé lorsque la longueur du message peut être déduite hors bande . Il est souvent appliqué aux chaînes codées en binaire ( chaîne terminée par un caractère nul ) car le caractère nul peut généralement être supprimé sous forme d' espace blanc .

Le remplissage par zéro est parfois également appelé « remplissage nul » ou « remplissage par zéro octet ». Certaines implémentations peuvent ajouter un bloc supplémentaire de zéro octet si le texte en clair est déjà divisible par la taille du bloc.

En cryptographie à clé publique , le remplissage est le processus de préparation d'un message pour le chiffrement ou la signature à l'aide d'une spécification ou d'un schéma tel que PKCS#1 v2.2, OAEP , PSS , PSSR, IEEE P1363 EMSA2 et EMSA5. Une forme moderne de remplissage pour les primitives asymétriques est l'OAEP appliqué à l' algorithme RSA , lorsqu'il est utilisé pour chiffrer un nombre limité d'octets.

Cette opération est appelée « remplissage » car à l'origine, des éléments aléatoires étaient simplement ajoutés au message pour le rendre suffisamment long pour la primitive. Cette forme de remplissage n'est pas sécurisée et n'est donc plus appliquée. Un schéma de remplissage moderne vise à garantir que l'attaquant ne peut pas manipuler le texte en clair pour exploiter la structure mathématique de la primitive et sera généralement accompagné d'une preuve, souvent dans le modèle d'oracle aléatoire , que briser le schéma de remplissage est aussi difficile que de résoudre le problème difficile sous-jacent à la primitive.

Même si des routines cryptographiques parfaites sont utilisées, l'attaquant peut obtenir des informations sur le volume de trafic généré. Il peut ne pas savoir de quoi Alice et Bob parlaient, mais il peut savoir qu'ils parlaient et dans quelle mesure ils parlaient. Dans certaines circonstances, cette fuite peut être très compromettante. Prenons par exemple le cas d'une armée qui organise une attaque secrète contre une autre nation : il peut suffire d'alerter l'autre nation pour qu'elle sache simplement qu'une grande activité secrète est en cours.

À titre d’exemple, lors du chiffrement des flux de voix sur IP qui utilisent un codage à débit binaire variable, le nombre de bits par unité de temps n’est pas masqué, et cela peut être exploité pour deviner des phrases parlées. De même, les modèles de rafales que produisent les encodeurs vidéo courants sont souvent suffisants pour identifier de manière unique la vidéo en streaming qu’un utilisateur regarde. Même la taille totale d’un objet à elle seule, comme un site Web, un fichier, un téléchargement de logiciel ou une vidéo en ligne, peut identifier de manière unique un objet, si l’attaquant connaît ou peut deviner un ensemble connu d’où provient l’objet. Le canal auxiliaire de la longueur du contenu chiffré a été utilisé pour extraire des mots de passe des communications HTTPS dans les attaques bien connues CRIME et BREACH .

Le remplissage d'un message chiffré peut compliquer l'analyse du trafic en masquant la longueur réelle de sa charge utile. Le choix de la longueur à laquelle remplir un message peut être effectué de manière déterministe ou aléatoire ; chaque approche présente des points forts et des points faibles qui s'appliquent dans des contextes différents.

Un nombre aléatoire de bits ou d'octets de remplissage supplémentaires peut être ajouté à la fin d'un message, accompagné d'une indication à la fin de la quantité de remplissage ajoutée. Si la quantité de remplissage est choisie comme un nombre aléatoire uniforme compris entre 0 et un maximum M, par exemple, un espion ne sera pas en mesure de déterminer précisément la longueur du message dans cette plage. Si le remplissage maximal M est petit par rapport à la taille totale du message, alors ce remplissage n'ajoutera pas beaucoup de surcharge , mais le remplissage masquera uniquement les bits les moins significatifs de la longueur totale de l'objet, laissant la longueur approximative des grands objets facilement observable et donc toujours potentiellement identifiable de manière unique par leur longueur. Si le remplissage maximal M est comparable à la taille de la charge utile, en revanche, l'incertitude d'un espion sur la taille réelle de la charge utile du message est beaucoup plus grande, au prix que le remplissage peut ajouter jusqu'à 100 % de surcharge ( explosion 2× ) au message.

En outre, dans les scénarios courants dans lesquels un espion a la possibilité de voir de nombreux messages successifs provenant du même expéditeur, et ces messages sont similaires d'une manière que l'attaquant connaît ou peut deviner, alors l'espion peut utiliser des techniques statistiques pour diminuer et éventuellement même éliminer l'avantage du remplissage aléatoire. Par exemple, supposons que l'application d'un utilisateur envoie régulièrement des messages de la même longueur, et que l'espion connaisse ou puisse deviner ce fait en se basant sur l'empreinte digitale de l'application de l'utilisateur par exemple. Alternativement, un attaquant actif pourrait être en mesure d' inciter un point de terminaison à envoyer des messages régulièrement, par exemple si la victime est un serveur public. Dans de tels cas, l'espion peut simplement calculer la moyenne sur de nombreuses observations pour déterminer la longueur de la charge utile du message régulier.

Un schéma de remplissage déterministe remplit toujours une charge utile de message d'une longueur donnée pour former un message chiffré d'une longueur de sortie correspondante particulière. Lorsque de nombreuses longueurs de charge utile correspondent à la même longueur de sortie remplie, un espion ne peut pas distinguer ou apprendre d'informations sur la véritable longueur de la charge utile dans l'un de ces compartiments de longueur , même après de nombreuses observations de messages de même longueur transmis. À cet égard, les schémas de remplissage déterministes ont l'avantage de ne pas divulguer d'informations supplémentaires à chaque message successif de la même taille de charge utile.

D'un autre côté, supposons qu'un espion puisse tirer profit de la connaissance de petites variations dans la taille de la charge utile, comme par exemple un octet de plus ou moins dans une attaque de devinette de mot de passe. Si l'expéditeur du message a la malchance d'envoyer de nombreux messages dont la longueur de la charge utile ne varie que d'un octet, et que cette longueur se situe exactement à la frontière entre deux classes de remplissage déterministes, alors ces longueurs de charge utile de plus ou moins un donneront également des longueurs de remplissage différentes (plus ou moins un bloc par exemple), divulguant exactement les informations fines souhaitées par l'attaquant. Contre de tels risques, le remplissage aléatoire peut offrir une meilleure protection en masquant indépendamment les bits les moins significatifs de la longueur des messages.

Les méthodes de remplissage déterministes courantes incluent le remplissage à une taille de bloc constante et le remplissage à la puissance de deux immédiatement supérieure. Cependant, comme le remplissage aléatoire avec une petite quantité maximale M , le remplissage déterministe à une taille de bloc bien inférieure à la charge utile du message masque uniquement les bits les moins significatifs de la longueur réelle du message, laissant la longueur approximative réelle du message largement non protégée. Le remplissage des messages à une puissance de deux (ou toute autre base fixe) réduit la quantité maximale d' informations que le message peut divulguer via sa longueur de O (log M ) à O (log log M ) . Cependant, le remplissage à une puissance de deux augmente la surcharge de taille du message jusqu'à 100 %, et le remplissage à des puissances de bases entières plus grandes augmente encore la surcharge maximale.

Le schéma PADMÉ, proposé pour les blobs aléatoires uniformes rembourrés ou PURB , remplit de manière déterministe les messages jusqu'à des longueurs représentables sous forme de nombre à virgule flottante dont la mantisse n'est pas plus longue (c'est-à-dire ne contient pas plus de bits significatifs) que son exposant. Cette contrainte de longueur garantit qu'un message laisse fuir au plus O (log log M ) bits d'information via sa longueur, comme un remplissage à une puissance de deux, mais entraîne beaucoup moins de frais généraux d'au plus 12 % pour les messages minuscules et diminuant progressivement avec la taille du message.