Subverting the key generation step in RSA public key cryptography

Question

I am interested in the ways 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 P₁*P₂ where P₁ is a fixed prime known only to the subverter, and P₂ a random prime. The owner of the key would end up with a modulus of the form P₁*P₂*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 P₁*P₂ 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 P₁,P₂, …, P_1000000 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 P₁, …, P_1000000) 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 P₁,P₂, …, P_1000000 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}

Answer 1

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).

Answer 2

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.

Answer 3

Chris's answer is great.

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.

Answer 4

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.