12 ms·
Stop using RSA (2019)
- arunc 6y agoFWIW, none of the major cloud providers support ed25519. It's 2020 and no one seems to care about it.
- MrRadar 6y agoFor TLS certificates? That's because none of the CAs support it.
- saagarjha 6y agoFor SSH, I’d guess.
- zinekeller 6y agoYes, for managed systems (meaning not a SSH inside a VPS), at least I'm sure that both AWS and Azure does not support other standards (no experience on GCP).
- ktta 6y agoFor TLS certs, you can just use ECDSA. Let's Encrypt has a ECDSA root.
- regecks 6y agoECDSA has some bad footguns as well. I don't see why you'd consider ECDSA to be any more robust than RSA if we're talking about certificates keys for TLS. 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.
- floatingatoll 6y agoThe point isn't "good crypto must not have footguns", it's "RSA has so many footguns, that we as a community should stop silently accepting uses of it".
- deleted 6y ago[deleted]
- pitaj 6y agoGithub suggests it in their docs[1] which I can confirm works as I just added one today. A coworker added my ed25519 key to a DigitalOcean server today as well, and I successfully ssh-ed in with no issue.
- globular-toast 6y agoGitlab has not only allowed it but recommended it for several years now iirc. I'm now in the habit of generating ed25519 keys for all of my ssh hosts.
- jchw 6y agoAWS won’t let me add an ED25519 SSH key, but Google Cloud Platform does and it seems to work. YMMV. (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...)
- silverwind 6y agoStop using them. SSH-RSA is deprecated in OpenSSH since a few versions now.
- deathanatos 6y agoWhat is deprecated in OpenSSH is not all of RSA in OpenSSH. They've deprecated "ssh-rsa", but there is still e.g., rsa-sha2-256. These describe the algorithms used in key exchange; ssh-rsa uses SHA-1. This is separate from the types of public/private keys, which is what parent is describing.
- Const-me 6y agoThat particular curve is less popular. Do they support NIST P-521?
- mcstafford 6y agoThe section entitled "So what should you use instead?" doesn't make a suggestion of what to use instead...
- timothy-quinn 6y agoThis is how most critical articles of crypto end. They criticise the algorithm or system, and then don't offer much in the way of solutions. They _do_ suggest using ECC, but in practice ECC support is super sporadic, and a lot of products charge extra for it.
- mundo 6y ago> Trail of Bits recommends using Curve25519 for key exchange and digital signatures... it is implemented in libsodium, which has easy-to-read documentation and is available for most languages.
- deleted 6y ago[deleted]
- TwoBit 6y agoDoesn't it say so in the last paragraph of that section?
- tptacek 6y agoYou use ECDH to establish keys for sessions or files. You use ECDSA and ECC-Schnorr stuff like Ed25519 to sign things. That covers 99.9% of what RSA is used for. HTH.
- ohazi 6y agoI bet there are a similar number of pitfalls with ECC, but (depending on the specific weakness) we just have a ~50-2000 year head start with RSA because prime numbers have been studied for far longer.
- ggm 6y agoHe explicitly said it doesn't suffer from identical problems, notably not having padding requirements and not having to select primes: users select random keys instead. Anything can be badly implemented. ECC can be badly implemented. Two specific, often repeated problems are not shared by ECC
- ohazi 6y agoYou, me, or djb still have to select a curve -- that's where I expect the pitfalls will be.
- ggm 6y agoLibsodium. Djb or his equivalent did that already and if there is a timing attack, it will get found and fixed faster.
- ohazi 6y agoI'm not referring to implementation bugs, I'm referring to choice of curve, which can't be changed after the fact. Look at the table at the bottom of: https://safecurves.cr.yp.to/ 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.
- phildenhoff 6y agoI would _love_ to abandon RSA, but Azure DevOps requires my SSH keys are RSA and no matter of fiddling with my public key on input seems to change that. At my home, and on our infrastructure, I only use ECDSA, but when providers _require_ RSA it's hard to stop using it.
- tptacek 6y agoI'm repeating myself but just to chime in on the most common pushback this sentiment ("no more RSA!") gets: nobody is telling you to switch providers so you can do ECC SSH. The gist of the argument is not to introduce RSA into new designs --- which is a thing you see people do a lot if you review cryptography implementations, and it's often a clownfire, moreso than NaCL ECC designs.
- lta 6y agoAzure has a nack to make everything annoying and/or dysfunctional
- drivebycomment 6y agoI don't like this article. 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.
- olliej 6y agoBut the thing is that it isn't. 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.
- regecks 6y agoI initially disliked the article as well, but I think it makes a fair point about misuse-resistant libraries. Or as you put it, "correct vetted tools". 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.
- vmception 6y ago> 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. Okay and what does an hour of their time cost?
- daeken 6y agoBased on what I billed out at at comparable shops, anywhere from $250-400/hr. Maybe $500 if one of their more crypto-focused people looks at it, but that'd be pretty unlikely for a whole codebase.
- tptacek 6y ago$2000/day is what you'd pay for a web application for an appsec shop. Double that for cryptography from a focussed cryptography practice, and add 50-75% on top if you're getting reviews by PhDs at Rambus, like Intel does for new designs.
- iJohnDoe 6y agoI think the last comment on the article is the most important for discussion. —- 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.
- daeken 6y agoWut. This is just false. D-Wave provides the "quantum computers" that others have and they're completely irrelevant when it comes to breaking ECC (or RSA, for that matter; ECC is broken by a variant of Shor's algorithm, which is used to break RSA). They're quantum annealing chips, not general-purpose quantum computers; they literally can't run Shor's algorithm, now or ever. 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.
- duskwuff 6y agoI'm not convinced that D-Wave's hardware is relevant to anything beyond D-Wave's profits. It's neat that their technology works, I guess, but it isn't clear at this point that it does anything better than a classical computer could.
- archgoon 6y agoThat comment goes off the rails once it starts talking about quantum computers breaking encryption (and only ECC, not RSA). 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.
- unnouinceput 6y agoNice try NSA. 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.
- tptacek 6y agoSchneier is wrong. Notably: this is not a subject Schneier has particular expertise in. There's a layperson belief that "cryptography" is a single domain, but it is subspecialized. You might take Schneier seriously for block cipher cryptography (though that field has moved far past the last serious engineering writing Schneier did about it), but I don't think it was ever the case that Schneier was someone you'd take to the bank for asymmetric cryptography.
- aborsy 6y agoSchneier has thousands of citations to his peer-reviewed scientific articles. He has authored a number of books in cryptography, and has thought cryptography in major places. He has been involved in the creation of many cryptographic algorithms. His contributions have been mostly in the area of symmetric crypto, but that doesn’t imply that he doesn’t understands well asymmetric crypto, especially the RSA. He teaches this stuff. A lot of us don’t have /any/ track record in /both/ symmetric and asymmetric crypto.
- ignoranceprior 6y agoThis seems to work better as an argument against rolling your own crypto than an argument against RSA in particular.
- FartyMcFarter 6y agoI think it does both - rolling your own crypto is almost always a bad idea, but some crypto is harder to implement well than other.
- SheinhardtWigCo 6y agoThis post ignores the fact that most users of RSA do not have to worry about these low-level implementation issues because they are using mature and well-vetted implementations. 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.
- nmadden 6y agoThe point of the article is that mature and well-vetted libraries have repeatedly been shown to have vulnerabilities in their RSA implementations. See [1] for just one recent example, but there have been many. [1]: https://www.cryptologie.net/article/461/the-9-lives-of-bleichenbachers-cat-new-cache-attacks-on-tls-implementations/ https://www.cryptologie.net/article/461/the-9-lives-of-bleic...
- forgotmypw17 6y agoSo the solution to a proven algo plus mature implementation with some issues is to... switch to a green algo with a green implementation?
- nmadden 6y agoSwitch to other proven and mature algorithms eg libsodium, Tink, etc. RSA has not been the only game in town for a long time.
- lmns 6y agoThe point is that the alternatives aren't "green" and their implementations are mature, arguably even better understood than RSA and its implementations.
- mattalex 6y agoThere are many other algorithms that are just as proven but don't feature many of the traps contained in RSA. The main issue with RSA is that depending on implementation and context-sensitive parameter selection (i.e. you actually have to think about them and can't just always use the same) you get wildly different results. Other algorithms, like ECC, also have parameters, but they aren't context-sensitive, so always choosing the same one is fine for developers and only security researchers have to think of new and better parameters. The Question really is how brittle do you expect/accept your encryption algorithm to be: RSA is very brittle in very unexpected ways, while e.g. ECC is only brittle if you choose a bad curve (but you can simply always select the same safe one) and people also know that.
- kobayashimaru 6y agoSecurity with keys mate......
- admax88q 6y agoA lot of the implementation challenges with RSA tend to stem from trying to he clever and prematurely optimize. 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.
- deleted 6y ago[deleted]
- MaximumYComb 6y ago>Moreover, p and q must be chosen independently. If p and q share approximately half of their upper bits, then N can be factored using Fermat’s method. 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
- NullPrefix 6y agoWhy would they? Given two random numbers with a size of n, the probability that upper halves (size of upper half is n/2) are the same is 1/(1+n/2).
- deathanatos 6y agoThat's not how the parent is interpreting that statement; their interpretation of, > 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.
- brianberns 6y agoThis is a good point. Perhaps they meant to say "if approximately the upper half of p and q's bits are identical"?
- MaximumYComb 6y agoThat might make more sense. If you have two integers in the same approximate range you might expect the upper halves to look similar.
- y7r4m 6y agoBack in university I learned the in and outs of RSA, and to be honest, it seemed simple, understandable, and frankly, quite solid. It absolutely depends that p and q are chosen at random, but besides that, should be basically uncrackable. 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?
- deleted 6y ago[deleted]
- benlivengood 6y agoThe article does list several real-world attacks on: - Lack of padding - Padding oracles - small public exponents - badly chosen private exponents - Badly randomized large primes - Re-used large primes
- nmadden 6y agoSee for example Dan Boneh’s “20 years of attacks on the RSA cryptosystem” [1]. Itself now written 20 years ago and the attacks keep coming. [1]: http://www.ams.org/notices/199902/boneh.pdf http://www.ams.org/notices/199902/boneh.pdf
- kebman 6y agotl;dr: "The attacks discovered so far mainly illustrate the pitfalls to be avoided when implementing RSA. At the moment it appears that proper implementations can be trusted to provide security in the digital world." (My own emphasis.)
- nmadden 6y agoWe’re still waiting to find one of those proper implementations 20 years later.
- dang 6y agoDiscussed at the time: https://news.ycombinator.com/item?id=20381779 https://news.ycombinator.com/item?id=20381779
- LeCow 6y agoTrail of Bits, I love your content and love your tools. 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.
- denysvitali 6y agoProbably what's wrong about this article is the title and the introduction. 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.
- redis_mlc 6y ago> cloud providers blah blah blah dumb HN comments blah blah blah If you don't understand the article (ie. you're the typical sysadmin or blub HN programmer), let me explain it to you. The author is saying don't write your own RSA routines because it's hard to get right. IOW, the same advice everybody has been told for decades. He is not saying that ssh and rsa is bad, though the ssh maintainers should of course check their code since millions of people use it. FYI: it's generally considered that SSL/TLS in practice has been broken by the US govt. due to setup problems per the article, and reuse of magic constants. Source: I actually studied the mathematics behind RSA, and also actually read and understand the full articles on crypto problems, since the 80's.
- edem 6y agoThis article reeks of arrogance. I stopped reading it after a while since I can't stand the style of the writer. They seem to think that they've seen it all and this is a huge red flag to me.
- aborsy 6y agoRSA itself is secure, if your primes are large and random. You should use a decent library like OpenSSH etc. 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?
- ganafagol 6y agoA more useful contribution than this rant would have been a structured guide for how to do RSA without any of those issues. If they are all so well known, then, well, write down exactly how to do it properly and make a list of all attack classes together with a convincing argument why your guideline prevents them. 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.
- FartyMcFarter 6y agoWhen it comes to security software, that doesn't work. There are so many ways to get things wrong, it's better to just use a well maintained existing library. Don't be the (next) person who makes one single mistake and throws everything away.
- ganafagol 6y agoSure, I totally agree. But that was not my point. I was trying to convey that it's always easier to rant than to actually contribute to improving things. 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.
- aborsy 6y agoHere is what Bernstein has to say about RSA https://www.hyperelliptic.org/tanja/vortraege/facthacks-29C3.pdf 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.
- FartyMcFarter 6y agoI'm not a crypto expert, but these slides mostly focus on "factoring" attacks, and don't cover other kinds of attacks mentioned in the submission link. For example, the slides you linked don't mention padding or exponent weaknesses.
- based2 6y agohttp://math.uni.lu/eml/projects/reports/prime-distribution.pdf http://math.uni.lu/eml/projects/reports/prime-distribution.p...
- ezekiel68 6y agoThis is not my realm and I am grateful for experts who can advise us well. But I have a nagging yet sincere quibble that isn't easily dismissed: Where are all the failure stories? Does "under attack" mean "successfully defeated"? 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]"
- 9ijdPuvp 6y ago"research has shown that roughly 1% of TLS traffic in 2012 was susceptible". 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.
- upofadown 6y agoSince this article comes up from time to time in a PGP context I generated a PGP FAN article discussing it: * https://articles.59.ca/doku.php?id=pgpfan:rsabad 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.
- jcranmer 6y agoWow, what a compelling rebuttal of the original article this is! </sarcasm> > 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.
- upofadown 6y ago>...PGP doesn't prescribe any particularly algorithm for these operations, so PGP implementations are potentially susceptible to these issues. 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?
- deleted 6y ago[deleted]