Les révélations d'Edward Snowden sur les activités de la NSA mentionnaient entre autres que cet organisme s'était efforcé d'introduire des vulnérabilités dans des systèmes cryptographiques commerciaux largement utilisés. En particulier, le 10 septembre 2013, le New York Times écrivait que d'après les documents de Snowden, l'un des générateurs pseudo-aléatoires proposés dans un standard NIST de 2006 (NIST SP 800-90A) avait été conçu par la NSA et contenait une porte dérobée (backdoor). Le 20 décembre 2013, on apprenait que RSA Security avait reçu 10 millions de dollars de la NSA pour proposer ce générateur par défaut dans ses produits.
L'hiistoire est racontée dans l'article de Wikipédia.
Le générateur Dual_EC_DRBG utilise la courbe elliptique P-256 du NIST. Ses paramètres sont les suivants : son équation est
$$ y^2 = x^3+ax+b \mod p$$$$p = p_{256} =2^{256}-2^{224}+2^{192}+2^{96}-1$$$$a =115792089210356248762697446949407573530086143415290314195533631308867097853948= -3 \mod p$$$$b =41058363725152142129326129780047268409114441015993725554835256314039467401291$$Elle est d'ordre premier
$$q=115792089210356248762697446949407573529996955224135760342422259061068512044369$$On prend comme générateur le point $P=(x_P,y_P)$
$$x_P =48439561293906451759052585252797914202762949526041747995844080717082404635286$$$$y_P =36134250956749795798585127919587881956611106672985015071877198253568414405109$$et l'algorithme utilise un mystérieux point $Q$ d'origine non précisée
$$x_Q =91120319633256209954638481795610364441930342474826146651283703640232629993874$$$$y_Q =80764272623998874743522585409326200078679332703816718187804498579075161456710$$La graine (seed) du générateur aléatoire est un entier $s_0$ choisi aléatoirement entre 1 et $q$.
On construit une suite d'états internes $s_i$, et à chaque itération on produit une chaîne $r_i$ de 240 bits pseudo-aléatoires par la récurrence suivante :
$$ s_i = x(s_{i-1}P)$$$$ r_i = {\rm lsb}_{240}(x(s_iQ)) $$où ${\rm lsb}_{240}$ prend les 240 bits de poids faible.
Il y a de nombreuses raisons de s'interroger sur le choix de ce générateur. Il est lent et possèdeun léger biais, ce qui est déjà inquiétant en soi.
Mais il y a bien pire. On sait que la courbe est d'ordre $q$ premier. Donc, il existe un entier $d$ tel que $Q=dP$. Il n'est pas interdit de supposer que la NSA connaisse $d$. Elle peut alors facilement calculer son inverse
$$e=d^{-1}\mod q$$Connaissant $e$, on peut prédire l'état interne $s_{i+1}$ du générateur (et donc les valeurs suivantes) à partir de deux sorties consécutives $r_i$ et $r_{i+1}$.
Pour en faire la preuve, on peut remplacer $Q$ par $Q_2=dP$ pour diverses valeurs de $d$ choisies aléatoirement, et vérifier expérimentalement que la connaissance de $d$ permet de prédire $r_{i+2}$ à partir de $r_i$ et $r_{i+1}$.
En effet, $r_i$ est la coordonnée $x$ du point $s_iQ_2 = s_idP$, amputée de ses 16 bits de poids fort. On peut donc essayer de le compléter avec les $2^{16}=65536$ valeurs possibles de ces bits, et tester pour chaque choix si la valeur $x$ obtenue est l'abscisse d'un point de la courbe. Pour cela, il suffit de vérifier si $x^3+ax+b$ est un carré dans ${\mathbb F}_p$, ce qui se produira environ une fois sur deux. On obtiendra ainsi une liste $S$ d'environ $2^{15}=32768$ points de la courbe.
Pour chacun de ces points $M=(x_M,y_M)$, on calcule $x(eM)$ et on compare ses 240 bits de poids faible à $r_{i+1}$.
Dans toutes les expériences, un seul point $M$ redonne $r_{i+1}$, et on retrouve ainsi l'état interne $s_i=x_M$.
On trouvera ici une démonstration en C (assez compliquée à mettre en place).
On peut facilement programmer ce test en pur Python, en utilisant simplement le fichier ent3.py de William Stein. La fonction qui teste si un entier est un carré modulo $p$ et calcule sa racine carrée s'appelle sqrtmod.
Voilà une manière possible de coder le générateur. Pour tester la méthode, on remplace le point $Q$ choisi par la NSA par un multiple de $P$ connu (mais choisi aléatoirement à chaque test) :
# Dual_EC_DRBG
import random
from ent3 import *
class Dual_EC_DRBG(object):
def __init__(self):
# p_256
self.p = p = 2**256 - 2**224 + 2**192 + 2**96 - 1
# E : y**2 = x**3+ a*x + b mod p
self.a = a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
self.b = b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
# Nombre de points de la courbe
q = 115792089210356248762697446949407573529996955224135760342422259061068512044369
# Génerateur
xP = 48439561293906451759052585252797914202762949526041747995844080717082404635286
yP = 36134250956749795798585127919587881956611106672985015071877198253568414405109
# Mystérieux second point
xQ = 91120319633256209954638481795610364441930342474826146651283703640232629993874
yQ = 80764272623998874743522585409326200078679332703816718187804498579075161456710
self.P = P = (xP, yP)
self.Q = Q = (xQ, yQ)
self.E = E = (a,b,p) # Définit la courbe elliptique pour ent3.py
self.N = 2**240-1 # C'est donc 111...1 (240 bits 1) en binaire
self.q = q
s0 = random.randint(2,q-1)
self.state = ellcurve_mul(E, s0, P)[0] # coordonnée x de s_0P
self.N = 2**240-1
def __call__(self):
return self
def next(self):
M = ellcurve_mul(self.E, self.state, self.Q)
self.state = ellcurve_mul(self.E, self.state,self.P)[0]
return M[0] & self.N # extrait les 240 bits de poids faible
class Backdoored(Dual_EC_DRBG):
def __init__(self):
Dual_EC_DRBG.__init__(self)
self.d = random.randint(2,self.q-1)
self.e = inversemod(self.d,self.q)
self.Q = ellcurve_mul(self.E,self.d,self.P)
B = Backdoored()
# Une première sortie
B.next()
# Et une deuxième
B.next()
Programmer le test expliqué ci-dessus. Pour mettre au point le programme, on vérifiera simplement que l'état interne s[2] (qu'on connait) se trouve bien dans la liste des candidats. Une fois que ce point sera acquis, on programmera le test complet (rechercher parmi les candidats ceux qui redonnent r2). Cette version prend plusieurs dizaines de minutes, peut-être jusqu'à une heure, selon la machine. On peut effectuer la recherche en parallèle sur plusieurs coeurs
du processeurs en utilisant le module concurrent.futures.
Avec cette optimisation, sur un HP Zbook à 8 coeurs de 2014, on effectue le recherche complète en moins de 10 minutes.
Le résultat pourrait ressembler à ça :
Two consecutive outputs of the backdoored generator: r1 = 1277941323679186258934025142033839006882569538354483136071270590034316138 r2 = 899874866902815707828419803028016218990090320870136781131892802870676470 Retrieving candidate points on curve from r1 Found 32631 points Computing possible values of internal state s[2] Finished computing possible values of s[2] Looking for those yielding r2 Found possible state s[2]: 114605066044855839627566149663784075654998897893152893540757536994975088891658 Predicted value: 1035016502411903328328870005589593117156858208215138600287531703575061563 Real value: 1035016502411903328328870005589593117156858208215138600287531703575061563 Correct guess? True