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.
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.
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?
The hybrid ciphersuite idea comes from [1, Section 5.2], though you could also chalk it up to common sense. I don't think the blog spells out how it's done.
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).
> 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.
1. Quantum computers do exist in reality, as in we can build qubits, shove them through quantum gates, and read the results.
2. Quantum computers that are large enough to do anything useful don't exist.
3. It's not clear if we can practically build systems that hold 000's of qubits without letting them decohere.
4. D-Wave's quantum computer isn't a quantum computer for the purposes of what most people talk about with quantum computing. It also doesn't look better than classical computers.
If you didn't read these claims from the clearly biased quantum information researchers (many of whom don't work on or receive grants for anything related to quantum computing, even in grant proposal prose la-la land) then where are you getting your probability assessments from? Not to mention all the physicists who work day-in day-out with quantum mechanics in completely different fields who are also extremely skeptical of the absolute physical impossibility of quantum computing.
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.
> 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.
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.
I don't contest that at all, I'm very much in the "let's have post-quantum redundancies here yesterday" camp. I just found it hard to believe (though I was quite entertained by the conjecture) that the people I know in QI are either NSA impostors or stupid enough to fall for NSA impostors of their colleagues.
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?
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.
> 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.
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.
33 comments
[ 2.5 ms ] story [ 79.4 ms ] threadThis 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.
Edit: What's the name of the scheme used?
They are using "New Hope" on top of EC-crypto and calling it CECPQ1-ECDSA.
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.
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?
[1] https://eprint.iacr.org/2014/599
If either method is broken (but not both) there is still enough entropy to create a safe key.
For those of us living under a rock, how realistic are these applications of quantum computing?
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).
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.
1. Quantum computers do exist in reality, as in we can build qubits, shove them through quantum gates, and read the results.
2. Quantum computers that are large enough to do anything useful don't exist.
3. It's not clear if we can practically build systems that hold 000's of qubits without letting them decohere.
4. D-Wave's quantum computer isn't a quantum computer for the purposes of what most people talk about with quantum computing. It also doesn't look better than classical computers.
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.
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.
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.
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?
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 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.
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)
Even if this is true, isn't it mitigated by certificate pinning?
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.