Cryptage préservant le format

En cryptographie , le chiffrement préservant le format ( FPE ) fait référence au chiffrement de telle manière que la sortie (le texte chiffré ) soit au même format que l'entrée (le texte en clair ). La signification du « format » varie. En général, seuls des ensembles finis de caractères sont utilisés : numériques, alphabétiques ou alphanumériques. Par exemple :

• Crypter un numéro de carte de crédit à 16 chiffres afin que le texte chiffré soit un autre numéro à 16 chiffres.
• Crypter un mot anglais afin que le texte chiffré soit un autre mot anglais.
• Cryptage d'un nombre à n bits de sorte que le texte chiffré soit un autre nombre à n bits (c'est la définition d'un chiffrement par bloc à n bits).

Pour de tels domaines finis, et pour les besoins de la discussion ci-dessous, le chiffrement est équivalent à une permutation de N entiers {0, ... , N −1 } où N est la taille du domaine.

L'une des motivations de l'utilisation du FPE est liée aux problèmes liés à l'intégration du chiffrement dans les applications existantes, avec des modèles de données bien définis. Un exemple typique serait un numéro de carte de crédit , tel que 1234567812345670(16 octets de long, chiffres uniquement).

L'ajout d'un chiffrement à de telles applications peut s'avérer difficile si les modèles de données doivent être modifiés, car cela implique généralement de modifier les limites de longueur des champs ou les types de données. Par exemple, la sortie d'un chiffrement par bloc classique transformerait le numéro de carte de crédit en une valeur hexadécimale (par exemple 0x96a45cbcf9c2a9425cde9e274948cb67, 34 octets, chiffres hexadécimaux) ou en une valeur Base64 (par exemple lqRcvPnCqUJc3p4nSUjLZw==, 24 octets, caractères alphanumériques et spéciaux), ce qui interromprait toutes les applications existantes qui s'attendent à ce que le numéro de carte de crédit soit un numéro à 16 chiffres.

Outre les problèmes de formatage simples, l'utilisation du mode AES-128-CBC peut entraîner le chiffrement de ce numéro de carte de crédit en valeur hexadécimale 0xde015724b081ea7003de4593d792fd8b695b39e095c98f3a220ff43522a2df02. Outre les problèmes causés par la création de caractères non valides et l'augmentation de la taille des données, les données chiffrées à l'aide du mode CBC d'un algorithme de chiffrement changent également de valeur lorsqu'elles sont déchiffrées et chiffrées à nouveau. Cela se produit car la valeur de départ aléatoire utilisée pour initialiser l'algorithme de chiffrement et incluse dans la valeur chiffrée est différente pour chaque opération de chiffrement. Pour cette raison, il est impossible d'utiliser des données chiffrées avec le mode CBC comme clé unique pour identifier une ligne dans une base de données.

FPE tente de simplifier le processus de transition en préservant le formatage et la longueur des données d'origine, permettant ainsi un remplacement immédiat des valeurs en texte clair par leurs textes chiffrés dans les applications héritées.

Bien qu'une permutation véritablement aléatoire soit le chiffrement FPE idéal, pour les grands domaines, il est impossible de pré-générer et de mémoriser une permutation véritablement aléatoire. Le problème du FPE est donc de générer une permutation pseudo-aléatoire à partir d'une clé secrète, de telle sorte que le temps de calcul pour une valeur unique soit faible (idéalement constant, mais surtout inférieur à O(N) ).

Un chiffrement par bloc de n bits est techniquement un FPE sur l'ensemble {0, ..., 2 ⁿ -1 }. Si un FPE est nécessaire sur l'un de ces ensembles de taille standard (par exemple, n = 64 pour DES et n = 128 pour AES), un chiffrement par bloc de la bonne taille peut être utilisé.

Cependant, dans l'usage courant, un chiffrement par bloc est utilisé dans un mode de fonctionnement qui lui permet de chiffrer des messages de longueur arbitraire, et avec un vecteur d'initialisation tel que décrit ci-dessus. Dans ce mode, un chiffrement par bloc n'est pas un FPE.

Dans la littérature cryptographique (voir la plupart des références ci-dessous), la mesure d'un « bon » FPE est la capacité d'un attaquant à distinguer le FPE d'une permutation véritablement aléatoire. Différents types d'attaquants sont postulés, selon qu'ils ont accès à des oracles ou à des paires de texte chiffré/texte clair connues.

Dans la plupart des approches répertoriées ici, un chiffrement par bloc bien compris (tel que AES ) est utilisé comme primitive pour remplacer une fonction aléatoire idéale. Cela présente l'avantage de faciliter l'incorporation d'une clé secrète dans l'algorithme. Lorsque AES est mentionné dans la discussion suivante, tout autre bon chiffrement par bloc fonctionnerait également.

La mise en œuvre de FPE avec une sécurité prouvée liée à celle du chiffrement par bloc sous-jacent a été entreprise pour la première fois dans un article des cryptographes John Black et Phillip Rogaway , qui ont décrit trois façons de procéder. Ils ont prouvé que chacune de ces techniques est aussi sûre que le chiffrement par bloc utilisé pour la construire. Cela signifie que si l'algorithme AES est utilisé pour créer un algorithme FPE, alors l'algorithme FPE résultant est aussi sûr qu'AES car un adversaire capable de vaincre l'algorithme FPE peut également vaincre l'algorithme AES. Par conséquent, si AES est sûr, alors les algorithmes FPE construits à partir de celui-ci sont également sûrs. Dans tout ce qui suit, E désigne l'opération de chiffrement AES qui est utilisée pour construire un algorithme FPE et F désigne l'opération de chiffrement FPE.

Une façon simple de créer un algorithme FPE sur {0, ..., N -1} consiste à attribuer un poids pseudo-aléatoire à chaque entier, puis à trier par poids. Les poids sont définis en appliquant un chiffrement par bloc existant à chaque entier. Black et Rogaway appellent cette technique un « chiffrement par préfixe » et ont montré qu'elle était probablement aussi efficace que le chiffrement par bloc utilisé.

Ainsi, pour créer un FPE sur le domaine {0,1,2,3}, étant donné une clé K, appliquez AES( K ) à chaque entier, donnant, par exemple,

poids (0) = 0x56c644080098fc5570f2b329323dbf62 poids (1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7 poids (2) = 0x47d2e1bf72264fa01fb274465e56ba20 poids (3) = 0x077de40941c93774857961a8a772650d 

Le tri [0,1,2,3] par poids donne [3,1,2,0], donc le chiffre est

F (0) = 3 F (1) = 1 F (2) = 2 F (3) = 0 

Cette méthode n'est utile que pour les petites valeurs de N. Pour des valeurs plus grandes, la taille de la table de recherche et le nombre de chiffrements requis pour initialiser la table deviennent trop importants pour être pratiques.

S'il existe un ensemble M de valeurs autorisées dans le domaine d'une permutation pseudo-aléatoire P (par exemple P peut être un chiffrement par bloc comme AES), un algorithme FPE peut être créé à partir du chiffrement par bloc en appliquant de manière répétée le chiffrement par bloc jusqu'à ce que le résultat soit l'une des valeurs autorisées (dans M ).

CycleWalkingFPE(x) { si 
P (x) est un élément de M 
alors 
renvoie 
P (x) sinon 
renvoie CycleWalkingFPE( P (x)) } 

La récursivité est garantie de se terminer. (Parce que P est bijectif et que le domaine est fini, l'application répétée de P forme un cycle, donc en commençant par un point dans M, le cycle finira par se terminer dans M. )

Cette méthode présente l'avantage de ne pas avoir à mapper les éléments de M sur une séquence consécutive {0,..., N -1} d'entiers. Elle présente l'inconvénient que, lorsque M est beaucoup plus petit que le domaine de P , un trop grand nombre d'itérations peut être nécessaire pour chaque opération. Si P est un chiffrement par blocs de taille fixe, tel que AES, il s'agit d'une restriction sévère sur les tailles de M pour lesquelles cette méthode est efficace.

Par exemple, une application peut vouloir chiffrer des valeurs de 100 bits avec AES de manière à créer une autre valeur de 100 bits. Avec cette technique, le chiffrement AES-128-ECB peut être appliqué jusqu'à atteindre une valeur dont les 28 bits les plus élevés sont définis sur 0, ce qui prendra en moyenne 2,28 ^itérations .

Il est également possible de créer un algorithme FPE en utilisant un réseau Feistel . Un réseau Feistel nécessite une source de valeurs pseudo-aléatoires pour les sous-clés de chaque tour, et la sortie de l'algorithme AES peut être utilisée comme ces valeurs pseudo-aléatoires. Une fois cette opération effectuée, la construction Feistel résultante est bonne si suffisamment de tours sont utilisés.

Une façon d'implémenter un algorithme FPE en utilisant AES et un réseau Feistel consiste à utiliser autant de bits de sortie AES que nécessaire pour égaler la longueur des moitiés gauche ou droite du réseau Feistel. Si une valeur de 24 bits est nécessaire comme sous-clé, par exemple, il est possible d'utiliser les 24 bits les plus bas de la sortie d'AES pour cette valeur.

Cela ne permet pas nécessairement à la sortie du réseau de Feistel de conserver le format de l'entrée, mais il est possible d'itérer le réseau de Feistel de la même manière que la technique de marche à vélo pour garantir que le format peut être préservé. Comme il est possible d'ajuster la taille des entrées d'un réseau de Feistel, il est possible de faire en sorte que cette itération se termine très rapidement en moyenne. Dans le cas des numéros de carte de crédit, par exemple, il existe 10 ¹⁵ numéros de carte de crédit possibles à 16 chiffres (en tenant compte du chiffre de contrôle redondant ), et comme 10 ¹⁵ ≈ 2 ^49,8 , l'utilisation d'un réseau de Feistel de 50 bits de large avec la marche à vélo créera un algorithme FPE qui crypte assez rapidement en moyenne.

Un mélange de Thorp est comme un mélange de cartes idéalisé, ou de manière équivalente, un chiffrement Feistel déséquilibré au maximum où un côté est un seul bit. Il est plus facile de prouver la sécurité des chiffrements Feistel déséquilibrés que des chiffrements équilibrés.

Pour les tailles de domaine qui sont une puissance de deux et un chiffrement par bloc existant avec une taille de bloc plus petite, un nouveau chiffrement peut être créé en utilisant le mode VIL tel que décrit par Bellare, Rogaway.

Le chiffrement Hasty Pudding utilise des constructions personnalisées (ne dépendant pas des chiffrements par blocs existants comme primitives) pour crypter des petits domaines finis arbitraires.

Le mode FFSEM d'AES (spécification ) qui a été accepté pour examen par le NIST utilise la construction de réseau Feistel de Black et Rogaway décrite ci-dessus, avec AES pour la fonction ronde, avec une légère modification : une seule clé est utilisée et est légèrement modifiée pour chaque tour.

Depuis février 2010, FFSEM a été remplacé par le mode FFX écrit par Mihir Bellare , Phillip Rogaway et Terence Spies. (spécification, NIST Block Cipher Modes Development, 2010).

Dans la norme JPEG 2000 , les codes marqueurs (dans la plage 0xFF90 à 0xFFFF) ne doivent pas apparaître dans le texte en clair et le texte chiffré. La technique modulaire simple 0xFF90 ne peut pas être appliquée pour résoudre le problème de chiffrement JPEG 2000. Par exemple, les mots de texte chiffré 0x23FF et 0x9832 sont valides, mais leur combinaison 0x23FF9832 devient invalide car elle introduit le code marqueur 0xFF98. De même, la technique simple de marche à vélo ne peut pas être appliquée pour résoudre le problème de chiffrement JPEG 2000 car deux blocs de texte chiffré valides peuvent donner un texte chiffré invalide lorsqu'ils sont combinés. Par exemple, si le premier bloc de texte chiffré se termine par les octets "...30FF" et que le deuxième bloc de texte chiffré commence par les octets "9832...", alors le code marqueur "0xFF98" apparaîtra dans le texte chiffré.

Deux mécanismes de cryptage préservant le format du JPEG 2000 ont été présentés dans l'article « Efficient and Secure Encryption Schemes for JPEG2000 » de Hongjun Wu et Di Ma. Pour réaliser un cryptage préservant le format du JPEG 2000, la technique consiste à exclure l'octet « 0xFF » du cryptage et du décryptage. Ensuite, un mécanisme de cryptage JPEG 2000 effectue une addition modulo-n avec un chiffrement par flux ; un autre mécanisme de cryptage JPEG 2000 effectue la technique de marche cyclique avec un chiffrement par bloc.

Plusieurs constructions FPE sont basées sur l'ajout de la sortie d'un chiffrement standard, modulo n, aux données à chiffrer, avec diverses méthodes de correction du résultat. L'ajout modulo n partagé par de nombreuses constructions est la solution immédiatement évidente au problème FPE (d'où son utilisation dans un certain nombre de cas), les principales différences étant les mécanismes de correction utilisés.

La section 8 de la norme FIPS 74, Federal Information Processing Standards Publication 1981 Guidelines for Implementation and Using the NBS Data Encryption Standard décrit une manière d'utiliser l'algorithme de chiffrement DES de manière à préserver le format des données via une addition modulo-n suivie d'une opération de correction de biais. Cette norme a été retirée le 19 mai 2005, la technique doit donc être considérée comme obsolète en tant que norme formelle.

Un autre mécanisme précoce de cryptage préservant le format était le « cryptage des données avec une plage de valeurs restreinte » de Peter Gutmann qui effectue à nouveau une addition modulo-n sur n'importe quel chiffrement avec quelques ajustements pour rendre le résultat uniforme, le cryptage résultant étant aussi fort que l'algorithme de cryptage sous-jacent sur lequel il est basé.

L'article « Using Datatype-Preserving Encryption to Enhance Data Warehouse Security » de Michael Brightwell et Harry Smith décrit une manière d'utiliser l' algorithme de chiffrement DES de manière à préserver le format du texte en clair. Cette technique ne semble pas appliquer une étape de dépolarisation comme le font les autres techniques modulo-n référencées ici.

L'article « Format-Preserving Encryption » de Mihir Bellare et Thomas Ristenpart décrit l'utilisation de réseaux Feistel « presque équilibrés » pour créer des algorithmes FPE sécurisés.

L'article « Format Controlling Encryption Using Datatype Preserving Encryption » d'Ulf Mattsson décrit d'autres façons de créer des algorithmes FPE.

Un exemple d'algorithme FPE est FNR ( Flexible Naor et Reingold ).

La publication spéciale 800-38G du NIST, « Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption » spécifie deux méthodes : FF1 et FF3. Des détails sur les propositions soumises pour chacune d'elles sont disponibles sur le site NIST Block Cipher Modes Development, y compris des informations sur les brevets et les vecteurs de test. Des exemples de valeurs sont disponibles pour FF1 et FF3.

• FF1 est le « mode de chiffrement basé sur Feistel préservant le format » de FFX[Radix], qui est également en cours de normalisation sous ANSI X9 sous les noms X9.119 et X9.124. Il a été soumis au NIST par Mihir Bellare de l'Université de Californie à San Diego, Phillip Rogaway de l'Université de Californie à Davis et Terence Spies de Voltage Security Inc. Des vecteurs de test sont fournis et certaines parties sont brevetées. (DRAFT SP 800-38G Rev 1) exige que la taille minimale du domaine des données chiffrées soit de 1 million (auparavant 100).

• FF3 est un BPS nommé d'après les auteurs. Il a été soumis au NIST par Éric Brier , Thomas Peyrin et Jacques Stern d' Ingenico en France. Les auteurs ont déclaré au NIST que leur algorithme n'est pas breveté. Le produit CyberRes Voltage, bien que prétendant détenir des brevets également pour le mode BPS. Le 12 avril 2017, le NIST a conclu que FF3 n'est « plus adapté comme méthode FPE à usage général » car les chercheurs ont découvert une vulnérabilité.
• FF3-1 (DRAFT SP 800-38G Rev 1) remplace FF3 et exige que la taille minimale du domaine des données chiffrées soit de 1 million (auparavant 100).

Un autre mode a été inclus dans le projet de guide du NIST mais a été supprimé avant la publication finale.

• FF2 est le schéma VAES3 pour FFX : un addendum à « Le mode de fonctionnement FFX pour la préservation du chiffrement » : une collection de paramètres pour chiffrer des chaînes de base arbitraire avec une opération de sous-clé pour prolonger la durée de vie de la clé de chiffrement. Il a été soumis au NIST par Joachim Vance de VeriFone Systems Inc. Les vecteurs de test ne sont pas fournis séparément de FF1 et certaines parties sont brevetées. Les auteurs ont soumis un algorithme modifié sous le nom de DFF qui est activement étudié par le NIST.

La Corée a également développé une norme FPE, FEA-1 et FEA-2.

Les implémentations Open Source de FF1 et FF3 sont disponibles publiquement en langage C, langage Go, Java, Node.js, Python, C#/.Net et Rust