[noise] Symmetric-crypto overhaul and stateful hashing

[Trevor Perrin]

Hi Paul, thanks for thoughtful feedback:

On Tue, Nov 13, 2018 at 10:28 AM Paul Rösler <paul.roesler at rub.de> wrote:
...
> > Goals for symmetric-key overhaul:
...
>
> >  * Provide simpler hashing, so that Noise keys can be derived directly
> > as key = hash(inputs), without long sequences of nested hashing.
> I guess this refers to the API? Because otherwise we have two different
> primitives (one stateful, one stateless). If it refers to API, then I agree.

My bullet point was vague, but I like that in the case of "traditional
hashes", we'd be able to express the "k" keys as just like:

k1 = SHA256("Noise_..." || transcript)
k2 = SHA256("Noise_..." || longer transcript)
k3 = SHA256("Noise_..." || even longer transcript)
etc

without all the nested hashing h=HASH(HASH(HASH(... and
ck=KDF(KDF(KDF(... we currently do.


> >  * Allow for Sponge/STROBE-like algorithms where the hash object is
> > capable of "Duplex"-style encryption/decryption, so implementations
> > can minimize code size by using a single crypto primitive like Keccak.
> I'm like the idea of generalizing and combining compatible building
> blocks into a more abstract primitive. However, mixing more independent
> functionality into a primitive makes it complicated to define and
> understand security. As a secure key computation can always be composed
> with a secure cipher, I do not see the reason for putting both into one
> primitive (at least from a theoretical point of view).

Good question.  I think the main benefit is that for an object (like
STROBE) based on permutation-crypto (like Keccak), doing Encrypt()
would simultaneously absorb the input into the hash state.

So we would *not* have to do a separate Absorb(ciphertext) after
encrypting, since this would already be taken care of, giving some
simplicity and speed benefits.

I agree that it makes the analysis a lot more complicated, though.


> >  * Decouple "absorbing" from "ratcheting" so we can absorb inputs more
> > efficiently and only "ratchet" when needed for forward-secrecy.
> Sounds legit, however I am not sure whether this is understood well by
> all developers. So in order to prevent squeezing without ratcheting
> (i.e., one squeezes without using the new absorbed entropy), the API
> should take care of this (e.g., by always ratcheting if something was
> absorbed recently, but ratcheting was not actively invoked).

I wasn't very clear there either, I was thinking of "ratcheting" as an
operation that ensures all previous inputs are mixed together, so that
if the state has enough entropy it can't be "inverted" to recover any
old inputs.  So this would be done for forward-secrecy, whenever we've
used our keys for encryption/decryption and then have to wait a period
of time in which we might be compromised.

So with a traditional M-D hash this just means finishing the current
block of input.  With a permutation-based hash, this means absorbing
the next block of input *and* overwriting the sponge's "rate" with
some zeros, so the permutation can't be inverted.

I agree that deciding when to do this ratcheting is subtle, and
something we'd have to think about carefully.  Currently we just do it
on every HKDF, which is both too much and in some cases too little,
e.g. in XX it would be nice to ratchet after the responder's first
message, but Noise currently reuses the same k to process the
initiator's response.


> >  * Provide an abstract API to the underlying stateful hash which can
> > be implemented via traditional hashes (with or without HMAC/HKDF), as
> > well as STROBE or other sponge constructions.
> Totally agree.
>
> > Notes:
> >
> >  * Noise will never squeeze more than HASHLEN bytes of output, for
> > compatibility with traditional hashes.
> As you are aiming for a generic primitive, why should the squeeze
> operation not require its (hash-based) implementation to generate as
> much output as requested (e.g., by iteratively ratcheting and squeezing)?

I'd like the "traditional hash" implementation to just compile down to
a single hash call, ie a sequence of Absorbs followed by a Squeeze
should just turn into:

k = SHA256(absorb1 || absorb2 || ...)

If we required "extensibible", XOF-style output we'd have to use
HKDF-Expand or something here.  I think it's simpler for Noise to
produce different outputs by just appending different labels to every
output:

k = SHA256(absorb1 || absorb2 || ... || "k")
h = SHA256(absorb1 || absorb2 || ... || "h")

etc.

Trevor