Subject: [Cfrg] Applied Quantum Resistant Crypto

From: "Dr. Pala" <[email-masked]>
Date: Tue, 17 Jul 2018 15:35:05 -0400

Hi all,

I was wondering if there are people interested in setting up some sort
of discussion forum where to discuss the deployment (from a practical
point of view) for QRC in their systems. The intent here would be to
share the experiences, provide feedback, and possibly even share
implementations/references/etc.

Moreover, being this quite a new field when it comes to real-world
applications, it would be interesting to understand the new requirements
so that we can plan for algorithm agility correctly and not having to go
through what we suffered in the past (and in some cases with current
protocols) to upgrade/switch among different schemes/algorithms.

For example, some of the topics might include:

  * How to deploy PKI services
  * Mixed environments considerations (QRC and "Traditional" Crypto)
  * Mixed environments (stateful vs. stateless)
  * Encryption and Key-Exchange for QRC - what are the options there (it
    seems auth is well understood, but other problems are still open)?
  * Are there implications for the deployment of PKIs we need to be
    aware of and are not currently mentioned/addressed?
  * Any real-world deployment out there (or plans for it)?
  * Algorithm Agility, what to plan for?
  * Applicability to Revocation Services

Most of the activities to standardize QRC in CMS/SecFirmware/etc. that I
can see are related to the use of Stateful HASHSIG and I have not seen
any "standardization" activities around stateless schemes (e.g.,
SPHINCS), but if I am wrong, please let me know (and if you could
provide some interesting links, that would be great). I think it would
be useful to understand how to practically deploy these new schemes and
how to refine / provide the building blocks required for their
implementation and deployment.

Here's some references:

Merkle Tree Signatures (Stateful):

  * https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/
  * https://datatracker.ietf.org/doc/draft-housley-cms-mts-hash-sig/
  * https://www.ietf.org/id/draft-housley-suit-cose-hash-sig-04.txt
  * https://datatracker.ietf.org/doc/rfc8391/ (XMSS)
  * https://eprint.iacr.org/2018/063 (Viability of Post Quantum X.509
    Certs Paper)

  * Implementations:
      o https://github.com/cisco/hash-sigs

SPHINCS Related (Stateless):

  * https://sphincs.org/

  * Implementations:
      o https://sphincs.org/data/sphincs+-reference-implementation-20180313.tar.bz2

Other Relevant Links:

  * https://datatracker.ietf.org/doc/draft-truskovsky-lamps-pq-hybrid-x509/
  * https://csrc.nist.gov/Projects/Post-Quantum-Cryptography
  * http://test-pqpki.com/

I guess this is all for now - you can reply privately at the following
addresses:

    [email-masked]
    [email-masked]

Thanks,
Max

-- 
Best Regards,
Massimiliano Pala, Ph.D.
OpenCA Labs Director
OpenCA Logo

---

From: CJ Tjhai <[email-masked]>
Date: Tue, 17 Jul 2018 21:08:26 +0100

Hi Max,

There is also an experimental work on hybrid post-quantum key-exchange for
IKEv2 VPN. The work was done on a forked of strongSwan and it is available
here: https://github.com/post-quantum/strongswan/commits/qske and it works
on Linux, Android and OS X. It relies on the post-quantum libraries that is
available at this repository: https://github.com/post-quantum/nistpqc,
which contains a number of post-quantum algorithms submitted as part of
NIST standardization. Not all submitted algorithms are included, but it's
pretty straightforward to add additional ones.

This experimental work implements version 00 of this IETF draft:
https://datatracker.ietf.org/doc/draft-tjhai-ipsecme-hybrid-qske-ikev2/. We
hope to update the experimental work once the draft is in a more mature
state.

Best regards,
CJ

On 17 July 2018 at 20:35, Dr. Pala <[email-masked]> wrote:

> Hi all,
>
> I was wondering if there are people interested in setting up some sort of
> discussion forum where to discuss the deployment (from a practical point of
> view) for QRC in their systems. The intent here would be to share the
> experiences, provide feedback, and possibly even share
> applications, it would be interesting to understand the new requirements so
> that we can plan for algorithm agility correctly and not having to go
>    - How to deploy PKI services
>    - Mixed environments considerations (QRC and "Traditional" Crypto)
>    - Mixed environments (stateful vs. stateless)
>    - Encryption and Key-Exchange for QRC - what are the options there (it
>    - Are there implications for the deployment of PKIs we need to be
>    - Any real-world deployment out there (or plans for it)?
>    - Algorithm Agility, what to plan for?
>    - Applicability to Revocation Services
>
> can see are related to the use of Stateful HASHSIG and I have not seen any
> "standardization" activities around stateless schemes (e.g., SPHINCS), but
> if I am wrong, please let me know (and if you could provide some
> interesting links, that would be great). I think it would be useful to
> understand how to practically deploy these new schemes and how to refine /
> provide the building blocks required for their implementation and
> deployment.
>
> Here's some references:
>
>    - https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/
>    - https://datatracker.ietf.org/doc/draft-housley-cms-mts-hash-sig/
>    - https://www.ietf.org/id/draft-housley-suit-cose-hash-sig-04.txt
>    - https://datatracker.ietf.org/doc/rfc8391/ (XMSS)
>    - https://eprint.iacr.org/2018/063 (Viability of Post Quantum X.509
>    Certs Paper)
>
>    - Implementations:
>       - https://github.com/cisco/hash-sigs
>
>    - https://sphincs.org/
>    - Implementations:
>    - https://sphincs.org/data/sphincs+-reference-
>       implementation-20180313.tar.bz2
>       <https://sphincs.org/data/sphincs+-reference-implementation-20180313.tar.bz2>
>
> Other Relevant Links:
>
>    - https://datatracker.ietf.org/doc/draft-truskovsky-lamps-pq-
>    hybrid-x509/
>    - https://csrc.nist.gov/Projects/Post-Quantum-Cryptography
>    - http://test-pqpki.com/
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>

---

From: Kris Kwiatkowski <[email-masked]>
Date: Tue, 17 Jul 2018 22:28:28 +0100

Hi,

At Cloudflare we are currently implementing SIKE/SIDH in Go
(https://github.com/cloudflare/p751sidh/pulls). Next step will be to add
it to TLS 1.3 (https://github.com/cloudflare/tls-tris). We may want to
use it for some some other things.
I'm definitely interested in discussion regarding QRC in real-world crypto.

Kind regards,
Kris Kwiatkowski

On 7/17/18 8:35 PM, Dr. Pala wrote:
> applications, it would be interesting to understand the new
> requirements so that we can plan for algorithm agility correctly and
> not having to go through what we suffered in the past (and in some
> cases with current protocols) to upgrade/switch among different
> schemes/algorithms.
>
>   * Encryption and Key-Exchange for QRC - what are the options there
>     (it seems auth is well understood, but other problems are still open)?
> Most of the activities to standardize QRC in CMS/SecFirmware/etc. that
> I can see are related to the use of Stateful HASHSIG and I have not
> seen any "standardization" activities around stateless schemes (e.g.,
> be useful to understand how to practically deploy these new schemes
> and how to refine / provide the building blocks required for their

-- 
Kris Kwiatkowski
Cryptography Engineer
Cloudflare

---

From: "Panos Kampanakis (pkampana)" <[email-masked]>
Date: Wed, 18 Jul 2018 03:01:14 +0000

Hi Kris,

Thank you for the update. Interested to see your results and SIKE’s performance.

Were you thinking to use SIKE in TLS 1.3 a similar manner to the one proposed in https://tools.ietf.org/html/draft-whyte-qsh-tls13-06 which uses a hybrid approach (traditional+QRC) KEM?

Also, SIKE has pretty small keys, but performance is much higher. From the reference benchmarks performance SIKE seemed to be 10^4 more expensive than the best candidate that does not have prohibitive KEM pk and ciphertext sizes. Any reason why you chose SIKE that you can share?

Rgs,
Panos

From: Cfrg [mailto:[email-masked]] On Behalf Of Kris Kwiatkowski
Sent: Tuesday, July 17, 2018 5:28 PM
To: [email-masked]
Subject: Re: [Cfrg] Applied Quantum Resistant Crypto

Hi,

At Cloudflare we are currently implementing SIKE/SIDH in Go (https://github.com/cloudflare/p751sidh/pulls). Next step will be to add it to TLS 1.3 (https://github.com/cloudflare/tls-tris). We may want to use it for some some other things.
I'm definitely interested in discussion regarding QRC in real-world crypto.

Kind regards,
Kris Kwiatkowski

Hi all,

I was wondering if there are people interested in setting up some sort of discussion forum where to discuss the deployment (from a practical point of view) for QRC in their systems. The intent here would be to share the experiences, provide feedback, and possibly even share implementations/references/etc.

Moreover, being this quite a new field when it comes to real-world applications, it would be interesting to understand the new requirements so that we can plan for algorithm agility correctly and not having to go through what we suffered in the past (and in some cases with current protocols) to upgrade/switch among different schemes/algorithms.

  *   How to deploy PKI services
  *   Mixed environments considerations (QRC and "Traditional" Crypto)
  *   Mixed environments (stateful vs. stateless)
  *   Encryption and Key-Exchange for QRC - what are the options there (it seems auth is well understood, but other problems are still open)?
  *   Are there implications for the deployment of PKIs we need to be aware of and are not currently mentioned/addressed?
  *   Any real-world deployment out there (or plans for it)?
  *   Algorithm Agility, what to plan for?
  *   Applicability to Revocation Services

Most of the activities to standardize QRC in CMS/SecFirmware/etc. that I can see are related to the use of Stateful HASHSIG and I have not seen any "standardization" activities around stateless schemes (e.g., SPHINCS), but if I am wrong, please let me know (and if you could provide some interesting links, that would be great). I think it would be useful to understand how to practically deploy these new schemes and how to refine / provide the building blocks required for their implementation and deployment.

Here's some references:

  *   https://eprint.iacr.org/2018/063 (Viability of Post Quantum X.509 Certs Paper)
  *   Implementations:

     *   https://github.com/cisco/hash-sigs

  *   https://sphincs.org/
  *   Implementations:

     *   https://sphincs.org/data/sphincs+-reference-implementation-20180313.tar.bz2

Other Relevant Links:

I guess this is all for now - you can reply privately at the following addresses:

    [email-masked]<mailto:[email-masked]>
    [email-masked]<mailto:[email-masked]>

Thanks,
Max
--
Best Regards,
Massimiliano Pala, Ph.D.
OpenCA Labs Director
[OpenCA Logo]

Cfrg mailing list

[email-masked]<mailto:[email-masked]>

--

Kris Kwiatkowski

Cryptography Engineer

Cloudflare

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 18 Jul 2018 11:10:43 +0300

On Wed, Jul 18, 2018 at 03:01:14AM +0000, Panos Kampanakis (pkampana) wrote:
> Were you thinking to use SIKE in TLS 1.3 a similar manner to the one
> proposed in https://tools.ietf.org/html/draft-whyte-qsh-tls13-06
> which uses a hybrid approach (traditional+QRC) KEM?

My own experiments on PQC (very small scale) have included:

- HILA5+X25519 for key exchange in TLS 1.3.
- LAKE(+X25519) for key exchange in TLS 1.3.
- Falcon for signatures in TLS 1.3.
- Dilithium for signatures in TLS 1.3.
- Pushing Firefox 52 ESR (version is weird, this one supports -draft28,
  not -draft18 52ESR is supposed to have disabled-by-default) to the
  breaking point. The one I discovered was that 65536 by certificate
  or larger breaks it.

The way I implemented hybrids was just to stick public key or
ciphertext for KEM in the same key share payload as X25519 public key.

Rationale for HILA5 was that it was the first CPA PQC KEM I found
that:

- Had small enough keys and ciphertexts (fits into TLS record without
  fragmentation).
- Open enough reference implementation that was a proper library or
  easy to modify to be a proper library.

Later for LAKE, the rationale was:

- Had small enough keys and ciphertexts for fitting the TLS CH/SH into
  one packet.
- Should admit implementation with decent speed using AES instructions.
- No known IPR (funkily enough, some of the authors have one of the most
  annoying pieces of IPR when it comes to PQC).

The reference implementation was in C++, and this was not acceptable,
so I wrote my own implementation (the code looks horrible). This
implementation is quite a bit faster than the timings reported for the
reference one, but no order of magnitude improvement (since the library
reference implementation uses for most operations is optimized).

Rationale for Falcon:

- There was a open enough library available.
- The most compact signatures for in NISTPQC.

Rationale for Dilithium:

- No known IPR (Falcon has known IPR).
- The second most compact signatures in NISTPQC.

The reference implementation only supported one variant at at a time,
so I ported the reference implementation to Rust, at the same time
removing the one-variant restriction.

The reason for finding breaking points of Firefox was to see what would
be acceptable for signatures if one used scheme similar to what was
proposed in draft-truskovsky-lamps-pq-hybrid-x509. The only relevant
restriction I found was that certificates had to be 65535 bytes or less
or Firefox would WSOD. I did not find other limits like limit on
individual size of an extension. 

I think testing other browsers and non-browser clients for similar
limits would be valuable, to discover what NISTPQC signature schemes
are acceptable. Be creative in making the testcases, as the dominant
limit can vary from client to client. The reason why one wants
something like hybrid-x509 is that anything like past two algorithm
transitions for WebPKI would be not acceptable if large quatum
computers would be coming around in 15 years. 

Yes, with TLS 1.0 and 1.1 already dying, one could try to use the
more advanced TLS 1.2 and 1.3 algorithm negotiation, but I am
concerned how well it would work in real world due to missing
server support in most servers.

Because Certificate Transparency is also coming, and frequently
is stapled into certificates, I internally used 1 key + 5 signatures
in 60kB as the criteria. The unbroken NISTPQC algorithms that can
meet this are (AFAICT):

- Falcon
- Dilithium
- pqNTRUsign
- qTESLA (heuristic only)
- LUOV

(Original round 1 submissions also had WalnutDSA and RankSign, but
both were broken far beyond what simple parameter tweaks can fix).

-Ilari

---

From: Kris Kwiatkowski <[email-masked]>
Date: Wed, 18 Jul 2018 10:45:55 +0100

Hi Panos,

Definitely hybrid approach, I just quickly looked at a draft, but I it's
good base. Nevertheless
I'm planning to start TLS part somewhere next week and maybe.

In fact, we would like to experiment with many different KEMs (based on
different hard problems).
At a time SIDH looked quite promising (indeed key sizes). It is simply
first one to try. It's also
interesting to see if work done around ECC could be "reused" for some
parts of QR algorithms.

Kind regards,
Kris

On 7/18/18 4:01 AM, Panos Kampanakis (pkampana) wrote:
> proposed in https://tools.ietf.org/html/draft-whyte-qsh-tls13-06 which
> uses a hybrid approach (traditional+QRC) KEM?
>
>  
>
> Also, SIKE has pretty small keys, but performance is much higher. From
> the reference benchmarks performance SIKE seemed to be 10^4 more
> expensive than the best candidate that does not have prohibitive KEM
> pk and ciphertext sizes. Any reason why you chose SIKE that you can share?
>
>  
>
> Rgs,
>
> Panos
>
>  
>
>  
>
> *From:*Cfrg [mailto:[email-masked]] *On Behalf Of *Kris Kwiatkowski
> *Sent:* Tuesday, July 17, 2018 5:28 PM
> *To:* [email-masked]
> *Subject:* Re: [Cfrg] Applied Quantum Resistant Crypto
>
>  
>
> Hi,
>
> (https://github.com/cloudflare/p751sidh/pulls). Next step will be to
> add it to TLS 1.3 (https://github.com/cloudflare/tls-tris). We may
> want to use it for some some other things.
>     I was wondering if there are people interested in setting up some
>     sort of discussion forum where to discuss the deployment (from a
>     practical point of view) for QRC in their systems. The intent here
>     would be to share the experiences, provide feedback, and possibly
>     even share implementations/references/etc.
>
>     requirements so that we can plan for algorithm agility correctly
>     and not having to go through what we suffered in the past (and in
>     some cases with current protocols) to upgrade/switch among
>     different schemes/algorithms.
>
>       * Encryption and Key-Exchange for QRC - what are the options
>         there (it seems auth is well understood, but other problems
>         are still open)?
>       * Are there implications for the deployment of PKIs we need to
>         be aware of and are not currently mentioned/addressed?
>     Most of the activities to standardize QRC in CMS/SecFirmware/etc.
>     that I can see are related to the use of Stateful HASHSIG and I
>     have not seen any "standardization" activities around stateless
>     schemes (e.g., SPHINCS), but if I am wrong, please let me know
>     (and if you could provide some interesting links, that would be
>     great). I think it would be useful to understand how to
>     practically deploy these new schemes and how to refine / provide
>     the building blocks required for their implementation and deployment.
>
>     Here's some references:
>
>         [email-masked] <mailto:[email-masked]>
>         [email-masked] <mailto:[email-masked]>
>
>     Thanks,
>     Max
>
>     -- 
>
>     Best Regards,
>
>     Massimiliano Pala, Ph.D.
>     OpenCA Labs Director
>
>     OpenCA Logo
>
>
>
>     [email-masked] <mailto:[email-masked]>
>

-- 
Kris Kwiatkowski
Cryptography Engineer
Cloudflare

---

From: Douglas Stebila <[email-masked]>
Date: Tue, 24 Jul 2018 22:23:17 -0400

Hi Kris and Panos,

As part of our Open Quantum Safe project (https://github.com/open-quantum-safe), we have made a variety of prototypes of post-quantum key exchange (hybrid or PQ-only) and post-quantum signatures in (modifications to) OpenSSL and OpenSSH. 

In particular we have:
- hybrid key exchange in TLS 1.2 via modifications to OpenSSL 1.0.2 (see the "OQS-OpenSSL_1_0_2-stable" branch in our openssl fork)
- hybrid and PQ-only key exchange in TLS 1.3 via modifications to OpenSSL 1.1.1  (see the "OQS-master" branch in our openssl fork)
- PQ-only auth in TLS 1.3 via modifications to OpenSSL 1.1.1  (see the "OQS-master" branch in our openssl fork)
- hybrid and PQ-only key exchange in SSH 2 via modifications to OpenSSH 

All of this is built on our core library "liboqs", which provides a variety of PQ KEMs and signature schemes.

There are a few different versions and we are in the middle of some refactoring, so if it is hard to find what you are looking for, feel free to email me and I can explain what's going on.  Happy to discuss further and certainly welcome any ideas or participation.

Douglas

> On Jul 18, 2018, at 5:45 AM, Kris Kwiatkowski <kris=[email-masked]> wrote:
> 
> Hi Panos,
> 
> Definitely hybrid approach, I just quickly looked at a draft, but I it's good base. Nevertheless
> In fact, we would like to experiment with many different KEMs (based on different hard problems). 
> At a time SIDH looked quite promising (indeed key sizes). It is simply first one to try. It's also
> interesting to see if work done around ECC could be "reused" for some parts of QR algorithms.
> 
> Kind regards,
> Kris
> 
> 
>> Were you thinking to use SIKE in TLS 1.3 a similar manner to the one proposed inhttps://tools.ietf.org/html/draft-whyte-qsh-tls13-06 which uses a hybrid approach (traditional+QRC) KEM?
>>  
>> 	• How to deploy PKI services
>> 	• Mixed environments considerations (QRC and "Traditional" Crypto)
>> 	• Mixed environments (stateful vs. stateless)
>> 	• Encryption and Key-Exchange for QRC - what are the options there (it seems auth is well understood, but other problems are still open)?
>> 	• Are there implications for the deployment of PKIs we need to be aware of and are not currently mentioned/addressed?
>> 	• Any real-world deployment out there (or plans for it)?
>> 	• Algorithm Agility, what to plan for?
>> 	• Applicability to Revocation Services
>> 	• https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/
>> 	• https://datatracker.ietf.org/doc/draft-housley-cms-mts-hash-sig/
>> 	• https://www.ietf.org/id/draft-housley-suit-cose-hash-sig-04.txt
>> 	• https://datatracker.ietf.org/doc/rfc8391/ (XMSS)
>> 	• https://eprint.iacr.org/2018/063 (Viability of Post Quantum X.509 Certs Paper)
>> 	• Implementations:
>> 		• https://github.com/cisco/hash-sigs
>> 	• https://sphincs.org/
>> 	• Implementations:
>> 		• https://sphincs.org/data/sphincs+-reference-implementation-20180313.tar.bz2
>> Other Relevant Links:
>> 
>> 	• https://datatracker.ietf.org/doc/draft-truskovsky-lamps-pq-hybrid-x509/
>> 	• https://csrc.nist.gov/Projects/Post-Quantum-Cryptography
>> 	• http://test-pqpki.com/