1
$\begingroup$

I understand that it is important to check how hard it is to attack RSA keys, but I assume at some key size attackers would not even try. Real attacks are carried out by exploiting mistakes in the whole process, not the cryptography.

The maximum key size attempted would obviously depend on the value of the protected secrets, and the cost to the attacker. What key size would a rational attacker try to break, if they knew they could gain $1000 / a million dollars / a billion dollars / a trillion dollars?

(Some part of the motivation: On a recent thread it was said that if you choose two primes p, q for RSA and p=q, then this would be absolutely insecure. But if a 2048 bit key is a square, would anyone actually bother checking this? BTW I think RSA wouldn’t “work” if p=q).

PS. The recommended link in the comment gives some answer. I would think that records set by academics don't represent what's possible, because it merely shows hardware improvements and from an academic standpoint it is quite boring. For government agencies, who would use it to detect secrets, 1,024 bit seems to be not 100% safe to protect a secret that is worth it. For a small time criminal, it would be safe.

But part of my question is: Where is the point where nobody will even try to crack it - with the result that some stupid mistake making a particular code insecure would never be detected, because nobody tries?

$\endgroup$
  • $\begingroup$ Does this answer How big an RSA key is considered secure today? satisfy you? $\endgroup$ – kelalaka Oct 4 at 21:25
  • $\begingroup$ RSA would practically work with $p=q$ if we compute and use $d=e^{-1}\bmod\varphi(n)$ or $d=e^{-1}\bmod\lambda(n)$ correctly, that is with $\varphi(n)=\lambda(n)=p\,(p-1)$. With encryption or signature padding, the probability to hit a case where decryption or verification fails is $1/p$, which is negligible. But as noted in this answer, that could well be detected, e.g. by students trying to factor all the RSA moduli they can grab using their Fermat factoring code. $\endgroup$ – fgrieu Oct 6 at 9:21
2
$\begingroup$

This question is based on a false premise, namely, that the difficulty of breaking cryptography (involving a given key type) depends only on the size of the key. This is not how cryptography is broken. The weak point in cryptography is usually flaws in the implementation.

For example, one way RSA can go wrong is if the key was not generated correctly. Cases of keys that were generated using a random generator that was not properly seeded are depressingly common. For example, Debian shipped a broken version of OpenSSL for two years which resulted in there being only a tiny number of possible SSH keys. Surveys of SSH and TLS public keys have shown that a small, but significant proportion of servers have keys that were generated with insufficient entropy or with a flawed process, resulting in keys that can be broken easily. (An RSA private key is determined by two (pseudo-)primes, and the public key is their product. If two private keys share a prime, it's trivial to spot this from the public keys $p \, q_1$ and $p \, q_2$.) Linux has had a steadfastly broken interface to random generation, historically giving the choice between an interface that blocks needlessly and one that is insecure in one specific but critical moment (just after the first boot of a system) (modern kernels have a good interface in the form of the getrandom system call, but because it's harder to use than the historical interfaces, a lot of software relies on the historical interfaces). In addition to the RNG problem, there is flawed key generation code out there, for example not using enough iterations when testing primality (which is a probabilistic test), or using computational shortcut that make the private key easier to calculate from the public key than brute force (such as generating primes that are close to each other, which can be faster, but is insecure).

A larger key size can help mitigate against a broken key generation process. For example, generating a larger key will request more material from the RNG and this can help if the RNG is not well-seeded at the beginning but receives additional entropy over time. Generating a larger key can also help if the code takes shortcuts, because it may compensate the loss of security from these shortcuts. But not all flaws can be mitigated that way. When the RNG is not seeded properly and only a small number of keys are possible at all (as in the Debian-OpenSSL case, or in the case of many embedded devices without a hardware RNG), no increase of the key size will help.

In addition to the key generation process, another source of weaknesses is the use of the key. Asymmetric (and symmetric) cryptography is prone to side channel attacks, where properties such as the timing of certain parts of the computation leaks information about the key, or about the data that the key is protecting. A larger key can help against some attacks, because many side channel attacks need to observe a large number of calculations in order to extract enough information to reveal the key or the data.

Asymmetric encryption is also prone to protocol attacks. Asymmetric decryption is tricky because it combines the private key with an input that cannot be trusted since it could have been produced by anyone. This can allow oracle attacks, where the attacker sends an invalid ciphertext, and based on the message or the timing of a decryption error, learns some information about the key. The general principle of this form of attack on RSA was published in 1998 by Bleichenbacher and was still a concrete problem 20 years later. Modern communication protocols avoid asymmetric decryption in favor of key establishment protocols where, rather than encrypting a session key with a symmetric key, both sides arrange to derive the same session key from different computations that give the same result. But RSA decryption is still used in the wild in TLS up to 1.2 (this is deprecated, but still used by “middleboxes” that intercept and filter TLS traffic in enterprise networks).

if a 2048 bit key is a square, would anyone actually bother checking this?

Well, yes, of course. It's very easy to check. It's also easy to factor the key if $p \approx q$, and it's one of the obvious things an attacker would try.

Where is the point where nobody will even try to crack it - with the result that some stupid mistake making a particular code insecure would never be detected, because nobody tries?

There is no such point. If you generate a key without a proper RNG, or if you store your key insecurely, or if you use an implementation that doesn't properly protect against applicable attacks such as side channel leaks and glitches, or if you use a flawed protocol, your key may be vulnerable no matter what its size is.

“Nobody will even try to crack it” is not a useful concept. It's based on the assumption that attackers are stupid and work in isolation. They aren't and they don't. Where there's a possible attack, all it takes is one expert to write a tool to perform a sophisticated attack, and sooner or later a conveniently packaged version of this tool will be available for free or for sale.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.