7 ms·

Seriously, stop using RSA: comments

74 points by upofadown 5y ago

mc4ndr3 5y ago
Simplicity in algorithm affords more capacity for studying implementation. Bugs are easier to find, even through very simple, automated fuzzing procedures, let alone formal verification. Bugs scale in frequency according to total source line count. Don't expect professionals to write perfect code, especially as complexity grows. Simplicity of algorithm is critical for peer review of the implementation, as the pool of reviewers is incredibly small. It's one thing to prefer community vetted implementations, but the implementation cannot be blindly trusted by everyone--that would be involve the logical fallacy of an appeal to authority.
- throwaway81523 5y ago
  We're not talking about code bugs per se (program computes something different from what you intended). It's more like mathematical errors: you correctly compute what you intended to, but that turns out to be insecure for subtle reasons. Padding oracle attacks are an example that the article spent some time on.
- tedunangst 5y ago
  20 years of RSA vulnerabilities and all they needed to do is fuzz it first!
- afiori 5y ago
  As the saying goes: simple and easy are very different.
oh_my_goodness 5y ago
Either most of this is not really a response to the article, or I'm really misunderstanding something here. (The article may be good or bad, I don't know.)
- cowsandmilk 5y ago
  ?? Half this blog post is quotes of the original article and the other half are direct responses to the quoted sections.
  - deleted 5y ago
    [deleted]
jchw 5y ago
I’m a bit miffed after just a couple paragraphs. My reading of the original article was that the issue of people feeling tempted to implement RSA was just exacerbating the problem of how difficult it is to implement RSA securely. I am not a cryptographer. I’d be rather cautious about implementing my own cryptography at all, less with my own code implementing the primitives. That said, Trail of Bits makes a compelling argument, that, in my reading, RSA is harder to get right in subtle ways, whereas ECC is just hard to grok period. A bad RSA implementation leads to weak cryptography, but a bad ECC implementation often leads to something that doesn’t work at all. This, alongside other benefits of ECC like smaller key sizes for similar cryptographic security, faster and simpler key generation, more idiot-tolerant properties, etc. makes ECC an obvious choice even disregarding if you can implement RSA. It’s just that people like to choose RSA because they feel like they understand it, but the truth is they only understand the surface-level basics. (To be fair, me too. Though I feel I also can grok some surface-level basics of some ECC-based algorithms, too.) Feel free to flame me for not reading the article entirely; I definitely earned it. But that opener made me not want to, sorry.
- throwaway81523 5y ago
  ECC is also easy to mess up, especially the NIST curves. Plenty of subtle stuff to get wrong.
  - deleted 5y ago
    [deleted]
  - tptacek 5y ago
    Curve25519 is significantly harder to mess up than RSA. You can go either way on the NIST curves vs. RSA, but at an architectural level there's simply less that goes around with the model of ECC than with RSA, which directly exposes an easy-to-use (and treacherously easy to fuck up) encryption transform. I wouldn't implement with the NIST curves at all, but if you asked me to pick between them and RSA, I'd still take P-256 over RSA.
  - jchw 5y ago
    That was acknowledged and accounted for in the original article. But given that we have curves that we believe are safe, I’m not sure this is an issue, at least any more so than relying on known-good ranges for parameters in any cryptosystem…
dang 5y ago
Recent and related: Seriously, Stop Using RSA (2019) - https://news.ycombinator.com/item?id=30879442 https://news.ycombinator.com/item?id=30879442 - April 2022 (101 comments)
tptacek 5y ago
The author of this article has misunderstood the piece it's responding to, and doesn't appear to be familiar with the literature. For instance, this response is dubious about the security implications of primality testing bugs, claiming that Prime & Prejudice --- famously relevant to RSA --- had no apparent connection to it (presumably they read the abstract and not the study itself, which repeatedly mentions RSA). It just goes on like this. This is part of a pattern with this author. They're extremely attached to PGP. PGP uses RSA. Therefore: RSA must be fine. Recurrence of the same pattern: PGP doesn't use authenticated encryption. Therefore, authenticated encryption must not be important, or maybe it's even a negative. There's another example somewhere in the comments here about forward secrecy being overrated. (I can cite, but you should just take my word for it that these takes have been shared here). It's frustrating, because the pattern isn't super clear in isolation (though this response actually mentions PGP as the impetus for the response) and, if you don't work in the field, it might not be clear how far these takes stray from cryptographic engineering orthodoxy. It's also frustrating because in general, we're not supposed to write things like this on HN --- a list of floridly bad previous comments from this author would be way over the line --- so one has to sort of tiptoe around the edges of the guidelines to find a way to describe what's going on here. Anyways, caveat lector. Hats off for describing Boneh's fault attack paper as "completely theoretical", though! Bold!
- throwaway81523 5y ago
  Yeah I think you are right, the article is weak. Even the first implementation advice it gives doesn't look right to me, if interpreted the obvious way: > Normally for RSA you pick 2 random numbers and then find a prime close to each. I.e. if you pick a number and then search upwaard til you find a prime, that gives a non-uniform distribution on the primes in that range. You instead want to pick a random number, and if it's composite, throw it away and pick another random number til you get a prime. Then repeat to get second prime.
  - kwantam 5y ago
    "Pick a random odd number and keep adding 2 until you find a prime" is, perhaps unintuitively, essentially fine for RSA key generation---under mild conditions, the security loss is single-digit bits at best. See Abboud and Prest, "Cryptographic Divergences: New Techniques and New Applications", SCN 2020 [1], Section 4.1. (This is a relatively recent result. And as I mentioned in my other comment, this is not a defense of the article!) [1] https://eprint.iacr.org/2020/815 https://eprint.iacr.org/2020/815
eternityforest 5y ago
What kind of maniac would implement a crypto algorithm in production themselves, unless their last name is something like Schnier or Bernstein?
- throwaway81523 5y ago
  I've done it and feel ok about it. Others here have done it and done a good job. But yeah, there are different levels you can work at, you always have to be careful, and you have to know some theory in order to be able to even think clearly about the topic. I found Bellare and Rogaway's old lecture notes[0] demystified the subject for me a lot. There are some actual textbooks now that are more up to date and complete, though I don't happen to know of titles offhand. For ECC with NIST curves, Menezes, Vanstone, et al have a book that gives very explicit step by step implementation instructions. [0] https://web.cs.ucdavis.edu/~rogaway/classes/227/spring05/book/main.pdf https://web.cs.ucdavis.edu/~rogaway/classes/227/spring05/boo...
  - eternityforest 5y ago
    Any particular reason you'd ever do this? Obviously it kinda makes sense as a hobby project never used for something important... but in production?
    - throwaway81523 5y ago
      I don't understand the question. Code has to come from somewhere, and there's not always a pre-written library you can use. That's what keeps programmers employed. Crypto primitives are actually not that dangerous to implement, since there will usually be test vectors and/or other implementations you can check against. You get in trouble if you try to develop your own protocols, make mistakes with parameter selection, and that sort of thing. Added: Here is some code that needs to be written, if it hasn't been already: * TLS stack written in Rust, so we don't have to keep using the legacy OpenSSL stack. Or similarly, in Ada. * SSH stack, same same. * High speed primitives in RISC-V assembly language, in multiple versions optimized for different architecture implementations * Lots of weird special primitives used in things like old fashioned payment protocols. I dealt with this somewhat when working on POS terminals. * Hardware implementations in VHDL and Verilog * Etc. I'd feel comfortable working on the first two of the above. Someone has to do it, and we can't always get DJB to do everything, so that leaves people like us.
klabb3 5y ago
One reason I like ECC (Curve25519 in particular) is speed and size of generated keys and signatures. It is a lot easier to compose crypto with business logic when you can basically assume instantaneous key gen (RSA takes a non-deterministic amount of ~seconds) as well as 32-byte signatures that are practical even for short messages (as opposed to 256-512 bytes).
oneplane 5y ago
Should both articles have been about implementing RSA rather than using it?
upofadown 5y ago
I guess this could use a bit of context (author here). This is part of a series of PGP advocacy articles [1]. There was a post of "Seriously, stop using RSA" on here yesterday that prompted me to look at my article again. A better article was possible so I rewrote it and posted it. So, yes, this is very focused and partisan by design. There is a larger discussion about RSA that I chose to ignore. [1] https://articles.59.ca/doku.php?id=pgpfan:index https://articles.59.ca/doku.php?id=pgpfan:index

74 points by upofadown 5y ago

Simplicity in algorithm affords more capacity for studying implementation. Bugs are easier to find, even through very simple, automated fuzzing procedures, let alone formal verification. Bugs scale in frequency according to total source line count. Don't expect professionals to write perfect code, especially as complexity grows. Simplicity of algorithm is critical for peer review of the implementation, as the pool of reviewers is incredibly small. It's one thing to prefer community vetted implementations, but the implementation cannot be blindly trusted by everyone--that would be involve the logical fallacy of an appeal to authority.

throwaway81523 5y ago
We're not talking about code bugs per se (program computes something different from what you intended). It's more like mathematical errors: you correctly compute what you intended to, but that turns out to be insecure for subtle reasons. Padding oracle attacks are an example that the article spent some time on.
tedunangst 5y ago
20 years of RSA vulnerabilities and all they needed to do is fuzz it first!
afiori 5y ago
As the saying goes: simple and easy are very different.

oh_my_goodness 5y ago

Either most of this is not really a response to the article, or I'm really misunderstanding something here. (The article may be good or bad, I don't know.)

cowsandmilk 5y ago
?? Half this blog post is quotes of the original article and the other half are direct responses to the quoted sections.
- deleted 5y ago
  [deleted]

jchw 5y ago

I’m a bit miffed after just a couple paragraphs. My reading of the original article was that the issue of people feeling tempted to implement RSA was just exacerbating the problem of how difficult it is to implement RSA securely. I am not a cryptographer. I’d be rather cautious about implementing my own cryptography at all, less with my own code implementing the primitives. That said, Trail of Bits makes a compelling argument, that, in my reading, RSA is harder to get right in subtle ways, whereas ECC is just hard to grok period. A bad RSA implementation leads to weak cryptography, but a bad ECC implementation often leads to something that doesn’t work at all. This, alongside other benefits of ECC like smaller key sizes for similar cryptographic security, faster and simpler key generation, more idiot-tolerant properties, etc. makes ECC an obvious choice even disregarding if you can implement RSA. It’s just that people like to choose RSA because they feel like they understand it, but the truth is they only understand the surface-level basics. (To be fair, me too. Though I feel I also can grok some surface-level basics of some ECC-based algorithms, too.) Feel free to flame me for not reading the article entirely; I definitely earned it. But that opener made me not want to, sorry.

throwaway81523 5y ago
ECC is also easy to mess up, especially the NIST curves. Plenty of subtle stuff to get wrong.
- deleted 5y ago
  [deleted]
- tptacek 5y ago
  Curve25519 is significantly harder to mess up than RSA. You can go either way on the NIST curves vs. RSA, but at an architectural level there's simply less that goes around with the model of ECC than with RSA, which directly exposes an easy-to-use (and treacherously easy to fuck up) encryption transform. I wouldn't implement with the NIST curves at all, but if you asked me to pick between them and RSA, I'd still take P-256 over RSA.
- jchw 5y ago
  That was acknowledged and accounted for in the original article. But given that we have curves that we believe are safe, I’m not sure this is an issue, at least any more so than relying on known-good ranges for parameters in any cryptosystem…

dang 5y ago

Recent and related: Seriously, Stop Using RSA (2019) - https://news.ycombinator.com/item?id=30879442 https://news.ycombinator.com/item?id=30879442 - April 2022 (101 comments)

tptacek 5y ago

The author of this article has misunderstood the piece it's responding to, and doesn't appear to be familiar with the literature. For instance, this response is dubious about the security implications of primality testing bugs, claiming that Prime & Prejudice --- famously relevant to RSA --- had no apparent connection to it (presumably they read the abstract and not the study itself, which repeatedly mentions RSA). It just goes on like this. This is part of a pattern with this author. They're extremely attached to PGP. PGP uses RSA. Therefore: RSA must be fine. Recurrence of the same pattern: PGP doesn't use authenticated encryption. Therefore, authenticated encryption must not be important, or maybe it's even a negative. There's another example somewhere in the comments here about forward secrecy being overrated. (I can cite, but you should just take my word for it that these takes have been shared here). It's frustrating, because the pattern isn't super clear in isolation (though this response actually mentions PGP as the impetus for the response) and, if you don't work in the field, it might not be clear how far these takes stray from cryptographic engineering orthodoxy. It's also frustrating because in general, we're not supposed to write things like this on HN --- a list of floridly bad previous comments from this author would be way over the line --- so one has to sort of tiptoe around the edges of the guidelines to find a way to describe what's going on here. Anyways, caveat lector. Hats off for describing Boneh's fault attack paper as "completely theoretical", though! Bold!

throwaway81523 5y ago
Yeah I think you are right, the article is weak. Even the first implementation advice it gives doesn't look right to me, if interpreted the obvious way: > Normally for RSA you pick 2 random numbers and then find a prime close to each. I.e. if you pick a number and then search upwaard til you find a prime, that gives a non-uniform distribution on the primes in that range. You instead want to pick a random number, and if it's composite, throw it away and pick another random number til you get a prime. Then repeat to get second prime.
- kwantam 5y ago
  "Pick a random odd number and keep adding 2 until you find a prime" is, perhaps unintuitively, essentially fine for RSA key generation---under mild conditions, the security loss is single-digit bits at best. See Abboud and Prest, "Cryptographic Divergences: New Techniques and New Applications", SCN 2020 [1], Section 4.1. (This is a relatively recent result. And as I mentioned in my other comment, this is not a defense of the article!) [1] https://eprint.iacr.org/2020/815 https://eprint.iacr.org/2020/815

eternityforest 5y ago

What kind of maniac would implement a crypto algorithm in production themselves, unless their last name is something like Schnier or Bernstein?

throwaway81523 5y ago
I've done it and feel ok about it. Others here have done it and done a good job. But yeah, there are different levels you can work at, you always have to be careful, and you have to know some theory in order to be able to even think clearly about the topic. I found Bellare and Rogaway's old lecture notes[0] demystified the subject for me a lot. There are some actual textbooks now that are more up to date and complete, though I don't happen to know of titles offhand. For ECC with NIST curves, Menezes, Vanstone, et al have a book that gives very explicit step by step implementation instructions. [0] https://web.cs.ucdavis.edu/~rogaway/classes/227/spring05/book/main.pdf https://web.cs.ucdavis.edu/~rogaway/classes/227/spring05/boo...
- eternityforest 5y ago
  Any particular reason you'd ever do this? Obviously it kinda makes sense as a hobby project never used for something important... but in production?
  - throwaway81523 5y ago
    I don't understand the question. Code has to come from somewhere, and there's not always a pre-written library you can use. That's what keeps programmers employed. Crypto primitives are actually not that dangerous to implement, since there will usually be test vectors and/or other implementations you can check against. You get in trouble if you try to develop your own protocols, make mistakes with parameter selection, and that sort of thing. Added: Here is some code that needs to be written, if it hasn't been already: * TLS stack written in Rust, so we don't have to keep using the legacy OpenSSL stack. Or similarly, in Ada. * SSH stack, same same. * High speed primitives in RISC-V assembly language, in multiple versions optimized for different architecture implementations * Lots of weird special primitives used in things like old fashioned payment protocols. I dealt with this somewhat when working on POS terminals. * Hardware implementations in VHDL and Verilog * Etc. I'd feel comfortable working on the first two of the above. Someone has to do it, and we can't always get DJB to do everything, so that leaves people like us.

klabb3 5y ago

One reason I like ECC (Curve25519 in particular) is speed and size of generated keys and signatures. It is a lot easier to compose crypto with business logic when you can basically assume instantaneous key gen (RSA takes a non-deterministic amount of ~seconds) as well as 32-byte signatures that are practical even for short messages (as opposed to 256-512 bytes).

oneplane 5y ago

Should both articles have been about implementing RSA rather than using it?

upofadown 5y ago

I guess this could use a bit of context (author here). This is part of a series of PGP advocacy articles [1]. There was a post of "Seriously, stop using RSA" on here yesterday that prompted me to look at my article again. A better article was possible so I rewrote it and posted it. So, yes, this is very focused and partisan by design. There is a larger discussion about RSA that I chose to ignore. [1] https://articles.59.ca/doku.php?id=pgpfan:index https://articles.59.ca/doku.php?id=pgpfan:index