5 ms·

SIDH in Go for quantum-resistant TLS 1.3

107 points by grittygrease 9y ago

JoshTriplett 9y ago
> Because SIDH is still new and unproven, the TLS integration performs a hybrid key exchange: it sends both an X25519 keyshare and an SIDH keyshare, performs both X25519 and SIDH shared secret computations, and feeds both shared secrets into the TLS key derivation mechanism. This ensures that even if SIDH turns out to be broken, the key agreement is at least as secure as X25519. This is the critical bit, and the same thing that Google did with their post-quantum crypto experiment: make it an additional layer of defense-in-depth, while still using standard crypto and ensuring that you still have at least that much security.
- DavidSJ 9y ago
  I'm no crypto expert, but why is this sort of defense-in-depth not more widely deployed? It seems that standard practice is to choose a single cipher for a message, rather than multiply enveloping the message in different ciphers, perhaps employing different fundamental crypto ideas, so that some future compromise of one of them may not necessarily reveal the plaintext of the present message. Obviously performance considerations may answer this in many, or even most cases, but this seems to be the practice nearly always.
  - hannob 9y ago
    This is rarely used because usually you don't have any realistic expectation that algorithm a may be secure while algorithm b may not be. To put it like this: AES is just good enough, there's no reason to combine it with anything. The post quantum + ecc combination is kinda unique here, because you have two classes of algorithms for which you have very different risk scenarios.
    - CorvusCrypto 9y ago
      apples and oranges. With Key exchange algorithms you can get away with this kind of reinforcement. If you start combining encryption algorithms however, you may accidentally reduce the overall entropy of your crypto system by combining algorithms.
      - riffraff 9y ago
        I have often read this, but I don't understand it. Why would `cypherA(cypherB(plaintext))` reveal more than `cypherA(plaintext)` or `cypherB(plaintext)` ? If it did, an attacker might just perform the second encryption and obtain the same result. The only example I've seen is "if you rot13 twice you get back to the start", but that seems a trivially flawed analogy.
        stouset 9y ago
        You're right that this is an oft-misstated reason for avoiding doing so. Layering encryption this way can only decrease security (in a theoretical sense) if the key and/or encryption algorithms aren't independent of one-another. If both are secure algorithms and you use two independent keys, the composition is at least as strong as the strongest of the two. The real reason is that the risk of a catastrophic AES break is less than the risk of you mis-implementing this feature. As a real world example, take this [bug in OpenSSL](https://marc.info/?l=openbsd-tech&m=144472550016118 https://marc.info/?l=openbsd-tech&m=144472550016118) that was intended to prevent DES weak keys. A more theoretical example of a buggy implementation might be actually a very narrow interpretation of the original point. If you reuse the same key between both algorithms (or, generally, using keys that aren't independent of one-another), it's possible for the second cipher to "undo" the work of the first. A trivial example is AES-CTR(k, AES-CTR(k, pt)), which undoes the original encryption. A less-silly but potentially problematic one might be ChaCha20(k, Salsa20(k, pt)). The two algorithms are different, but very similar in design. There's no known issue with combining them in this way, but it would make me extremely nervous to see such a construct in the wild. So in a sense we've come full circle. As I pointed out, the real reason is that you're more likely to introduce a bug implementing layered encryption than you are to prevent a catastrophic failure of your cipher. But ironically, one of the more likely instances of a buggy implementation is reusing the same key for both ciphers, which is something along the lines of what the grandparent poster indicated. As a postscript, one other reason is performance. AES is hardware-accelerated, but other algorithms aren't (though ChaCha20 is extraordinarily fast in general-purpose hardware). Layering means a performance penalty, which is a generally minor but still very valid reason to avoid layering.
  - colmmacc 9y ago
    Unfortunately layering is not as simple as "defense in depth". Each layer may have its own vulnerabilities, and so the attack surface is increased. There is also a history of issues in mis-matches and side-channels arising in how layers are combined, which can be very subtle. So overall there's a trend to simplicity and as little code as possible.
  - madez 9y ago
    I suggested on HN recently to try a layering approach to incorporate self-made cryptography, but was downvoted to hell for it. This made me aware that even people in tech can be dogmatic.
bitmadness 9y ago
Probably worth pointing out that the author of this article has a fairly controversial reputation in the crypto community: https://eindhoven.cr.yp.to/false-statements-by-henry-de-valence.txt https://eindhoven.cr.yp.to/false-statements-by-henry-de-vale... Also, I feel obliged to point out two things: firstly, lattice based cryptosystems, SIDH, etc are only conjectured to be quantum resistant; there is no actual work showing that they are any better than traditional cryptosystems at foiling quantum attacks. Secondly, the kind of industrial grade quantum hardware necessary to be useful for breaking our current crypto (using currently known algorithms) is at least 20+ years away. So worrying about quantum attacks is fairly premature, especially in light of the very dangerous classical security problems we've encountered in the past few years (Heartbleed, Cloudbleed, etc).
- nkcmr 9y ago
  Well, the Year 2032 problem [1] is still a ways off but it doesn't mean we shouldn't prepare for it. [1]: https://en.wikipedia.org/wiki/Year_2038_problem https://en.wikipedia.org/wiki/Year_2038_problem
miller_joe 9y ago
Excellent. Explained so simply.
smegel 9y ago
> Unfortunately, this requires writing assembly, because writing high-performance arithmetic is not possible in Go — it's simply not a design goal of the language. (There are a few reasons, most notably that there's no way to directly compute the (128-bit) product of 64-bit integers.) Can any language do this, without also calling through some library that has hand-crafted assembly in it? Will assigning the product of 2 longs in C to a long long result in the correct instructions?
- hmrten 9y ago
  Forth has great support for double width and mixed width intermediate operations like / which does xy/z with x*y being 128 bits on a 64 bit Forth. Was mainly intended for fixed point operations.
- ekiru 9y ago
  In nightly builds of Rust (on 64-bit x86 platforms; no idea about support elsewhere), `(a as u128) * (b as u128)` where `a` and `b` are 64-bit integers will compile to a single `mul` instruction: see https://godbolt.org/g/Be7ncs https://godbolt.org/g/Be7ncs
- giovannibajo1 9y ago
  GCC supports 128 bit integers as an extension to the language.

107 points by grittygrease 9y ago

> Because SIDH is still new and unproven, the TLS integration performs a hybrid key exchange: it sends both an X25519 keyshare and an SIDH keyshare, performs both X25519 and SIDH shared secret computations, and feeds both shared secrets into the TLS key derivation mechanism. This ensures that even if SIDH turns out to be broken, the key agreement is at least as secure as X25519. This is the critical bit, and the same thing that Google did with their post-quantum crypto experiment: make it an additional layer of defense-in-depth, while still using standard crypto and ensuring that you still have at least that much security.

DavidSJ 9y ago
I'm no crypto expert, but why is this sort of defense-in-depth not more widely deployed? It seems that standard practice is to choose a single cipher for a message, rather than multiply enveloping the message in different ciphers, perhaps employing different fundamental crypto ideas, so that some future compromise of one of them may not necessarily reveal the plaintext of the present message. Obviously performance considerations may answer this in many, or even most cases, but this seems to be the practice nearly always.
- hannob 9y ago
  This is rarely used because usually you don't have any realistic expectation that algorithm a may be secure while algorithm b may not be. To put it like this: AES is just good enough, there's no reason to combine it with anything. The post quantum + ecc combination is kinda unique here, because you have two classes of algorithms for which you have very different risk scenarios.
  - CorvusCrypto 9y ago
    apples and oranges. With Key exchange algorithms you can get away with this kind of reinforcement. If you start combining encryption algorithms however, you may accidentally reduce the overall entropy of your crypto system by combining algorithms.
    - riffraff 9y ago
      I have often read this, but I don't understand it. Why would `cypherA(cypherB(plaintext))` reveal more than `cypherA(plaintext)` or `cypherB(plaintext)` ? If it did, an attacker might just perform the second encryption and obtain the same result. The only example I've seen is "if you rot13 twice you get back to the start", but that seems a trivially flawed analogy.
      - stouset 9y ago
        You're right that this is an oft-misstated reason for avoiding doing so. Layering encryption this way can only decrease security (in a theoretical sense) if the key and/or encryption algorithms aren't independent of one-another. If both are secure algorithms and you use two independent keys, the composition is at least as strong as the strongest of the two. The real reason is that the risk of a catastrophic AES break is less than the risk of you mis-implementing this feature. As a real world example, take this [bug in OpenSSL](https://marc.info/?l=openbsd-tech&m=144472550016118 https://marc.info/?l=openbsd-tech&m=144472550016118) that was intended to prevent DES weak keys. A more theoretical example of a buggy implementation might be actually a very narrow interpretation of the original point. If you reuse the same key between both algorithms (or, generally, using keys that aren't independent of one-another), it's possible for the second cipher to "undo" the work of the first. A trivial example is AES-CTR(k, AES-CTR(k, pt)), which undoes the original encryption. A less-silly but potentially problematic one might be ChaCha20(k, Salsa20(k, pt)). The two algorithms are different, but very similar in design. There's no known issue with combining them in this way, but it would make me extremely nervous to see such a construct in the wild. So in a sense we've come full circle. As I pointed out, the real reason is that you're more likely to introduce a bug implementing layered encryption than you are to prevent a catastrophic failure of your cipher. But ironically, one of the more likely instances of a buggy implementation is reusing the same key for both ciphers, which is something along the lines of what the grandparent poster indicated. As a postscript, one other reason is performance. AES is hardware-accelerated, but other algorithms aren't (though ChaCha20 is extraordinarily fast in general-purpose hardware). Layering means a performance penalty, which is a generally minor but still very valid reason to avoid layering.
- colmmacc 9y ago
  Unfortunately layering is not as simple as "defense in depth". Each layer may have its own vulnerabilities, and so the attack surface is increased. There is also a history of issues in mis-matches and side-channels arising in how layers are combined, which can be very subtle. So overall there's a trend to simplicity and as little code as possible.
- madez 9y ago
  I suggested on HN recently to try a layering approach to incorporate self-made cryptography, but was downvoted to hell for it. This made me aware that even people in tech can be dogmatic.

bitmadness 9y ago

Probably worth pointing out that the author of this article has a fairly controversial reputation in the crypto community: https://eindhoven.cr.yp.to/false-statements-by-henry-de-valence.txt https://eindhoven.cr.yp.to/false-statements-by-henry-de-vale... Also, I feel obliged to point out two things: firstly, lattice based cryptosystems, SIDH, etc are only conjectured to be quantum resistant; there is no actual work showing that they are any better than traditional cryptosystems at foiling quantum attacks. Secondly, the kind of industrial grade quantum hardware necessary to be useful for breaking our current crypto (using currently known algorithms) is at least 20+ years away. So worrying about quantum attacks is fairly premature, especially in light of the very dangerous classical security problems we've encountered in the past few years (Heartbleed, Cloudbleed, etc).

nkcmr 9y ago
Well, the Year 2032 problem [1] is still a ways off but it doesn't mean we shouldn't prepare for it. [1]: https://en.wikipedia.org/wiki/Year_2038_problem https://en.wikipedia.org/wiki/Year_2038_problem

miller_joe 9y ago

Excellent. Explained so simply.

smegel 9y ago

> Unfortunately, this requires writing assembly, because writing high-performance arithmetic is not possible in Go — it's simply not a design goal of the language. (There are a few reasons, most notably that there's no way to directly compute the (128-bit) product of 64-bit integers.) Can any language do this, without also calling through some library that has hand-crafted assembly in it? Will assigning the product of 2 longs in C to a long long result in the correct instructions?

hmrten 9y ago
Forth has great support for double width and mixed width intermediate operations like / which does xy/z with x*y being 128 bits on a 64 bit Forth. Was mainly intended for fixed point operations.
ekiru 9y ago
In nightly builds of Rust (on 64-bit x86 platforms; no idea about support elsewhere), `(a as u128) * (b as u128)` where `a` and `b` are 64-bit integers will compile to a single `mul` instruction: see https://godbolt.org/g/Be7ncs https://godbolt.org/g/Be7ncs
giovannibajo1 9y ago
GCC supports 128 bit integers as an extension to the language.