Score:3

Another question about equivalent keys and RSA

um flag

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

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

Score:3
ng flag

(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 00h 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.

oCriptoPanquer avatar
um flag
It's amazing how much we you can learn from your answers!!!
Crypto Learner avatar
in flag
Yeah, I agree. Even when we've been reading crypto books we can't see analysis like that: except after reading a lot of papers. So, yeah, I also learn a lot reading answer like that in Cyrpto.SE.
Crypto Learner avatar
in flag
@fgrieu, Let me ask more, pls, on your update: even if the original $(n,e)$ was registered in a CA, is still possible that the adversary to register $(n',e')$?
fgrieu avatar
ng flag
@CryptoLearner: yes. When a CA receives a Certificate Signing Request (a public key, some ID information like a common name "website.com", and a signature of that), they check the syntax, that the signature verifies against the public key and the rest of the info, that the request matches the ID information (e.g. because there is evidence of that in the DNS system for website.com), and grant the certificate. There is typically little or no attempt to check that the public key is safe and/or unrelated to that of another entity. And in the attack I'm pointing after update, it couldn't be done.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.