Subject: Re: [Cfrg] Postquantum cryptography in IETF protocols

From: "Tams, Benjamin" <[email-masked]>
Date: Tue, 14 Mar 2017 17:31:41 +0000

Hi John,

> Good that CFRG starts some more detailed discussion on PQC. It makes sense
> to support post-quantum key exchange for use cases that need long-term
> confidentiality (15 years). For other use cases I think it can wait until
> PQC key exchange algorithms has been thoroughly evaluated and
> standardized. If implemented now, it should be used in addition to ECDHE,
> just like Google has done with their experimental New Hope implementation.

I absolutely agree with your view on the subject. Especially for those use
cases where the attack scenario "collect today, decrypt tomorrow" is a threat, 
we should start thinking of PQ-safe key exchange methods in time. Even if
they eventually turn out to be insecure; we can now combine them with
classical key exchange algorithms. We have nothing to lose.

There is already IETF work addressing PQ-security in Internet protocols, e.g.
IKE and an Internet Draft for a Quantum-Safe Hybrid Ciphersuite for TLS

https://tools.ietf.org/html/draft-fluhrer-qr-ikev2-03
https://tools.ietf.org/html/draft-whyte-qsh-tls13-03

On the other hand, there is (to my knowledge) no specification for a PQ-safe
patent-free key exchange algorithm suitable for implementation. In fact, in 
https://tools.ietf.org/html/draft-whyte-qsh-tls13-03
only NTRUEncrypt is specified but is subject to patents.

A possible first step is that CFRG creates an Internet Draft. In fact,
the algorithm New Hope has already been implemented as a plugin for
strongSwan (IPSec implementation for the Linux kernel)

https://github.com/strongswan/strongswan/tree/master/src/libstrongswan/plugins/newhope

So why do we not start with a draft for which the above implementation can 
serve as a reference implementation?

Kind regards,
Benjamin

---

From: William Whyte <[email-masked]>
Date: Tue, 14 Mar 2017 15:34:56 -0400

I should note that Security Innovation, which owns the patents for NTRU and
which I work for, has announced an intent to make the NTRUEncrypt IP public
domain. A formal announcement should follow shortly.

Cheers,

William

On Tue, Mar 14, 2017 at 1:31 PM, Tams, Benjamin <[email-masked]>
wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Watson Ladd <[email-masked]>
Date: Tue, 14 Mar 2017 19:38:31 -0700

> serve as a reference implementation?

Why should we preempt the current NIST postquantum standardization efforts?

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: "Tams, Benjamin" <[email-masked]>
Date: Wed, 15 Mar 2017 13:10:49 +0000

Hi William,

> I should note that Security Innovation, which owns the patents for NTRU and which I work for, has announced an intent to make the NTRUEncrypt IP public domain. A formal announcement should follow shortly.

Good to know. Is there already a timeline for making NTRUEncrypt IP public domain?

Kind regards,
Benjamin

---

From: "Tams, Benjamin" <[email-masked]>
Date: Wed, 15 Mar 2017 13:10:58 +0000

Hi Watson,

> Why should we preempt the current NIST postquantum standardization efforts?

According to the timeline suggested in 

http://csrc.nist.gov/groups/ST/post-quantum-crypto/workshops.html

first NIST standardization drafts  for postquantum key exchange algorithms will appear in 2023 - 2025. For the use cases that need long-term confidentiality of approx. 15 years (as mentioned in John's post) we should not wait 6-8 years before we can even start with implementing PQ-safe key exchange algorithms for these purposes.

I appreciate the efforts of NIST because the specification outputs will have passed a 3-5 year analysis phase and can then be considered more robust as post-quantum key exchange algorithms that we have today; and, maybe any specification that we can establish now, will eventually turn out to be vulnerable. On the other hand, if we implement a hybrid key exchange algorithm suitable for implementation, as in

we will not lose security but gain the possibility of having PQ-safety already in the near future. Furthermore, the draft already refers to four PQ-safe algorithms but only to one specific - NTRU.  Why not specify the remaining by CFRG? Not for recommending them as a final specification but for temporary using them in applications where PQ-safety is required already now.

Kind regards,
Benjamin

---

From: William Whyte <[email-masked]>
Date: Wed, 15 Mar 2017 09:36:55 -0400

I don't want to overcommit and disappoint, but we hope it'll be soon.

Cheers,

William

On Wed, Mar 15, 2017 at 9:10 AM, Tams, Benjamin <[email-masked]>
wrote:

> Hi William,
>
> > I should note that Security Innovation, which owns the patents for NTRU
> and which I work for, has announced an intent to make the NTRUEncrypt IP
> public domain. A formal announcement should follow shortly.
>

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 15 Mar 2017 17:24:26 +0200

> https://tools.ietf.org/html/draft-whyte-qsh-tls13-03

Briefly read that document. Some quick comments:

- Looks quite confusing. Especially the parts about HelloRetryRequest.
  But looking closer, that message is not used except for handling
  missed algorithm guess, right? So that if client guesses right (and
  it can make multiple guesses at cost of computation and bandwidth)
  there might not be HRR, right?
- I don't think extending TLS extensions past 64kB is feasible.
  Especially in ClientHello It would require changes with nasty
  side-effects.
- The document looks to be made for older draft of TLS 1.3. The
  way key is combined is bit unclear. I presume the key mixing
  should be done in two steps (adding a new step into TLS 1.3
  key schedule, as the two existing mixing steps are already
  used for PSK and DH) because that's likely the easiest to
  implement.
- Adding new handshake messages should be avoided, but AFAICT,
  there are none added.

-Ilari

---

From: William Whyte <[email-masked]>
Date: Wed, 15 Mar 2017 11:31:15 -0400

There's a new draft of that document on the way, which has been developed
in collaboration with some other stakeholders and should be more up-to-date
wrt TLS 1.3. Again, not to overpromise, but hopefully by the end of next
week.

Cheers,

William

---

From: John Mattsson <[email-masked]>
Date: Wed, 15 Mar 2017 17:08:27 +0000

TLS 1.3 forbids static RSA for a reason, draft-whyte-qsh-tls13-03 seems to
bring it back in the form of static NTRUEncrypt. I see no reason to do
that. If someone wants to do early PCQ in TLS 1.3, I think the two lattice
based protocols suggested by David McGrew (Frodo, New Hope) as well as
Supersingular Elliptic Curve Igogeny Diffie-Hellman (SIDH) is the way to
go. The lattice-based variants are fast while SIDH has much smaller
ephemeral keys.

John

---

From: William Whyte <[email-masked]>
Date: Wed, 15 Mar 2017 13:28:17 -0400

That draft is in the process of being updated, but it was never intended to
propose static NTRU keys; if it looks like it does, it needs to be
clarified. NTRU key generation is fast enough that there's no need to avoid
ephemeral keys.

Cheers,

William

---

From: Aaron Zauner <[email-masked]>
Date: Wed, 22 Mar 2017 00:27:16 +0100

Hi,

Quick comment:

> On 14 Mar 2017, at 18:31, Tams, Benjamin <[email-masked]> wrote:
> 
> Hi John,
> 

NewHope has been implemented in Tor and also in Chrome for testing purposes. As for StrongSwan: they implement quite a lot. There's also a NTRU IKE implementation available in StrongSwan (https://wiki.strongswan.org/projects/strongswan/wiki/NTRU). Just because there's an implementation of something doesn't necessarily warrant work on an internet draft/standard. To me PQC is quite a new field and security boundaries are not as established as they're for say symmetric or public key cryptography (someone correct me if I've missed major news in that area). BTW there was a recent paper with some "improved" attacks on NewHope (it doesn't break the scheme, they just recommend more conservative parameter choices) - https://eprint.iacr.org/2017/221

Aaron

---

From: "Tams, Benjamin" <[email-masked]>
Date: Wed, 22 Mar 2017 10:54:06 +0000

Hi Aaron,

> NewHope has been implemented in Tor and also in Chrome for testing purposes.
> As for StrongSwan: they implement quite a lot. There's also a NTRU IKE implementation
> available in StrongSwan (https://wiki.strongswan.org/projects/strongswan/wiki/NTRU). 
> Just because there's an implementation of something doesn't necessarily warrant work
> on an internet draft/standard.

The other way round does neither: Just because there are Internet Drafts specifying
PQ-safe key exchange algorithms, this does not mean they have to be implemented. Anyway,
existing implementations are indications for the need of PQ-safe key exchange algorithms. 
Therefore, in my view, it is reasonable to specify Internet Drafts for state-of-the-art
PQ-safe key exchange algorithms suitable for implementation.

> To me PQC is quite a new field and security boundaries are not as established as they're
> for say symmetric or public key cryptography (someone correct me if I've missed major
> news in that area).

I agree. But as I mentioned in an earlier post (https://www.ietf.org/mail-archive/web/cfrg/current/msg09070.html)
we will not lose anything on security if we couple candidates for PQ-safe key exchange
algorithms with classical key exchange algorithms. Not for recommending them as a final
specification but for temporarily using them in applications where PQ-safety is needed.

As I noted above, it depends on the application whether a hybrid key exchange algorithm
is used that has the chance of being PQ-secure at the cost of increased key size and
increased running complexity. But if for an application one is willing to have that trade-off,
specifications for candidates of PQ-safe key exchange algorithms would be very useful. Again,
not for recommending them as a final specification but for temporarily using them in
applications where PQ-safety is needed.

> BTW there was a recent paper with some "improved" attacks on  NewHope (it doesn't
> break the scheme, they just recommend more conservative parameter choices) - 
> https://eprint.iacr.org/2017/221

@CFRG: Is there anyone interested in specifying PQ-safe key exchange algorithms at the
state of the art suitable for implementation 
(e.g., implementations of protocols as https://tools.ietf.org/html/draft-whyte-qsh-tls13-03)?

Kind regards,
Benjamin

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 22 Mar 2017 12:26:17 +0000

Hi,

This e-mail I sent back on 15th March laying out the CFRG leadership's
current position on post-quantum algorithms does not appear to have made
it into the CFRG archive and perhaps did not make it to the list. It seem
pertinent to send it again, in view of an on-going discussion on the list.

Regards

Kenny 

On 15/03/2017 08:23, "Paterson, Kenny" <[email-masked]> wrote:

>Hi Benjamin,
>
>Full disclosure: I am involved in one proposal being prepared for the NIST
>process.
>
>
>Wearing my CFRG co-chair's hat, I would say that Watson is correct, in the
>sense that the current CFRG approach is to define RFCs for a few
>relatively mature post-quantum primitives, such as hash-based signatures,
>but to wait for the results of the NIST process for everything else.
>
>The NIST process is going to run for many years - it just started, and is
>slated at 5-7 years. It will entail a significant effort by the research
>community, which is right and proper given the current state of the field.
>
>Regards,
>
>Kenny
>
>On 15/03/2017 02:38, "Cfrg on behalf of Watson Ladd"
><[email-masked] on behalf of [email-masked]> wrote:
>
>>>https://github.com/strongswan/strongswan/tree/master/src/libstrongswan/p
>>>l
>>>ugins/newhope
>>>

---

From: William Whyte <[email-masked]>
Date: Wed, 22 Mar 2017 08:34:25 -0400

Hi Kenny,

I didn't see that mail, thanks for forwarding.

>> The other way round does neither: Just because there are Internet Drafts
specifying
PQ-safe key exchange algorithms, this does not mean they have to be
implemented. Anyway,
existing implementations are indications for the need of PQ-safe key
exchange algorithms.
Therefore, in my view, it is reasonable to specify Internet Drafts for
state-of-the-art
PQ-safe key exchange algorithms suitable for implementation.

There are organizations that need to plan for a migration now in order to
properly manage risk and that can't wait for the NIST process to complete.
Providing an interoperability specification for PQ algorithms to be used in
a hybrid context allows these organizations to start development and
prototype deployment.

I'm not sure the "current CFRG approach" has been formally decided on; it's
more "what CFRG happens to be doing at the moment". If CFRG members see
value in specifying a wider range of algorithms, the CFRG approach can be
changed.

Cheers,

William

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 22 Mar 2017 14:36:04 +0000

Hi William,

You are right that there's no formally agreed approach for CFRG, but the
current approach that the *leadership* of CFRG (i.e. the co-chairs) would
like to take is that explained in my message below. But we can of course
revisit the question as a research group.

To reiterate: I would consider it a mistake for CFRG to go down the route
of standardising PQ algorithms ahead of the NIST process, aside from in
mature areas like hash-based signatures where we have a lot of research
that we can draw on. For me, the rest of the field is in too much of a
state of flux, and the expertise that might otherwise be available is
(rightly) focussed on the NIST process with its (rightly) much longer
timescales. 

I would welcome a CFRG-wide decision to look at "an interoperability
specification for PQ algorithms to be used in a hybrid context" as you put
it. But that's not the same as looking at PQ algorithms. Let's not
conflate/confuse them.

Further comments/discussion very welcome - as always.

Cheers,

Kenny 

On 22/03/2017 12:34, "William Whyte" <[email-masked]> wrote:

>properly manage risk and that can't wait for the NIST process to
>complete. Providing an interoperability specification for PQ algorithms
>to be used
> in a hybrid context allows these organizations to start development and
>prototype deployment.
>
>
>I'm not sure the "current CFRG approach" has been formally decided on;
>it's more "what CFRG happens to be doing at the moment". If CFRG members
>see value in specifying a wider range of algorithms, the CFRG approach
>can be
> changed.
>
>
>Cheers,
>
>
>William
>
>
>
>
>
>
>
>
>On Wed, Mar 22, 2017 at 8:26 AM, Paterson, Kenny
><[email-masked]> wrote:
>
>Hi,
>
><https://tools.ietf.org/html/draft-fluhrer-qr-ikev2-03>
>>>> 
><https://tools.ietf.org/html/draft-whyte-qsh-tls13-03>
>>>>
><https://tools.ietf.org/html/draft-whyte-qsh-tls13-03>
><https://www.irtf.org/mailman/listinfo/cfrg>
>>>
>>>
>>>
>>>--