Nombre rien-dans-la-manche

Carte dissimulée dans une manche.

Les nombres rien-dans-la-manche (en anglais : nothing-up-my-sleeve number) sont des nombres utilisés en cryptographie dont la définition leur évite d'être soupçonnés d'avoir des propriétés cachées. La formule est empruntée au monde de la prestidigitation, lorsque le magicien montre qu'il ne cache pas de carte dans sa manche avant son tour.

Description

Ces nombres sont utilisés dans la spécification de fonctions cryptographiques telles que les fonctions de hachage et les algorithmes de chiffrement, qui ont souvent besoin de constantes arbitraires, explicitement définies, par exemple pour initialiser leur état ou effectuer une permutation initiale sur leur entrée.

On peut alors choisir les valeurs de ces constantes afin qu'il soit évident qu'elles n'aient pas pu être manipulées dans un but néfaste, par exemple, pour créer une porte dérobée à l'algorithme. En utilisant des nombres connus d'avance ou créés d'une manière qui laisse peu de place possible à l'ajustement ou la manipulation, on peut ainsi dissiper de tels soupçons.

Par exemple, on peut utiliser comme constante initiale un nombre formé des 10 premières décimales de π. Un algorithme qui l'utilise dans sa définition sera vu comme plus digne de confiance qu'un autre qui utiliserait les décimales de π à partir de la 10 294 317^e décimale. En effet, dans le dernier cas, le concepteur de l'algorithme aurait pu sélectionner spécifiquement ce point de départ pour que le nombre choisit affaiblisse les propriétés de la fonction, ce que le concepteur pourrait ensuite exploiter. Leur utilisation est motivée par une controverse qui a rapidement fait surface autour du Data Encryption Standard, un standard de chiffrement publié par le gouvernement américain en 1975. Sa définition fit l'objet de critiques; en effet aucune explication n'avait été fournie pour les constantes utilisées dans ses tables de substitutions (ou S-box).

On supposa alors que ces constantes avaient été choisies par la NSA pour rendre les messages chiffrés avec ce standard plus faciles à déchiffrer. Il fut découvert plus tard qu'elles avaient effectivement été soigneusement sélectionnées, non pas pour affaiblir, mais pour renforcer l'algorithme contre une technique de cryptanalyse encore tenue secrète à l'époque : la cryptanalyse différentielle. Toutefois, à la suite de cette controverse, il apparut nécessaire de faire preuve de transparence dans le choix des constantes pour les normes cryptographiques.

On conjecture que, dans la représentation en notation positionnelle (dans une base quelconque) de nombre réels tels que π, e ou les racines carrées, tous les chiffres apparaissent à la même fréquence (ce sont des nombres normaux). Ces nombres peuvent être considérés comme l'opposé des nombres aléatoires au sens de Chaitin-Kolmogorov, puisque la suite de leur chiffres est d'aspect aléatoire mais ils ont une entropie d'information très faible. Ces nombres sont donc des candidats idéaux pour générer des suites de chiffres au-dessus de tout soupçon.

Exemples

• Ronald Rivest utilisa la fonction sinus pour générer les constantes de la fonction de hachage MD5.
• La National Security Agency aux États-Unis utilisa des racines carrées de petits nombres entiers pour produire les constantes utilisées dans l'algorithme SHA-1. Les fonctions SHA-2 utilisent les racines carrées et les racines cubiques des petits nombres premiers. SHA-1 utilise également le nombre hexadécimal 0123456789ABCDEFFEDCBA9876543210F0E1D2C3 comme valeur de hachage initiale.
• L'algorithme de chiffrement Blowfish utilise la représentation binaire de π (sans le 3 initial) pour initialiser l'étape de préparation des clés.
• La RFC 3526 spécifie des nombres premiers pour le protocole Internet Key Exchange qui sont également générés à partir de π.
• La S-box de l'algorithme de chiffrement NewDES est dérivée de la déclaration d'indépendance des États-Unis.
• L'algorithme DFC, candidat au standard de chiffrement AES, dérive toutes ses constantes arbitraires, y compris toutes les entrées de la S-box, à partir du développement binaire de e.
• Le schéma de clé ARIA utilise le développement binaire de 1/ π.
• Le schéma de clé du chiffrement RC5 utilise des chiffres binaires provenant à la fois de e et du nombre d'or.
• Plusieurs algorithmes de chiffrement, par exemple TEA et Red Pike, utilisent 2654435769 ou 0x9e3779b9 qui est ⌊2 ³² / ϕ ⌋, où ϕ est le nombre d'or.
• La fonction de hachage BLAKE, finaliste du concours SHA-3, utilise une table de 16 mots constants qui sont les 512 ou 1024 bits de initiaux de la partie décimale de π .
• Le schéma de clé de l'algorithme KASUMI utilise 0x123456789ABCDEFFEDCBA9876543210 pour dériver la clé modifiée.
• La famille de chiffrements Salsa20 utilise la chaîne ASCII "expand 32-byte k" comme constantes dans son processus d'initialisation de bloc.

Contre-exemples

• La S-box de la fonction de hachage Streebog était censée avoir été générée de manière aléatoire, mais, après étude. s'est avérée avoir été générée de manière algorithmique et avoir quelques faiblesses « surprenantes ».
• Le Data Encryption Standard (DES) a des constantes données par la NSA. Ils se sont révélés être loin d'être aléatoires, ayant été séléctionées pour que l'algorithme résiste à la cryptanalyse différentielle, une méthode non connue du public à l'époque.
• Dual_EC_DRBG, un générateur de bits pseudo-aléatoires cryptographiques recommandé par le NIST, a fait l'objet de critiques en 2007 parce que les constantes recommandées pour une utilisation dans l'algorithme auraient pu être sélectionnées de manière à permettre à leur auteur de prédire les sorties futures à partir d'un échantillon de valeurs générées par le passé. En septembre 2013, d'après le New York Times, « des mémos internes divulgués par un ancien sous-traitant de la NSA, Edward Snowden, suggèrent que la NSA a généré l'un des générateurs de nombres aléatoires utilisés dans une norme NIST de 2006 - appelée la norme Dual EC DRBG - qui contient une porte dérobée pour la NSA ».
• Les courbes P sont normalisées par le NIST pour la cryptographie des courbes elliptiques. Les coefficients de ces courbes sont générés en hachant des graines aléatoires inexpliquées, telles que :
  • P-224 : bd713447 99d5c7fc dc45b59f a3b9ab8f 6a948bc5 .
  • P-256 : c49d3608 86e70493 6a6678e1 139d26b7 819f7e90 .
  • P-384 : a335926a a319a27a 1d00896a 6773a482 7acdac73 .

Bien qu'ils ne soient pas directement liés, après que la porte dérobée dans Dual EC DRBG ait été exposée, des aspects suspects des constantes de la courbe P du NIST ont fait craindre que la NSA ait choisi des valeurs qui leur donnaient un avantage pour trouver des clés privées. Depuis lors, de nombreux protocoles et programmes ont commencé à utiliser la courbe 25519 comme alternative à la courbe NIST P-256.

Limites

Bernstein et collègues démontrent que l'utilisation de nombres rien-dans-la-manche comme point de départ d'une procédure cryptographique complexe (par exemple les courbes elliptiques) peut ne pas être suffisante pour empêcher l'insertion de portes dérobées. En effet, il y aurait un espace suffisamment large de constantes "insoupçonnables"parmi lesquelles choisir pour qu'on puisse en trouver une ayant des propriétés de portes dérobées souhaitées.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Nothing-up-my-sleeve number » (voir la liste des auteurs).