[noise] Post-Quantum Noise with New Hope

[Trevor Perrin]

On Fri, Jul 15, 2016 at 9:33 AM, Rhys Weatherley <rhys.weatherley at gmail.com>
wrote:
> New Hope [1] seems to be the latest "it" PQ scheme, with Google
> investigating adding it to TLS.  So I did a little digging and
> experimenting.
[...]
>
> I've put the details on the method on the wiki [2]


Thanks!, that's a great exploration of different approaches to post-quantum
forward-secrecy in Noise.  Let's try to work through them and figure out
what's best:


(1) Split(SSK) - Per current spec, the PQ handshake is handled at the
application layer, which feeds a "secondary symmetric key" into Noise.  But
that's punting the problem, not solving it!

Also, mixing in the SSK at the end of the handshake doesn't protect
identity info exchanged during the handshake.


(2) Treat the PQ handshake as a DH:  Rhys combines this with (1), i.e. he
does a Noise_NN handshake using a PQ algorithm in the application layer,
then uses the result as an SSK to Split() the enclosing handshake.

A related approach which wouldn't require nesting Noise protocols would be
to define a "combined" DH function ("25519+NewHope" or something) where "e"
is actually a pair of (25519, NewHope) public values, and "dhee" performs
both 25519 and NewHope, and mixes together the results.

But in either case, does it make sense to treat NewHope as a DH function?
That's an interesting terminology question.  Rhys (and the NewHope authors)
argue that NewHope is DH-like.

The Noise spec actually has no definition of what a DH() function should
do!  That needs fixing, e.g. with terms like "Non-Interactive Key Exchange"
(NIKE) and "Gap-DH" or something to justify key reuse.

NewHope wouldn't meet those criteria:
 * Unlike a NIKE, NewHope required ordered messages: one party presents a
public key, and the other party gives them a value they can derive a shared
secret from.  Rhys finesses this ("unbalanced" vs "balanced" DH), but I
sort of feel that "balanced" aka "non-interactive" is the essence of DH.
Instead, NewHope seems more like a One-Pass Key Exchange (OPKE) or Key
Encapsulation Method (KEM) [1].  The KEM term is used in related works
(NewHope also uses it, so does NTRU-Prime [2], and Peikert [3]).

 * But unlike other OPKEs / KEMs, the NewHope public key is single-use.  So
we could call this an... "ephemeral KEM"?  Anyone have something better?

Anyways, because NewHope has ordering and single-use restrictions that
existing DH functions don't have, it feels awkward to pretend it's the same
as other DHs.  So that leaves...


(3)  Add new tokens for NewHope, and other post-quantum options.  For
example:

  "ekem1" - Sends the first NewHope message, or a similar one-time public
key from (SIDH, NTRU-Prime, etc).  Encrypts the value if "k" is present.

  "ekem2" - Sends the second NewHope message, or a similar encapsulated
key, that is combined with "ekem1" to produce a 32-byte key which is
provided to MixKey().  Encrypts the value if "k" is present.


We can easily transform any of the interactive patterns to use ekem:

Noise_XX(s, rs):                 Noise_XXekem(s, rs):
  -> e                                     -> e, ekem1, s
  <- e, dhee, s, dhse             <- e, ekem2, dhee, dhes, s, dhse
  -> s, dhse                           -> s, dhse

But if we want the ekem1/ekem2 values to be encrypted, maybe for
indistinguishability, we could also send them later:

Noise_XX(s, rs):                 Noise_XXekem+???(s, rs):
  -> e                                     -> e
  <- e, dhee, s, dhse             <- e, dhee, s, dhse, ekem1
  -> s, dhse                           -> s, dhse, ekem2


And we could name ekem protocols like:

  Noise_XXekem_25519+NewHope_ChaChaPoly_SHA256


Having "ekem1" and "ekem2" be encrypted if k exists (like static DH public
keys) lets us move them in or out of encryption, so that seems better than
treating them like DH ephemerals which are always in clear (DH ephemerals
have a special role to play in randomizing the encryption, thus can't be
encrypted themselves).


Anyways, I tentatively like the new tokens approach (3), *if* the semantics
of something like ekem1/ekem2 can be made a good-enough fit for the
most-likely PQ algorithms - which I'm not sure about?


Trevor

[1] https://eprint.iacr.org/2009/436.pdf
[2] https://eprint.iacr.org/2016/461.pdf
[3] https://web.eecs.umich.edu/~cpeikert/pubs/suite.pdf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/noise/attachments/20160715/020bb18f/attachment.html>