Backdooring Cryptography - Two characters that break your SSL encryption

In this article, we demonstrate a subtle but devastating backdoor in finite-field Diffie–Hellman. By computing public keys modulo $p^2$ instead of $p$ while restricting the secret exponent to $x \leq p-1$, the discrete logarithm becomes efficiently recoverable using Fermat quotients. We show the full derivation and provide a working Sage implementation.

Backdoors are always bad — but they are catastrophic when they are embedded in a fundamental primitive like Diffie–Hellman key exchange. If your browser shows a green lock, you assume your connection is secure. But what if the implementation of Diffie–Hellman contains a tiny change that looks harmless in code review — and yet allows an attacker to recover the private exponent in milliseconds?

In this post I’ll show a nasty little backdoor that requires only a tiny modification: using a modulus of $p^2$ instead of $p$, while keeping the secret exponent bounded by $p$ This completely breaks the security of Diffie–Hellman over finite fields since it allows to recover the secret exponent basically no time.

A Minimal Diffie–Hellman Implementation

Below you find a very simple implementation of the basic crypto steps needed for a Diffie-Hellman key agreement:

// prime number
p = 4823742384723409283742093847209487248923
    7319827409283472394087917413210193021832
    1302803821839103810312310013444302322818
    199199911119
// base number
g = 2
// private exponent
x = randint(2,p-2)
// public key
PK = power_mod(g,x,p) 
...
// session key using the opposite public key
session_key = power_mod(PK_remote,x, p)  			

Now the backdoored one:

// prime number
p = 4823742384723409283742093847209487248923
    7319827409283472394087917413210193021832
    1302803821839103810312310013444302322818
    199199911119
// base number
g = 2
// private exponent
x = randint(2,p-2)
// public key
PK = power_mod(g,x,p^2) 
...
// session key using the opposite public key
session_key = power_mod(PK_remote,x, p)  			
  			

Can you see it? It is very subtle, but it totally renders the key agreement useless. The session key can be computed by an adversary that can eavesdrop onto the communication in a matter of milliseconds.

To make it clear, the target ephemeral Diffie–Hellman and the attacker only needs passive eavesdropping on your messages. In the following i want to show you:

1. how exactly the backdoors works

2. that it works also for real-life non educationally implementations

How does the backdoor work?

The theoretical part is actually easy. The task is to compute the exponent $x$ from $$g^x \pmod{p^2}$$ assuming $$x \leq p$$ The last inequality is the critical point. Normally the random exponent should be in the range of the modulus, to be more precise in this case $0 \leq x \leq p(p-1)$. But the way the backdoor is implemented the random exponent is upper bounded by $p$ not $p^2$. I know at least two methods to solve this efficiently. The first is using Hensel-Lifting from $p$ to $p^2$ using the binomial theorem. The second is to use Fermat quotients, which i came up with someday on my own. I dont know if it is already known (probably it is) but i will show it below.

Rules for the Fermat quotient

Given a prime $p$ and an integer $0 \leq g \leq p-1$, the fermat quotient is $$q_p(g) := \frac{g^{p-1}-1}{p}$$ There are many known rules for the Fermat quotient (see the link), here we cite only those that we gonna need, which are actually only three.

Rule 1: $$q_p(g^x) = xq_p(g) \pmod{p}$$ Rule 2: $$q_p(g+k\cdot p) = q_p(g) - k/g \pmod{p}$$ Rule 3: $$q_p(g+k\cdot p^2) = q_p(g) \pmod{p}$$

Lets apply these rules to solve the backdoor.

Executing the backdoor

Task: Given the tuple $(p^2,r = g^x \pmod{p^2})$ with $x \leq p$ compute $x$.

Clearly, we want to use Rule 1 to linearizes the exponent: $$q_p(g^x) = xq_p(g)$$ The $q_p(g)$ can be computed easily, but how to compute $g_p(g^x)$? - It is $g^x \equiv r \pmod{p^2}$, so we can write $$g^x = r + p^2\cdot K$$ for some integer $K$. After applying Rule 3, we get $$ q_p(g^x) = g_p(r + p^2\cdot K) = g_p(r) = xq_p(g)$$ Now we have to further reduce $r$ down to less than $p$. Currently, the integer $r$ is in the range $0 \leq r \leq p^2-1$, so we can write $r = r' + k\cdot p$ and using Rule 2: $$ q_p(r) = g_p(r' + p\cdot k) = g_p(r') - \frac{k}{r'} = xq_p(g)$$ Now we are done, we only have Fermat quotients with an inputs smaller than $p$: $$ q_p(g)^{-1}\left(g_p(r') - \frac{k}{r'}\right) = x$$

One may ask

But how to compute an actual Fermat quotient? There is a fraction with $p$ in the divisor, we can not simply compute this modulo $p$!

Thats right, but not a problem. To compute $q_p(g)$ one computes $g^{p-1} = \omega = 1 + p\cdot k \pmod{p^2}$ then $$q_p(g) = \frac{g^{p-1}-1}{p} = \frac{\omega-1}{p} \equiv k \pmod{p}$$ which works totally fine modulo $p$.

A little example helps to build trust :)

We choose a safe prime, e.g.: $$p = 1208925819614629174708367$$ and set the generator to a random group element $$g = 1041004417494971846215356$$ We sample a random SECRET exponent for $x$: $$x = 1120478221914553609542643$$ Then we compute $r$ from $g^x \pmod{p^2}$ $$r = 304270210557141954048307191933100972508764971772$$ The value $r'$ is simply $r \pmod{p}$ hence $$r' = 775130548410270250034456$$ and $k$ is $$k = (r-r')/p = 251686419150295389597148$$ Further we need the two fermat quotients $q_p(g)$ and $g_p(r')$ $$g_p(r) = 1038010834383851421083784$$ $$g_p(r') = 1099542264378767565462870$$ Now we have all our input and can compute $x$ $$q_p(g)^{-1}\left(g_p(r') - \frac{k}{r'}\right) = 1120478221914553609542643$$

You can see that the final output is equal to the secret exponent $x$. Below you find a small implementation of the algorithm.

   // Sage implementation of 
   // the backdoor
   
    def fermatQuotient(g,p):
    	R = power_mod(g,p-1,p^2);
    	r = power_mod(g,p-1,p^1);
    	return Integer(Mod((R-r)/p,p));
	
    // We compute Safe Primes, but 
    // all primes would work
    def nextSafePrime(p):
        while (is_prime(floor((p-1)/2)) == false):
            p = next_prime(p)
        return p;

    p = nextSafePrime(2^80)
    g = randint(2,p-2); 
    print(f"p = {p} g = {g}")
    x = randint(1,p-1); 
    print(f"x = {x}"); // secret exponent
    r = Integer(power_mod(g,x,p^2)) // Target
    rp = Integer(Mod(r,p));
    k = (r-rp)/p;
    q_g = fermatQuotient(g,p);
    q_rp = fermatQuotient(rp,p);
    T = Mod(inverse_mod(q_g,p)*(q_rp-k*inverse_mod(rp,p)),p);
    print(f"x = {T}")
  

Real-live implementations

The current backdoor has two main drawbacks.

First, mostly the actually crypto primitives are encapsulated in higher API calls. Developers of crypto libraries cover critical operations such that later no mistakes can happen. For example if you use BouncyCastle, the generation of the integer $r$ and $x$ are coverd by

    	DHBasicKeyPairGenerator(...)
    

Second, the integer $r$ is larger than the actual prime number $p$, which might looks suspicious when looking at the messages. This does not cause per se a problem on the otherside. Computing the session will work perfectly, if no boundary check is done. But well known libraries like OpenSSL do indeed a boundary check, see below.

      BN_copy(tmp, params->p);
      BN_sub_word(tmp, 1);
      if (BN_cmp(pub_key, tmp) >= 0)
        *ret |= FFC_ERROR_PUBKEY_TOO_LARGE;
    

So if pub_key > p one gets a ERROR_PUBKEY_TOO_LARGE error.

Note:The use of certificates is not a direct drawback. Our backdoor here adresses the ephemeral public key, which would get signed from the long term public key, for which you have the certificate.

Modern cryptographic libraries typically:

1. enforce modulus bounds,

2. validate public keys,

3. restrict domain parameters,

4. encapsulate key generation inside hardened APIs.

As shown above, OpenSSL rejects public keys larger than $p$. Such boundary checks prevent the $p^2$ manipulation from going unnoticed. However, custom implementations, embedded systems, or modified crypto libraries may omit these checks — intentionally or accidentally.

Related Posts:

• The NSA Backdoor

• NSA Backdoor: SP800-90-Dual-EC-PRNG