Cryptanalyse : des nombres premiers “truqués” ?

 

[…]

L’utilisation des nombres premiers dans les standards internationaux de cryptographie
[…]

Les standards internationaux de cryptographie comportent des nombres premiers qui ont vocation à être utilisés à grande échelle. Ces standards concernent une partie des opérations réalisées en cryptographie, notamment l’échange de clés de Diffie-Hellman (inventé en 1976), qui sert à peu près universellement : HTTPS, VPN, afin de sécuriser les échanges et les communications.

Un nombre premier ne définit pas “une clé” mais plutôt “un contexte”. Et si on réussit à résoudre un problème mathématique difficile attaché à ce nombre premier, appelé problème du logarithme discret, alors toute la cryptographie qui s’appuie dessus est mise en péril. C’est-à-dire que par exemple chaque communication sécurisée par Diffie-Hellman, lorsqu’elle emploie ce nombre premier p, peut être déchiffrée par la personne qui a résolu le logarithme discret pour p.

Ce n’est pas très grave tant que le problème du logarithme discret pour le nombre premier p reste dans des horizons inatteignables en termes de temps de calcul. Pour ce faire, il faut bien choisir la taille du nombre premier. Pour des nombres premiers “honnêtes”, sans propriétés particulières, l’échelle de difficulté, en termes de taille, est la suivante :

• 768 bits : très facilement atteignable ;
• 1024 bits : vraisemblablement trop facile, sans doute atteignable avec de gros moyens, et hélas encore trop répandu ;
• 2048 bits : solide.
  […]

Des nombres premiers à risque, munis d’une “trappe”
[…]

Une équipe de chercheurs, Joshua Fried et Nadia Heninger (Université de Pennsylvanie), Pierrick Gaudry (Équipe CARAMBA, CNRS/Université de Lorraine) et Emmanuel Thomé (Équipe CARAMBA, Inria/Université de Lorraine), vient de démontrer que tous les nombres premiers ne se valent pas. Tout dépend de la manière dont ils ont été choisis.

“En effet, il existe une façon de choisir des nombres premiers “truqués”, munis d’une “trappe” (trapdoored primes). Une entité qui aurait la responsabilité de la rédaction d’un standard pourrait alors proposer à l’usage général un tel nombre premier, et garder par-devers elle cette trappe, lui donnant un avantage pour tout casser !”

Cette méthode de conception n’est pas nouvelle, elle date de 1992. À l’époque, le procédé de fabrication d’un nombre premier “truqué” était le même que celui employé aujourd’hui, mais comme il s’agissait de nombres premiers globalement plus petits, la tricherie était détectable et par conséquent le risque limité.

Vingt-cinq ans plus tard, la conclusion est très différente. Sur des nombres premiers plus gros la tricherie n’est pas détectable en l’état actuel de l’art.
Pour un attaquant qui connaîtrait la trappe, l’échelle de difficulté deviendrait:

• 768 bits : très facile ;
• 1024 bits : facile (notre calcul) ;
• 2048 bits : hors d’atteinte pour l’instant, mais pas aussi difficile que ce que l’on aurait envie de croire pour protéger des informations sensibles.
  […]

Un risque d’espionnage des particuliers comme des intérêts économiques
[…]

Il existe dans les standards, ou dans les logiciels de cryptographie, des nombres premiers dont on ne connait pas l’origine.
Prenons le contexte d’un VPN. Si, pensant utiliser un nombre premier de 1024 bits “honnête”, on en utilise un “truqué”, alors toutes les communications sont déchiffrables par le possesseur de la trappe, et il peut “écouter” ce qui passe sur le câble réseau.
Aujourd’hui, trop de serveurs acceptent de converser sur la base de nombres premiers dont l’origine est invérifiable: au moins 37% en HTTPS (parmi le million de sites les plus visités d’Internet), au moins 13% sur les VPN IPsec — c’est beaucoup, beaucoup trop.
[…]

Comment se protéger ?
[…]

Pour convaincre qu’un nombre premier est honnête, il y a deux solutions :

• prendre les décimales de pi, ou un nombre quelconque au-dessus de tout soupçon et standardiser “le nombre premier suivant”, en quelque sorte. C’est fait dans certains standards, et ces nombres premiers sont (heureusement) très utilisés ;
• “prendre des chiffres au hasard de façon vérifiable”, de façon à fabriquer un nombre premier à partir d’une “graine”. Si on publie le nombre premier et la graine ensemble, on peut vérifier qu’ils correspondent. Ces méthodes de “hasard vérifiable” ne sont malheureusement presque jamais utilisées, et on trouve à leur place dans les standards des nombres premiers fournis sans aucune justification.

Il faudrait strictement, dans les standards et dans les logiciels, s’en tenir à ces deux méthodes de génération de nombres premiers. Cela impliquerait, au minimum, de supprimer un standard en particulier, nommé RFC5114. Il serait d’autre part nécessaire de relever l’exigence minimale en termes de taille de nombres premiers à 2048 bits.
Enfin, l’usage de courbes elliptiques serait une bonne façon de se libérer de ce risque.

Article de Laurence Goussu, Inria.