Le logarithme discret et le PSG

Le 28 janvier 2016, OpenSSL a publié un avis de sécurité notamment sur une erreur d’implémentation affectant le protocole Diffie Hellmann. Enfin plus précisemment, OpenSSL annonce avoir corrigé un bug dans la génération de nombre premier utilisé pour ce protocole.

Histoire de fixer les notations, rappelons ici rapidement comment l’on utilise le problème du logarithme discret pour assurer le partage de secret entre deux parties Alice et Bob :

Alice et Bob se mettent d’accord sur  un nombre premier « P » et un nombre « g » (ces deux nombres sont publics).

  • Alice choisit un nombre a, calcule g^a \mod P puis transmet le résultat à Bob
  • De la même façon Bob  choisit un nombre b, calcule g^b \mod P puis transmet le résultat à Alice.

Le secret partagé est alors le nombre g^{ab} \mod P

Du coup si nous nous penchons un peu sur le logarithme discret, toute la sécurité repose sur la difficulté à retrouver rapidement a en fonction de g^a \mod P.

En théorie oui, mais comme nous allons le voir, il se peut en pratique qu’on puisse retrouver a’ différent de a tel que :
g^{a'} \mod P = g^a \mod P

Du coup, cela peut alors énormément faciliter la tâche des attaquants. Le choix de P et de g est déterminant pour garantir un bon niveau de sécurité du protocole DH (et plus généralement du logarithme discret).

Afin de fixer les esprits prenons volontairement un P petit : P=13.  En observant les 2 tableaux ci dessous, on constate plusieurs choses. Expliquons si elle n’est pas évidente la sémantique de nos tableaux : En abscisse les différentes valeurs de g, et en
ordonnée les puissances a, ainsi la case (g,a) donne g^a \mod P.
Rappelons ici que nous n’avons besoin de calculer que pour a\leq P car a^P = a \mod P : car qu delà cela devient cyclique (cf petit théorème de Fermat).
groupe Z/13Z
D’abord sur le tableau de droite montre l’occurrence de g^a = 1 \mod 13
Remarquons le grand nombre de 1, la symétrie mais aussi que seules 4 lignes n’ont aucun 1 (autre que celui de la première colonne).

Remarquons également dans le premier tableau, les colonnes de même couleur qui représentent les g qui ont le même cycle (i.e. pour qui g^a = 1 \mod P pour le même a).

En particulier :
a=1, {1}
a=2, {1,12}
a=3, {1,3,9}
a=4, {1,12,5,8}
a=5, {1}
a=6, {1,3,4,9,10,12}
a=7, {1}
a=8, {1,5,8,12}
a=9, {1,3,9}
a=11,{1}
a=12, {1,2,3,4,5,6,7,8,9,10,11,12}

Intéressons nous au cas 1,2,3,4,6 et 12 et remarquons que pour chacun le nombre d’élément tel que g^a mod P = 1 est précisement égale à « a » (Ainsi pour a=6, il y a 6 éléments tels que g^6 = 1 mod P).

Remarquons par ailleurs que 1,2,3,4,6 et 12 sont tous les diviseurs de 12 et que 12 = 13 – 1… = \phi(P)
Voilà vous commencez à voir venir le « truc » déjà abordé ici ?

Il ne faut pas choisir un P trop friable (avec trop de petit facteur) et un g dans le cycle serait court.

On se rapproche ici un peu de l’idée de P-1 de Pollard, ou pour éviter d’avoir des collisions faciles sur g^a \mod P, il faut que P n’ait de petit facteur et que g ne soit pas un générateur d’un sous groupe trivial de P.

C’est ainsi que nous arrivons à parler du nombre PSG. Le nombre PSG ou nombre premier de Sophie Germain (également appelé dans la littérature anglophone « safe prime » est un nombre premier P impair donc de la forme 2q+1 avec q également premier.

De tels nombres ne sont pas si rares : il n’y a pas de preuve formelle (à notre connaissance), mais une estimation correcte de leur nombre entre 0 et N  est \frac{N}{\log(N)^2} (à comparer au  \frac{N}{\log(N)} des nombres premiers.).

Ainsi pour un nombre premier de Sophie Germain, nous n’aurons que 4 diviseurs de P-1 = 1,2,q et 2q.

Les membres des 2 premiers sous groupes sont triviaux : 1 et p-1 (en effet (p-1)^2 = p^2-2p+1 = 1 \mod P).  Restent donc des générateurs aillant des cycles de q ou 2q, ce qui dès lors que q est grand (1024 bit) est satisfaisant en terme de sécurité.

Reprenons un tableau avec la même idée que ci-dessus mais avec P=23 = 2*11+1
groupe Z/23Z

Lors d’une négociation SSL/TLS avec de la « PFS », il pourrait être intéressant d’étudier systématiquement la sécurité des paramètres de DH proposé par le hote distant.

Note importante sur IKE :
A contrario de SSL/TLS, le protocol IKE (tout comme SSH) ne laisse pas libre des P que l’on peut utiliser pour DH : ils sont très précisément expliciter dans les RFCs.

Du coup, nous vous invitons à lire ou relire la publication de l’INRIA pour un panorama complet de la sécurité du protocol Diffie-Hellman

Publicités

A propos JoMendes

Amateur de mathématiques et d'hexadécimal. Je m'intéresse de près ou de loin suivant mon niveau à tous les sujets de sécurité de l'information.
Cet article, publié dans Cryptographie Asymétrique, Uncategorized, est tagué , , , , . Ajoutez ce permalien à vos favoris.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s