Re: [Cfrg] Applied Quantum Resistant Crypto

[Ilari Liusvaara <[e-mail]>]

On Wed, Jul 18, 2018 at 03:01:14AM +0000, Panos Kampanakis (pkampana) wrote:
> 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?
 

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