# Subverting the key generation step in RSA public key cryptography

I am interested in the ways the implementation of an RSA key generation implementation can or cannot be subverted so that the subverter has an advantage, but the owner of the key, and the people who interact with the owner, are left unaware that something is going on. I assume that the owner of the key does not have the ability to detect subtle bugs in the key-generation implementation, but that the key will be used for encryption and decryption with standard implementations outside the subverter's control.

1. My first idea was that a subverted primality test might accept, instead of rejecting, numbers of the form P1*P2 where P1 is a fixed prime known only to the subverter, and P2 a random prime. The owner of the key would end up with a modulus of the form P1*P2*Q, which the rest of the world would not necessarily be able to distinguish from a semiprime number. However, according to this answer, the owner of the key may find themselves unable to crack their own public key, that is, to read messages intended for them. I understand the linked answer to mean that the prime decomposition of the modulus is necessary to read encrypted messages, and in effect, the owner of the key would not have this decomposition. The owner of the key would only have P1*P2 on the one hand and Q on the other hand.

2. Another idea would be that the prime generation implementation might be subverted in a way such that there exist a million primes P1,P2, …, P1000000 that the implementation is more likely to generate than the others (say, each has probability 1/2000000 to be generated each time). This would, in effect, amount to a private Mining your Ps and your Qs attack(*), reserved for the subverter (who would know the values of P1, …, P1000000) but, as long as the subverted implementation remained in moderate use, unlikely to be detected by anyone else (owner of the key and rest of the world).

(*) It occurs to me after having written the question that the subverter can keep its game preserve more private if the subverted implementation never pairs a prime from the list P1,P2, …, P1000000 with another prime from the list. This doesn't prevent them to be discovered one by one using the original “Mining your Ps and your Qs” attack, but at least they do not unravel all at the same time.

My question is: can 1. be made to work using, say, some sort of pseudoprime instead of a composite number to maliciously accept as prime? Is there a reason why 2. might not work in practice?

These are two questions but they are related in that they are relevant to the same purpose

-
This method subverts the RSA public key in several ways, one of which is by embedding part of the secret prime in the modulus itself. The rest can be recovered in polynomial time. – Samuel Neves Aug 15 '14 at 12:49
Subvert the PKI infrastructure itself. If an attacker can issue valid signed keys, they don't need to break anyone elses' keys. – Jeff-Inventor ChromeOS Aug 16 '14 at 5:07

I don't think idea 1 can be made to work at all. The main point is that in order to generate a correct secret decryption key, the key generator must know the order of $\mathbb Z^*_n$, i.e., the totient of the modulus $n$. The generator knows that $n=p \cdot q$, where it believes that $p$ and $q$ are primes, and so it believes that the totient is $(p-1)(q-1)$. But in reality, if $p$ is not prime, the actual totient must be smaller, because the totient of $p$ is strictly less than $p-1$ (and similarly for $q$). So the generator will not be working with the correct totient, and cannot compute a correct secret key. (Technically, all of this assumes that $p$ and $q$ are actually coprime, which the generator can check for itself.)

As for idea 2, it essentially has been implemented in practice, in the sense that several key-generation algorithms having that flaw were deployed and used for years without suspicion. The simplest explanation is that these were accidental rather than malicious flaws, but the same kind of flaw could be deployed maliciously as well.

UPDATE: the "problem" with subversion of type 2 is that the public can discover that many keys share a common prime, and thus learn of the subversion. Here is another kind of subversion that does not have the problem of shared primes, but does allow the subverter to factor the generated modulus. The subverter designs the generation algorithm to choose a prime that is close to the output of a PRF applied to (say) the email address and/or time of day -- some (quasi-)public information that will be associated with the key, which will be unique every time the generator is run. So the chosen primes will likely never be the same, but the subverter can find them easily using the secret key of the PRF. The only catch is that the PRF secret key must also be hidden in the generator algorithm. A suspicious user might be able to discover the subversion by inspection or by running the algorithm in controlled ways, but not by discovering shared primes across keys (because they do not exist).

-
Thanks! One of the sub-questions regarding idea 2 is whether it can be implemented in a way such that it cannot be detected by others, which is not the case for the accidental weaknesses we are now aware of :). I was thinking about this and editing the question with a side-remark at about the same time you were writing your answer. Also, other known weaknesses in keys (P or Q too small, P and Q too close to each other, …) are disqualified for the same reason: someone else will notice by looking at the public key. – Pascal Cuoq Aug 15 '14 at 12:22

The most effective trapdoor I could imagine an adversary building into an RSA key generation algorithm would be the following:

Preparation

The adversary generates a set of RSA keys of varying sizes. The public keys will be built into the malicious key generation code, the secret keys are kept by the adversary.

Key generation algorithm

The algorithm is given a key size to be output. Let's call this key size $K$. The algorithm now picks one of the pregenerated key pairs with key size $k$. This is picked to be the largest key satisfying $k < K/2 - log(K)$

The algorithm chooses $k-1$ random bits. These random bits are encrypted using the adversary's public key. We'll call the result $c$.

Use the $k-1$ random bits as seed for a PRNG. Use the output of the PRNG as input to any prime generation algorithm in order to generate a $K/2$ bit prime. We'll call this $p$

Pick a candidate $q$ such that $\lfloor{pq/2}\rfloor \mod 2^{k-1} = c$, increase $q$ by $2^{k}$ until a prime is found.

Use $p$ and $q$ as in an ordinary RSA algorithm.

Reversing

The adversary can use the key size to find which public key was used to produce $c$, and the corresponding private key. The adversary can now strip the lowermost bits from $n$ (ignoring the least significant bit, which is always 1). The remaining bits can be decrypted using the adversary's secret key to recover the random seed. Using the random seed, the adversary can compute the secret key.

Security

The adversary can trivially compute the private key from the public key. For attacks by anybody else, the key size is effectively halved - they can attack the adversary's public key instead.

-
This is too sophisticated for the adversary to be able to deny malicious intent if the key generation algorithm is reverse-engineered, but a great answer nonetheless. – Pascal Cuoq Aug 15 '14 at 18:48
@PascalCuoq I was imagining the trapdoor getting placed Thompson style. So it didn't occur to me that this sort of deniability would be required as well. I was OTOH thinking about how the adversary could construct a trapdoor, which could not be used by somebody else who reverse engineered the code. Satisfying both requirements would be difficult, but DECDRBG with alternative constants could be a starting point to place a trapdoor with plausible deniability. – kasperd Aug 15 '14 at 19:11
Actually I am happy that I didn't mention deniability in the question, because an interesting range of proposals have emerged as a result, and yours is clearly the best at “protecting the innocent”. – Pascal Cuoq Aug 15 '14 at 19:23
The easiest proposal to deny is Chris Peikert's: build your own PRNG into the key generation program, write it so that it tries to obtain entropy from various sources of decreasing quality, ending up with a bad but user-specific source such as the IP address of the victim's computer. And then make sure that a bug causes the last source in the list always to be used… – Pascal Cuoq Aug 15 '14 at 19:38

As it does not address how one would detect #2, I'll take a stab at it.

Assume there is some watchdog looking at public keys in your system, trying to detect a problem. They can easily tell if two public keys share a prime by computing gcd. A gcd of anything other than 1 would identify bad keys. So, let's assume that once two people have generated a public key that share a prime, the watchdog realizes it and raises the red flag. How many keys would have to be generated for this to happen?

There are a million bad primes. We would expect a collision of bad primes after approximately $\sqrt{1000000}=1000$ bad public keys are created (birthday problem). The question now is, how likely are bad keys?

You have 1000000 bad primes, each with probability 1/2000000. So, the probability of the first prime being bad is 1/2. Similarly, the probability of the second prime being bad is 1/2. So, we can expect that, on average, every key being generated by your system is bad. So, after your user base is around 1000 users, there is a better than 50% chance primes have collided and the watchdog would detect the issue.

-
More precisely, without the “do not pair a bad prime with a bad prime” rule, on average, 3/4 of the keys are bad. With the rule enforced, it could be a different ratio (it really depends how the rule is enforced). Anyway, these were just illustrative figures, I didn't try to tweak them much because it is difficult to win against the birthday paradox. – Pascal Cuoq Aug 15 '14 at 13:10

The other answers tackle 2. very well, so I'll only look at 1.

I think it can be made to work in some specific instances, namely if

1. the key generator was part of a closed product with its own key storage or
2. the private key used a format where only the modulus and exponents were stored.

(Note that 2. is not common, because knowing the primes can be used to accelerate RSA operations.)

If either of those is the case, the key generator could generate a multiprime RSA key where $n=pqr$, with e.g. $r$ known to the attacker (either constant or depending on some public information like in Chris Peikert's answer). Then $p$ and/or $q$ could be small enough that the attacker could brute force them.

I'm not sure if this would have any advantages over the second attack. Perhaps with enough resources the attacker could ensure they are the only ones capable of brute forcing the random factors.

-