2
$\begingroup$
DK = PBKDF2(PRF, Password, Salt, c, dkLen)

When PBKDF2 is used for key derivation (not password hashing), is it possible for an adversary who doesn't know Password to learn anything about Salt when given DK?

Edit

To clarify this question a bit, let's fix c and dkLen and simplify the function a bit:

DK = PBKDF2(PRF, Password, Salt)

This function has 3 inputs and 1 output. When given PRF, Password and Salt, we can calculate DK exactly.

My question is actually very simple:

When given PRF and DK, is it possible for an adversary to learn anything about Salt?

Here are some trivial examples that may help you understand the question better:

  • If we define function1(PRF, Password, Salt) = Password, then obviously the adversary won't learn anything about Salt because it's not being used.

  • If we define function2(PRF, Password, Salt) = Salt, then obviously the adversary will learn something (everything, in fact) about Salt.

The parameter name Salt may be confusing because we are not using it as a salt here. Instead, it's some information that we want to keep a secret. This may or may not be its original design goal. But I'd simply like to know whether it's safe to use PBKDF2 in this way.

$\endgroup$
  • $\begingroup$ I assume you mean not for password stretching for password storage. But the "PB" in PBKDF2 stands for password-based. Since it's hash based you're hashing a password no matter what. If I assume you mean with no stretching (c = 1), then I don't know why you would use PBKDF2-Whatever-Hash instead of Whatever-Hash. (Then you would need a stronger password, too.) $\endgroup$ – Future Security Jul 6 '18 at 22:06
  • $\begingroup$ Normally when you use any key you never reveal its value. Giving the attacker DK goes against that. And normally salts are not designed to require the same level of secrecy as keys. (That's why they're not called keys.) It's supposed to be public salt + secret password = secret key. Not public key + secret password = secret salt. $\endgroup$ – Future Security Jul 6 '18 at 22:08
  • $\begingroup$ @FutureSecurity No, we don't give attacker DK. We just want to protect Salt even when the attacker happens to know DK. In our use case, that parameter is actually not used as a salt here. I just wrote the function as Wiki presents it. See EDIT. $\endgroup$ – Cyker Jul 7 '18 at 2:15
3
$\begingroup$

No, the adversary won't learn anything about the salt, if the salt is a cryptographic random of sufficient length.

A PBKDF such as PBKDF2 is generally build up from keyed one-way-functions (PRF's) such as HMAC's. That means that you cannot retrieve any of the inputs given the output. It does mean that if the inputs when put together can be guessed or brute forced that the input can be verified to be correct.

A secret salt is commonly called a pepper which acts as a secret key. The security provided by the pepper is comparable to a secret key of the same length.

A pepper can be concatenated with a real salt to create a new salt input parameter. The real salt can be stored together with the output of PBKDF2 or the ciphertext to avoid that identical pepper & password combinations can be identified.

$\endgroup$
  • $\begingroup$ If the pepper (Salt in the original function) may not be long enough but Password is always long and secret, then the adversary can enumerate the pepper and may have encountered the right one. However, since the adversary doesn't know Password, he cannot verify the pepper is what actually being used. Therefore, the pepper is still safe. Am I correct on this? $\endgroup$ – Cyker Jul 7 '18 at 12:14
  • $\begingroup$ Sure, you would need to know al the input parameters to get the correct result. $\endgroup$ – Maarten - reinstate Monica Jul 7 '18 at 12:17
2
$\begingroup$

For any reasonably good $\text{PRF}$ (including $\text{HMAC}$ used in practice), $\text{PBKDF2}$ behaves as a $\text{PRF}$. And the adversary learns nothing helping find $\text{Salt}$ from outputs, until finding an exact match. The later holds even if $\text{Password}$ is known.

Possible exceptions: the length of $\text{Salt}$ could leak by timing attack; and when using PBKDF2-HMAC-H with a very low-entropy password (e.g. known), and the collision-resistance of H is broken (e.g. MD5), it is possible to test several $\text{Salt}$ (with a complex relation among them) in a single try. But now that the question has mutated from its initial simple form to something theory-oriented, I guess that's not the point.


Restricting to $\text{dkLen}$ equal to the width of $\text{PRF}$, $$\text{PBKDF2}(\text{PRF}, \text{Password}, \text{Salt},c)=U_1\oplus U_2\oplus\ldots U_c$$ with $$\begin{align} U_1&=\text{PRF}(\text{Password}, \text{Salt}\mathbin\|\mathtt{00000001})\\ U_2&=\text{PRF}(\text{Password}, U_1)\\ \cdots\\ U_c&=\text{PRF}(\text{Password}, U_{c-1}) \end{align}$$

Without proof: if $\text{PRF}$ is a wide-enough truly random function, then $\text{PBKDF2}$ is computationally indistinguishable from a random function. Therefore, from a computational perspective, learning something about its input from its output is an all-or-nothing thing: if the adversary can guess the right $\text{Password}$ and $\text{Salt}$, and finds a match, s/he has strongly comforted the guess (there's probability $2^{-8\cdot\text{dkLen}}$ that a random try matches). Otherwise, s/he learns nothing of any significance.

If $\text{PRF}$ is badly defective (perhaps intentionally), then something about $\text{Salt}$ can leak. For example we can define $$\text{PRF}(\text{Password},x)=\begin{cases} \text{the all-zero bitstring, if }x\text{ has width dkLen}\\ x\text{ zero-padded then left-truncated to width dkLen, otherwise.} \end{cases}$$ and then the left $\text{dkLen}$ bytes of $\text{Salt}$ leak (except when $\text{Salt}$ is exactly $\text{dkLen}-4$-byte, and that exception can further be reduced, or removed for odd $c$).

$\endgroup$
  • $\begingroup$ So is it possible for an attacker to do better than a random guess? And does this depend on the PRF being used, or any PRF will do? $\endgroup$ – Cyker Jul 7 '18 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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