[noise] Post-Quantum Kyber and Noise

[Trevor Perrin]

On Mon, Jul 3, 2017 at 10:21 AM, Rhys Weatherley
<rhys.weatherley at gmail.com> wrote:
> There is a new post-quantum algorithm called Kyber, which comes from the
> same family as NewHope.  Where NewHope only supported DH-like ephemeral
> operations, Kyber is a key encapsulation method (KEM) that can be used for
> both ephemeral and static use cases.

Cool, Kyber looks like a nice advance in lattice crypto: not just more
functionality, but smaller keys and maybe more conservative crypto
choices.  Seems well worth experimenting with.


> I have thrown together a quick draft as to how Kyber could be used for
> Hybrid Forward Secrecy (I haven't implemented this - it's all theoretical)
> in [3].  This uses Kyber in ephemeral-only mode to augment the forward
> secrecy of a classical DH-using Noise handshake.  But Kyber is of course
> capable of much more.
>
> To make the best use of Kyber, we need to think about how KEM's in general
> would work with Noise.

Yeah, this is definitely a good opportunity to think about
post-quantum beyond just forward-secrecy.

(And being able to handle "KEMs" also means we could incorporate RSA
or other public-key encryption, and do more SKEME-like protocols).


> Looking at the paper, some of the mechanics of authenticated key exchange
> would come for free from the way Noise's chaining key works.

Agreed - we have our own AKE framework and KDF, so we don't need that
part of the paper.  For example, their AKE in Figure 3 is roughly
this, in Noise notation:

-> s
<- s
...
-> e
<- e, ee, se, es

But of course, we can express more variations (zero-RTT encryption,
transmitting static keys, PSKs, etc).


> Off the top of my head: if we had ekem and skem tokens for example, we could
> treat the ephemeral and static parts of the exchange separately and then get
> the authenticated aspect by chaining together applications of MixKey() in
> the appropriate order.

My first thought is maybe we can view KEM operations as just
"restricted" forms of ephemeral-ephemeral or ephemeral-static key
agreement.  The restrictions would be that the static key must be sent
before its corresponding "ephemeral" (the KEM ciphertext), and that
the "ephemerals"/"KEM ciphertexts" here are targeted towards a
particular recipient key, and can't be reused in multiple operations,
the way DH can.

In other words, KEMs can implement patterns like:
 -> e
 <- e, ee

or

 -> s
 <- e, se

The responder's "e" in both cases being a KEM ciphertext, and the "ee"
or "se" representing a key output from the "encapsulation" /
"decapsulation" algorithms.

We earlier talked about representing the ephemeral-ephemeral case as:
 -> f
 <- f, ff

If we want to generalize to also cover the ephemeral-static case, we
have some thinking to do.

To throw something out, a different notation could allow numbered sets
of public keys, with the keys in each numbered set only allowed to
interact with each other?  So instead of "f", hybrid forward-secrecy
could be:
 -> e1
 <- e1, e1e1

And hybrid, ephemeral-static encryption, done in the same protocol, could be:
 -> s2
 <- e2, s2e2

So if we wanted a hybrid post-quantum XX with PQ authentication *and*
PQ forward-secrecy, we'd get something like:

 -> e, e1
 <- e, e1, ee, e1e1, s, s2, es
 -> e2, e2s2, s, s3, se,
 <- e3, s3e3

Note that the PQ authentications (e2s2 and s3e3) happen later than
their conventional counterparts, because the KEM ordering restriction
prevents "ephemerals" being sent before the corresponding static.

This notation hides the distinction between KEM public keys and
ciphertexts, but has the advantage of being somewhat consistent with
our existing notation.

Thoughts?

Trevor