Cryptographie - TD6 : La porte dérobée dans Dual_EC_DRBG

(Dual Elliptic Curve Deterministic Random Bit Generator)

Les révélations d'Edward Snowden sur les activités de la NSA mentionnaient entre autres que cet organisme s'est 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ède un 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 ent.py de William Stein . 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 ent import *


class Dual_EC(object):

    def __init__(self):
        # Prime p_256
        self.p = p = 2**256 - 2**224 + 2**192 + 2**96 - 1
        # E = curve y**2 = x**3+ a*x + b mod p
        self.a = a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
        self.b = b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
        # Order of the curve
        q = 115792089210356248762697446949407573529996955224135760342422259061068512044369
        # Generator
        xP = 48439561293906451759052585252797914202762949526041747995844080717082404635286
        yP = 36134250956749795798585127919587881956611106672985015071877198253568414405109
        # Mysterious second point
        xQ = 91120319633256209954638481795610364441930342474826146651283703640232629993874
        yQ = 80764272623998874743522585409326200078679332703816718187804498579075161456710

        self.P = P = (xP, yP)
        self.Q = Q = (xQ, yQ)
        self.E = E =  (a,b,p)
        self.N = 2**240-1
        self.q = q

        s0 = random.randint(2,q-1)
        self.state = ellcurve_mul(E,s0, P)[0]
        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


class Backdoored(Dual_EC):
    def __init__(self):
        Dual_EC.__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)



Exercice

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.


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