4
$\begingroup$

HKDF is used in one of my projects to derive separate keys from a common master key. But profiling has shown it to be the performance bottleneck under certain circumstances. Is there any faster alternative? The only things I get after googling "key derivation function" are HKDF and password stretching algorithms like PBKDF2 or scrypt.

$\endgroup$
  • $\begingroup$ HKDF is the standard choice for key derivation. IIRC it needs four calls to the hash function to derive a short key (2 to extract via HMAC IIRC and 2 to derive via HMAC). There's no faster (standard) solution. Which hash function are you using / do you have at your disposal (Keccak / SHAKE / Skein maybe)? $\endgroup$ – SEJPM Jan 12 '16 at 14:56
  • 6
    $\begingroup$ You're creating millions of subkeys per second? Could you elaborate a bit more on the use case and context? Is the master key fixed or different each time? How long are the derived keys? $\endgroup$ – CodesInChaos Jan 12 '16 at 15:29
  • $\begingroup$ @CodesInChaos: OK, I profiled again, and this time HKDF did not show up as the bottleneck. Maybe I was wrong. But I am still interested to see why HKDF seems to be the only standard solution, when any PRF should suffice. $\endgroup$ – Siyuan Ren Jan 12 '16 at 15:54
8
$\begingroup$

If you are using the full HKDF each time, you could possibly save time by only using the Extract portion once and Expand once per derived key. That could even halve the total time taken, if you had a worst case situation.

Another speedup possibility within HKDF is to use another hash. Either a faster hash or one that matches the required key length better. For example, if you are generating a 256-bit key you would likely not want to use SHA-1 even though it is faster than SHA-256, because you would need two serial iterations.

Depending on the use case, you might also want to look into using KDF1 or KDF2, which are faster hash-based KDFs. They are defined in ISO18033, but KDF1 is also in RFC 3447 (appendix B.2), under the name MGF1.

However, as explained in the HKDF paper (pdf), the Expand scheme could work with any PRF. That means that for best performance you could roll your own version by replacing HMAC with a block cipher that you have in hardware (e.g. AES-NI on some new CPUs), since secure block ciphers are indistinguishable from a PRF up to the birthday bound.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.