[noise] New branch: hkdf

Mon Oct 12 21:22:30 PDT 2015

On Mon, Oct 12, 2015 at 5:34 PM, Stephen Touset <stephen at squareup.com> wrote:
> It would be nice if the noise spec was flexible enough to allow for hash functions with built-in HKDF-like properties (e.g., blake2b and SHA-3). I see Jason is using it this way for his own purposes, but doing so is clearly a deviation from the spec as written. Doing so now could future-proof noise a bit as these hashes become more widespread in their use.

It's not trivial to summarize what "HKDF-like properties" are (it's a
PRF, a hash function, and an entropy extractor).  That's why I'm
finding it easier to just specify HKDF, which you can certainly use
with BLAKE2 and SHA3.

But if you have a different function that takes a 32-byte key,
variable-length input, and produces 64 bytes output, and you think it
has the same properties as HKDF, it would be easy to plug in.

Trevor

>
>> On Oct 10, 2015, at 12:21 PM, Trevor Perrin <trevp at trevp.net> wrote:
>>
>> More on the GETKEY-based key derivation (n0 branch) versus the HKDF
>> version (hkdf branch):
>>
>> * Simplicity:
>>   * HKDF adds a new variable (ck).
>>   * The n0 branch conditionalizes the n=0 case, and requires
>> implementing MixKey() using a pair of functions (GETKEY and HMAC)
>> instead of a single function (HKDF), so complexity of all this versus
>> the extra variable is probably a wash.
>>   * The descriptions of how to optimize GETKEY() by calling the
>> cipher directly are ugly; it's also unintuitive to call an encryption
>> function as part of the key derivation.
>>
>> * Efficiency:  Looking at the XX handshake, n0 would take 3 HMAC and
>> 4 GETKEY, HKDF would take 12 HMAC.  So n0 is potentially faster, but
>> some (most?) AES-GCM implementations will build lookup tables for AES
>> and GCM for each new key.  In that case n0 is probably slower.
>>
>> But assuming well-optimized code:  If the HKDF version is, say, 8-9
>> HMACs slower, then it's hashing an extra ~2000 bytes (with SHA256).
>> To put very rough numbers on it, that might be 20K Haswell cycles [1].
>> Compared to 3 ECDHs + 1 keygen at ~500K cycles [2], this is < 5% speed
>> difference for the handshake.
>>
>> The main reason HKDF is less efficient is that after HMAC'ing the next
>> DH, it performs another HMAC to derive ck from k, instead of using k
>> directly.  But this extra derivation has some minor advantages:
>>
>> * Flexibility:   Deriving k from ck lets their sizes differ - for
>> example, the HKDF version could be easily be adapted to HMAC-SHA512
>> and 64-byte ck, or AES-128 and 16-byte k.
>>
>> * Resilience in case k is leaked:  Even if the value of k was somehow
>> leaked (side-channels? cryptanalysis?) that wouldn't directly reveal
>> the chaining variable ck, with HKDF.  (But this is a very minor
>> argument, because if the cipher key is being leaked, then transport
>> messages encrypted with the cipher probably won't be secure either.)
>>
>> * Modularity with AEAD algorithm:  The GETKEY design requires the
>> first 32 bytes of encrypting zeros to be a PRF from the cipher key -
>> but there's no guarantee that a general AEAD will satisfy this, so we
>> have to add extra stipulations (the auth tag must come at the end, the
>> AEAD has to be deterministic so it doesn't add an IV at the beginning,
>> and it must not expand the ciphertext beyond the auth tag, e.g. add
>> zero-padding at the beginning or something).  While these stipulations
>> are probably sufficient (?), and probably achieved by most
>> deterministic AEAD modes, this means extra care in choosing symmetric
>> crypto parameters: n0 can't be used with *any* arbitrary AEAD mode
>> because it wants to break the abstraction and peek into the
>> ciphertext.
>>
>> * Random Oracle security analysis: If the hash function is modelled
>> as a random oracle, there's no significant difference, I think.  The
>> GETKEY version requires an additional assumption that GETKEY is a PRF,
>> so the analysis is a tiny bit more complicated.
>>
>> * Familiarity:  HKDF is familiar from IPsec, QUIC, TLS 1.3, and
>> Hugo's papers and RFC.  Using chained HKDFs in this way is also
>> familiar from TextSecure's "Axolotl" ratcheting.
>>
>> ---
>>
>> In sum: I think the HKDF design is a little easier to explain,
>> analyze, implement, and justify.  It's a few percent slower when
>> well-optimized, but likely faster in naive implementations when using
>> ciphers with low key agility (e.g. AES-GCM).
>>
>> HKDF also provides a more modular design where the cipher keys and
>> HKDF keys are distinct, which gives more flexibility to adapt the
>> design to different key sizes, or different AEAD algorithms.
>>
>> Based on all this, I favor the HKDF design at the moment.  I'll
>> probably merge it to master in a few days if there aren't any
>> compelling counter-arguments.
>>
>>
>> Trevor
>>
>>
>> [1]
>> https://www-ssl.intel.com/content/dam/www/public/us/en/documents/white-papers/haswell-cryptographic-performance-paper.pdf
>>
>> [2]
>> https://docs.google.com/spreadsheets/d/1SO3NGX-EgIZ1slw9uExb5FoeFy5TVkuA2lEutP6roYI/edit#gid=0
>> _______________________________________________
>> Noise mailing list
>> Noise at moderncrypto.org
>> https://moderncrypto.org/mailman/listinfo/noise
>
> --
> Stephen Touset
> stephen at squareup.com
>
>
>