The Pohlig-Hellman Attack

Curve 25519 has a little bit of a problem — in that it has a subgroup with a co-factor of 8. This means that we have an eighth of the total range of a group, and which can be compromised by the Pohlig-Hellman attack. Within X25519, we get around this by clamping the three least significant bits (LSB), and there is no equivalent method for Ed25519. For this, we can turn to Ristretto255 [here], which makes sure we have a prime number order. So, let’s look at the attack method on a non-prime order.

The attack operates on both discrete logarithm and elliptic curve problems, and was created by Steve Pohlig and Marty Hellman [1]:

So what’s an order of a group?

In cryptographic systems, we typically implement within a group with a prime order of ℓ. But what does this mean? Well, let’s say we have a simple cipher and where we modular multiply by h, and then to decipher, we modulo divide by h. The cipher would then be:

c=h.x (mod p)

If we select p as 7 and h as 2, we then map:

x=0 -> c=0
x=1 -> c=3
x=2 -> c=6
x=3 -> c=2
x=4 -> c=5
x=5 -> c=1
x=6 -> c=4

And then we repeat:

x=7 -> c=0
x=8 -> c=3
and so on.

This is a ring which has outputs from 0 to 6, and thus the number of valid outputs is 7 — and which is known as the order of the group. In this case number of possible outputs is equal to the prime number, but the order can differ from this as not all the outputs might be valid.

If we now have c=g^x (mod p) we have the discrete logarithm problem, and where it is difficult to find x if we have a large prime number of p. With g=3 and p=11, we get:

x=0 -> c=1
x=1 -> c=3
x=2 -> c=2
x=3 -> c=6
x=4 -> c=4
x=5 -> c=5

And now we repeat:

x=6 -> c=1
x=7 -> c=3
and so on.

The order is now 6. Overall in this type of discrete log problem, the order is p−1 and which will not be a prime number. This provides us with a problem: the Pohlig Hellman attack. So let’s analyse.

Composite numbers and factorizing the order

Every composite number (m) can be defined as product of prime powers (p_1, p_2, and so on), such that:

For example, if m=102, we get:

102=2×3×17

and where the three prime numbers are 2, 3 and 17.

For m=39,883, we get:

39883=2×3×17×17×23=2×3×17²×23

If we have g^x (mod p), the order will be (p-1). As this is not prime, we can then factoize the order with:

This gives us a number of subgroups which are defined by the prime number factors. The coding is [here]:

import libnum
import sys
p=21

if (len(sys.argv)>1):
 p=int(sys.argv[1])

p_1=p-1
a=libnum.factorize(p_1) 
count=0
print(f"If we have g^x (mod p)")
print(f"With: p={p}")
print(f"Order: {p_1}")
print(f"\nThe prime powers will be: ",end='')
for key in a:
 for i in range(0,a[key]):
  if (count==0):
   print (f"{key}",end='')
  else:
   print (f"x{key}",end='')
  count=count+1

and a sample run is [here]:

If we have g^x (mod p)
With: p=7919
Order: 7918
The prime powers will be: 2x37x107

After we find the subgroups, we can then take:

x (mod p_1)
…
x (mod p_k)

and use Chinese Remainder Theory to determine x (mod n), and where n is the order of the group:

The attack is based on a smooth number [here] order. After this we find the subgroups, we can determine:

and where k is the number of prime numbers that make up the order. With this we can then use Chinese Remainder Theory to determine x ( mod p):

References

[1] Pohlig, S., & Hellman, M. (1978). An improved algorithm for computing logarithms over GF (p) and its cryptographic significance (corresp.). IEEE Transactions on information Theory, 24(1), 106–110.