Stop using RSA (2019)
blog.trailofbits.com
blog.trailofbits.com
Also, this part in particular displays an alarming lack of nuance:
> if you come to us with a codebase that uses RSA, you will be paying for the hour of time required for us to explain why you should stop using it.
[1]: https://www.cryptologie.net/article/461/the-9-lives-of-bleic...
On the other hand, it’s now recommended to use PSS padding with RSA, which requires a random value for each signature.
What's the nuance you see that they don't?
So, sure, use RSA certs for your TLS connections, and I guess, fine, use RSA SSH keys,
But don't add RSA to new designs where it doesn't have to be there.
Was there a publicly available RSA implementation (even a commercial one) that was 20 years old 15 years ago?
From the security perspective, RSA is a perfectly acceptable choice. EdDSA is good and also a perfectly acceptable choice. They have different tradeoffs (some of which are mentioned in the article but not all), so you may want to consider trade offs, but as a user (e.g. choosing ssh or ssl keys), not a designer, everyone should feel free to choose either from the security perspective. You need to choose the right key size for both, and you need to use the correct vetted tools for both. But there really isn't much of downsides for using either.
As a system designer, there are some trade offs, but once again, in almost all practical system designs, both are acceptable security wise.
RSA is much harder to make secure that even simply ECC. It is systemically hard to make time it timing safe, more or less any mistake I padding completely compromises it. More or less every single operation involved in computing RSA exchanges is susceptible to timing attacks.
Then as the article says, it's very easy to choose "bad" keys. Bad keys are ones that aren't prime (I mean duh, but primality testing is probabilistic and has been found to go wrong before).
At a theoretically level RSA and ECC are essentially equivalent (in the sense that the maths is based on the same core problem), but the details of how it's approached is really important.
Then when get to basic practicality. ECC keys are much much smaller than RSA for the same level of security - 256 bits vs. 4-8k - and while RSA is faster than ECC, the advantage is severely impacted by key size, so secure rsa keys will be slower the equivalent ECC in not too long.
That's before considering the network traffic cost and latency for key exchange and certificate validation.
The only advantage RSA has over ECC at this point is that it is conceptually easier to understand - the mathematics are all basic primary/grade school arithmetic on simple whole numbers.
Where are all the secure hybrid RSA schemes?
I use RSA-OAEP for tiny messages and feel quite good about it. But that's not a general purpose tool. If I had to manually do all the steps to properly combine it with AES for block or streaming encryption, I'd be in danger.
libsodium is seriously ubiquitous and you only really have to worry about nonces.
https://www.hyperelliptic.org/tanja/vortraege/facthacks-29C3...
See the conclusion slides. In short, RSA is secure if primes are large and random.
It’s worth mentioning, Bernstein is the author of a competing algorithm. There are hundreds of scientific talks and articles about RSA by renowned cryptographers.
For example, the slides you linked don't mention padding or exponent weaknesses.
I don't think this is right. Researchers showed that 1%ish of keys they found on the internet are bad, not that 1% of traffic is susceptible.
From having studied this in a large enterprise setting more recently, there is in fact a really high prevalence of junk keys but much of it is concentrated in self signed certs and other garbage. Voip devices, printers, and management cards. Roca, internet of shit etc. The last big issue that hit the a high proportion of traffic was maybe the debian debacle from 2008.
Now, is this better or worse you decide, but it is a different claim.
The keys that do the vast bulk of traffic generally come from respectable implementations.
EdDSA is better, but is in general not yet supported in the WebPKI (browsers, BRs). I did manage to successfully use it for an internal mTLS setup though, so I think it's only going to be a matter of time.
(I have no idea why AWS won’t let you do this. I am pretty sure it just passes the SSH key to the VM and that it just writes it to authorized keys by default. But at least in the UI, it doesn’t seem to validate whereas RSA keys do...)
Please let me know if I am wrong (outside of a quantum computing breakthrough).
edit: I understand that p and q need to be large primes. But there are a gargantuan number of large primes. AFAIK, if 52 cards in a deck shuffled randomly outnumbers in possibilities than the number of atoms in the universe, than surely RSA beats that by many many orders of magnitude in terms of computational complexity even at 1024 key length?
- Lack of padding
- Padding oracles
- small public exponents
- badly chosen private exponents
- Badly randomized large primes
- Re-used large primesNo offense, but typical uni knowlege of these things is woefully underprepared for understanding security subtleties, and uni-level api design in my experience is not mature and skews towards power and flexibility instead of ease and safety.
Don't worry too much about quantum computers for now; worry about the attacks listed tfa, about the history of attacks being discovered, and the history of implementations being weak years after those attacks being discovered. And then consider that the NSA is the world's largest employer of mathematicians, who have each been toying with RSA since the very beginning of their career.
I find historical argument not very convincing. RSA have been around for a long time.
Will we be reading "do not use ECC" articles in 2039 after comparable amount of research will be put into finding subtle unexpected errors in ECC?
Whereas RSA is more thoroughly researched and various weaknesses revealed.
I don't know if that's true, I wrote a toy ECDSA implementation years ago (during highschool), and compared to RSA, ECC is certainly more complicated. Sure there are fewer parameters, and we currently know of fewer requirements for these parameters. But who is to say a weak class of ECC private keys won't be discovered in the future?
If you're paranoid about what weaknesses might be discovered, I suppose using RSA+ECC is a option :)
And, yes. Expect ECC to be broken. It was initially developed by Miller at the NSA, who only released that information when Koblitz discovered the cryptosystem independently. So they've been trying to crack it for a very long time, and you can be certain that they know of unpublished breaks. It's almost certain that they can break certain parameter classes, but the discrete log problem itself keeps getting weaker and weaker.
If moving away from weak crypto on a regular basis sounds like an undue burden, get out of the game, don't roll your own, leave it to the experts or you'll be doing yourself and your users a disservice.
I'm not a number theorist, but I did a lot of crypto and rubbed elbows with several NSA-employed cryptologists in my undergrad. I'm a decent developer, too, but I know far too much to think that I'm qualified to roll my own.
That Microsoft is in bed with NSA is common knowledge at this point, and that the libsodium authors choose to (keep being) associate(d) with them doesn't exactly fill me with confidence…
(yes, the actual risk of NSA messing with the repository without libsodium authors' knowledge is probably very low, but still, it doesn't give the best impression… )
If you have a degree in computer science and not in cryptography it is quite frankly unlikely that you learned more than the basics of RSA.
> It absolutely depends that p and q are chosen at random, but besides that, should be basically uncrackable.
No. There are many things that can go wrong even if you choose p and q adequately.
I find it singulary unsatisfying to hear in response, "Well, you know, the ones who got owned are too ashamed / too afraid of liability to come forward... [etc]"
Wouldn't p and q normally share around half their upper bits if chosen independently? I suspect the probability distribution would be centered around 0.5
> If p and q share approximately half of their upper bits
That, of the upper bits, are approximately half are the same? Since the combinations of two corresponding bits in p & q are 00, 01, 10, and 11, and, if they're chosen uniformly, one would expect about half to be the same.
I suspect that your interpretation is what the article wants to say, but I think that the parent's interpretation is reasonable given how it was written.
They _do_ suggest using ECC, but in practice ECC support is super sporadic, and a lot of products charge extra for it.
Whether its trying to save space by using smaller keys which is silly because the key size is rarely the bottleneck. Or trying to save time with clever prime genetation algorithms. The safest way to generate primes is also the easiest, just generate random numbers of appropriate size until you get one that is prime. Its not blazing fast but it's plenty usable.
Lots of security problems seem to stem from trying to be clever or optimize something that really doesn't need optimization.
But that would open up responsibility on the author's side, and who wants that? It's oh so much easier to just blast out a rant with some bits of information that are enough to illustrate your rant's point but far from sufficient to actually be helpful.
Don't be the (next) person who makes one single mistake and throws everything away.
Mind you, the post does not just say "dont't roll your own". It essentially says "don't use RSA no matter which implementation". And the argument for that is not very strong. It's an arbitrary selection of what could go wrong. In which libraries does it? Maybe for the major implementations this is all just cold coffee and they don't have those issues. But then I go and use one of them, and since the author just wrote a random rant, they pull the next trick out the sleeve and claim the next thing this implementation got wrong. It's easy to be in that position. It's harder to compile a complete list so that I can go and see that my framework does not violate any of those issues, so it can be trusted just as much as his favorite ECC framework. But yeah that would not just take work but would risk being criticized for being incomplete, so just easier to publish a rant instead.
Okay and what does an hour of their time cost?
Transition from RSA to ECC has an issue: unlike RSA where you increase the security by keeping the same algorithm but increasing the key length, in ECC there are a zoo of curves. You have heard that parameters in 25519 are secure, but then later you upgrade to another curve with dubious parameters. Each of these curves needs its own cryptanalysis. Now you have to deal with a lot of fragmented algorithms and complexity.
Also I kind of believe the difficulty of the factorization problem that has not been solved 2500 years more than the difficulty of the discrete log problem. There is no doubt more work on factorization, but that also indicates solving it gets increasingly difficult.
Most algorithms have limitations. Mentioning the limitations of one algorithm to promote another is not a proper comparison. What if the users pick up one of those NIST curves?
On this topic I think I'll go with Schneier and continue using RSA in general, and PGP in particular. Also Veracrypt is a good choice for an overall solution.
A lot of us don’t have /any/ track record in /both/ symmetric and asymmetric crypto.
Anything can be badly implemented. ECC can be badly implemented. Two specific, often repeated problems are not shared by ECC
Look at the table at the bottom of: https://safecurves.cr.yp.to/
Today, Curve25519 is a good choice because it's popular and checks all the boxes. But how many undiscovered columns are in this table?
My top level comment seems unpopular, so for what it's worth, I'll clarify that I definitely agree that there are fewer knobs for the non-cryptographer implementer to get wrong with ECC. But that's because the only way to implement an ECC system exactly as specified by the cryptographers. That's clearly an improvement over RSA, but I remain unconvinced that the cryptographers designing the curves are infallible. There are curves and curve parameters that, for various reasons, are bad.
Maybe there's a proof that it's impossible to do better than Curve25519, but if there is, I haven't seen it, and tptacek would rather be snarky than provide a reference. Is it impossible for more columns to show up in that safecurves table? If so, prove it. Otherwise, I think my top level suspicion is reasonable.
I was also proud that your CEO stood up against the Time AI bullshit at black hat. Someone had to do it.
But Christ, this article is ridiculous.
The article isn't about stop using RSA, the article is about stopping to roll your own crypto with RSA. I honestly don't see why anyone of us should write any crypto implementation: no matter how hard we try, I bet that without being a mathematician focused on crypto writing such an important algorithm will inevitably make it not secure.
* https://articles.59.ca/doku.php?id=pgpfan:rsabad
A generally relevant excerpt:
The writer ends with a discussion of alternatives to RSA. The writer says this:
> … the math behind ECC is so complicated that very few people feel confident enough to actually implement it. In other words, it intimidates people into using libraries built by cryptographers who know what they’re doing. RSA on the other hand is so simple that it can be (poorly) implemented in an hour.
In other words; the ECC encryption method is superior because it is significantly more complex than RSA. That is at the end of an article that talks about how hard RSA is to get right. This is not a compelling argument.
> The writer mostly talks about common implementation errors. PGP has been using RSA for a very long time now. There is no real chance that there are any of those errors in the PGP code.
The opening sections of the article are about how choosing the primes and exponents in RSA is fraught with error. PGP doesn't prescribe any particularly algorithm for these operations, so PGP implementations are potentially susceptible to these issues.
> The writer has a section on padding oracle attacks. Such attacks are not applicable to PGP simply because the encryption is only done once and there is no reverse channel.
Wow. Just wow. There is actually quite a few ways to get reverse channels out of email, some that don't even require social engineering. The most trivial one is the 1×1 tracking pixel that phones home, which is pretty common in email for tracking purposes.
Sorry, this is the kind of rebuttal that proves the actual point of cryptographers: designing cryptosystems is fraught with error, and amateurs are likely to fall into traps they didn't know about. PGP is already decently well-known as being a bad cryptosystem; it's basically a message format that wraps Enc(x) and Sign(x) for your given cryptographic algorithm, and we've spent the last several decades learning that these primitives are not secure by themselves and do not naïvely compose.
OpenPGP and implementations get a fair bit of academic scrutiny. The published PGP standard refers to RFC3447 which is PKCS #1 v2.1 for RSA. It is quite unlikely that there are any bonehead errors in any of the popular implementations.
>The most trivial one is the 1×1 tracking pixel that phones home, which is pretty common in email for tracking purposes.
I think it was clear from context that I did not mean that no reverse channels existing anywhere, only in a form suitable for oracle attacks. The HTML image thing is a straight up leak that has actually been used to exfiltrate decrypted plaintext.
>PGP is already decently well-known as being a bad cryptosystem...
That isn't really true. It is actually one of the solidest cryptographic protocols ever.
>...do not naïvely compose.
What does that mean?
—- KEEP USING RSA!
This article is misleading to make it appear that RSA is not secure, but only the only evidence presented is improper implementation.
Properly implemented RSA has been proven secure and unbreakable by the NSA with case studies such as Snowden, Lavabit, dark markets, and ECC is much harder to properly implement than RSA.
The NSA has been pushing ECC because their quantum chips can break it easily. D-Wave, Google, Alibaba, and others already have quantum chips. The disinformation agents claim that “quantum computers don’t exist” which is true because nobody uses a computer to break crypto, they use specialized custom chips.
All ECC (X25519-P521) will be broken by private sector quantum chips before RSA-2048 due to the physical limitations of stabilizing qubits.
The people making false claims against RSA are either being paid or they are useful idiots.
We're orders of magnitudes out (qubit-wise, on real quantum computers) from breaking RSA or ECC in practice, and the difficulty level is on the same order for both.
Yes, (real) Quantum computers can break ECC and RSA encryption. I have no idea why they think the NSA (and apparently Google as well) has secret Quantum Computers that are capable of breaking ECC, but not RSA.
https://arxiv.org/pdf/quant-ph/0301141.pdf
My incredulity is in the idea that Google and the NSA apparently have 1000 qubit machines that can do that, but not 2000 qubit ones (and you should be very confident that will remain the case in future).
Note that once you're at the "I have a stable 1000 qubit machine that can perform complex calculations" realm, you can consider doing things like entangling it with that other 1000 qubit machine you have lying around, bringing yourself rapidly into the 2000 qubit realm. Getting to the first part is really hard. If you can pull that off, you're probably only a few years away from the second. The main thing that's stopping us from doing that today is that the (physcial) qubits we've made so far aren't stable enough; getting to a single logical qubit is anticipated to take 1000 physical ones.
Google and NSA can produce more of the same thing. But they probably have no major secret sauce for things such as error correction that the public does not have.
ECC eschews all that complexity. Writing a safe ECC implementation especially for Edwards or Montgomery curves is pretty simple.
PGP is mortebund and has a lot of cruft.
RSA does some things that are really cool like accumulators, Pallier, etc. But if you are doing them you are doing black magic.