[noise] ASKs again: Dependent and Independent?

[Mathias Hall-Andersen]

I am also in favor of having two different extensions:

The dependent ASK extension is very simple and straightforward to implement.

Whereas the independent implementation is more involved, 
but able to provide the forward-secrecy feature desired.

Although the independent ASK implementation suggested is simple from an implementers perspective,
I do not like that ASK affects the operation of the handshake:

- I think it has immense value that the protocol name fully describes the operation of the protocol:
  it simplifies debugging and documentation, since users can simply state "connect with Noise_IK_448_ChaChaPoly_BLAKE2b".
  With the independent ASK proposal, we start moving implementation details of the handshake into the application
  (by having the application call the ASK extensions in the same order).

- It introduces possible branches in the state machine and opens the door for having
  future extensions introducing additional branches in the handshake, the interplay of which we have to reason about:
  at which point the simplicity of Noise may be compromised.

- It complicates gradual adoptions of ASK applications, e.g.
  if the server/client wants to start using ASKs to implement a version of 0-RTT encryption by having the prologue containing a encrypted psk
  sent before the Noise message, then the server cannot start generating tickets for a client which may (not) support the feature since it breaks the handshake.

- Might complicate proofs, depending on how this is modeled it introduces a branch in the state machine
  where an agent may process the next handshake message or do an ASK extraction.

- Minor point: it is the only update to the ck that does not involve the addition of new key material.

If we opt for something like the "independent ASKs" proposal 
we might opt to have the user specify a priori when ASKs should be extracted, 
since they need to agree on when the ASK operation is applied:
whether this is done in the application at run-time or at "pattern selection time" seems to makes little difference.

If specifying this is acceptable: 
then we might be able to extract independent ASKs parallel to ck in the MixKey, 
similar to what str4d originally suggested without introducing the 
overhead of having to generate the ASKs for every MixKey / MixKeyAndHash in the handshake.
However this is still much more invasive to implement than your suggestion

In short: I think the independent ASK proposal appears deceptively simply, 
because it pushes the complexity onto the application.

- Mathias

On 06/08/18 00:44, Trevor Perrin wrote:
> I'd like to summarize our current proposals for ASKs, and try to
> combine their benefits into another proposal:
>
>
> Background
> -----------
> I think the state of the Additional Symmetric Key (ASK) discussion is
> this:  We had a tentative design based on (1) deriving an "ask_master"
> key from previous ck, then (2) deriving chain keys from the
> ask_master, then (3) deriving the actual ASKs (the output keys) from
> these chain keys:
>
> https://moderncrypto.org/mail-archive/noise/2018/001713.html
>
> (1) means that the ASKs are independent from the previous ck.
> Separating (1) and (2) means that you don't have to decide on your set
> of labels until later.
>
> But this means 3 HKDFs between ck and an output key, and pre-emptively
> deriving the ask_master during every MixKey "just in case".  So
> Matthias proposed deriving things more directly from ck, for
> simplicity and efficency:
>
> https://moderncrypto.org/mail-archive/noise/2018/001791.html
>
> However, then the output ASKs are no longer independent from the
> current ck, so that would lose the forward-security property we
> wanted.
>
>
> Goals
> ------
> We'd like a simple key derivation for the simple cases that are our
> main use cases:
>  - Deriving additional traffic keys if a Noise handshake is being used
> to key a non-Noise transport protocol
>  - Deriving additional keys for some sort of "transmission security"
> or "indistinguishability padding" security mechanisms
>  - Deriving a single resumption PSK
>
> However we'd also like a design that was capable of supplying
> forward-secure keys, e.g. if you want to use a single Noise handshake
> to generate multiple resumption PSKs, where a point-in-time compromise
> can't compromise the resumption PSKs that were produced earlier.
>
>
> Proposal
> ---------
> Applications can request either "dependent" or "independent" ASKs.
> Dependent ASKs are based on Matthias's proposals.  Independent ASKs
> are largely the same, except they "ratchet" the ck, so the ASK becomes
> "independent" of the new ck.
>
> Dependent:
>   ask = HKDF(ck, h || label, info="askd")
>
> Independent:
>   ask, ck = HKDF(ck, h || label, info="aski")
>
>
> Dependent ASKs can't achieve forward-security until the ck they depend
> on is deleted.
>
> Independent ASKs update ck when they are requested.  Thus Alice and
> Bob must request synchronized independent ASKs.  This makes
> independent ASKs more difficult to use and more expensive to
> calculate, but more secure in some cases.
>
> ASKs would either be associated to a handshake message, or
> post-handshake.  If associated to a handshake message, they would be
> derived just before the handshake payload is encrypted.
>
> For post-handshake ASKs, Split() would be modified to set ck = third
> output from HKDF, so you could continue deriving both Independent and
> Dependent ASKs after the handshake.
>
>
> Examples
> ---------
> Alternative traffic keys:  Derive dependent ASKs "traffic_send" and
> "traffic_recv" associated to the final handshake message.
>
> Transmission security: Derive an additional dependent ASK
> "padding_key" associated to every handshake message.
>
> Resumption PSKs:  Derive post-handshake independent ASKs with
> alternating labels "psk" followed by "psk_addendum".
>
>
> Questions
> ----------
>  * Requiring independent ASKs be ordered and synchronized is maybe a
> lot to ask.  But Noise generally assumes parties can stay in lockstep,
> so maybe not a big deal?
>
>  * Asking users to reason about the difference between "dependent" and
> "independent" ASKs could also be a lot to ask.  However most users
> should use profiles of Noise that already provide resumption PSKs or
> whatever, and not have to deal with this mechanism directly.  And the
> edges aren't *that* sharp, since using a dependent value instead of
> independent just means you have worse forward-security, but that's not
> usually a catastrophe.
>
>  * Independent ASKs would modify ck but wouldn't be reflected in the
> protocol name, so they'd violate our current principle that the
> protocol name fully describes the handshake crypto operations, i.e. we
> can produce test vectors based only on the protocol name.  Independent
> ASKs would be safe despite this because the ASK HKDFs are fully
> self-describing, but at minimum it would complicate test vectors, and
> (arguably) invalidate formal analysis results for existing patterns,
> since the crypto operations are changed.
>
> Anyways, what do people think?
>
> Trevor
> _______________________________________________
> Noise mailing list
> Noise at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/noise