Having read this, I still don’t understand the difference between PRF and KDF security guarantees. To be honest I expected this to be explained in the “PRF? KDF? OMGWTFBBQ” section, but instead it just defines the primitives themselves. I don’t see how any difference in security follows from these definitions.
This area is one of the places where the libsodium docs are not ideal. I’d love to see a follow-on post telling me how to go from a password to a set of keys with libsodium’s pwhash and kdf APIs and what I need to think about in terms of salts / contexts (is it even possible to have a secure UI where the user provides a single password and I derive keys for different uses from it?).
Yup. I fixed this an hour or so ago but I’m super tired because of work meetings and didn’t have the energy to reply until just now. Thanks for finding and pointing out that error.
It’s that you’re now outside the specific definition of the primitive, and have to assume a fallback to PRF security rather than KDF security.
In order to meet the PRF security bar, your IKM cannot be structured. It must be uniformly random. KDF security isn’t as stringent.
Misusing HKDF salts doesn’t “break” anything, it’s just the security proof equivalent to undefined behavior. It might be okay; good luck proving it’s okay.
You might be able to recover the proof, but the work is not already done for you. A broken proof would be unrecoverable.
And how did you come to this conclusion, that it’s not allowed to pick a random salt? The paper seems to say the opposite: We stress that this notion of security can only be achieved for randomized KDFs where the salt value r is chosen at random from a large enough set.
Right, because there is only one random value in the game for the security definition, the definition does not apply when the attacker is allowed different random values.
Looking at it further, isn’t there an even bigger problem, that this definition also requires that the attacker does not know the context?
Looking at it further, isn’t there an even bigger problem, that this definition also requires that the attacker does not know the context?
Definition 7, steps 4 and 5 gives the attacker control over the context passed to the KDF in the distinguishing game. Control is a stronger notion than knowledge, so their knowledge of the context is implied.
But isn’t A only allowed to pick c other than the challenge c? Does that still imply knowledge of c? It’s probably in the details somewhere, I just haven’t seen it.
So the deal is that the proofs of KDFs put constraints on the salt that your “salting” might not meet, but they don’t put those constraints on the info field - the proofs assume that the info field might contain non-uniform random data, or even predictably structured data.
So if you want to rely on those proofs, best to stay within the well-lit area and stick your extra non-uniform randomness in the info field; if you were to stick it in that (oh-so-tempting) salt field you’re now outside the proof assumptions & it’s possible that you’ve just weakened the KDF you’re using.
You’re using a construction that uses HKDF because it needs the “KDF” security definition rather than the mere PRF security definition. This happens when your key isn’t uniformly random (computer-generated passwords, DH/ECDH outputs).
You use the HKDF salt field in a way that violates the security definition, so you only get PRF security.
In this situation, you can’t claim to have a security proof unless you do extra work to recover the proof.
Having read this, I still don’t understand the difference between PRF and KDF security guarantees. To be honest I expected this to be explained in the “PRF? KDF? OMGWTFBBQ” section, but instead it just defines the primitives themselves. I don’t see how any difference in security follows from these definitions.
Read this. I’ve added a link to that answer in the section you indicated.
EDIT: Also, https://soatok.blog/2021/11/17/understanding-hkdf/#prf-vs-kdf-security-definitions
This area is one of the places where the libsodium docs are not ideal. I’d love to see a follow-on post telling me how to go from a password to a set of keys with libsodium’s pwhash and kdf APIs and what I need to think about in terms of salts / contexts (is it even possible to have a secure UI where the user provides a single password and I derive keys for different uses from it?).
[Comment removed by author]
Yup. I fixed this an hour or so ago but I’m super tired because of work meetings and didn’t have the energy to reply until just now. Thanks for finding and pointing out that error.
You’re welcome. I’ll delete my comment to remove useless noise here.
I am having trouble following.
Are you saying that the security proof for the KDF security of HKDF breaks when you use it twice with the same input but different salts?
It’s not that a proof is broken.
It’s that you’re now outside the specific definition of the primitive, and have to assume a fallback to PRF security rather than KDF security.
In order to meet the PRF security bar, your IKM cannot be structured. It must be uniformly random. KDF security isn’t as stringent.
Misusing HKDF salts doesn’t “break” anything, it’s just the security proof equivalent to undefined behavior. It might be okay; good luck proving it’s okay.
You might be able to recover the proof, but the work is not already done for you. A broken proof would be unrecoverable.
And how did you come to this conclusion, that it’s not allowed to pick a random salt? The paper seems to say the opposite: We stress that this notion of security can only be achieved for randomized KDFs where the salt value r is chosen at random from a large enough set.
You’re allowed a random salt. The security definition doesn’t extend to static (IKM, Info, length) but variable salt.
It does extend to static (IKM, salt, length) but variable info.
The blog post addresses this.
Right, because there is only one random value in the game for the security definition, the definition does not apply when the attacker is allowed different random values.
Looking at it further, isn’t there an even bigger problem, that this definition also requires that the attacker does not know the context?
Definition 7, steps 4 and 5 gives the attacker control over the context passed to the KDF in the distinguishing game. Control is a stronger notion than knowledge, so their knowledge of the context is implied.
But isn’t A only allowed to pick c other than the challenge c? Does that still imply knowledge of c? It’s probably in the details somewhere, I just haven’t seen it.
So the deal is that the proofs of KDFs put constraints on the salt that your “salting” might not meet, but they don’t put those constraints on the info field - the proofs assume that the info field might contain non-uniform random data, or even predictably structured data.
So if you want to rely on those proofs, best to stay within the well-lit area and stick your extra non-uniform randomness in the info field; if you were to stick it in that (oh-so-tempting) salt field you’re now outside the proof assumptions & it’s possible that you’ve just weakened the KDF you’re using.
Have I got that right?
Yep. The worst case scenario is:
In this situation, you can’t claim to have a security proof unless you do extra work to recover the proof.