Intent to Implement and Ship: CECPQ1 for TLS

[Adam Langley]

Contact emails

m...@google.com, a...@chromium.org, davi...@chromium.org

Summary and motivation

CECPQ1 is a post-quantum cipher suite: one that is designed to provide confidentiality even against an attacker who possesses a large quantum computer. It is a key-agreement algorithm plugged into TLS that combines X25519 and NewHope, a ring-learning-with-errors primitive. Even if NewHope turns out to be breakable, the X25519 key-agreement will ensure that it provides at least the security of our existing connections.

This is only an experiment and will only be used on a small fraction of HTTPS connections between Chrome and Google. (Most connections between Chrome and Google will use QUIC, and we haven't integrated CECPQ1 into QUIC.)

The aim is to a) provide the research community a target because it would be very useful to know whether the ring structure in R-LWE is a mistake sooner rather than later and b) to test the real-world impact on latency and compatibility with the larger handshake messages that any post-quantum scheme seems likely to need.

For more background, see https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html

Interoperability and compatibility risk

This is a TLS cipher suite and so is negotiated each time it's used. It could be removed without any compatibility impact.

It is not expected that any other browser or server will implement this feature. In time, the Internet may well need to move to post-quantum cipher suites but this is very experimental and more experimentation and research is needed before we'll have something ready for widespread implementation.

There is a minor chance that even advertising support for these cipher suites could break some buggy servers, but we have added cipher suites in the past without issue and so do not anticipate any issues.

There is a chance that the larger handshake messages will cause network middleware to have problems. Discovering this early is one of the goals of this experiment.

Ongoing technical constraints

We will remove this experiment within two years—hopefully because we have something better to replace it with.

Spec

Not intended for widespread implementation so there's not a detailed spec. For background on the R-LWE primitive see https://www.imperialviolet.org/2015/12/24/rlwe.html and https://eprint.iacr.org/2015/1092.

Is this feature supported on all Chromium platforms?

These cipher suites are controlled by Finch and are currently not enabled on mobile. Once latency data has been analysed on desktop, we'll make the decision about whether to test on mobile.

Tracking bug

https://bugs.chromium.org/p/chromium/issues/detail?id=626363

Link to entry on the feature dashboard

https://www.chromestatus.com/features/5749214348836864

Requesting approval to ship?

Yes.

Cheers

AGL

[PhistucK]

A two year period is a very long time... Servers may depend on it.

I understand this will be advertised to the entire web and not only to Google, right? This creates a possibility for dependencies ("we only support the most secure and up to date cipher, so our server only accepts CECPQ1" and the like). Combined with the long period, this sounds somewhat risky and it might be harder to remove.

☆PhistucK

--
You received this message because you are subscribed to the Google Groups "net-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to net-dev+u...@chromium.org.
To post to this group, send email to net...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/net-dev/CAL9PXLzfX8oURQgi6QBcPmRad6%2Bu7P%2BiuZERWCZrsJeB%2BkY4WQ%40mail.gmail.com.

[Adam Langley]

On Thu, Jul 7, 2016 at 9:12 AM, PhistucK <phis...@gmail.com> wrote:

A two year period is a very long time... Servers may depend on it.

I understand this will be advertised to the entire web and not only to Google, right?

That's correct, there's no if (google) around the code.

This creates a possibility for dependencies ("we only support the most secure and up to date cipher, so our server only accepts CECPQ1" and the like). Combined with the long period, this sounds somewhat risky and it might be harder to remove.

Any server that did this would be unable to communicate with any non-Chrome browser, and even some fraction of Chrome (because they'll be in the control group, or on an excluded platform). While I certainly share the desire that this not become non-trivial to remove, depending on it would sufficiently cripple a server that I don't think it'll happen.

Cheers

AGL 

[Jochen Eisinger]

Do you have any concrete research plans, or do you know about researchers that will yet to evaluate the new algorithm?

Anyway, even just trying to see whether the larger handshake causes problems seems worthwhile, so lgtm1

[Adam Langley]

On Thu, Jul 7, 2016 at 9:38 AM, Jochen Eisinger <joc...@chromium.org> wrote:

Do you have any concrete research plans, or do you know about researchers that will yet to evaluate the new algorithm?

We'll watch the latency of TLS handshakes to Google across the two populations as our main metric once we have a useful population size. Detecting any middleware / MITM proxy breakage is never as clean, I'm afraid. If there are problems then that information should appear in the flow of bug reports which we (i.e. davidben) handle anyway.

I'm not aware of any specific researchers who plan to try and analyse NewHope because of this, but nor would I expect to because that's generally not how they work.

Cheers

AGL 

[Katriel Cohn-Gordon]

Is there a spec for CECPQ1?

Does it follow from the work of Stebila et al that NewHope + ECDSA is at least as secure as ECDSA? (I can imagine buggy ways of combining them that don't satisfy that property, not that I think that is the case here.)

[Adam Langley]

On Thu, Jul 7, 2016 at 10:06 AM, Katriel Cohn-Gordon <katr...@google.com> wrote:

Is there a spec for CECPQ1?

No. We would typically write an IETF draft for work in this space that we wished to standardise, but we don't wish to standardise this. (Nor, indeed, to see it spread.)

With the bit of luck, the next iteration, in a year or two, will be suitable for a push at the IETF.

 

Does it follow from the work of Stebila et al that NewHope + ECDSA is at least as secure as ECDSA? (I can imagine buggy ways of combining them that don't satisfy that property, not that I think that is the case here.)

(I assume that you mean NewHope + ECDHE.)

We are depending on the TLS 1.2 KDF to mix the outputs of these two key-agreement primitives. From the spec, we can see that the concatenation of X25519 and NewHope will be used as a "key" to HMAC-SHA256 or HMAC-SHA384. If we assume that NewHope is broken and outputs all zeros every time then the difference between X25519 and X25519++NewHope will either be the difference between HMAC(key = X25519-output, …) and HMAC(key = SHA-256(X25519-output + '\x00'*32), …), or no difference at all (with SHA-256 and SHA-384, respectively).

So, assuming second-preimage resistance of SHA-2, I think we're good. That's at least my hand-wavy justification for why concatenating the two is reasonable.

Cheers

AGL

[Jochen Eisinger]

out of curiosity, is there a high-level description available somewhere for why NewHope is supposedly safe in a post-quantum world?

[Adam Langley]

On Thu, Jul 7, 2016 at 11:12 AM, Jochen Eisinger <joc...@chromium.org> wrote:
> out of curiosity, is there a high-level description available somewhere for
> why NewHope is supposedly safe in a post-quantum world?

Quantum computation is substantially different from classical and I do
not claim, even slightly, to understand it well enough to give a good
answer here.

But, very roughly, quantum computers aren't magic: they don't provide
a way to speed up the solution of any problem. A quantum algorithm
needs to ensure that all the wrong answers to a problem cancel out so
that there's a high probability of the correct answer remaining and we
only know of such algorithms for a subset of problems.

Factoring and discrete log are two problems where do have a quantum
algorithm, and that's the problem because everything is built on them,
pretty much. But, in the same way that we believe that factoring is
hard on a classical computer, we believe that several problems on
lattices, R-LWE included, are hard on both classical and quantum
computers. There's no proof of that however, in the same way that
there's no proof that someone won't solve factoring with classical
computers tomorrow. (Indeed, it's possible that R-LWE /might/ turn out
to be easy even on classical computers!)

There may be a deeper intuition about why these lattice-based problems
are unlikely to admit a quantum solution, but I'm afraid that I don't
know enough to see it.


Cheers

AGL

[Katriel Cohn-Gordon]

(Disclaimer: not even a little bit of an expert in post-quantum crypto.)

There is some evidence that LWE is a hard problem:

• Lyubashevsky et al published a quantum reduction to the approximate shortest vector problem.
  
• Regev proved a worst-case/average-case result: the average case of RLWE is as hard as the worst case of SVP.
• LWE looks a bit like the problem of distinguishing distributions, which is known to be hard.

If you feel uncomfortable with "evidence" instead of nice concrete proofs, Scott Aaronson has written a good blog post (unrelated to RLWE) about the meaning of evidence for problems in discrete maths.

[Rick Byers]

LGTM2

Experiments that we can try (without putting Chrome/Google at some special advantage in the ecosystem) and then change/remove without breaking anything are great from an interop-risk perspective.

[Antonio Sanso]

thanks for sharing.

It would be nice to have some more details though, so if somebody is willing to write a server supporting this Cipher can do it (without getting crazy doing reverse engineering), just for fun :)

regards

antonio

--
You received this message because you are subscribed to the Google Groups "Security-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to security-dev...@chromium.org.

[Philip Jägenstedt]

LGTM3

Given TLSs negotiation and that the experiment isn't intended to ever be enabled for 100% of the users (right?) the risk of lock-in here seems small.

On security I am totally unqualified, but it makes intuitive sense that concatenating two things before HMAC is as secure as the least secure of the two things used independently.

Also, if Finch is used it sounds like the whole thing can be aborted quickly even if some non-Google servers start supporting (or requiring) the new things.