[noise] Proposal for the Disco extension (Noise + Strobe)

[Trevor Perrin]

On Sat, Jul 22, 2017 at 11:06 PM, David Wong <davidwong.crypto at gmail.com> wrote:
>
> I released a new draft according to the feedback:
> https://github.com/mimoo/NoiseGo/blob/master/disco/specification.md


Nice, I like this direction.  I think you could go even further in
defining things via SymmetricState and CipherState:

 * "Channel Binding" and "Rekey" seem like they should be accomplished
via a SymmetricState.GetHash (or something) and CipherState.Rekey.

 * I'm not sure you need section 3, seems like some of that is
repeating things from Strobe, and the rest could just be inlined into
descriptions of a SymmetricState and CipherState implementation.

If you were to define a CipherState, we could also think about whether
the CipherState API should be modified to take explicit nonces to
support out-of-order / UDP protocols like Wireguard.  I'm not sure how
STROBE would support that?

Another thing I'm curious about is whether the permutation could be
run for fewer rounds when encrypting versus MixHash / MixKey steps.  I
think some constructions like "MonkeyDuplex" use more rounds when
absorbing the key and fewer rounds when encrypting.  That could make
sense in the Noise context as well.


> Some more answers inline:
>
>> It might be better to:
>>  * Leave HandshakeState alone
>>  * Treat Noise's SymmetricState and CipherState as "interfaces" and
>> describe how to re-implement them with Strobe.
>
> I thought about that and it seemed less elegant, but your point about
> extending the HandshakeState in future revisions of Noise is indeed a
> concern. It could be painful to constantly try to keep Disco
> up-to-date with Noise's HandshakeState in the future. If you think
> SymmetricState and CipherState are going to be more stable this sounds
> good.


Good question, we don't have an answer to that yet.  It's probably
more complicated than a single version number, since we'll need to
indicate that some parts of Noise are stable while other parts are
less so, and other extensions are being developed.

See the thread on "Document structure" which discusses some
possibilities for refactoring our documents to support this:

https://moderncrypto.org/mail-archive/noise/2017/thread.html

We'll have to come up with something soon, good extension documents
are starting to pile up without processes for them (Rhys' "hybrid
forward secrecy", Alexey's NoiseSocket, and DISCO).

I'll encourage everyone to think about the "Document structure" thread
and suggest ways forward.



>>  * Should MixKey operations be done with STROBE "KEY" instead of STROBE "AD"?
>
> There are two big differences between the KEY and the AD operations:
>
> 1. the KEY operation forces a permutation to happen
> 2. the KEY operation replaces the bytes of the new state (instead of
> XORing into it). This creates the forward secrecy
>
> I don't think it is a better operation, because of the following points:
>
> * this operation doesn't need to be influenced by the previous ones
> (so 1. is not needed)
> * forward secrecy is not needed at this stage (so 2. is not needed)
> * forcing a permutation at this point would slow down the handshake

The current KDF is capable of providing forward secrecy during the
handshake, i.e. it deletes and replaces old keys (ck,k) with new keys
derived via a one-way function.

The forward-secrecy property mostly isn't needed, because 0-RTT data
is currently encrypted with the responder's static and the initiator's
ephemeral, which can't be deleted right away.

But that might not always be the case.  For example we've talked about
resumption based on PSKs or published / short-lived "semi-ephemerals".
In that case it might be possible for the server to delete such values
after receiving a 0-RTT ciphertext.  Then forward-secure MixKey during
the handshake phase could have security benefit.

It seems like the cost of preserving this KDF property is low (just a
few extra permutations, during the handshake)?

I'll also bring out an argument from our previous HMAC/HKDF
discussions:  "Extra" hashing between KDF inputs isn't necessarily
wasted.  It's important that KDF inputs not be able to influence each
other, e.g. "cancel" other inputs, so if the hash function turns out
to be bad we might be happy to have "extra" hashing between the
inputs.


>>  * The Strobe specification mentions several STROBE instances (e.g.
> 128/1600, 256/800, etc).  The STROBE paper mentions even more
> generality, e.g. using STROBE with different sponges.  Do we want to
> generalize and extend the naming for different STROBE instances and
> other sponges?
>
> I've been talking to Mike Hamburg about this, I think we should indeed
> include the permutation in the name. It was actually part of the
> naming in prior versions of Strobe and was removed for some reasons.
>
> I love what Frank has done with libHydrogen (and what the Gimli team
> has done with Gimli), and in practice yes you can switch the
> permutation in Strobe since it already has three different ones
> (keccak-f[400], keccak-f[800] and keccak-f[1600]). (Now I would be
> careful with Gimli at the moment because the amount of cryptanalysis
> Keccak has received compared to this new permutation is way too
> important to ignore it due to "worse" performance.)

Agreed that Gimli is very new, and like any new symmetric crypto
primitive, it needs much more analysis before real use.

But I'd like to figure out our naming conventions for
permutation-based crypto, so Gimli as well as Keccak variants are good
test cases.

So how do we name all these?  It seems like we are combining some
underlying permutation (Gimli, Keccak) with some construction
("STROBE"; maybe "Hydrogen" or "MonkeyDuplex" or something):

Noise_XX_25519_STROBEv1.0.2/Keccak1600
Noise_XX_25519_STROBEv1.0.2/Keccak800
Noise_XX_25519_Hydrogen/Gimli

?

Trevor