In A Comprehensive Study of Backdoors for RSA Key Generation, T. Lin et al. proposed three cryptographic backdoors associated with the key generation step of RSA. The first two, RSA-SBLT, and RSA-SBES have the same advantages as Crépeau and Slakmon’s RSA-HP$_{\beta}$ while the third, RSA-BDH, is a novel construction based on the decisional Diffie-Hellman assumption.

The RSA-BDH backdoor is a strong-SETUP attack meaning that keypairs generated using its dishonest key generation routine are polytime indistinguishable from keypairs generated using an honest key generation routine.

The decisional Diffie-Hellman assumption states that there exists no Turing Machine which can solve the Diffie-Hellman problem in a cyclic group $\mathcal{G}$ in probabilistic polynomial time, and the Diffie-Hellman problem states that it’s super hard to find $g^{ab}\bmod{r}$ within a cyclic group $\mathcal{G}$ given a safe prime $r$, $g^a\bmod{r}$ and $g^{b}\bmod{r}$. The intractability of the decisional Diffie-Hellman problem in $\mathcal{G}$ is rivaled only by the unyielding desire of states to subvert communications security in the name of communications security and serves as the founding element of the RSA-BDH backdoor.

This particular cryptographic backdoor relies on a two-step process which is initiated by a device manufacturer, or by an adversary that can introduce firmware backdoors onto a target device.

The first step establishes a set of globally shared domain parameters to be installed on each of a given manufacturer’s devices, and the second step is performed on a per-device basis. That is, a device manufacturer establishes a set of global constants used for the backdoor, and then a set of constants which are set on a per-device basis. These constants are ideally stored in a non-volatile memory region such as within NVRAM in order to ensure that the backdoor is persistent, and difficult to detect.

The manufacturer set-up for RSA-BDH is as follows where $(g, r, x, Y, w)$ is set globally for all of a given manufacturer’s devices:

1. Select a safe prime $r$ of $k/2$ bits;
2. Select a generator $g$ of $\mathcal{G}$ where $\mathcal{G}$ is a cyclic group of $\mathbb{Z}^*_r$ of order $r-1$;
3. Choose an integer $x\in(0, r-1)$;
4. Set $Y=g^{x}\bmod{r}$; and
5. Choose an odd number $w\in(0, r-2)$

The device-specific set-up is as follows where $(t_1, t_2, c)$ are constants that are set on a per-device basis:

1. Randomly choose an integer $c\in(0, r-2)$;
2. Randomly choose two integers $t_1, t_2\in(0, 1)$;
3. If $p=g^{c+w\cdot t_1}\cdot Y^{c}\bmod{r}$ and $q=g^{-w\cdot t_2}\cdot Y^{-c}\bmod{r}$ are not prime, go back to step #1;
4. Set $n=p\cdot q$;
5. If $\texttt{gcd}(e, \phi(n))\neq 1$ where $\phi(n)=(p-1)\cdot(q-1)$ go back to step #1;
6. Compute $d\equiv e^{-1}\bmod{\phi(n)}$; and
7. Output the public key $(n, e)$ and the private key $d$

In order for the device manufacturer, or interested party to perform key escrow and consequently recover the prime factors $(p, q)$ of the RSA modulus $n$ the following steps must be performed given $(g, r, x, Y, w, n)$:

1. Set $\bar{p}=n^{1+x}\bmod{r}$. If $n\bmod\bar{p}=0$ jump to step #5;
2. Set $\bar{p}=\bar{p}\cdot g^{w}\bmod{r}$. If $n\bmod\bar{p}=0$ jump to step #5;
3. Set $\bar{p}=(ng^{w})^{1+x}\bmod{r}$. If $n\bmod\bar{p}=0$ jump to step #5;
4. Set $p=((ng^{-w})^{1+x}\cdot g^{w}\bmod{r})$; and
5. Set $p=\bar{p}$ and $q=\frac{n}{p}$ yielding the prime factorization of $n$.

For ease of retrieval, $(t_1, t_2, c)$ should be indexed within a database which is accessible to the device manufacturer, or through a side-channel such as a hardware debugger.

A toy implementation of the RSA-BDH backdoor can be constructed as follows using a static set of Diffie-Hellman parameters which correspond to different RSA modulus sizes. As an example, let’s use the RSA-BDH key generation routine to subvert 512-bit RSA. First, we need to select a 256-bit safe prime $r$ given $g=2$:

\$ openssl dhparam -text 256
Generating DH parameters, 256 bit long safe prime, generator 2
This is going to take a long time
..................+..........+..........+...........+..............................+.....+..........+.++*++*++*++*++*++*++*++*++*++*++*++*
DH Parameters: (256 bit)
prime:
00:bf:03:9f:fa:bd:f9:77:7c:f5:70:d2:a3:a6:3a:
0f:d3:42:ba:e0:5c:8f:ea:d0:1e:f4:36:15:b0:ef:
generator: 2 (0x2)
-----BEGIN DH PARAMETERS-----
MCYCIQC/A5/6vfl3fPVw0qOmOg/TQrrgXI/q0B70NhWw761LOwIBAg==
-----END DH PARAMETERS-----


Then, we need to select a random integer $x\in(0, r-1)$, a random integer $w\in(0, r-2)$, and $Y=g^{x}\bmod{r}$. For simplicity, let’s assume the following global parameters:

• $g=$0x2;
• $e=$0x10001;
• $r=$0xbf039ffabdf9777cf570d2a3a63a0fd342bae05c8fead01ef43615b0efad4b3b;
• $x=$0x2ca2bf052fe700ef8ea0a2a74597c3e7551a4b65213f73befcccbe6fadc002d4;
• $Y=$0x3421c839aac17d1f10616774969d075f0e2059ff5dd79ef680cff97463dfb38; and
• $w=$0x7d31191b02843c9f6133cc498976f695b9321416f62d7273020828e3cb36429f

And the following device parameters:

• $c=$0x506aeae91660d3879ac61fcbc7bdd9aa809d9a0289ff041084dfe1026f03a103;
• $t_1, t_2=$0; and

We can determine $(p, q)$ as follows in accordance with the RSA-BDH key recovery algorithm:

• $p=n^{x+1}\bmod{r}\rightarrow$0xbad0497e5efa8191746504298f526d35666c8c885b98f8243a94888dbb15af49;
• Since $p\bmod{n}=0$, we find that $q=\frac{n}{p}\rightarrow$0xb9069d4a2bba63a8063fdaf6c6dd6d5e7d131f850dd35f50a10ebd5980c5a6df.

Given that $p\cdot q=n$, and $(p, q)$ are prime, we can conclude that this is the prime factorization of $n$.

A full implementation the RSA-BDH key generation, and recovery routines is available here and relies on the Carmichael function $\texttt{LCM}(p-1, q-1)$ in lieu of $\phi(n)$.