Repository files navigation

• Know howDiffie-Hellman key exchange works

In this article, I hope to explain clearly and as simply as possible what asmall subgroup confinement attack is and how this attack works.
And finally, at the end of this article, how to protect yourDiffie-Hellman key exchange from this attack.

The goal of asmall subgroup confinement attack is to force the key to be confined to an unexpectedly small subgroup of the desire group and to recover a secret private integer (a orb).

To perform this attack and retrieve the secret integer chosen by our target, we must use aman in the middle attack (MITM) attack and give a tampered parameter to our target.

I’m not going to explain what’s a MITM attack and how to perform it in this article.

We’ve intercepted Alice’s parameters, but we can only interact with Bob. How do we get the shared secret to decrypt Alice's encrypted message?

We will tamper Bob’s parameters in order to get his secret private integerb.
For that, we’re going to use a small subgroup confinement attack.

Thefirst step is to find asmooth prime numberp upper than the p given by Alice, with many small factors(factors less than or equal to 2¹⁶ are good because they don't require much computation time, which makes the attack faster).

You can find a very good function (get_smooth_prime) in thisCTF write up, to make smooth prime where you can easily choose his length and smoothness.

With this smooth prime numberp, we have a lot of small factors which dividep-1.

The attack can start !

You will do these4 steps on all factors ofp to get the secret integerb of Bob.
We’re going to call each factorf.

Step 1

To do that, we have to find a number A’ in order that:

A’^{(rand_int(p-1) / p)} (mod p) != 1.
Example of a python function to find A’:

fromrandomimportrandintdefget_tampered_public_key(f,p):tampered_A=1whiletampered_A==1:tampered_A=pow(randint(1,p), (p-1)//f,p)returntampered_A

Step 2

SendA’ to Bob asAlice public key

Step 3

Bob useA’ to create hisshared secret. [Bob shared secret =A’^b (mod p)]

Step 4

Intercept Bob’sMAC(shared_secret, message)
WithA’ used in Bob shared secret, we have reduced the possible value of theshared secret, because Bob raised our A’ to a power b and the order ofA’ isf.
We deliberately choose small factorsf so we can brute force all possible value from1 tof until we find anx such asA’^x (mod p) is equal to BobMAC(shared_secret, message).
The result can be written like that:x ≡ b₁ (mod f₁)

After repeating this fourth step, we have a lot of equations like this:

• x₁ ≡ b₁ (mod f₁)
• x₂ ≡ b₂ (mod f₂)
• …
• x_n ≡ b_n (mod f_n)

With all these equations we can easily recover the secret integer of Bob using theChinese remainder theorem (CRT).

Example to calculate the CRT of our equations in python:

fromsympy.ntheory.modularimportcrt#Where f_n is the list of all the factors of our tampered p and x_n the list of all the x in our equationsb=crt(f_n,x_n)[0]

One solution to protect your Diffie-Hellman key exchange from this attack is to use asafe prime p wherep = 2q + 1 andq is prime.

Check that 2 <= y <= p-2 (otherwise there may be a 1 bit leak)

Withp a safe prime,p-1 has a large prime factor that makes the small subgroup confinement attack impossible due to computational time.

Obviously, don’t use a prime number p with a small bit-length for a communication. According to theFederal Office for Information Security:

“The length of p should be at least 2000 bits, and at least 3000 bits for a period of use beyond 2022” (7.2.1 Diffie Hellman – Key length)

• C.H. Lim and P.J. Lee. (1998). "A key recovery attack on discrete log-based schemes using a prime order subgroup"
• Measuring small subgroup attacks against Diffie-Hellman
• NDSS 2017: Measuring small subgroup attacks against Diffie-Hellman (video)