- Know how Diffie-Hellman key exchange works
In this article, I hope to explain clearly and as simply as possible what a small subgroup confinement attack is and how this attack works.
And finally, at the end of this article, how to protect your Diffie-Hellman key exchange from this attack.
The goal of a small 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 or b).
To perform this attack and retrieve the secret integer chosen by our target, we must use a man 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 integer b.
For that, we’re going to use a small subgroup confinement attack.
The first step is to find a smooth prime number p upper than the p given by Alice, with many small factors (factors less than or equal to 216 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 this CTF write up, to make smooth prime where you can easily choose his length and smoothness.
With this smooth prime number p, we have a lot of small factors which divide p-1.
The attack can start !
You will do these 4 steps on all factors of p to get the secret integer b of Bob.
We’re going to call each factor f.
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’:from random import randint def get_tampered_public_key(f, p): tampered_A = 1 while tampered_A == 1: tampered_A = pow(randint(1, p), (p-1)//f, p) return tampered_ASend A’ to Bob as Alice public key
Bob use A’ to create his shared secret. [Bob shared secret = A’b (mod p)]
Intercept Bob’s MAC(shared_secret, message)
With A’ used in Bob shared secret, we have reduced the possible value of the shared secret, because Bob raised our A’ to a power b and the order of A’ is f.
We deliberately choose small factors f so we can brute force all possible value from 1 to f until we find an x such as A’x (mod p) is equal to Bob MAC(shared_secret, message).
The result can be written like that: x ≡ b1 (mod f1)
After repeating this fourth step, we have a lot of equations like this:
- x1 ≡ b1 (mod f1)
- x2 ≡ b2 (mod f2)
- …
- xn ≡ bn (mod fn)
With all these equations we can easily recover the secret integer of Bob using the Chinese remainder theorem (CRT).
Example to calculate the CRT of our equations in python:
from sympy.ntheory.modular import crt
#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 equations
b = crt(f_n, x_n)[0]One solution to protect your Diffie-Hellman key exchange from this attack is to use a safe prime p where p = 2q + 1 and q is prime.
Check that 2 <= y <= p-2 (otherwise there may be a 1 bit leak)
With p 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 the Federal 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)