KDF traits

[warner]

In vladikoff/rust-hkdf#6, we're talking about whether you'd like to see rust-hkdf moved under the RustCrypto umbrella (Vlad just released 0.2.0, which uses the Digest and Hmac traits from RustCrypto).

I'm not sure what would be the best way to integrate this. Maybe a new set of KDF traits in this repo, followed by a new kdfs repo that includes HKDF?

It'd be nice if the signature of the new trait could encompass a variety of KDFs.. not sure if this is feasible. All the KDFs I'm interested in take an arbitrary-length input and a salt. Some take a "context" or "purpose" string. Some KDFs do stretching (scrypt, Argon2, PBKDF), which requires a couple of additional parameters to control the resource usage.

(the stretching KDFs are frequently called "password hashing functions" or "key-stretching functions", so it might not even be appropriate to lump them into the same category as an expansion-only function like HKDF)

name	Salt?	Context?	Stretching params	Variable-length output
HKDF	yes	yes	none	yes
PBKDF2	yes	no	num_iterations	yes
scrypt	yes	no	N, r, p	yes
Argon2	yes "nonce"	"associated data" X	M, T, d	yes

HKDF (RFC5869) is a non-stretching expansion function expressed in two phases (extract and expand). The extraction step takes a salt and some IKM ("initial keying material") to produce an intermediate value PRK (pseudorandom key). The expansion step takes PRK, a "context" string named info, and an output length. It is also parameterized by the choice of hash function, usually SHA256.

PBKDF2 is a fairly simple stretch based on repeated application of a compression function (usually HMAC-SHA256 or HMAC-SHA1). It is not memory-hard, and hence regrettably easy to parallelize, especially in hardware. It is parameterized by the compression function, password, salt, iteration count, and output length. It expands first, so unfortunately the runtime is proportional to the output length (rounded up to the size of the compression function output).

scrypt (RFC7914) is memory-hard, parameterized by N (always a power of 2), r, and p. Time is proportional to N*r*p, and memory usage is proportional to N*r. N/r/p of 2^16/8/1 requires 64MiB of memory, and about 1.0s on my desktop computer. It always uses the same hash functions (PBKDF2-HMAC-SHA256 and Salsa20/8).

Argon2 is memory-hard, parameterized by M (KiB of memory used), T (number of passes), and d (parallelism / number of cores). Time is proportional to T*d on a single-core machine, or just T if there are enough cores. It comes in several flavors, including "Argon2d" (which resists tradeoff attacks better) and "Argon2i" (which resists side-channel attacks better). There are optional inputs for a secret key K, and associated data X. It always uses the same hash function (Blake2b).

For the "context" string, maybe the trait should require a context value, but for PBKDF2 and scrypt it should assert that the slice is zero-length? Or maybe accept an Option()?

I have no idea what to do for the stretching parameters. If this were Python, I'd use keyword parameters that default to None, but I know Rust doesn't do that.

Another question is how (or whether) to model the two-part extract-then-expand phases of HKDF. If you were deriving a number of different values from a single large IKM, then perhaps there is a performance benefit to retaining the intermediate value, but in most applications I've seen, the entire HKDF function is invoked in a single step (out = HKDF(IKM, salt, context, length)). None of the stretching-based KDFs do this, because the stretching phase is much longer than the expansion step.

The input material is typically pretty short: it's variable length because it's frequently a password, rather than a whole document. So it probably doesn't require the Digest trait's ability to submit the input across multiple calls.

So maybe the trait should expose a single function for non-stretching, which takes slices for IKM, salt, context (optional), and length, and returns a Vec[u8]. And then a second function for stretching, which also takes something to define the cost parameters (no idea what).

[newpavlov]

Thank you for your review and sorry for the late answer!

I've created password-hashing repository specifically for this kind of algorithms, but as you correctly mention HKDF does not fall into this category. Initially I thought about using KDFs repository, but after discussion with @tarcieri it was decided to go with "password-hashing" instead. So for now we could keep HKDF in its own repository, if you'll decide to move it to RustCrypto.

As for traits, I am not yet sure what kind of trait we need. For PBKDF2 for now I simply wrote a function. One way to define this trait would be to use configuration struct and associated type. Something like this:

trait Kdf {
    type Config;
    fn compute(secret: &[u8], salt: &[u8], out: &mut[u8], config: Config)
}

[tarcieri]

Naming the traits involved here is a tricky problem, because password hashing functions, KDFs, and XOFs have a Venn Diagram-like overlap.

That said, HKDF is certainly a bit different from password hashing KDFs, because HKDF is completely unsuitable as a password hashing function.

[newpavlov]

We could use marker trait approach to distinguish password-hashing functions:

trait PasswordHashing: Kdf {}

As for XOFs, I am not sure how to deal with them. Currently they are defined as part of digest crate, but it also makes sense to link them to KDF somehow...

[tarcieri]

The problem with that is not all password hashing functions are KDFs.

I think it would be best if password hashing functions which are KDFs implement both traits.

[tarcieri]

I think we can close this issue?

[tarcieri]

On second thought, reopening this issue to discuss KDF traits.

It'd be nice to have a kdf crate with some common abstractions for KDFs, and as @newpavlov noted above, some sort of marker trait for memory hard KDFs as seen in password hashes, e.g.:

trait PasswordHashing: Kdf {}