[noise] ASKs again: Dependent and Independent?

[Trevor Perrin]

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