<div dir="ltr"> On Fri, Jul 15, 2016 at 9:33 AM, Rhys Weatherley <<a href="mailto:rhys.weatherley@gmail.com">rhys.weatherley@gmail.com</a>> 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?<div> </div><div> Trevor [1] <a href="https://eprint.iacr.org/2009/436.pdf">https://eprint.iacr.org/2009/436.pdf</a> [2] <a href="https://eprint.iacr.org/2016/461.pdf">https://eprint.iacr.org/2016/461.pdf</a> [3] <a href="https://web.eecs.umich.edu/~cpeikert/pubs/suite.pdf">https://web.eecs.umich.edu/~cpeikert/pubs/suite.pdf</a></div><div> </div></div>