Introduction

In symmetric cryptography, the secret key is kept secret, and is hence a source of entropy for the enemy.  If the only thing that an enemy knows, is a cypher text, there's no way for him, normally, to 'calculate backwards' what was the key.  This assumption breaks down in principle when the enemy knows a cypher text and the clear text that goes with it and then, breaking symmetric cryptography is not so different from breaking asymmetric cryptography.  But at least, the enemy has to obtain clear text, which he was supposed not to access in the first place.  However, in asymmetric cryptography, there's no such condition.  The public key is out in the public, and already contains all the information needed to know the private key.  There is in most cases, a 1-1 relationship between the public key and the private key and this 1-1 relationship is even, mathematically, quite simple.  The whole security of an asymmetric crypto system resides in the fact that it is assumed that nobody knows an efficient way to solve that mathematical problem.  However, the "an efficient way to solve that problem" is of course relative.

In symmetric cryptography, it is usually assumed that the only way to "reverse" the system is by guessing the secret key: the "brute force" attack.  It is usually considered that if there are methods that are significantly faster than the brute force attack, the symmetric crypto system is broken in principle.  It can still work in practice, if what remains to try after using these acceleration techniques is still too large to be practical.   But most used symmetric crypto systems that are still considered "valid" have in practice, no faster way to be attacked than to try mostly all possible secret keys.

No such asymmetric system is known.  Even though the mathematical problem on which the relation from public key to private key is considered "difficult", all such problems, as of today, have known significant progress in the way to tackle them.

Bit-security of a crypto system

Consider that we have, as enemy, sufficient data, in a cryptographic setting, that allows us, in principle, to verify whether a given key is the secret key we are after.  For instance, this can be a cypher text including a MAC in the settings of symmetric cryptography, or a given cypher text and clear text in symmetric cryptography.  Or it can simply be the availability of a public key in asymmetric cryptography. 

The question to be answered is: how many random trials are necessary, on average, to find the secret key from the information available ?  If the symmetric crypto system doesn't allow any specific "inversion technique", then the only thing we can do, is try every single possible key, and see whether it is the secret key.   The bit security is defined as the power of 2 that gives the number of trials, on average, that need to be performed to discover the private key.  The bit-security of such a system is then equal to the number of bits out of which the secret key is made ; ideally, it is the entropy of the secret key.  This is the best one can hope for.  A system that uses a key of 80 bits, will, ideally, have a bit security of 80 bits, because one needs to test 280 different keys in order to find the key (in fact, on average, one only needs 279 trials, but we neglect this factor of two often).   A good symmetric crypto system has an effective bit security that is not much lower than the entropy of the secret key (it can be a little bit lower if some techniques exist, but it is usually considered that the system is broken in principle, if the bit security is significantly lower than the key length).

The bit security gives a rough idea of the difficulty of breaking the system.  What is missing is the effort needed to verify one single key trial.  There are crypto systems where this is fast, and there are systems where this is much slower.  In fact, what the bit security level indicates, is the ratio between the effort needed by a legitimate user (knowing the secret key) to use the system, versus an enemy using the system (and having to guess the key).   But one doesn't need to be precise.  the bit security level should be high enough, so that even a very powerful enemy, with lots of resources to spend on the breaking of the system, should need so much time to do so, that this is orders and orders of magnitude beyond what is necessary.

To give an idea, DES, which has a bit security level of 56 (the number of bits in the key) is never really broken in the sense that nobody ever figured out a way to find a DES key with much less than 256 trials.  But performing 256 trials has been done since the end of the 20th century with rather modest but specialized equipment.  This indicates, in general, that a bit security level of 56 bits is totally insufficient these days (except eventually for secrets that don't have a long life time).  One usually considers that to be secure, one needs now at least 80 bits of security and preferentially more.

With asymmetric cryptography, one cannot hope to have a bit security level of the order of the bit length of the secret key.  The "difficult" mathematical problems on which they are based, all suffer from mathematical methods that allow one to find the "forbidden" reverse solution much faster than by just brute force, even though these problems remain "hard".  As such, the estimation of the security of an asymmetric crypto system depends on the best algorithms the enemy might possess to solve the problem at hand.  One can only suppose that the enemy has no particular mathematical knowledge that is not publicly known.  Otherwise, all bets are off.

In fact, there are generic algorithms that can attack the two hard problems used in most asymmetric systems: the prime factorisation, and the discrete logarithm in a general group, that make that the bit security of such a system can be at most half of the key length.  However, for specific systems, there are more sophisticated and specific methods that can reduce the bit security level still much more.    For RSA and Diffie-Hellman, it turns out that with actually known methods, a 1024 bit key is needed to reach 80 bit security.  If one needs 128 bit security, keys of 3072 bit are needed, and if one desires 256 bits, we have to go to 15360 bit keys !  It is remarkable that the two problems of factorisation and discrete logarithms in a prime field have techniques of resolution of about the same efficiency.

Pollard-rho

The Pollard-rho algorithm is a generic algorithm that improves significantly the resolution of the discrete logarithm problem.  It is a statistical method that, on average, divides the bit security by two,  that is to say, when the brute force method would need N trials, the Pollard rho method only needs, on average, sqrt(N) trials.  If there were 1000 billion keys, we only need to try one million.  But, moreover, the trial needed in Pollard's rho method demands much less  effort than a genuine trial.  Pollard's rho method only needs a few group multiplications per trial, while a genuine trial needs a full exponentiation.

We will use this method to attack the standard Diffie-Hellman system.  It has to be said that the standard Diffie-Hellman system uses the hard discrete logarithm problem in the multiplicative group of a modular field, and given that specific group, there are even much more powerful attacks (that is, much more efficient algorithms to solve the discrete logarithm problem) than the Pollard's rho method.  The main goal is simply to illustrate the method, which is generic.  Pollard's rho method is, as of this day, the most efficient attack against elliptic curve crypto systems.

The principle of Pollard's rho method is the following.

We have y = ax mod p

where p is the prime, and a the generator of the Diffie Hellman system, x is the (unknown) private key, and y is the (known) public key.

The question is: how do we find x if we know y (and p and a, of course) ?

Pollard's rho method tries to find integers u,v, U and V in {0 ... p-2} such that we can assert:

au yv = aU yV

If we can find such a set of numbers,this implies that:

au + xv aU+xV

from which follows that:

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

If we can solve this equation for x in the modular ring with modulus p - 1, then we have found a solution.  Given that p - 1 is not a prime, it is not guaranteed that this solution exists or is unique.  If the solution doesn't exist, we have to find another set of numbers u,v, U and V.  If the solution is not unique, we can, if there aren't too many solutions, test all of them "brute force" by exponentiation.

The Tortoise and the Hare

Of course, there's a priori no reason why finding 4 numbers u, v, U and V is any easier than finding one number x: if we would have to brute-force u,v,U and V, then this is much more work than to brute-force x on its own !

So what is the idea ?

The idea is that we consider a kind of pseudo-random "next" function on the (u,v) couple, that is, given an (u,v) couple, we have a function f(u,v) that gives us (u',v').

In the group, with an (u,v) couple corresponds an element of the group, A, and, hence, another group element A' corresponds to (u',v'), which we can call "F(A)".

The succession of elements A, F(A), F(F(A)), ... will be finite: sooner or later, a B = F(n)(A) must be equal to an C = F(m)(A).  When we find these two elements B and C, we have a good set (u,v,U,V).  There are good reasons why, when this mapping is "random", these cycles are potentially short.

There is an algorithm that can find rather efficiently such cycles: it is the "Tortoise-and-Hare" algorithm.

The basic idea of the tortoise-and-hare algorithm is to have two ways to run along a sequence A, F(A), F(F(A)),.... : a "slow" one (the tortoise) and a "fast" one (the hare).  Whenever the sequence enters into a cycle, the tortoise and the hare will run along the cycle, and the hare will catch up with the tortoise, so both will meet at a point.

The "tortoise" goes one step at a time, the "hare" takes two steps at a time.

For instance, if we consider numbers, and the sequence is:

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

then we will find the following progression:

step tortoise hare
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

The Hare enters (of course) faster the cycle than the Tortoise: the hare hits it at step 4, the Tortoise, at step 7.  From step 7 onwards, the Hare and the Tortoise will meet for sure, and in this case, it happens immediately. 

Implementation

We implement this algorithm in the frame of our simple code environment, where we would like to remind: Code examples.  We first need a simple helper function, that clones big numbers:

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

Now, we implement the pseudo-random function that modifies (u,v) into its successor (and takes care of the corresponding group element too):

 
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

It is an often-used and rather simplistic "random" function.  The group elements are divided in 3 blocks, and depending on where the current group element x is, one out of 3 different simple successors of (u,v) (and hence of x) is chosen.

The three blocks are simply, in our case: x is smaller than "onethird", x is between "onethird" and "twothird", and x is larger than "twothird".  In the code, what we called u and v, is called a and b.  Essentially, we have three possible successors of (u,v):

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

The successor of x is calculated correspondingly.

With this "random successor function", we can establish Pollard's rho method to guess the secret key from a given Diffie-Hellman setup and a given public key:

 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

 The code has two parts.  The first part is the Tortoise and Hare application of the "random" helper function.   The tortoise and the hare both start out at the neutral element of the group.  However, because an exhaustive search is not possible, we limit the number of trials before the "cycle closes".  If it doesn't close before, we consider that the method failed.

The second part of the code tries to solve the equation

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

This is done by writing (b - B) x = A - a  mod (p-1)

and by dividing (b-B), (A-a) and (p-1) by their GCD, to increase the chances to find a solution.

If we do that, we actually solve the problem:

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

The actual solution will then be x = X + k q, where k is to be determined.  We loop up to a certain point with k, and "brute-test" whether the obtained x is the solution.

A run on a relatively small problem with 35-bit keys results, after a few seconds of run time on a modest PC, where the "base" is 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 !! 

Note that we needed, for cracking both private keys, less than 100 000 trials, while the key entropy is 35 bits.  So the bit security, as empirically seen, is less than 17 bits.

A more serious cracking with a key of 56 bits (remember that DES has a 56 bits key !), on a modest portable PC:

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 !! 

In the code, we modified the int declarations into long long declarations to have 64-bit individual words and go faster.   The keys were cracked in less than 5 minutes on a modest portable PC.