Cryptanalyse des nombres premiers de 1024 bits truqués

Nous venons d'achever un calcul de logarithme discret considérable en taille (corps fini premier de 1024 bits), mais très facile (2 mois de calcul sur 2000 à 3000 cœurs). En comparaison, le «vrai» record en la matière (datant de ce printemps) est de seulement 768 bits, et a nécessité plus de 10 fois plus de ressources de calcul.

Pour parvenir à ce résultat, nous avons triché. Délibérément. Nous avons choisi le nombre premier qui définit le problème spécialement de sorte à ce que le calcul soit facile. Mais la trappe que l'on a ainsi fabriquée est subtile, et non détectable.

Malheureusement, pour la plupart de nombres premiers aujourd'hui utilisés en cryptographie, aucune garantie n'est fournie qui permette d'exclure qu'ils aient été truqués de la sorte, avec une trappe. En l'absence de trappe, les casser serait au moins 10 000 fois plus dur que ce que nous avons entrepris.

Notre travail fait peser le doute sur certains standards d'Internet qui promeuvent des nombres premiers qui ne sont assortis d'aucune garantie. Sur le papier, il serait techniquement possible de fournir des éléments de traçabilité prouvant l'absence de trappe. Ce n'est malheureusement presque jamais fait. Si une entité mal intentionnée a été en mesure de manipuler un standard, ou bien un logiciel en particulier pour forcer l'usage à grande échelle d'un ou plusieurs nombres premiers truqués, alors cette entité est en mesure, après un calcul initial similaire au nôtre, de casser en un temps faible toute communication «sécurisée» par ces nombres premiers.

Éléments techniques additionnels.

• Nous avons mené un calcul de logarithme discret de 1024 bits par le "special number field sieve", une variante rapide du "general number field sieve" (crible algébrique). Cette variante ne s'applique que dans de très rares cas.
• Le problème du logarithme discret est l'un des problèmes qui sont supposés difficiles pour garantir la sécurité du protocole Diffie-Hellman et des signatures DSA. Les records de calcul de logarithmes discret servent de base pour établir les recommandations de tailles de clés cryptographiques.
• Casser le problème du logarithme discret dans le contexte d'un échange de clé Diffie-Hellman permet à l'attaquant de décrypter les messages chiffrés avec la clé de session négociée par Diffie-Hellman. Casser le problème du logarithme discret dans le contexte d'une signature DSA permet à l'attaquant de falsifier des signatures.
• Pour certains nombres premiers de 1024 bits très utilisés, provenant par exemple de la RFC 5114, nous n'avons pas été en mesure de trouver des éléments permettant d'expliquer la façon dont ils ont été générés, et d'exclure la présence d'une éventuelle trappe. Une alternative raisonnable à l'utilisation de ces groupes est de s'en tenir à des groupes comme les groupes "Oakley", ou encore les groupes proposés par TLS 1.3 (plus spécifiquement la RFC 7919). Ces groupes ne peuvent pas contenir de trappe semblable à celle que nous avons exploitée.
• Notre attaque concerne seulement les protocoles DH et DSA, et n'affecte ni ECDH ni ECDSA. Concernant RSA, il n'y a pas n'analogue aux paramètre global qu'est le nombre premier dans le contexte DH, paramètre global dont nous démontrons qu'il peut contenir une trappe.
• Si vous administrez un serveur, nous vous recommandons d'utiliser des courbes elliptiques, ou des nombres premiers de 2048 bits ou plus.
• Si vous développez un logiciel, ou participez à l'élaboration de standards, générez de nouveaux paramètres cryptographiques s'appuyant sur un aléa dont vous publierez également la graine initiale. L'appendice A.1.1.2 du standard FIPS 186 décrit une façon de faire cela pour des nombres premiers "DSA".

Ce travail a été mené par

• Joshua Fried, University of Pennsylvania
• Pierrick Gaudry, CNRS/Université de Lorraine, Nancy
• Nadia Heninger, University of Pennsylvania (contact)
• Emmanuel Thomé, INRIA/Université de Lorraine, Nancy (contact)

L'article technique décrivant ce travail est ici.

Liens supplémentaires: Computer Security Research group at UPenn; projet INRIA/LORIA CARAMBA.

Note (07/10): une version précédente de cette note contenait une erreur de retranscription concernant la comparaison avec un nombre premier de 1024 bits non truqué.