[noise] Extensions for forward secrecy and New Hope

[Trevor Perrin]

On Fri, Aug 19, 2016 at 4:23 PM, Rhys Weatherley <rhys.weatherley at gmail.com>
wrote:

> I have created draft documents for two extensions to Noise based on
> previous discussions on the list:
>
> Additional forward secrecy:
>     https://github.com/rweather/noise_spec/blob/forward_
> secrecy/extensions/ext_forward_secrecy.md
>
> New Hope:
>     https://github.com/rweather/noise_spec/blob/forward_
> secrecy/extensions/ext_newhope.md
>
>

Sorry for delay - thanks for putting these together, they bring up
important questions:


PQ algorithms and document status
---
I think it's working well to have a small and stable set of algorithms in
the main spec.

Post-quantum lattice crypto is an active research area.  The relative
merits of (LWE, Ring-LWE/NewHope, NTRU, NTRU Prime, etc) are still being
debated.  I think we should view all these as "promising-but-experimental",
and not expect any of them in the main spec soon.

However, we *should* extend the framework for them, and have some choices
for people willing to live on the bleeding-edge.


Overall approach
---
You're using a "+" in the DH name to modify processing rules for hybrid
forward secrecy.  Our naming scheme is already complicated with "PSK" mode,
and "pattern transformations":

Noise[PSK]_PATTERN[transformation]_DH_CIPHER_HASH

Having another way to indicate modes, inside the DH name, makes this even
more complicated.  It also means that the pattern name no longer determines
the sequence of SymmetricState calls (MixHash, MixKey, etc) by itself.

We previously discussed whether to treat a DH+PQ scheme as:
 (A) A hybrid DH function that redefines the "e" token to send a hybrid
DH+PQ key, and redefines "dhee" to call MixKey() on the combined DH+PQ
output.
 (B) Separate functions triggered by their own tokens ("f" and "dhff", for
example).

Your current spec is in-between:  It calls MixHash() and MixKey()
separately for the PQ values, instead of concatenating them with the DH
values, but the sequence of calls is determined by redefining the rules for
"e" and "dhee", instead of by separate tokens.

It makes sense for SymmetricState to process the PQ and DH values
independently, particularly for MixKey():  We've designed the KDF to
produce secure output if any MixKey() input is secure, and we want to
ensure the PQ scheme can't worsen the DH.

But if we're going this route, I wonder if we should go all the way to (B):

 * The existing notion of "transformations" lets us indicate more clearly
that an existing pattern is being transformed to a pattern with hybrid
forward secrecy.  E.g. transform "dhee" -> "dhee, dhff" and transform "e"
-> "e, f".

Noise_XX
  -> e
  <- e, dhee, s, dhse
  -> s, dhse

Noise_XXhfs(s, rs):
  -> e, f
  <- e, dhee, f, dhff, s, dhse
  -> s, dhse

(Assuming "f" is encrypted we have to move it after the "dhee", as shown
here, to not violate pattern validity.  Your spec doesn't encrypt "f", in
which case the transformation is simpler - "e, f, dhee, dhff, ...").

 * The pattern name continues to determine the SymmetricState calls, as
currently.

 * This avoids redefining the existing "e" and "dhee" tokens.

 * The pattern notation makes the the exact sequence of steps more clear.


Naming and separator chars
---
If we go with pattern transformations and explicit tokens ("f", "dhff"), we
still have the problems of:
 - indicating multiple pattern transformations, like "noidh" with "hfs"
(this is an existing problem)
 - indicating multiple public-key functions, like "25519" with "NewHope"

Brian points out that using "+" makes Noise protocol names invalid tokens
in a lot of programming languages.

I'm not sure if there are good alternatives that avoid this, however.
Using more underscores makes parsing more complicated and context-sensitive.

So assuming we want some non-underscore separator for indicating a
combination of (pattern transformation, or public key algorithms), is there
something better than "+"?  Of the below, "+" looks best to me:


  Noise_XXhfs+noidh_25519+NewHope_AESGCM_SHA256


  Noise_XXhfs&noidh_25519&NewHope_AESGCM_SHA256


  Noise_XXhfs,noidh_25519,NewHope_AESGCM_SHA256



Encrypting the forward-secrecy values
---
Ephemeral DH public keys are not encrypted, because:

(1) They're random one-time values, so not much is gained by encrypting
them.

(2) Avoids ciphertext expansion (32 byte key -> 48 byte ciphertext).

(3) If the protocol needs to be indistinguishable from random, the
ephemeral public keys can be mapped to random values (e.g. Elligator).  And
at least one of them will probably be sent before any encryption is
possible, so supporting something like Elligator is probably necessary
regardless.

(4) The ephemeral public keys are used to randomize the PSK, and the
ephemeral DH outputs are used to randomize the other keys, so encryptions
performed before these randomizations might not be secure.


When considering hybrid forward secrecy, I'm not sure these points apply:

(1) DH has fairly fast key-generation, but some post-quantum algorithms
might not.  So it might be reasonable to generate a post-quantum ephemeral
once and use it repeatedly, in which case encrypting the post-quantum
ephemeral would have more value, since it prevents observation of this
reuse.

(2) Post-quantum keys seems to be significantly larger (~2 KB for NewHope),
so ciphertext expansion matters less.

(3) Post-quantum algorithms might not support something like Elligator.

(4) The DH values suffice to randomize the keys.

I'm not sure I've thought this through, but maybe this argues for
encrypting the PQ public values?


Trevor
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/noise/attachments/20160828/fc9105f0/attachment.html>