client-side DH tracker

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.

Ce travail a été mené par

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é.

Dernière modification: Wed 20 Sep 2017 01:35:46 PM CEST
© 2006– membres du projet ; XHTML 1.0 valide, CSS valide