Add support for larger outputs

[dbakker]

I'd like to use HKDF but I'm running into a couple of issues:

1. The output is currently limited to hashlen * 255.
2. It is necessary to know the exact length of the data you'll need, and all of it needs to be generated and stored in memory at once.

For this I would like to propose the following enhancements:

1. Add support for counters longer than 8 bits. (The paper the standard is based on says any fixed size counter is fine, so that shouldn't be an issue security-wise).
2. Make it possible to generate and read the OKM one block at a time.

I've attempted to tweak the existing code to allow for this new functionality while keeping the existing interface intact. The tests pass on both Python2 and Python3 and I believe the performance should still be the same or better.

If you agree with this idea/implementation we can add new unittests for the new values generated by the 16bit+ counters.

[kurtbrose]

The length limitation is part of the algorithm as defined in the RFC. From section 2.3 "Step 2: Expand" https://tools.ietf.org/html/rfc5869

  L        length of output keying material in octets
           (<= 255*HashLen)

Because the RFC says the counter must be exactly one byte, there are two issues beyond implementation:

1- Compatibility: other implementations of HKDF will not support counter values > 255, e.g. https://tools.ietf.org/html/rfc6234#section-8.4

2- Security: I'm not sure if the security proofs (http://eprint.iacr.org/2010/264.pdf) depend on the fixed length of the counter.

Do you have a use case where you are running into the length limitation? That sounds like perhaps the application really calls for a pseudo-random stream. For most applications, a KDF is going to output 32 bytes or less, so the length limitation is trivial. (Asymmetric keys such as elliptic curve or RSA keys are larger; but these cannot be just any random bytes, they require their own generation algorithm. And even these do not run into the limit.)

Some examples of pseudo-random stream generation are AES-CTR, AES-GCM (which is CTR + Galois Hash), AES-CFB (don't use this). Also, in general any "stream" cipher (as opposed to "block" cipher) works on this principle. In these examples, the psudo-random stream is XOR'd with plaintext; that is, used as a one-time pad. Is that the kind of application you want? In addition to the length limitation, HKDF has very bad performance as a stream cipher.

[dbakker]

Thank you for taking the time to write such a detailed response. :)

My use case

I'm working on a password generator similar to supergenpass. I need an algorithm that generates unique, strong passwords based on a strong master key.

The challenge is that pseudorandomly generated data short enough to be a password (e.g. taking the first 10 characters of base64'd data) is often not "random" enough. For example, you might get something like BBaaaaaa or 123woman.

To combat this, instead of just generating 1 password I'm generating hundreds of candidate passwords until one matching all security criteria is found. Because this is basically a form of keystretching HKDF seems to be the perfect choice. HKDF also has the advantage of being simple to implement in other languages which is useful for porting.

I've also considered PBKDF2 with a count of 1, but that violates the minimum iteration count of 1000 and basically makes PBKDF2 a less secure version of HKDF (such as described in its own comparison with other algorithms).

About security and compatibility

2- Security: I'm not sure if the security proofs (http://eprint.iacr.org/2010/264.pdf) depend on the fixed length of the counter.

The paper referenced in the RFC states (page 10):

the counter i is non-wrapping and of a given fixed size, e.g., a single byte

So according to the author any size counter is fine, as long as it is fixed size.

1- Compatibility: other implementations of HKDF will not support counter values > 255, e.g. https://tools.ietf.org/html/rfc6234#section-8.4

You are correct, I haven't found any other implementations with bigger counters. However, the 8bit variant still has the same output, and for the other bitcounts we're essentially changing nothing except for the size of the counter. So any other implementations with the same counter size should produce the same result, as long as they use the same endianness. For this, network order (big endian) seems a good choice but we could make it configurable (by adding more COUNTER variants) if there is ever demand for that.

[kurtbrose]

Shoot, I'm sorry I should have specified -- I'm not the project author just another user who is interested.

That is an interesting use case. The generated password needs to not only be random, but also look random to a human. (Or, sacrifice a minimal amount of true randomness for apparent randomness.)

That is very tricky; I agree the most conservative approach is probably to use an extension of HKDF.