Researchers have demonstrated a way to attack RSA encryption faster than before, allowing them to compromise (admittedly already deprecated) 1024-bit RSA in just five months on classical computers in an academic CPU cluster.
Fig 7 shows the symmetric security level drops for the most common key sizes.
The big one is RSA-2048, because 90-bits is entering the territory of NSA’s supercomputing capabilities. RSA-3072 should probably be considered the minimum RSA key size from now on, with 4096 for anything that needs headroom.
I don’t necessarily disagree with you, and I’m not saying you’re implying otherwise, but I do also want to remind people that you should not be using RSA if you have the choice to use something better, like Curve25519.
I am not a cryptographer. But the folks at Trail of Bits probably include at least one, and @soatok is someone I trust is a cryptographer (who also seems to agree with Trail of Bits on this and/or that they include at least one cryptographer).
Yeah I wholeheartedly agree with you here. But just like you said, Curve25519 is not available everywhere. My point was merely that the key size recommendations need an update.
Using e.g. OpenSSH’s RSA implementation is highly unlikely to run into padding oracle attacks etc. Those people know what they’re doing. But if you’re going to deploy RSA in your own code, the best way to do that is to f***ing not. Ed/X25519 is so much more better especially in terms of footguns. The only things you need to do is ensure public key 0 is not accepted and that you hash the shared secret before use. Also you should probably be already working to pair it with ML-KEM.
It’s not necessarily that simple. RSA is expected to be (at least marginally) more resistant to quantum attacks than ECC[1], which could possibly buy a few years against an attacker performing a harvest now decrypt later attack. It is unclear to me from what I’ve read so far if this can be combined with Shor’s algorithm to negate that advantage against a quantum adversary, though.
Yeah who knows what leaps qubit scaling will take in the near future. I’d probably bet on ML-KEM + x25519 over good implementation of RSA despite the incremental security gains of RSA over ECDH in term of qubit requirements. RSA carries the nasty part of no forward secrecy.
I personally would tend to agree, I just don’t think it’s reasonable to say that ECC is always preferable to RSA. There are possible threat models where that’s not the case, and the nuance could matter.
ECC does not inherently include forward secrecy. Forward secrecy is provided by a protocol, not an algorithm. RSA can also be used to provide forward secrecy in a protocol that is designed to support it (e.g., Diffie-Hellman, which is also what provides forward secrecy when using ECC, in the form of ECDHE)
Is Signal’s Android app still dual-signed with a 1024-bit RSA key?
You’re right of course. You can e.g. do single RSA key exchange and switch to hash ratchet. Or you can try to obtain forward and future secrecy with RSA-ratchet where you keep signing new RSA keys with long term key-pair. You can even pair those approaches for double-ratchet. But using ratcheting RSA has some rather unfortunate effects on performance:
A quick test on my machine with pyca/cryptography library shows a single RSA-4096 key takes 357ms, where as x25519 key generation takes 25µs. Using RSA would thus result in 14,271 times more compute time per message for key generation. And this is a relatively fast computer. I can’t imagine RSA-4096 based double-ratchet for Signal running on some potato Android would be terribly good idea.
A DH-ratchet also brings on the table some post-quantum resistance, probably from the sheer volume of keys and the chance that single public key is missed making it a guessing game instead of another round of Shor. At least JP Aumasson mentioned the incremental resistance in his book Serious Cryptography, but he didn’t specify that claim.
So at least for messaging, the performance limitations will come in the way. But for some USB HSM used to sign stuff without forward secrecy, it might be somewhat more secure against quantum adversaries to use large RSA keys over Ed25519, at least until hybrid signatures become a thing.
It’s worth noting that even RSA-2048 has been discouraged by governments for a while now:
This matters for older Proton users, since many of them may could still have RSA-2048 keys: Proton doesn’t rotate keys automatically.
And as has been said, plenty of cryptographers discourage RSA regardless of key size
