[noise] Nonce-based AEAD and duplex objects (was Re: Notes from CRYPTO)

[Trevor Perrin]

On Mon, Sep 25, 2017 at 7:48 AM, David Wong <davidwong.crypto at gmail.com> wrote:
>
>> A "half-duplex" protocol (perhaps not best term, given that "duplex" has a different meaning in context of permutation crypto)
>
> True. This could be renamed to *turn-by-turn* and *simultaneous*
> perhaps? More verbose but more descriptive imo.

BLINKER and Strobe both use the "half-duplex" terminology, so I guess
it's not easy to move away from.  Now that we've put half-duplex in
the spec maybe we don't need to discuss it much more.


>> We could mention this (half-duplex) briefly as an "Advanced feature" in the Noise spec
>
> glad it made it to the spec! I have one nitpick though: this could
> potentially allow you to not have to store two CipherStates, but the
> way the spec makes you implement it still allocates space for two
> CipherStates. I like the tendency of the Noise spec to be opiniated
> and to make the right choices for the developers, so it would make
> more sense to mention "not to return two CipherStates but one" instead
> of "not to use the second one".

Tried to clarify the text.  In the pseudocode Split() returns 2
outputs, so we have to address that, but I think this text is clear
about the optimization:

"""
In some application protocols the parties strictly alternate sending
messages.  In this case Noise can be used in a "half-duplex" mode
[@blinker] where the first `CipherState` returned by `Split()` is used
for encrypting messages in both directions, and the second
`CipherState` returned by `Split()` is unused.  This allows some small
optimizations, since `Split()` only has to calculate a single output
`CipherState`, and both parties only need to store a single
`CipherState` during the transport phase.
"""
https://github.com/noiseprotocol/noise_spec/compare/rev33


[[Referring to session-supporting authenticated encryption]]
>> I don't care much about that property in the Noise transport phase (after the handshake).
>
> It is not of the utmost importance, but it is what Strobe is about
> (inspired by Noise!) and why I find it elegant. (It's mostly this nice
> continuity that led me to read more about it and sponges btw!)

The influence is mostly in the other direction (Noise was influenced
by Mike's early thoughts about Strobe).

Certainly Noise's SymmetricState is similar to a Sponge/Duplex object,
in that it "absorbs" inputs and "squeezes out" keys.  However once we
move from the handshake to transport phase, and from SymmetricState to
CipherState, the absorbing and squeezing is finished, and I think
conventional, nonced AEAD becomes the most useful primitive.


> I think there are two ways to integrate a duplex construction in
> Noise. You can either (1) replace each primitive by its duplex
> equivalent (which should be straightforward. cSHAKE could replace
> everything OR HMAC could be KMAC, AESGCM could be Ketje, SHA256 could
> be SHAKE/K12, HKDF could be SHAKE, etc...). Note that this would
> mostly make use of sponge constructions rather than a duplex
> construction, but this would allow you to easily mix and match with
> the currently defined crypto algos in Noise. Or you can (2) deeply
> merge a duplex construction into Noise, which is what I had in mind
> for Disco.

I think there's more!  Here's a bunch of ways you could imagine
plugging permutation crypto, like Keccak, into Noise:

 (1) Implement Noise's hash and cipher functions, as you mention:
 - hash = "SHA3/256" or "SHAKE128" or "K12"
 - cipher = "Kravatte" or "Keyak"

 (2) Instead of implementing HASH(), provide some flavor of XOF that
replaces all HKDF, HMAC, and HASH uses.  This is not-yet-designed, but
maybe would allow specifying "KMAC" or "cSHAKE" or "TupleHash".  More
in this thread:

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

 (3) A "Disco" approach of replacing the SymmetricState and
CipherState objects, but where a nonced AEAD interface is implemented
on top of Duplex, e.g. by using a sequence of KEY;AD;ENC;MAC Strobe
calls for every AEAD call, as we discussed earlier.

 (4) A "Disco"-like approach but where nonce-based AEAD is provided by
a more efficient construct, such as Farfalle/Kravatte.

 (5) A "Disco" approach where CipherState is replaced by a stateful
duplex object, providing "session-based" authentication encryption
instead of "nonce-based".

Option 1 is easy and works well.  Also, there's not a huge demand for
any of this.  I think the more complex options should be explored but
we shouldn't feel pressured to rush something out.


> If we're
> using a duplex construction inside of Noise let's not make compromises
> and see what it can fully accomplish. The whole dealing with nonces
> and setting up AEADs can be removed which is a plus even only thinking
> about complexity.

You're advocating Option 5, but that's my least favorite.
Session-based authenticated encryption means:
 - No support for out-of-order transport messages
 - Less efficient because less parallelism
 - More state stored between encryption calls (entire duplex object,
instead of just 32-byte key)

What benefits do we get that outweigh those disadvantages?

I'm skeptical of your claim that "dealing with nonces" adds much
complexity.  Having different types of symmetric crypto with different
properties and APIs seems more complex.

The security argument for authenticating the entire session seems
pretty thin (if keys are secure, then authenticating each message
individually accomplishes the same thing).  Most real systems seem
happy with Rogaway's nonced AEAD notion.  The CAESAR competition also
focuses on nonced AEAD.

My impression is that the Duplex design fell out of the Sponge design
as a side effect; it's not that great for authenticated encryption,
and will probably be superceded by better things (Farfalle or other
full-state constructs).  The notion of "session-supporting"
authenticated encryption seems like an attempt to spin the flaws of
this design (lack of parallelism; lack of out-of-order support) as a
feature.

So I'm still not convinced we should be bending backwards to support
duplex/session-based encryption; I'd rather see cryptographers fit
their designs into the standard and flexible notion of nonced AEAD.

Trevor