Games with prime factors

A different avenue opens up if we focus on a different aspect of RSA keys: the relationship between the public and private exponents:

e × d = 1 mod ɸ(N)

That is e and d are multiplicative inverses modulo ɸ. Since e is usually fixed by convention to a small prime, one can ask: does such an inverse always exist?

Surprisingly the answer is no. Multiplicative inverse exists if and only if e is relatively prime to ɸ. We can estimate how often that condition fails. Recalling that ɸ is a large number, and e is prime, there is only one way they could fail to be “relatively prime: e divides ɸ. Since ɸ = (p – 1)(q – 1) that would also imply e divides at least one (possibly both) of the factors.

When p and q are generated independently as random primes, p-1 and q-1 are also effectively random. We can approximate the probability of the product being divisible by e as 1/e + 1/e = 2/e. (Ignoring the highly improbable case where it divides both of them) For e = 65537, this is less than one in thirty thousand— unlikely to be encountered unless one is generating a lot of RSA keys.

Now what happens if we deliberately choose one of the primes to trigger this condition? In that case e is no longer invertible modulo ɸ and there is no “private key” in the traditional sense. This is a necessary but not sufficient condition to render the key unusable.

Root cause

To see why traditional “private key” does not completely neutralize a public key, let’s review the mechanics of RSA encryption.

The ciphertext C is obtained from the source plaintext P as:

C = P^e mod N

So encryption involves raising the ciphertext to the e-th power modulo N. Inverting the relationship we can say the plaintext is the e-th root of ciphertext modulo N. This is the important observation: decryption involves computing e-th roots.

In the case of signatures, a signature S is related to the original message M as:

M = S^e mod N

Note the similar relationship: obtaining the signatrure S involves computing the e-th root of the message.

In “standard” RSA, computing e-th roots is straightforward: we raise the input to the d-th power, where d is the private exponent. For efficiency reason, this is actually done as two separate calculations: first computing the root modulo p and later modulo q, then combining the results.

This gets more complicated in our version where no such d exists, because one or both of the primes were deliberately chosen such that e divides p-1.

Here we need to distinguish between two issues:

1. Lack of unique roots. When e divides p-1, the structure of the group changes. It is no longer the case that every element has a unique e-th root. In fact most elements do not have e-th roots. Some minority— exactly fraction 1/e in fact— have an abundance of them, exactly e for each such element.
2. Computing those roots when they exist is no longer a straightforward process of raising the input to some suitable exponent.

If a root does not exist, that message can not be signed or that ciphertext can not be decrypted (This latter case is less likely to be encountered in practice; no such ciphertext would be generated by a valid encryption process.) That is a mathematical constraint, not a computational limitation. No future quantum-computer or theoretical Zeno machine changes that.

On the other hands, the existence of multiple roots messes with the semantics of RSA. For example ciphertexts become ambiguous. They can decrypt into different plaintexts, each of the a valid root. The recipient can not determine which one the sender had in mind. Interestingly signatures are impacted in the a different way. There will be multiple valid signature corresponding to a given message. This is no different intrinsically probabilistic signatures such as ECDSA. An adversary would be considered to have defeated the system if they can find any one of those roots to forge a signature.

That becomes a computational problem for which well-known algorithms exist. For example Tonelli-Shanks algorithm computes square roots in a prime modulus. That corresponds to the special case e=2. Since p is prime, 2 will always divide p-1 so there can not be a “private exponent” to calculate roots in the general case. Adleman-Manders-Miller algorithm generalizes that to work for any e.

Deliberately mangled RSA keys

Revisiting the problem that started this blog post, suppose we generate a deliberately malformed platform key (PK) as described in the previous section. Can users be confident that it can not be used to updated the KEK? Recall that UEFI specification requires KEK updates to be signed by the KEK, so this comes down to asking what it would take to create a valid signature using the mangled key.

Let’s posit that the “attacker” already knows the factorization of the modulus. This is a realistic assumption since the OEM generating the modulus is part of the threat model.

Recall that even with knowledge of the modulus, there are two obstacles to signing:

1. Finding a “signable” message. Not every message can be signed because some elements have no e-th roots. However attackers are usually not limited to targeting a single message. Often they can generate variations of a message that have cosmetic differences but carry the same semantics. In the case of UEFI variable updates, an attacker can generate different KEKs in the hopes that one of them results in a signable message. In other cases the hashing scheme is probabilistic, as with PSS so it is sufficient to keep the same message and vary some random padding to generate variants. This problem lends itself to brute-force after trying roughly e steps. Each step consists of generating a candidate message, hashing it and checking the order of the resulting group element. Desired roots exist if and only if the element order is divisible by e.
2. Computing any e-th root once a suitable message is located. Time complexity of the AMM algorithm is linear in e and polynomial in bits of the prime.

The bad news is with the default RSA public exponent of e=65537, neither of these is prohibitive. Knowledge of the prime factors allows computing roots the hard way with AMM and forging signatures. The good news is we can extend the construction to greatly increase the difficulty along two dimensions.

First, we can use large public-exponents. For example if e is selected to be 128-bits, both of the above computational problems become intractable. While it is straightforward to scale up difficulty this way, it runs into a compatibility problem: not all software implementations can handle large public exponents. (For example the Windows cryptography stack used to assume public exponents fit into 32 bits.) Some systems even mandate e=65537.

Adding primes

A different approach involves increasing the number of primes. The above example implicitly assumed the RSA modulus follows the usual rules: product of exactly two distinct primes and only p has the special structure with respect to p. Suppose q is also selected to have the property q ≡ 1 mod e.

This creates a new problem for the attacker on step #1. Recall that for a group element to have e-th roots, such roots must exist modulo p and modulo q individually Since messages are mapped to group elements by a hash function, the probability of that condition being met for each prime individually is still 1/e. But the probability that it holds for both prime at the same time is 1/e². Compared to the original design, that ratcheted up the difficulty by another factor of e.

Interestingly the difficulty level of the second step does not change. AMM still takes the same effort for each prime. It has to be done twice, once for each prime factor but that is merely doubling the effort— not a material increase in cryptographic terms. The real step-up in difficulty comes from finding a signable hash with e-th roots. With two primes and e=65537, that will now require over four billion attempts on average.

No need to stop with two primes. RSA works the same way over multiple primes. This is even defined in the standard under the heading multi-prime RSA. Meanwhile recipients can not detect how many primes went into a modulus short of successfully factoring it. It follows that our 2048-bit key can be generated as a product of three or more primes. Suppose we use eight primes of roughly 256-bits, all deliberately chosen to make e-th roots rare. Now the odds of a random group element modulo N having e-th roots goes down to 1 in 2¹²⁸. Looked another way, it would require 2¹²⁸ attempts on average to locate a valid message with a hash that can be signed.

If one is willing to use large public exponents and forego any pretense of being a valid RSA key, there is another approach in the opposite direction: use a single prime number as the RSA modulus. Unlike previous examples that look like a real RSA modulus to anyone else who can not factor the product, this case is easily detectable by running a primality test. It would also be completely insecure under ordinary circumstances; the private exponent can be computed trivially from the public exponent. But the choice of public exponent here ensure no such value exists and forging a signature is equivalent to extracting e-th roots which is intractable for large e. Surprisingly this would still maintain compatibility with existing software attempting to check for valid signatures: no major implementation checks if a peer’s alleged “public key” was generated properly as a composite number. Meanwhile the formulas for signature verification operate the same way even in a prime group. It is not possible to forge a valid signature without solving the difficult root-extraction challenge modulo that prime.

Burden of proof

The last piece of the puzzle is proving that a given RSA key was generated according to the scheme described. Since the public exponent is typically determined by convention, this comes down to demonstrating the special structure of the modulus.

The exact difficulty of the proof depends on the approach taken. Single prime is the easy case, because no proof is required. Anyone can verify that the modulus N is a prime and observe its relationship to the public exponent.

For composite modulus, the standard approach involves zero-knowledge proofs. There is work going back to Bellare and Yung [CRYPTO 1992] for proving properties about a given RSA key in zero-knowledge, specifically that it defines a valid permutation. In our case, that is false by construction: public-exponents are chosen to guarantee it is not a permutation and that many elements map to the same image under the public-key operation. More recent work such as Goldberg et. al. [2019] extends that result to construct non-interactive proofs that a given N is the product of two prime powers or that it is square-free (eg no prime factor is repeated.) Since these protocols only involve the modulus and not the public exponent, they can serve as building blocks. But there is still a missing piece around proving that for every prime p that divides the modulus, we have p = 1 mod e for the public exponent e.

For the case when the modulus consists of many small primes, there is a more direct approach around revealing the factorization. Recall that the heuristic argument for difficulty above is based on an attacker already knowing the factorization. When there are many small prime factors (to keep the public exponent at 65537 for compatibility) those factors may well be within reach of ECM anyway. Even the threat model implies the security of the scheme can not rest on difficulty of factorization, because one of the “adversaries” to defend against is the person who generated modulus and has full knowledge of the factors.

CP