Introduction

En cryptographie symétrique, la clé secrète est gardée secrète et est la source d'entropie pour l'ennemi.  Si la seule chose que connaît l'ennemi, c'est un texte chiffré, il n'y a aucune façon pour lui, de "calculer" ce qui pourrait être la clé.  Cette supposition n'est plus valable en principe quand l'ennemi connaît aussi des paires de texte en clair et texte chiffré, et dans ce cas, sur le plan du principe, il n'y a plus une grande différence entre casser un système symétrique ou asymétrique.  Mais au moins, l'ennemi doit "faire un effort" pour arriver à, potentiellement, obtenir une source d'information concernant la clé secrète.   Dans la cryptographie asymétrique, une telle condition n'est pas présente: la clé publique contient toute l'information pour connaître la clé secrète.  Il y a, dans la plupart des cas, une relation 1-1 entre la clé publique et la clé privée.  En plus, cette relation est mathématiquement relativement simple à formuler.  Toute la sécurité d'un système asymétrique réside dans le fait que personne ne connaît un algorithme suffisamment efficace pour résoudre ce problème mathématique.  Mais "algorithme efficace" est bien sûr une notion relative.

Dans la cryptographie symétrique, on suppose souvent que la seule façon existante pour "inverser" le système, est de "deviner" la clé: c'est l'attaque par force brute.  On considère souvent que s'il existe des méthodes qui sont beaucoup plus efficaces que l'attaque par force brute, alors le système cryptographique est cassé en principe.  Il peut encore fonctionner dans la pratique, si le travail à faire, même en utilisant cette accélération, reste insurmontable dans la pratique.  Mais la plupart des systèmes symétriques qui sont utilisés et considérés valide, n'ont, en pratique, aucune façon d'être attaquée à part la force brute, en essayant toutes les clés possibles.

Aucun système asymétrique du genre n'est connu.  Même si le problème mathématique sur lequel repose la relation de clé publique et clé secrète et considéré "difficile", tous ces problèmes ont, à ce jour, connu un progrès significatif dans la façon de les résoudre.

Bit-sécurité d'un système cryptographique

Considérons que nous avons, comme ennemi, suffisamment de données pour que nous puissions vérifier si une clé donnée est la clé secrète que nous cherchons.  Par exemple, il peut s'agir d'un texte chiffré avec un MAC dans le cadre de la cryptographie symétrique, ou d'un texte en clair et un texte chiffré, aussi dans le cas de la cryptographie symétrique.  Il se peut aussi que nous ayons une clé publique, dans le cas de la cryptographie asymétrique.

La question à laquelle nous voulons trouver une réponse, est: combien d'essais sont nécessaire en moyenne, pour trouver la clé secrète de l'information à notre disposition ?  Si dans le cadre de la cryptographie symétrique, aucune technique d'inversion est connue, la seule chose à faire est d'essayer toute clé possible, et de vérifier si c'est bien la bonne clé secrète, ou non.  La bit-sécurité est définie comme la puissance de deux qui donne ce nombre d'essais nécessaires en moyenne, pour découvrir la clé secrète.  La bit-sécurité d'un tel système est alors égal au nombre de bits dont est faite la clé secrète: idéalement, c'est l'entropie de la clé secrète. C'est le mieux qu'on peut espérer.  Un système qui utilise une clé de 80 bits, aura, idéalement, une bit-sécurité de 80 bits, car il faudra tester 280 clés (en réalité, en moyenne, 279 mais souvent on néglige ce petit facteur de 2 qui correspond à un seul bit).  Un bon système cryptographique symétrique a une bit-sécurité qui n'est pas beaucoup plus petit que l'entropie de sa clé.  On considère le système cassé en principe (même s'il fonctionne encore bien en pratique) si cela n'est pas le cas.

La bit-sécurité donne une idée grossière de la difficulté pour casser le système.  Ce qui manque, bien sûr, c'est l'effort nécessaire pour générer/tester une seule clé.  Il y a des systèmes où cela est rapide, et il y en a d'autres où cela demande beaucoup plus d'efforts.  En fait, ce qu'indique la bit-sécurité, c'est le rapport entre l'effort à fournir par l'utilisateur légitime (qui possède la clé), et l'ennemi qui doit deviner la clé.  De toute façon, on n'a pas besoin d'une grande précision.  La bit-sécurité doit simplement être suffisamment grande que même un adversaire puissant qui peut dépenser beaucoup de ressources pour casser le système, aurait besoin de tellement de temps que ceci est beaucoup d'ordres de grandeur plus long que nécessaire.

Pour donner une idée, DES, qui avait une bit-sécurité de 56 (le nombre de bits dans la clé), n'a jamais réellement été cassé, dans le sens que personne n'a jamais trouvé un moyen de trouver une clé DES avec beaucoup moins que 256 essais.   Mais effectuer 256 essais a été fait depuis la fin du 20ième siècle avec un équipement modeste mais spécialisé.  Ceci indique qu'en général, une bit-sécurité de 56 bits est totalement inadéquat ces jours-ci, sauf peut-être pour des secrets qui n'ont pas besoin d'une longue durée de vie (disons, des secondes).  On considère maintenant qu'une bit-sécurité d'au moins 80 bits est nécessaire, et de préférence, d'avantage.

Avec la cryptographie asymétrique, il ne faut pas espérer d'avoir une bit-sécurité de l'ordre de l'entropie de la clé.  Les problèmes difficiles mathématiques sur lesquels ils sont basés, souffrent tous de méthodes de résolution qui permettent de résoudre le problème plus rapidement qu'en devinant la solution par force brute, même si ces méthodes demandent encore beaucoup d'effort.  Il faut donc considérer la sécurité de ces systèmes en fonction des meilleurs algorithmes dont dispose l'ennemi.  On ne peut que supposer que l'ennemi ne connaît pas de techniques mathématiques autres que celles qui sont publiquement connues.  Sinon, tout peut arriver.

Il y a des techniques génériques pour attaquer les deux problèmes difficiles sur lesquels sont basés la plupart des systèmes asymétriques: la factorisation en nombres premiers, et le logarithme discret dans un groupe général, qui font que la bit-sécurité d'un tel système ne peut jamais dépasser la moitié de la longueur de la clé.  Pour certains systèmes, il y a des techniques plus sophistiquées spécifiques qui peuvent réduire la bit-sécurité d'avantage.  Pour RSA et Diffie-Hellman, des techniques existent qui réduisent une clé de 1024 bits en 80 bits de sécurité.  S'il faut 128 bits de sécurité, il faut utiliser une clé de 3072 bits et si on veut 256 bits de sécurité, il faut une clé de 15360 bits.  C'est remarquable que les deux problèmes de factorisation et de logarithme discret dans un champs modulaire premier ont des techniques de résolution d'une efficacité comparable: c'est parce que les deux problèmes sont en fait, liés dans ces groupes.

Pollard-rho

L'algorithme Pollard-rho est un algorithme générique qui accélère significativement la résolution de tout problème de logarithme discret.  C'est une méthode statistique qui, en moyenne, divise la bit-sécurité par deux, c'est à dire, quand la méthode force brute aurait besoin de N essais, la méthode Pollard rho aura besoin, en moyenne, que de sqrt(N) essais.  S'il y avait 1000 milliard de clés possibles, avec la méthode Pollard rho, seulement un million d'essais seraient nécessaires.  Mais en sus, un essai "Pollard rho" est moins compliqué et demande moins de calculs qu'un essai au hasard: cette méthode ne nécessite que quelques multiplications de groupe par essai, alors qu'un essai au hasard a besoin d'une exponentiation complète à chaque fois.

Nous allons utiliser cette méthode pour attaquer le système standard Diffie-Hellman.  Le système standard Diffie-Hellman utilise le problème difficile du logarithme discret dans le groupe multiplicatif d'un champs modulaire.  Dans un tel groupe, il y a des attaques bien plus puissantes que Pollard-rho, c'est à dire, des algorithmes bien plus puissants existent pour résoudre un problème de logarithme discret, que l'algorithme que nous allons décrire.  Mais notre but est d'illustrer la méthode qui est générique.  L'attaque Pollard rho est, à ce jour, la technique la plus efficace publiquement connue contre les crypto systèmes à base de groupes à courbe elliptique.

Le principe de la méthode Polllard rho est le suivant:

Nous avons y = ax mod p

où p est un nombre premier et a est le générateur du système Diffie-Hellman ; x est l'inconnue (la clé privé) et y est une donnée (la clé publique).

La question est: comment trouver x quand nous connaissons y (et bien sûr, aussi p et a) ?

La méthode de Pollard rho essaie de trouver les entiers u, v, U et V dans {0, ... , p-2} tel que nous pouvons dire:

au yv = aU yV

Si nous trouvons un jeu d'entiers tel, alors cela implique que:

au + xv aU+xV

ce qui implique:

u + x v = U + x V mod (p - 1)

Si nous pouvons résoudre cette équation pour dans l'anneau modulaire avec module p - 1, alors nous aurons trouvé une solution.  Notez que p - 1 n'est pas un nombre premier, et il n'est donc pas garantie que la solution existe ou est unique.  Si la solution n'existe pas, il nous faut trouver un autre jeu u,v,U,V.  Si la solution n'est pas unique, nous pouvons, si le nombre de solutions n'est pas trop grand, essayer chacune d'elles par exponentiation.

La tortue et le lièvre

Il n'y a, à priori, pas de raison pour laquelle trouver les nombres u, v, U et V serait plus facile que de trouver le nombre x: si nous devions utiliser la force brute pour essayer des u, v, U et V, nous aurions beaucoup plus de travail que d'essayer de trouver x directement par force brute !  Alors, comment on s'y prend ?

Il faut considérer une sorte de fonction pseudo-aléatoire "le suivant" du couple (u,v) ; par cela nous entendons que étant donné un couple (u,v), nous avons une fonction f(u,v) qui nous donne un (u',v').  Dans le groupe, avec un (u,v) correspond un élément A du groupe et (u',v') correspond à un autre élément A' du groupe, qu'on peut donc appeler A' = F(A).  La succession A, F(A), F(F(A)) .... sera finie: tôt ou tard, un B = F(n)(A) doit être égal à un C = F(m)(A).  Quand nous trouvons ces deux éléments B et C, nous avons un bon jeu (u,v,U,V).  Il y a de bonnes raisons pour supposer que si F est "aléatoire", ces cycles seront relativement courts.

Il y a un algorithme connu qui peut trouver efficacement ces cycles: c'est l'algorithme de la tortue et du lièvre. L'idée de base de cet algorithme est qu'on va parcourir la suite A, F(A), F(F(A)), F(F(F(A))), ....: une façon lente (la tortue), et une façon rapide (le lièvre).  Quand la séquence entre dans un cycle, la tortue et le lièvre vont tourner en rond dans ce cycle, et le lièvre rattrapera la tortue.  Quand les deux se rencontrent, nous connaissons le cycle.  La tortue prend un pas à la fois, le lièvre en prend deux.  Par exemple considérons la suite suivante:

345,12,898,11,792,9,15,543,34,15,543,34,15,....

alors la progression sera:

pas tortue lièvre
1 345 345
2 12 898
3 898 792
4 11 15
5 792 34
6 9 543
7 15 15
8 543 34
9 34 543
10 15 15

Le lièvre entre dans le cycle plus tôt que la tortue: le lièvre y est déjà au pas numéro 4, la tortue seulement au pas 7.  A partir du pas 7, le lièvre et la tortue vont se rencontrer sans défaut.  Ici, cela arrive même tout de suite.

Implémentation

Nous allons implémenter cet algorithme dans le cadre de notre environnement simple.  Nous voulons rappeler:   Exemples de code

Nous avons d'abord besoin d'une simple fonction d'aide qui copie des gros nombres:

void clone(number* x, number* c)
  {
  int i;
  for (i = 0 ; i < nofdigits ; i++)
    {
    c->digit[i] = x->digit[i];
    }
  }  // end clone 

Ensuite, nous implémentons une fonction pseudo-aléatoire qui transforme (u,v) en un successeur (et s'occupe de l'élément de groupe correspondent aussi):

 
void diffiepolrhohelper(number* dhprime, number* dhprimem1, number* dhgen, number* onethird, number* twothird, number* pkey, number* x, number* a, number* b)
/* helper function for the Pollard's Rho method against Diffie-Hellman */
  {
  number newx;
  number newa;
  number newb;
  number one;
  int i;

  clone(dhprime,&modulo);

  makebig(1,&one);

  if (isbigger(x,onethird) == -1) 
    {
    /* we are in the first third */
    timesnum(x,pkey,&newx);
    clone(a,&newa);
    clone(dhprimem1,&modulo);
    sumnum(b,&one,&newb);
    clone(dhprime,&modulo);
    }
  else if (isbigger(x,twothird) == -1)
    {
    /* we are in the second third */
    timesnum(x,x,&newx);
    clone(dhprimem1,&modulo);
    sumnum(a,a,&newa);
    sumnum(b,b,&newb);
    clone(dhprime,&modulo);
    }
  else
    {
    /* we are in the last third */
    timesnum(x,dhgen,&newx);
    clone(dhprimem1,&modulo);
    sumnum(a,&one,&newa);
    clone(dhprime,&modulo);
    clone(b,&newb);
    }

  /* we overwrite the inputs */
  clone(&newa,a);
  clone(&newb,b);
  clone(&newx,x);
  
  }  // end diffiepolrhohelper

C'est une fonction "aléatoire" simpliste, mais souvent utilisée.  Les éléments de groupe sont divisés en trois blocs, et en fonction du bloc dans lequel se trouve l'élément de groupe x, les successeurs de (u,v) et donc de x, sont choisis parmi un de trois "formules" possibles.  Les trois blocs sont simplement: x plus petit que onethird, x entre onethird et twothird, et finalement, x plus grand que twothird.  Dans le code, ce que nous appelons ici u et v, s'appelle a et b, et nous avons 3 possible successeurs de (u,v):

  1. (u,v+1)
  2. (2u,v)
  3. (u+1,v)

Le successeur de x est calculé de façon correspondante.   Avec cette fonction de succession "aléatoire", nous allons établir la méthode Pollard rho pour deviner la clé secrète à partir d'un cadre Diffie-Hellman donné et une clé publique:

 int diffiepolrho(int n, number* dhprime, number* dhgen, number* pkey, number* skey)
/* we implement the Pollard' Rho attack on a Diffie Hellman secret key */
/* when the function returns a non-zero number, we have found a solution, when it returns 0, we didn't 
   The non-zero number is equal to the number of steps needed */
  {

  number three;
  number zero;
  number onethird;
  number twothird;
  number dummy;
  number one;
  number grouporder;
  int i;
  int j;
  number oldmodulo;
  number turtoisex;
  number turtoisea;
  number turtoiseb;
  number harex;
  number harea;
  number hareb;
  number difa;
  number difb;
  number abgcd;
  number abngcd;
  number divgrouporder;
  number dummy1;
  number dummy2;
  number difared;
  number difbred;
  number inversedifbred;
  number skey2;
  number pkeytest;
  int toreturn;


  /* we put the current modulus away and set the modulus to the prime of the DH group */
  for (i = 0 ; i < nofdigits ; i++)
    {
    oldmodulo.digit[i] = modulo.digit[i];
    modulo.digit[i] = dhprime->digit[i];
    }

  /* we prepare the onethird and twothird needed by the helper function */
  makebig(1,&one);
  makebig(3,&three); 
  makebig(0,&zero);
  difnum(dhprime,&one,&grouporder);
  dividenum(&grouporder,&three,&onethird,&dummy);
  sumnum(&onethird,&onethird,&twothird);

  /* we prepare the turtoise-hare loop */
  makebig(0,&turtoisea);
  makebig(0,&turtoiseb);
  makebig(0,&harea);
  makebig(0,&hareb);
  makebig(1,&turtoisex);
  makebig(1,&harex);
  i = 0;
  do
    {
    i++;
    /* next turtoise */
    diffiepolrhohelper(dhprime,&grouporder,dhgen,&onethird,&twothird,pkey,&turtoisex,&turtoisea,&turtoiseb);
    /* next hare */
    diffiepolrhohelper(dhprime,&grouporder,dhgen,&onethird,&twothird,pkey,&harex,&harea,&hareb);    
    diffiepolrhohelper(dhprime,&grouporder,dhgen,&onethird,&twothird,pkey,&harex,&harea,&hareb);    
    }
  while (i < n && isbigger(&harex,&turtoisex) != 0); 

  if (isbigger(&harex,&turtoisex) != 0)
    {
    /* we didn't find a solution */
    toreturn = 0;
    }
  else
    {
    /* if we are here, then we did find a solution, we simply have to calculate it 
       the calculation takes place in the modular ring modulo p - 1 */
    clone(&grouporder,&modulo);
    difnum(&turtoisea,&harea,&difa);
    difnum(&hareb,&turtoiseb,&difb);

    if (isbigger(&difb,&zero) == 0)
      {
      /*failure: the difference is 0 */
      toreturn = 0;
      }
    else
      {
      /* because p - 1 is not a prime, we cannot guarantee that 1/difb exists.
         at least we increase our chances by simplifying by the gcd of difa and difb and the group order 
         we then try to solve the inversion in a smaller group  (order divided by GCD) */
      exteuclid(&difa,&difb,&abgcd,&dummy1,&dummy2);
      exteuclid(&abgcd,&grouporder,&abngcd,&dummy1,&dummy2);
      printf("GCD is: \n");
      printnum(&abngcd);
      dividenum(&difa,&abngcd,&difared,&dummy1);
      dividenum(&difb,&abngcd,&difbred,&dummy2);
      dividenum(&grouporder,&abngcd,&divgrouporder,&dummy1);
      clone(&divgrouporder,&modulo);
      inversenum(&difbred,&inversedifbred);
      timesnum(&inversedifbred,&difared,skey);
      clone(dhprime,&modulo);
      /* we now test the candidates, which are of the form skey + k * divgrouporder */
      j = 0;
      clone(skey,&skey2);
      do
        {
        j++;
        clone(&skey2,skey);
        power(dhgen,skey,&pkeytest);
        sumnum(skey,&divgrouporder,&skey2);
        }
      while(j < n && isbigger(&pkeytest,pkey) != 0);
      if (isbigger(&pkeytest,pkey) == 0)
        {
        toreturn = i;
        }
      else
        {
        /* failure, we ran out of trials with k */
        toreturn = 0;
        }
      }
    }

  /* we put the original modulo parameter back */
  for (i = 0 ; i < nofdigits ; i++)
    {
    modulo.digit[i] = oldmodulo.digit[i];
    }     
  return toreturn;
  }  // end diffiepolrho

Le code a deux parties.  La première partie est l'application tortue et lièvre avec la fonction d'aide de successeur aléatoire.  La tortue et le lièvre partent tous les deux de l'élément neutre du groupe. Seulement, comme une recherche exhaustive n'est pas envisageable, nous allons limiter le nombre d'essais avant de trouver le "cycle fermé".   Si le cycle n'est pas fermé avant que ce nombre d'essais soit atteint, nous considérons que notre attaque a échoué.

La deuxième partie essaye de résoudre l'équation suivante:

a + x b = A + x B mod (p - 1)

Cela est fait en écrivant:  (b - B) x = A - a  mod (p-1)et en divisant (b-B), (A-a) et (p-1) par leur plus grand diviseur commun pour augmenter les chances de trouver une solution.  Si nous faisons cela, nous sommes en train de résoudre le problème suivant:

(b' - B') X = (A' - a') mod q

La solution actuelle sera alors du type x = X + k q,où k est à déterminer.  Nous allons tester des k de façon "brute force" et tester si le x ainsi obtenu est la solution.

Une application sur un petit problème avec une clé de 35 bits, donne comme résultat après quelques secondes sur un PC modeste (la base est 1000) :

 The D-H prime is: 
0 0 0 11 404 390 799 
and the generator is: 
0 0 0 5 952 600 645 
For Alice, the private key is: 
0 0 0 8 88 546 345 
and her public key is: 
0 0 0 1 585 188 715 
while for Bob, the private key is: 
0 0 0 10 314 859 650 
and his public key is: 
0 0 0 1 479 570 777 
Alice finds as a common secret with Bob: 
0 0 0 4 530 706 175 
while Bob finds as a common secret with Alice: 
0 0 0 4 530 706 175 
we try to find the secret key of Alice: 
GCD is: 
0 0 0 0 0 0 2 
we found a candidate for Alice's secret key !  We needed 73334 trials. It is : 
0 0 0 8 88 546 345 
SUCCESS !! 
we try to find the secret key of Bob: 
GCD is: 
0 0 0 0 0 0 2 
we found a candidate for Bob's secret key !  We needed 93048 trials. It is : 
0 0 0 10 314 859 650 
SUCCESS !! 

Il faut noter que nous avions besoin, pour trouver les deux clés secrètes, moins que 100 000 essais, alors que l'entropie de la clé est de 35 bits.  Ainsi, la bit-sécurité comme mesuré empiriquement est moins que 17 bits.

Un exercice un peu plus poussé consiste à casser une clé de 56 bits (souvenez-vous que DES avait des clés de 56 bits!) sur un modeste PC portable:

The D-H prime is: 
71839933 825330523 
and the generator is: 
36553240 431415466 
For Alice, the private key is: 
63623063 678056489 
and her public key is: 
7804247 481391585 
while for Bob, the private key is: 
67504596 914169198 
and his public key is: 
4373797 986442233 
Alice finds as a common secret with Bob: 
16521159 773150454 
while Bob finds as a common secret with Alice: 
16521159 773150454 
we try to find the secret key of Alice: 
GCD is: 
0 2 
we found a candidate for Alice's secret key !  We needed 456917241 trials. It is : 
63623063 678056489 
SUCCESS !! 
we try to find the secret key of Bob: 
GCD is: 
0 2 
we found a candidate for Bob's secret key !  We needed 24743341 trials. It is : 
67504596 914169198 
SUCCESS !! 

Dans le code, nous avons modifié les déclarations d'entiers en long long pour avoir des mots individuels de 64 bits et d'aller plus vite.  Les clés ont été cassées en moins de 5 minutes.