7 ms·

Bernstein on a "thought experiment", analyzing how government could have deliberately weakened cryptographic standards through various means. It's actually quit

by jvehent 12y ago

Bernstein on a "thought experiment", analyzing how government could have deliberately weakened cryptographic standards through various means. It's actually quite compelling, given that we know DES key size was weakened by the NSA back in the 70s, against IBM's will, and that we know Dual_EC_DRBG was backdoored also by the NSA a few years ago. Bernstein's main point is that we need independent, peer-reviewed, cryptography that doesn't depend on government standardization. This talk is mostly a justification for his own work on ChaCha20/Poly1305 and DNSCurve, that were designed to be fast, constant-time and padding resistant. But the talk doesn't make mention of alternatives, except for Serpent that should have been a better cipher than Rijndael in the AES competition. A good read. I would love to see broader adoption of ChaCha20 in OpenSSL and its standardization in TLS1.3. Google already supports it and it needs more attention from cryptographic before we start using it everywhere. It also seems that SHA-3 has failed to convince, and everyone is standardizing on SHA-2 instead, despite the computational cost. Maybe here too we need an alternative...

higherpurpose 12y ago
I would also like to see Curve25519 (as well as others) supported in all browsers. It really bothers me that while at least websites are making an effort to default to ECDHE encryption with PFS, they have to resort to using the low-performance, insecure and probably NSA-backdoored P-256 curve, because most browsers aren't supporting anything else right now.
- sarciszewski 12y ago
  I agree. Through PECL, PHP is soon going to have curve25519 support http://pecl.php.net/package/libsodium http://pecl.php.net/package/libsodium There's already a Node-Sodium package... https://github.com/paixaop/node-sodium https://github.com/paixaop/node-sodium Why can't browsers support it natively? (e.g. through NSS)
- jvehent 12y ago
  If anyone has the time and skills to implement these curves in NSS, I'm sure that the Firefox and Chrome security teams would be more than happy to enable them!
  - sarciszewski 12y ago
    https://bugzilla.mozilla.org/show_bug.cgi?id=957105 https://bugzilla.mozilla.org/show_bug.cgi?id=957105 Looks like there's already a bug in Mozilla's tracker.
  - tptacek 12y ago
    Very smart crypto implementors are already working on this codebase, aren't they?
    - jvehent 12y ago
      Not being one of them myself, I can only notice that their time is limited, and many much wanted improvements sit on the backburner waiting for a smart crypto implementor to work on them. NSS and OpenSSL are difficult codebases to work with, which may also explain why it's so hard to find people to work on them.
  - higherpurpose 12y ago
    I'm not as worried about Chrome/Mozilla as I am about IE and Safari (including the mobile one).
  - hsivonen 12y ago
    Why do you expect Firefox and Chrome to take patches as opposed to saying that patches should wait for specs from the TLS WG which waits for the CFRG to bless something? The political problem is that unless there's an authority whose blessing can be appealed to to justify inclusion, how do you decline curves from Microsoft Research and so-called NUMS curves? (Of course, it's not like the CFRG is a politically spoyless authority...)
- tptacek 12y ago
  You could cite sources on "probably NSA-backdoored" P-256, but they'd all boil down to "you can with some effort devise a scenario in which it would have been possible for NSA to influence the curve selection". You'd be in a very similar rhetorical position to the "controlled demolition" conspiracy theorists. We should, of course, demand rigid curves, and very few of the mainstream curves are rigid. But there's a difference between that and the assertion that P-256 is "probably backdoored"; for one thing, the latter assertion encourages people to adopt RSA, which is more fraught than ECC. That RSA vs. ECC issue is even worse in browsers, which I think makes your sentiment even less useful. In ground-up implementations, you can get some comfort from OAEP/PSS for RSA. No such help in TLS, where RSA still uses (terribly broken) PKCS1v15.
  - mentat 12y ago
    My understanding of the issues with P-256 is that it's very easy for mistakes in the ECC implementation around certain points to leak information whereas with other curves it is not. Not quite "backdoored" but certainly not optimal in terms of security. Edit: based on http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4...
    - tptacek 12y ago
      It's true that P-256 is more susceptible to implementation flaws than other curves, because P-256 wasn't designed to be misuse-resistant, unlike recent curves where that was a design goal. It's unlikely that any credible new protocol is going to adopt a NIST curve. They exist only for legacy support now. BULLRUN killed them. Fortunately, in this case I think hysteria actually served a good purpose. I do not think highly of crypto standards, and these ones in particular were dragging the industry down.
  - MichaelGG 12y ago
    I'm going to display lots of ignorance in the hope you'll correct me. I thought these "possibly backdoored" curves needed a seed, and the creators provided a "provably random" one by hashing... a random number they provided. That alone is so silly and I'm not sure how anyone could take it seriously. But then, after that, it was discovered all those "provably random" seeds had a 1-in-a-million weakness. While this weakness alone doesn't comprise everything, it's an indicator that someone intentionally found those seeds so it might indicate something more. Is my poor understanding terribly wrong?
fpgaminer 12y ago
Could I give a mention to Threefish as well? It's in the same vein as ChaCha20, but it's a block cipher, based on modern ideas, is more capable than AES, and naive implementations are resistant to power/timing attacks by default. Yet, I rarely hear much talk about it. Half of the time I see it discussed, it's along the lines of "Hey, AES is looking really old, should I use Threefish in my new application/library?" to which people respond "AES is proven and still secure, so just keep using that." Personally, I find Threefish to be a beautiful algorithm; simple and effective just like ChaCha20. Seems to me we've hit this local minima with various crypto algorithms. SHA2, AES, et. al are still considered secure, and almost no one has the guts to "risk" something new while the old stuff still works. Whereas before, we knew SHA1, DES, etc. were failing, so people were happy to jump to new algorithms as soon as they hit the market. (Side note: I chose to use Threefish-512 in my hardware password manager project. It gets used in the disk and database encryption, so its built in tweaking is a godsend.)
- tptacek 12y ago
  Can you actually pose an argument in favor of Threefish? I have suspicions as to why Threefish, Twofish, Blowfish, &c come up in discussions like these, but rarely in discussions between actual cryptographic engineers.
  - tedunangst 12y ago
    A vigenere cipher with the Key "BRUCESCHNEIER" is in fact unbreakable.
    - tptacek 12y ago
      ... by the kinds of people who pick cryptographic primitives because they were authored by Bruce Schneier. (ducking)
  - fpgaminer 12y ago
    I can tell you why I picked it, but I'm not a professional cryptographic engineer; just a hobbyist. Compared to AES: Implementation and use is dead simple and short (less room for bugs). The algorithm is easy to grasp. Naive implementations are resistant to timing and power analysis. Built in support for Tweaking, so you don't need to mess around with weird modes of operation. Large key size, and no mis-match between key and block size. Efficient (~6 cpb). It was designed by a large group of well known and respected cryptographers. The simplicity of Threefish is the most important, in my opinion. Applications of AES in the wild have been broken numerous times because of improper use of AES and its modes of operation. Threefish is less likely to suffer those issues, since Tweaking is built in. So, as of today, I think that benefit outweighs the possible risk of Threefish being found weak (and keep in mind that Threefish is specifically designed to resist analysis by using a large number of rounds. Breaks in reduced Threefish are expected, and are not likely to be breaks in full Threefish). Additionally, if people (e.g. Google) are willing to use ChaCha20, I don't see why they wouldn't be willing to use Threefish. They're built on the same principles, as far as I can tell, and both have just as much backing (in terms of peer review and who designed them). Again, the only arguments I've heard in favor of AES involve fear of the unknown.
floody-berry 12y ago
Are there actually many alternatives at this time? SHA-3, and more recently CAESAR, still received submissions based on AES. Grøstl (one of the SHA-3 submissions borrowing from AES) was a top 5 candidate. Constant time, side-channel free algorithms don't seem to be a big issue for many people yet.
- pbsd 12y ago
  I don't think this is a fair assessment. There was a lot of concern over implementation issues during SHA-3 and every finalist did have constant-time implementations, usually coming from the design team itself. The thing with AES and its derivatives is that they make it very easy to prove resistance against cryptanalysis (differential and linear); ARX designs are very hard to analyze exaustively, and bit-oriented designs tend to be slow. Using AES-like constructions provides a middle ground of reasonable performance and provable security (for some value of security).
  - floody-berry 12y ago
    Grøstl's round 3 specification document mentions 3 'strategies' for constant time implementations: AES-NI, vperm (AVX/XOP/NEON), or bitsliced (which they estimate "only a 50% overhead" for vs tables). Yet almost all of the implementations they provide that are not AES-NI are either table based or horrifically slow. ARM/NEON is the only non-AES-NI platform with a constant time implementation that is sometimes on par with the table based alternative. Their constant time approach is "assume use of hardware AES instructions, otherwise enjoy a speed hit if you want to be safe".
    - pbsd 12y ago
      I'm not sure what's your point. Your claim was that constant-time was not a big issue for many people. Maybe it's not. But the Groestl people wrote an entire report on implementation strategies for it [1], specifically mentioning cache-timing issues on the table-based approaches. They clearly took it seriously. There are many competing requirements when designing a primitive. Groestl's choices were not necessarily wrong, even when treating side-channel attacks as a "big issue". I don't like Groestl, but I get what they were trying to achieve; Keccak did it much better, though. [1] http://www.groestl.info/groestl-implementation-guide.pdf http://www.groestl.info/groestl-implementation-guide.pdf

by jvehent 12y ago

higherpurpose 12y ago

I would also like to see Curve25519 (as well as others) supported in all browsers. It really bothers me that while at least websites are making an effort to default to ECDHE encryption with PFS, they have to resort to using the low-performance, insecure and probably NSA-backdoored P-256 curve, because most browsers aren't supporting anything else right now.

sarciszewski 12y ago
I agree. Through PECL, PHP is soon going to have curve25519 support http://pecl.php.net/package/libsodium http://pecl.php.net/package/libsodium There's already a Node-Sodium package... https://github.com/paixaop/node-sodium https://github.com/paixaop/node-sodium Why can't browsers support it natively? (e.g. through NSS)
jvehent 12y ago
If anyone has the time and skills to implement these curves in NSS, I'm sure that the Firefox and Chrome security teams would be more than happy to enable them!
- sarciszewski 12y ago
  https://bugzilla.mozilla.org/show_bug.cgi?id=957105 https://bugzilla.mozilla.org/show_bug.cgi?id=957105 Looks like there's already a bug in Mozilla's tracker.
- tptacek 12y ago
  Very smart crypto implementors are already working on this codebase, aren't they?
  - jvehent 12y ago
    Not being one of them myself, I can only notice that their time is limited, and many much wanted improvements sit on the backburner waiting for a smart crypto implementor to work on them. NSS and OpenSSL are difficult codebases to work with, which may also explain why it's so hard to find people to work on them.
- higherpurpose 12y ago
  I'm not as worried about Chrome/Mozilla as I am about IE and Safari (including the mobile one).
- hsivonen 12y ago
  Why do you expect Firefox and Chrome to take patches as opposed to saying that patches should wait for specs from the TLS WG which waits for the CFRG to bless something? The political problem is that unless there's an authority whose blessing can be appealed to to justify inclusion, how do you decline curves from Microsoft Research and so-called NUMS curves? (Of course, it's not like the CFRG is a politically spoyless authority...)
tptacek 12y ago
You could cite sources on "probably NSA-backdoored" P-256, but they'd all boil down to "you can with some effort devise a scenario in which it would have been possible for NSA to influence the curve selection". You'd be in a very similar rhetorical position to the "controlled demolition" conspiracy theorists. We should, of course, demand rigid curves, and very few of the mainstream curves are rigid. But there's a difference between that and the assertion that P-256 is "probably backdoored"; for one thing, the latter assertion encourages people to adopt RSA, which is more fraught than ECC. That RSA vs. ECC issue is even worse in browsers, which I think makes your sentiment even less useful. In ground-up implementations, you can get some comfort from OAEP/PSS for RSA. No such help in TLS, where RSA still uses (terribly broken) PKCS1v15.
- mentat 12y ago
  My understanding of the issues with P-256 is that it's very easy for mistakes in the ECC implementation around certain points to leak information whereas with other curves it is not. Not quite "backdoored" but certainly not optimal in terms of security. Edit: based on http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4...
  - tptacek 12y ago
    It's true that P-256 is more susceptible to implementation flaws than other curves, because P-256 wasn't designed to be misuse-resistant, unlike recent curves where that was a design goal. It's unlikely that any credible new protocol is going to adopt a NIST curve. They exist only for legacy support now. BULLRUN killed them. Fortunately, in this case I think hysteria actually served a good purpose. I do not think highly of crypto standards, and these ones in particular were dragging the industry down.
- MichaelGG 12y ago
  I'm going to display lots of ignorance in the hope you'll correct me. I thought these "possibly backdoored" curves needed a seed, and the creators provided a "provably random" one by hashing... a random number they provided. That alone is so silly and I'm not sure how anyone could take it seriously. But then, after that, it was discovered all those "provably random" seeds had a 1-in-a-million weakness. While this weakness alone doesn't comprise everything, it's an indicator that someone intentionally found those seeds so it might indicate something more. Is my poor understanding terribly wrong?

fpgaminer 12y ago

Could I give a mention to Threefish as well? It's in the same vein as ChaCha20, but it's a block cipher, based on modern ideas, is more capable than AES, and naive implementations are resistant to power/timing attacks by default. Yet, I rarely hear much talk about it. Half of the time I see it discussed, it's along the lines of "Hey, AES is looking really old, should I use Threefish in my new application/library?" to which people respond "AES is proven and still secure, so just keep using that." Personally, I find Threefish to be a beautiful algorithm; simple and effective just like ChaCha20. Seems to me we've hit this local minima with various crypto algorithms. SHA2, AES, et. al are still considered secure, and almost no one has the guts to "risk" something new while the old stuff still works. Whereas before, we knew SHA1, DES, etc. were failing, so people were happy to jump to new algorithms as soon as they hit the market. (Side note: I chose to use Threefish-512 in my hardware password manager project. It gets used in the disk and database encryption, so its built in tweaking is a godsend.)

tptacek 12y ago
Can you actually pose an argument in favor of Threefish? I have suspicions as to why Threefish, Twofish, Blowfish, &c come up in discussions like these, but rarely in discussions between actual cryptographic engineers.
- tedunangst 12y ago
  A vigenere cipher with the Key "BRUCESCHNEIER" is in fact unbreakable.
  - tptacek 12y ago
    ... by the kinds of people who pick cryptographic primitives because they were authored by Bruce Schneier. (ducking)
- fpgaminer 12y ago
  I can tell you why I picked it, but I'm not a professional cryptographic engineer; just a hobbyist. Compared to AES: Implementation and use is dead simple and short (less room for bugs). The algorithm is easy to grasp. Naive implementations are resistant to timing and power analysis. Built in support for Tweaking, so you don't need to mess around with weird modes of operation. Large key size, and no mis-match between key and block size. Efficient (~6 cpb). It was designed by a large group of well known and respected cryptographers. The simplicity of Threefish is the most important, in my opinion. Applications of AES in the wild have been broken numerous times because of improper use of AES and its modes of operation. Threefish is less likely to suffer those issues, since Tweaking is built in. So, as of today, I think that benefit outweighs the possible risk of Threefish being found weak (and keep in mind that Threefish is specifically designed to resist analysis by using a large number of rounds. Breaks in reduced Threefish are expected, and are not likely to be breaks in full Threefish). Additionally, if people (e.g. Google) are willing to use ChaCha20, I don't see why they wouldn't be willing to use Threefish. They're built on the same principles, as far as I can tell, and both have just as much backing (in terms of peer review and who designed them). Again, the only arguments I've heard in favor of AES involve fear of the unknown.

floody-berry 12y ago

Are there actually many alternatives at this time? SHA-3, and more recently CAESAR, still received submissions based on AES. Grøstl (one of the SHA-3 submissions borrowing from AES) was a top 5 candidate. Constant time, side-channel free algorithms don't seem to be a big issue for many people yet.

pbsd 12y ago
I don't think this is a fair assessment. There was a lot of concern over implementation issues during SHA-3 and every finalist did have constant-time implementations, usually coming from the design team itself. The thing with AES and its derivatives is that they make it very easy to prove resistance against cryptanalysis (differential and linear); ARX designs are very hard to analyze exaustively, and bit-oriented designs tend to be slow. Using AES-like constructions provides a middle ground of reasonable performance and provable security (for some value of security).
- floody-berry 12y ago
  Grøstl's round 3 specification document mentions 3 'strategies' for constant time implementations: AES-NI, vperm (AVX/XOP/NEON), or bitsliced (which they estimate "only a 50% overhead" for vs tables). Yet almost all of the implementations they provide that are not AES-NI are either table based or horrifically slow. ARM/NEON is the only non-AES-NI platform with a constant time implementation that is sometimes on par with the table based alternative. Their constant time approach is "assume use of hardware AES instructions, otherwise enjoy a speed hit if you want to be safe".
  - pbsd 12y ago
    I'm not sure what's your point. Your claim was that constant-time was not a big issue for many people. Maybe it's not. But the Groestl people wrote an entire report on implementation strategies for it [1], specifically mentioning cache-timing issues on the table-based approaches. They clearly took it seriously. There are many competing requirements when designing a primitive. Groestl's choices were not necessarily wrong, even when treating side-channel attacks as a "big issue". I don't like Groestl, but I get what they were trying to achieve; Keccak did it much better, though. [1] http://www.groestl.info/groestl-implementation-guide.pdf http://www.groestl.info/groestl-implementation-guide.pdf