[noise] BLAKE2X as KDF

[Trevor Perrin]

On Mon, Dec 26, 2016 at 4:31 PM, Brian Smith <brian at briansmith.org> wrote:
> Trevor Perrin <trevp at trevp.net> wrote:
>>
>>  * Noise's core design, including the chain-of-HKDF for key
>> derivation, has been unchanged since 2015. [...]
>>
>>  * HKDF and HMAC are conservative designs. [...]
>>
>>  * HKDF and HMAC are widely used for KDF (Signal, Noise, IPsec, TLS
>> 1.3),  [..]
>>
>>  * Having a simple interface to crypto primitives makes it easy to
>> plug in new primitives without complicated design and analysis. [...]
>
> One option that might address the above concerns would be to
> parameterize the key derivation function not as HKDF(hash) but as
> Extract-then-Expand(mac). This is actually how HKDF is defined in [1],
> "Extract-then-Expand KDF and a HMAC-based Instantiation."

HKDF is more complicated than that:

 * The Extract-then-Expand concept requires an entropy extractor
(Extract) followed by a PRF (Expand).  A MAC is not necessarily either
of those things.

 * HKDF is defined on top of HMAC, not an arbitrary MAC (e.g. the
analysis in Section 6 of the HKDF paper uses HMAC's outer and inner
functions, and in Sections 5 and 6 it discusses modelling the
underlying hash as a Random Oracle).

 * Noise uses HKDF within a multi-stage KDF, so the "salt" is not just
for randomizing Extraction, but is also used to accumulate previous
inputs, so we have additional requirements, e.g. we'd like the
function to be a PRF if keyed by either the salt or input key
material, or at least to be a Random Oracle if the underlying hash is
a Random Oracle (see discussion / security model at [1]).  Polynomial
MACs (like GCM and Poly1305) don't meet these requirements.


>>  * You suggest that Keyed BLAKE2x will be easier to implement than
>> HMAC/HKDF, if libraries don't have an HMAC function.  But HKDF is easy
>> to implement given any hash (e.g. BLAKE2).  BLAKE2X requires modifying
>> the BLAKE2 internals to change the parameter block, which could be
>> difficult (e.g. if you have a hardware core or assembly code that
>> implements BLAKE2 but not Keyed BLAKE2X).
>
> I imagine most BLAKE2 implementations are going to implement at least
> Keyed BLAKE2 in addition to the unkeyed version. However, I have to
> admit I don't see a significant advantage of BLAKE2X over
> Extract-then-Expand(Keyed BLAKE2). I imagine that crypto library
> maintainers would rather not add a bunch of BLAKE2-specific code and a
> bunch of SHA-3 specific code to do things the same-way-but-different
> as how things are currently being done with SHA-2

I'd extend that same argument to preferring HMAC-BLAKE2 over keyed
BLAKE2, in this use case.

Keyed BLAKE2 is just a key-prepend MAC, and HMAC is just a nested pair
of key-prepend MACs, so HMAC is a bit slower but more conservative and
means we have a consistent structure, which simplifies design /
implementation / analysis for all hashes, instead of needing custom
effort for each.


> Anway, if I already have AES-CBC-MAC and AES-CCM (or even AES-CBC-AMC
> and AES-GCM) in hardware, it would be unfortunate to have to make a
> software HMAC just to get a KDF, even though HMAC is admittedly very
> simple. Of course, if it were possible to avoid HMAC then I'd also
> want to find a way to avoid needing a hash function at all just for
> the handshake hash.

Well, we already need a HASH() function for "h", so I don't think
we're going to eliminate that, or build it on top of an AEAD.

If you want to unify all symmetric crypto around a single primitive
maybe a sponge could be used, but that would require re-defining the
entire SymmetricCrypto layer of Noise.  Which could be done, but I'm
not sure the practical advantages would be that significant (smaller
code size, but not necessarily faster or less RAM use).

Anyways, I definitely need to add a rationale section about this, but
I'm still quite happy with the current KDF design, and I think there's
enough implementation support (WhatsApp, WireGuard, various libraries)
that we should consider it frozen.

Trevor

[1] https://moderncrypto.org/mail-archive/noise/2016/000599.html