### Subverting 512-bit RSA using RSA-BDH: an RSA backdoor based on the Decisional Diffie-Hellman (DDH) assumption

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 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 in probabilistic polynomial time, and the Diffie-Hellman problem states that it’s super hard to find within a cyclic group given a safe prime , and . The intractability of the decisional Diffie-Hellman problem in 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 is set globally for all of a given manufacturer’s devices:

- Select a safe prime of bits;
- Select a generator of where is a cyclic group of of order ;
- Choose an integer ;
- Set ; and
- Choose an odd number

The device-specific set-up is as follows where are constants that are set on a per-device basis:

- Randomly choose an integer ;
- Randomly choose two integers ;
- If and are not prime, go back to step #1;
- Set ;
- If where go back to step #1;
- Compute ; and
- Output the public key and the private key

In order for the device manufacturer, or interested party to perform key escrow and consequently recover the prime factors of the RSA modulus the following steps must be performed given :

- Set . If jump to step #5;
- Set . If jump to step #5;
- Set . If jump to step #5;
- Set ; and
- Set and yielding the prime factorization of .

For ease of retrieval, 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 given :

```
$ 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:
ad:4b:3b
generator: 2 (0x2)
-----BEGIN DH PARAMETERS-----
MCYCIQC/A5/6vfl3fPVw0qOmOg/TQrrgXI/q0B70NhWw761LOwIBAg==
-----END DH PARAMETERS-----
```

Then, we need to select a random integer , a random integer , and . For simplicity, let’s assume the following global parameters:

`0x2`

;`0x10001`

;`0xbf039ffabdf9777cf570d2a3a63a0fd342bae05c8fead01ef43615b0efad4b3b`

;`0x2ca2bf052fe700ef8ea0a2a74597c3e7551a4b65213f73befcccbe6fadc002d4`

;`0x3421c839aac17d1f10616774969d075f0e2059ff5dd79ef680cff97463dfb38`

; and`0x7d31191b02843c9f6133cc498976f695b9321416f62d7273020828e3cb36429f`

And the following device parameters:

`0x506aeae91660d3879ac61fcbc7bdd9aa809d9a0289ff041084dfe1026f03a103`

;- 0; and

We can determine as follows in accordance with the RSA-BDH key recovery algorithm:

`0xbad0497e5efa8191746504298f526d35666c8c885b98f8243a94888dbb15af49`

;- Since , we find that
`0xb9069d4a2bba63a8063fdaf6c6dd6d5e7d131f850dd35f50a10ebd5980c5a6df`

.

Given that , and are prime, we can conclude that this is the prime factorization of .

A full implementation the RSA-BDH key generation, and recovery routines is available here and relies on the Carmichael function in lieu of .