Another question about equivalent keys and RSA

Question

I've been trying to understand the multiple keys thing in RSA. I'm quite sure that multiples private keys are possible:

• In RSA, why are there multiple possible private keys, and even the public key itself that can be used to decrypt the message?
• More than one private key for RSA
• Do equivalent RSA keys exist?
• Will publishing two or more public keys of the same RSA private key cause a security risk?

But, my questions are:

1. If a malicious adversary took an RSA private key $(n, d)$ (and all its internal elements used to generate it), will s/he be able to create another equivalent and well-formatted public key, using standard $e$ values, even if the original keys were created following the best practices for an RSA key generation, the adversary can create something like $(n, e+ \lambda(n))$, but, in the real use of crypto, would it go unnoticed?

2. Given a RSA signature of a message $m$ under a private key $(n,d)$ and public key $(n,e)$:

   $s = Sig(m,n,d)$

   so is it feasible (with a non-negligible probability) for the adversary create another equivalent public key $(n',e)$ that successfully verifies the same signature $s$?

3. That problem (a maliciously generated equivalent public key that goes unnoticed) is also an issue with other signatures schemes (non-RSA based)?

Answer 1

(1) Equivalent public key in RSA

An adversary with $(n,d)$ can factor $n$ (except if $e$ is secret and large, which is unusual). Therefore they can build a public key $(n,e')$ with $e'=e+k\,\lambda(n)$ for any $k\in\mathbb Z$ such that $e'$ is acceptable by whoever checks public keys. The most standard such check is odd $e'$ with $3\le e'<n$ (standardized in PKCS#1), and that always allows at least one $e'\ne e$, and would pass mustard against many automated checks (e.g. those in OpenSSL). There are exceptions: FIPS 186-5 prescribes $65537\le e'<2^{256}$, which (combined with other prescriptions in this standard) would allow a single $e$.

That's usually not much of a problem: the adversary can simply use public key $(n,e)$ and present it as their public key. Since they know $(n,d)$, they can sign as the legitimate key holder, and obtain a genuine certificate that $(n,e)$ belongs to them. This can help them to misappropriate any signature made by the genuine signer. This can be detected in an audit if someone compares $n$ in public keys; using $(n,e')$ rather than $(n,e)$ won't change that much.

(2) Signature misappropriation by key substitution in RSA

Given an RSA signature $s$ of a message $M$ under a private key $(n,d)$ and public key $(n,e)$, is it feasible (with a non-negligible probability) for the adversary to create another equivalent public key $(n′,e)$ that successfully verifies the same signature $s$?

That depends on the signature padding. If we sign a message as $s\gets\operatorname{SHA-512}(M)^d\bmod n$, and verify by comparing $s^e\bmod n$ against $\operatorname{SHA-512}(M)$, then yes. All it takes is finding a moderate prime factor $r$ of $s$ (it's possible with high probability), and $n'=r\,n$ will do.

That technique works with most standard RSA signature schemes when $n$ and $n'$ have the same byte size, which can only happen when the bit size of $n$ is not a multiple of 8. For usual parametrization, it can still happen for the common RSASSA-PKCS1-v1_5 signature padding and a slightly too permissive implementation of signature verification, allowing extra 00_h byte(s) on the left.

But this would not be much of a practical issue, because certification authorities would not certify the public key $(n',e)$ unless $(n,d)$ has leaked (and then we are back at 1). And independently, this can be detected in an audit by observing that $n'\bmod n=0$.

Update: If we allow for $(n',e')$ rather than only $(n',e)$ as in the question, now adversaries can find a public key $(n',e')$ such that signature $s$ prepared for known $(n,e)$ verifies for $(n',e')$ and the (unmodified) message $M$ (which needs not be known). That's with $n'$ the same usual bit size as $n$, and $e'$ acceptable per PKCS#1, so that common verification procedures give a pass. The adversaries know the factorization of $n'$ and can build a valid $(n',d')$, so that they can get their public key $(n',e')$ certified the normal way. That's all without knowing a private key matching $(n,e)$. And an audit wouldn't find any corelation between $(n,e)$ and $(n',e')$ unless it also considers $s$. Only the fact that $e'$ is rather unusual would be a clue that it may be crafted for an attack. The attackers can use techniques similar to those there. That makes RSA as practiced (RSASSA-PKCS1-v1_5, RSASSA-PSS, ISO/IEC 9796-2) vulnerable to signature misappropriation. This could be an issue in some contexts.

(3) Other signature schemes

Is that problem (a maliciously generated equivalent public key that goes unnoticed) is also an issue with other signatures schemes (non-RSA based)?

Some signatures are immune to signature misappropriation, including EdDSA. It's easy to make RSA just as resistant to that kind of attacks: instead of using $H(M)$, use $H(H(\mathsf{PubKey})\mathbin\|H(M))$ both at signature and verification.

For more on such attacks and status of signature systems against these, see Dennis Jackson, Cas Cremers, Katriel Cohn-Gordon, and Ralf Sasse's Seems Legit: Automated Analysis of Subtle Attacks on Protocols that Use Signatures, in proceedings of CCS 2019.