<div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Aug 19, 2016 at 4:23 PM, Rhys Weatherley <span dir="ltr"><<a href="mailto:rhys.weatherley@gmail.com" target="_blank">rhys.weatherley@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div><div><div><div><div>I have created draft documents for two extensions to Noise based on previous discussions on the list:<br><br></div>Additional forward secrecy:<br>    <a href="https://github.com/rweather/noise_spec/blob/forward_secrecy/extensions/ext_forward_secrecy.md" target="_blank">https://github.com/rweather/<wbr>noise_spec/blob/forward_<wbr>secrecy/extensions/ext_<wbr>forward_secrecy.md</a><br><br></div>New Hope:<br>    <a href="https://github.com/rweather/noise_spec/blob/forward_secrecy/extensions/ext_newhope.md" target="_blank">https://github.com/rweather/<wbr>noise_spec/blob/forward_<wbr>secrecy/extensions/ext_<wbr>newhope.md</a><br><br></div></div></div></div></div></blockquote><div><br></div><div><br></div><div>Sorry for delay - thanks for putting these together, they bring up important questions:</div><div><br></div><div><br></div><div>PQ algorithms and document status</div><div>---</div><div>I think it's working well to have a small and stable set of algorithms in the main spec.</div><div><br></div><div>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.</div><div><br></div><div>However, we *should* extend the framework for them, and have some choices for people willing to live on the bleeding-edge.</div><div><br></div><div><br></div><div>Overall approach</div><div>---</div><div>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":</div><div><br></div><div>Noise[PSK]_PATTERN[transformation]_DH_CIPHER_HASH</div><div><br></div><div>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.</div><div><br></div><div>We previously discussed whether to treat a DH+PQ scheme as:</div><div> (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. </div><div> (B) Separate functions triggered by their own tokens ("f" and "dhff", for example).</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>But if we're going this route, I wonder if we should go all the way to (B):</div><div><br></div><div> * 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".</div><div><br></div><div>Noise_XX</div><div>  -> e </div><div>  <- e, dhee, s, dhse</div><div>  -> s, dhse</div><div><br></div><div>Noise_XXhfs(s, rs):</div><div>  -> e, f </div><div>  <- e, dhee, f, dhff, s, dhse</div><div>  -> s, dhse</div><div><br></div><div>(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, ...").  </div><div><br></div><div> * The pattern name continues to determine the SymmetricState calls, as currently.</div><div><br></div><div> * This avoids redefining the existing "e" and "dhee" tokens.</div><div><br></div><div> * The pattern notation makes the the exact sequence of steps more clear.</div><div><br></div><div><br></div><div>Naming and separator chars</div><div>---</div><div>If we go with pattern transformations and explicit tokens ("f", "dhff"), we still have the problems of:</div><div> - indicating multiple pattern transformations, like "noidh" with "hfs" (this is an existing problem)</div><div> - indicating multiple public-key functions, like "25519" with "NewHope"</div><div><br></div><div>Brian points out that using "+" makes Noise protocol names invalid tokens in a lot of programming languages.</div><div><br></div><div>I'm not sure if there are good alternatives that avoid this, however.  Using more underscores makes parsing more complicated and context-sensitive.</div><div><br></div><div>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:</div><div><br></div><div><br></div><div>  Noise_XXhfs+noidh_25519+NewHope_AESGCM_SHA256</div><div><br></div><div><br></div><div>  Noise_XXhfs&noidh_25519&NewHope_AESGCM_SHA256</div><div><br></div><div><br></div><div>  Noise_XXhfs,noidh_25519,NewHope_AESGCM_SHA256</div><div><br></div><div><br></div><div><br></div><div>Encrypting the forward-secrecy values</div><div>---</div><div>Ephemeral DH public keys are not encrypted, because:</div><div><br></div><div>(1) They're random one-time values, so not much is gained by encrypting them.</div><div><br></div><div>(2) Avoids ciphertext expansion (32 byte key -> 48 byte ciphertext).</div><div><br></div><div>(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.</div><div><br></div><div>(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.</div><div><br></div><div><br></div><div>When considering hybrid forward secrecy, I'm not sure these points apply:</div><div><br></div><div>(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.</div><div><br></div><div>(2) Post-quantum keys seems to be significantly larger (~2 KB for NewHope), so ciphertext expansion matters less.</div><div><br></div><div>(3) Post-quantum algorithms might not support something like Elligator.</div><div><br></div><div>(4) The DH values suffice to randomize the keys.</div><div><br></div><div>I'm not sure I've thought this through, but maybe this argues for encrypting the PQ public values?</div><div><br></div><div><br></div><div>Trevor</div><div><br></div><div><br></div></div></div></div>