[noise] Symmetric-crypto overhaul and stateful hashing

[Trevor Perrin]

On Tue, Nov 13, 2018 at 6:58 PM Paul Rösler <paul.roesler at rub.de> wrote:
>
> On 13.11.18 19:06, Trevor Perrin wrote:
> >
> > 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 see that this saves one line of code and maybe (due to the allowed
> interleave of operations Enc and Absorb within STROBE-like
> constructions) a bit more efficiency.

To expand on the efficiency goal:

Noise does both authenticated-encryption *and* hashing of each
handshake payload.  Handshake payloads could be many KBs, e.g. if
doing 0-RTT encryption, or sending certificate chains in the payloads.

Since any ciphertext in the Noise handshake is going to get hashed,
there's a potential optimization to hash the ciphertext once but
simultaneously use that calculation for (1) the "authenticated" part
of "authenticated encryption", and (2) to update Noise's transcript
hash.

STROBE shows how to do that fairly naturally with permutation-style
crypto (like Keccak), using the "duplex" construction.  But you could
imagine this optimization with other algorithms, e.g. doing AES-CTR
(without GCM), and adding a hash-based authentication tag.

So one goal is to allow optimizations like this.


> > I agree that it makes the analysis a lot more complicated, though.
> It is maybe not only a bit more complicated for an analysis, but
> potentially also for developers and users less comprehensible regarding
> the primitive's idea: to me it is not really clear what the nature of a
> stateful hash with encryption is. The feature described above (absorbing
> during encryption) is from my point of view not really obvious to a user

That's a good point, we'd need to be clearer on what an Encrypt
function would do.

Roughly, I think that calling Encrypt(msg) on a Stateful Hash Object
("SHO") should have the same security properties as the sequence:
 * key = Squeeze'(32)
 * output = AEAD(key, msg)
 * Absorb(output)
 * return output

Where Squeeze' is just a variant of Squeeze() that returns independent
output (e.g. Squeeze and Squeeze' add padding that differs in 1 bit or
something, before processing the final hash block, so they return
different results).

If the SHO doesn't support an Encrypt() function, then Noise would use
something very close to the above sequence to encrypt things:
 * Clone() the state, and then operate on the clone:
 * Absorb("k")
 * key = Squeeze(32)
 * output = AEAD(key, msg)
 * Absorb(output)
 * return output

The only differences are for domain-separation:
 * SHO.Encrypt() uses Squeeze' so that its internal processing won't
collide with any other values calculated by users of the SHO.
 * Noise would clone and then append "k" so that Noise can perform
domain-separation by appending a different type byte before squeezing
any output.

So SHO.Encrypt() would have equivalent security properties to a
Squeeze/Encrypt/Absorb sequence, but would allow more optimized
implementations.


> > 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.
> Thanks for clarifying, but I just wanted to comment that maybe after
> Absorb(..); and before ..<-Squeeze(..); automatically a Ratchet();
> should be triggered within Squeeze in case the developer forgets to
> explicitly invoke it.

We'll need some rule for when to add Ratchet() when compiling a
handshake pattern into a sequence of SHO operations.

I think it's going to be a little more complicated than your
suggestion, since users might optionally call GetHandshakeHash() or
GetAdditionalSymmetricKey() during the handshake, so these functions
need to just clone the main transcript object and Squeeze() an output
without modifying the object with ratcheting.

Tentatively I think we should add a Ratchet() at the end of every
handshake message.  We could add exceptions (e.g. only ratchet if
MixKey was called, i.e. some secret information was added to the
transcript object).  But it might be simpler just to always do this.


> > 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")
> Okay, I understand, but you could also do:
> k||h||x||y <- Squeeze(4*HASHLEN)
>
> Squeeze(n):
>   output = empty
>   for(i=0;i =< n/HASHLEN;i++):
>     output <- output||SHA256(absorb1 || absorb2 || ... || i)
>   return output

That's true.  Then we'd have to reserve an extra byte (or more) at the
end for this counter, though.  That's a small cost, but since we
mostly don't need it I'm not sure it's worth it.

Trevor