6 ms·

HTTPS crypto’s days are numbered. Here’s how Google wants to save it

46 points by stanleydrew 10y ago

sctb 10y ago
Recent discussion about post-quantum cryptography at Google: https://news.ycombinator.com/item?id=12050220 https://news.ycombinator.com/item?id=12050220
cm3 10y ago
Can someone explain how the stacking on top of existing crypto works? Is it redundant (aka double)?
- hannob 10y ago
  This is pretty simple: The results from the two key exchanges are concatenated and hashed. The result is used as a TLS session key. The idea is then that in order to attack this an am attacker would need to break both key exchanges. Thus even if one of them is insecure the combination still stays secure. This is a well known method, but it's rarely used. Usually we are confident enough in our algorithms and most people don't see a need to combine them.
  - cm3 10y ago
    But there is splitting involved, or it's duplicate, isn't it? Edit: What's the name of the scheme used?
    - are595 10y ago
      Their blog post goes into more details: https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html https://security.googleblog.com/2016/07/experimenting-with-p... They are using "New Hope" on top of EC-crypto and calling it CECPQ1-ECDSA.
      - cm3 10y ago
        I've read that, but can't find the details or make concrete sense of the scheme involved. will use a post-quantum key-exchange algorithm in addition to the elliptic-curve key-exchange algorithm that would typically be used. By adding a post-quantum algorithm on top of the existing one, we are able to experiment without affecting user security. The post-quantum algorithm might turn out to be breakable even with today's computers, in which case the elliptic-curve algorithm will still provide the best security that today’s technology can offer. I mean, I can't answer the question with the info found in the blog. Hanno commented this is a well known scheme without mentioning the name. If someone knows the name, I'll look that up. In the meantime, I'll dig through the code to understand what they're actually doing.
        Ar-Curunir 10y ago
        The new key exchange is based on lattice cryptography, which is conjectured to be quantum resistant. The precise assumption is RLWE.
        cm3 10y ago
        Thanks, and yes, I've read about what hardness assumption is used. My confusion is about what pieces are concatenated. Is the same input processed twice (different ciphers) and then concatenated, which is then the generated key?
        tptacek 10y ago
        The outputs of an RLWE and ECDH handshake are both fed into the TLS KDF.
        cm3 10y ago
        Thanks for the info. May I ask if you figured that out from the blog or BoringSSL code?
  - stephengillie 10y ago
    How do we know the inner cryptography isn't weakening the outer cryptography? Couldn't they conflict somehow, making the message easier to decrypt?
    - Ar-Curunir 10y ago
      It because the hash function is just looking at a concatenation of two (computationally) pseudorandom strings, and output the hash of that. If either method is broken (but not both) there is still enough entropy to create a safe key.
goblin89 10y ago
First and third paragraphs make strong claims, mentioning forecasts for crypto doomsday scenarios but offering no links. For those of us living under a rock, how realistic are these applications of quantum computing?
- johncolanduoni 10y ago
  Realistic in the sense that we will one day have scalable quantum computing? Very. There have been a few (non-crackpot) people in QI and adjacent fields who have argued that it will be impossible indefinitely (one I know of is Gil Kalai), but the consensus that this is physically possible is pretty overwhelming. As to timeframe? Estimates are all over the place but some groups have made promising and somewhat unexpected strides in the last few years (Martini's group at UCSB/Google have done some particularly impressive things). If people in quantum information get extraordinarily lucky, even the more optimistic estimates (usually ~20 years) could be shortened dramatically. Considering how long it takes to roll out totally new crypto, we really should've gotten started yesterday. The biggest complication is that all our quantum-resistant encryption systems are young and untested by crypto standards. We don't want them to be our first line of defense until we have more confidence there won't be some unfortunate way to beat them with a Python script on a laptop in 15 seconds. This seems like a good compromise, especially if they can do it without increasing the number of roundtrips in the handshake (I don't in principle see why they couldn't do both in parallel, but I'm not sure how feasible that is with TLS).
  - deleted 10y ago
    [deleted]
  - baby 10y ago
    > but the consensus that this is physically possible is pretty overwhelming Most of what I read is "it might happen". No one knows for sure. Most of the claims come from people in need of funding for Quantum research, so this is to take with a grain of salt.
    - jcranmer 10y ago
cm3 10y ago
Given the history of past innovations in cryptography (public key), it's reasonable to assume that there are quantum machines in the works or already operating (to some extent) behind closed doors inside institutions that benefit from having everyone believe such a capability doesn't exist yet. We don't know if someone has it, but I don't agree with Google's remark that there's no imminent threat. It's wise to assume it does and speed up R&D of production PQC. Even if it doesn't exist, there's enough data that can be recorded now and is still valuable to decrypt later, so it makes a lot of sense to implement and deploy PQC. Edit: To rephrase: even if we don't know of any capable system, it's wise to take precautions now. I'd compare it to a storm shelter. You don't unpack a blowup storm shelter once the weather report comes in. You prepare, assuming the worst. I'm not arguing that someone has such a system, but that we don't know and have been proven wrong before only after Whitman and Diffie combined the pieces and had to fight for publishing their results. NSA and BT came forward after their paper was published and wouldn't have otherwise.
- johncolanduoni 10y ago
  > it's reasonable to assume that there are quantum machines in the works or already operating (to some extent) behind closed doors inside institutions that benefit from having everyone believe such a capability doesn't exist yet. I would be very surprised. Somehow, the more clandestine parts of governments would have had to siphon off a whole ton of people working in quantum information (physicists, engineers, mathematicians), which is a relatively new and close-knit field, without anybody noticing. Or, people who work in collaboration with parts of the government (NIST and UMD's JQI) are all making up work that looks like they haven't cracked it yet, when they really did last year. If all the NSA needed were mathematicians and electrical engineers that specialized in classical computing, then I could believe they had something going on. As it stands, most people in QI seem to land in industry, academia, or perhaps some national laboratories, not report to Fort Meade or fall of the face of the Earth. This would be like doing the Manhattan project, but with the extra complication finding convincing body doubles for Feynman, Oppenheimer, etc.
  - roblabla 10y ago
    There's a good point in GP's post though. The thing is, one day quantum computers WILL BE available to the NSA or whatever. And they also have the means to record all encrypted transmissions (and they probably do). So one day, the NSA will be able to crack those transmissions that are using pre-quantum algorithms. Using post-quantum algorithms ASAP would at least make sure that from this point on, we're "safe" from quantum computers making a sudden appearance tomorrow.
ethbro 10y ago
As a crypto layman, can someone explain to me how PFS plays into currently used TLS schemes? Am I correct in assuming that each session would still need to be decrypted individually, even were one in possession of a trivially-decrypting quantum computer?
- segf4ult 10y ago
  Each session would need to be decrypted individually, but if it only took you a few ms per session, you could essentially decrypt as many as you want.
  - johncolanduoni 10y ago
    Moreover what we know from the physics of our current general purpose quantum gates (different rules apply for quantum annealers like the D-Wave but these cannot perform Shor's algorithm) it is unlikely it will take more than that to perform a computation. Quantum states in circuits decohere quite rapidly; this is the main obstacle we face in developing them. Chances are we won't have a choice but to do things relatively quickly with quantum computers (there are some possibilities where we need to take time to prepare resources for the computation, but these have the advantage of being trivially parallelizable). On the plus side, all quantum algorithms will be unable to perform a Logjam-style attack[1] where you do part of the computation once because the same parameters are reused by many servers. You can't copy quantum memory in any useful sense. [1]: https://weakdh.org/ https://weakdh.org/
baby 10y ago
This was the title of the article yesterday: https://twitter.com/lyon01_david/status/751530478335823875 https://twitter.com/lyon01_david/status/751530478335823875 > HTTPS crypto on the brink of collapse. Google has a plan to fix it. Apparently it was changed for a less click-baity title. But in my opinion it still shows a bias on the hypothetical outcome of Quantum Computers. No, HTTPS crypto's days are not numbered for sure.
xnull2guest 10y ago
HTTPS is no longer end-to-end encryption as everybody from corporate networks to load balancers to governments transparently MiTM. The three big things that need to be solved are: - How to do fault tolerate distributed end-to-end encryption - How to develop a stronger trust model than exists in PKI - How to move from an privatized ownership model of trust (CAs) to a public individualized model of ownership (web of trust doesn't seem to work)
- daave 10y ago
  So you're assuming there are compromised CA keys in the hands of governments & corrupt corporations? Even if this is true, isn't it mitigated by certificate pinning?
  - xnull2guest 10y ago
    It's well known that governments are trusted CAs themselves in addition to their having 'shadow certificates' (issued by CA's to impersonate other identities) as well as compromised CA certificates. There's no assumptions there. With regard to corporations, most large ones configure employee browsers to trust corporate proxies which can see their traffic in plaintext. That's not unusual at all. Certificate pinning very partially mitigates these issues. It should be done, but pinning certificates (as fragile as that process is to begin with) isn't enough when you can't trust what you're pinning to begin with. In short it's a good idea to use certificate pinning but in no way should be thought of as a fix for fundamental problems that exist in PKI. I might add Moxie's concept of "trust-mobility" to the list of things in the list up the comment stack.
cs600 10y ago
Another description of the mod. they made: https://medium.com/@sergey_nog/google-learning-errors-rings-a944281967f3#.51skfk6up https://medium.com/@sergey_nog/google-learning-errors-rings-...

46 points by stanleydrew 10y ago

sctb 10y ago

Recent discussion about post-quantum cryptography at Google: https://news.ycombinator.com/item?id=12050220 https://news.ycombinator.com/item?id=12050220

cm3 10y ago

Can someone explain how the stacking on top of existing crypto works? Is it redundant (aka double)?

hannob 10y ago
This is pretty simple: The results from the two key exchanges are concatenated and hashed. The result is used as a TLS session key. The idea is then that in order to attack this an am attacker would need to break both key exchanges. Thus even if one of them is insecure the combination still stays secure. This is a well known method, but it's rarely used. Usually we are confident enough in our algorithms and most people don't see a need to combine them.
- cm3 10y ago
  But there is splitting involved, or it's duplicate, isn't it? Edit: What's the name of the scheme used?
  - are595 10y ago
    Their blog post goes into more details: https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html https://security.googleblog.com/2016/07/experimenting-with-p... They are using "New Hope" on top of EC-crypto and calling it CECPQ1-ECDSA.
    - cm3 10y ago
      I've read that, but can't find the details or make concrete sense of the scheme involved. will use a post-quantum key-exchange algorithm in addition to the elliptic-curve key-exchange algorithm that would typically be used. By adding a post-quantum algorithm on top of the existing one, we are able to experiment without affecting user security. The post-quantum algorithm might turn out to be breakable even with today's computers, in which case the elliptic-curve algorithm will still provide the best security that today’s technology can offer. I mean, I can't answer the question with the info found in the blog. Hanno commented this is a well known scheme without mentioning the name. If someone knows the name, I'll look that up. In the meantime, I'll dig through the code to understand what they're actually doing.
      - Ar-Curunir 10y ago
        The new key exchange is based on lattice cryptography, which is conjectured to be quantum resistant. The precise assumption is RLWE.
        cm3 10y ago
        Thanks, and yes, I've read about what hardness assumption is used. My confusion is about what pieces are concatenated. Is the same input processed twice (different ciphers) and then concatenated, which is then the generated key?
        tptacek 10y ago
        The outputs of an RLWE and ECDH handshake are both fed into the TLS KDF.
        cm3 10y ago
        Thanks for the info. May I ask if you figured that out from the blog or BoringSSL code?
- stephengillie 10y ago
  How do we know the inner cryptography isn't weakening the outer cryptography? Couldn't they conflict somehow, making the message easier to decrypt?
  - Ar-Curunir 10y ago
    It because the hash function is just looking at a concatenation of two (computationally) pseudorandom strings, and output the hash of that. If either method is broken (but not both) there is still enough entropy to create a safe key.

goblin89 10y ago

First and third paragraphs make strong claims, mentioning forecasts for crypto doomsday scenarios but offering no links. For those of us living under a rock, how realistic are these applications of quantum computing?

johncolanduoni 10y ago
Realistic in the sense that we will one day have scalable quantum computing? Very. There have been a few (non-crackpot) people in QI and adjacent fields who have argued that it will be impossible indefinitely (one I know of is Gil Kalai), but the consensus that this is physically possible is pretty overwhelming. As to timeframe? Estimates are all over the place but some groups have made promising and somewhat unexpected strides in the last few years (Martini's group at UCSB/Google have done some particularly impressive things). If people in quantum information get extraordinarily lucky, even the more optimistic estimates (usually ~20 years) could be shortened dramatically. Considering how long it takes to roll out totally new crypto, we really should've gotten started yesterday. The biggest complication is that all our quantum-resistant encryption systems are young and untested by crypto standards. We don't want them to be our first line of defense until we have more confidence there won't be some unfortunate way to beat them with a Python script on a laptop in 15 seconds. This seems like a good compromise, especially if they can do it without increasing the number of roundtrips in the handshake (I don't in principle see why they couldn't do both in parallel, but I'm not sure how feasible that is with TLS).
- deleted 10y ago
  [deleted]
- baby 10y ago
  > but the consensus that this is physically possible is pretty overwhelming Most of what I read is "it might happen". No one knows for sure. Most of the claims come from people in need of funding for Quantum research, so this is to take with a grain of salt.
  - jcranmer 10y ago

cm3 10y ago

Given the history of past innovations in cryptography (public key), it's reasonable to assume that there are quantum machines in the works or already operating (to some extent) behind closed doors inside institutions that benefit from having everyone believe such a capability doesn't exist yet. We don't know if someone has it, but I don't agree with Google's remark that there's no imminent threat. It's wise to assume it does and speed up R&D of production PQC. Even if it doesn't exist, there's enough data that can be recorded now and is still valuable to decrypt later, so it makes a lot of sense to implement and deploy PQC. Edit: To rephrase: even if we don't know of any capable system, it's wise to take precautions now. I'd compare it to a storm shelter. You don't unpack a blowup storm shelter once the weather report comes in. You prepare, assuming the worst. I'm not arguing that someone has such a system, but that we don't know and have been proven wrong before only after Whitman and Diffie combined the pieces and had to fight for publishing their results. NSA and BT came forward after their paper was published and wouldn't have otherwise.

johncolanduoni 10y ago
> it's reasonable to assume that there are quantum machines in the works or already operating (to some extent) behind closed doors inside institutions that benefit from having everyone believe such a capability doesn't exist yet. I would be very surprised. Somehow, the more clandestine parts of governments would have had to siphon off a whole ton of people working in quantum information (physicists, engineers, mathematicians), which is a relatively new and close-knit field, without anybody noticing. Or, people who work in collaboration with parts of the government (NIST and UMD's JQI) are all making up work that looks like they haven't cracked it yet, when they really did last year. If all the NSA needed were mathematicians and electrical engineers that specialized in classical computing, then I could believe they had something going on. As it stands, most people in QI seem to land in industry, academia, or perhaps some national laboratories, not report to Fort Meade or fall of the face of the Earth. This would be like doing the Manhattan project, but with the extra complication finding convincing body doubles for Feynman, Oppenheimer, etc.
- roblabla 10y ago
  There's a good point in GP's post though. The thing is, one day quantum computers WILL BE available to the NSA or whatever. And they also have the means to record all encrypted transmissions (and they probably do). So one day, the NSA will be able to crack those transmissions that are using pre-quantum algorithms. Using post-quantum algorithms ASAP would at least make sure that from this point on, we're "safe" from quantum computers making a sudden appearance tomorrow.

ethbro 10y ago

As a crypto layman, can someone explain to me how PFS plays into currently used TLS schemes? Am I correct in assuming that each session would still need to be decrypted individually, even were one in possession of a trivially-decrypting quantum computer?

segf4ult 10y ago
Each session would need to be decrypted individually, but if it only took you a few ms per session, you could essentially decrypt as many as you want.
- johncolanduoni 10y ago
  Moreover what we know from the physics of our current general purpose quantum gates (different rules apply for quantum annealers like the D-Wave but these cannot perform Shor's algorithm) it is unlikely it will take more than that to perform a computation. Quantum states in circuits decohere quite rapidly; this is the main obstacle we face in developing them. Chances are we won't have a choice but to do things relatively quickly with quantum computers (there are some possibilities where we need to take time to prepare resources for the computation, but these have the advantage of being trivially parallelizable). On the plus side, all quantum algorithms will be unable to perform a Logjam-style attack[1] where you do part of the computation once because the same parameters are reused by many servers. You can't copy quantum memory in any useful sense. [1]: https://weakdh.org/ https://weakdh.org/

baby 10y ago

This was the title of the article yesterday: https://twitter.com/lyon01_david/status/751530478335823875 https://twitter.com/lyon01_david/status/751530478335823875 > HTTPS crypto on the brink of collapse. Google has a plan to fix it. Apparently it was changed for a less click-baity title. But in my opinion it still shows a bias on the hypothetical outcome of Quantum Computers. No, HTTPS crypto's days are not numbered for sure.

xnull2guest 10y ago

HTTPS is no longer end-to-end encryption as everybody from corporate networks to load balancers to governments transparently MiTM. The three big things that need to be solved are: - How to do fault tolerate distributed end-to-end encryption - How to develop a stronger trust model than exists in PKI - How to move from an privatized ownership model of trust (CAs) to a public individualized model of ownership (web of trust doesn't seem to work)

daave 10y ago
So you're assuming there are compromised CA keys in the hands of governments & corrupt corporations? Even if this is true, isn't it mitigated by certificate pinning?
- xnull2guest 10y ago
  It's well known that governments are trusted CAs themselves in addition to their having 'shadow certificates' (issued by CA's to impersonate other identities) as well as compromised CA certificates. There's no assumptions there. With regard to corporations, most large ones configure employee browsers to trust corporate proxies which can see their traffic in plaintext. That's not unusual at all. Certificate pinning very partially mitigates these issues. It should be done, but pinning certificates (as fragile as that process is to begin with) isn't enough when you can't trust what you're pinning to begin with. In short it's a good idea to use certificate pinning but in no way should be thought of as a fix for fundamental problems that exist in PKI. I might add Moxie's concept of "trust-mobility" to the list of things in the list up the comment stack.

cs600 10y ago

Another description of the mod. they made: https://medium.com/@sergey_nog/google-learning-errors-rings-a944281967f3#.51skfk6up https://medium.com/@sergey_nog/google-learning-errors-rings-...