Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

The purpose of PBKDF2 is to create a derived key (DK) from a master password (PW) and a salt, often using a function like HMAC-SHA256. I have read that the salt should be as random as possible. But if that's the case, why does it play such a minor role?

I'll let the equations speak for themselves, starting with HMAC-SHA256:

$$\def\op{\operatorname}\def\0#1#2#3{\text{0×#2#3}} \op{HMAC-SHA256}( PW, m ) = \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ m ) ) $$ where $$\begin{align*} K &= \begin{cases} PW &\textrm{if } \op{bytes}( PW ) = 64 \newline \op{SHA256}( PW ) ∥ [\0x00]_{32} &\textrm{if } \op{bytes}( PW ) > 64 \quad \textrm{ (32 zero bytes)} \newline PW ∥ [\0x00]_{64-\op{bytes}(PW)} & \textrm{if } \op{bytes}( PW ) < 64 \end{cases} \newline K_i &= K ⊕ [\0x36]_{64} \newline K_o &= K ⊕ [\0x5c]_{64} \newline \end{align*}$$

Now PBKDF2:

$$ \begin{align*} DK &= T_1 ∥ T_2 ∥ ... ∥ T_{\op{len}(DK)/\op{len}(T_i)} \newline T_i &= U_1^i ⊕ U_2^i ⊕ ... ⊕ U^i_{\text{iterations}} \newline U^i_1 &= \op{HMAC-SHA256}( PW, \op{salt} ∥ \op{INT32}( i ) ) \newline U^i_n &= \op{HMAC-SHA256}( PW, U^i_{n-1} ) \end{align*} $$

But watch what happens if the two are combined:

$$\begin{align*} U^i_1 &= \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ \op{salt} ∥ \op{INT32}( i ) ) ) \newline U^i_2 &= \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ \op{salt} ∥ \op{INT32}( i ) ) ) ) ) \newline & \dots \end{align*}$$

Or in pseudocode:

$$\begin{align*} &T[i] = 0 \newline &U = \op{salt} ∥ \op{INT32}(i) \newline &\text{for } n = 1 \text{ to }c: \newline &\qquad U = \op{SHA256}( K_i ∥ U ) \newline &\qquad U = \op{SHA256}( K_o ∥ U ) \newline &\qquad T[i] = T[i] ⊕ U \newline &\text{next }n \newline \end{align*}$$

So the salt is used only once per output block, while the master password is used twice per iteration (in the forms $K_o$ and $K_i$). I understand that the avalanche effect means a slight change in the initial hash input will have a significant impact on the hash output, but wouldn't it make sense to introduce as much entropy into the final result as possible?

share|improve this question
    
Welcome to Cryptography Stack Exchange. We have some kind of TeX-like formatting here, which allows both easier and nicer formatting than what is possible in HTML. I edited your question to include this formatting, as well as a clearer title. Feel free to revert or edit again. –  Paŭlo Ebermann Sep 5 '12 at 20:12
    
Danke kind sir. –  ericball Sep 6 '12 at 13:44
add comment

2 Answers

Summary: I don't know of any good reason why it has to be this way. In practice, I don't think it is necessary to inject the password into every iteration. As far as I know, I think the construction would still be secure (in practice) if you used the salt and password only in the input to the first iteration, and then just repeatedly hashed the result many times without feeding in the password any further.

So why does PBKDF2 do it, if it is not strictly necessary for security? I don't know. I can only speculate -- and you should take my speculation with a large grain of salt. That said, my speculation is that, by using the key in every iteration, you can get some slightly better provable-security results.

Technical speculation: it has to do with the security proof. In particular, with PBKDF2, it is possible to prove a statement along the lines of: if HMAC-SHA256 is a secure PRF, and if the password is a full-entropy full-strength crypto key, then PBKDF2(password, salt) is a secure cryptographic key. No such statement would available if every iteration after the first used a bare hash instead of a HMAC PRF; you'd need to make stronger assumptions, such as work in the random oracle model (i.e., assume that the hash is perfect in every regard).

That said, the difference in provable security feels rather negligible to me. The security claim that you can prove about PBKDF2 (without the random oracle model) is not very exciting. PBKDF2 is primarily used to derive keys from a memorable password that is not full-entropy, and that situation is not covered by the security proof above. So, as far as I can see, I don't know of any compelling reason why PBKDF2 was designed to inject the password into every iteration of the algorithm.

Standard disclaimer: don't roll your own. Please don't take this post as a justification for modifying PBKDF2 and using your modified version of PBKDF2. That would be a pretty risky thing to do. Even if we can't think of any strong reason why PBKDF2 had to be designed the way it did, it's still safer to use the standard primitive. PBKDF2 has been well-vetted, and who knows, maybe there's some problem with the variant that hasn't occurred to me.

share|improve this answer
    
I agree - repeatedly injecting low entropy into a hash function just doesn't seem "right". In addition, the last 256 bits of the SHA256 input will be zero (as Ki/Ko are defined to be 512 bits and SHA256 has a 256 bit output and a 512 bit block size); again adding low entropy to the function. If I were to design a PBKDF I'd want to inject as much entropy as possible, but I also agree with the disclaimer. –  ericball Sep 7 '12 at 16:15
add comment

It's not really PBKDF2 that uses the key twice. PBKDF2 uses HMAC, and HMAC happens to work by using the key twice.

More specifically, PBKDF2 is actually a general construction that uses a cryptographic Pseudo-Random Function (PRF) to do some of the internal work. The PRF used here is keyed HMAC. The HMAC construction itself uses two keys derived separately from the original key. From the PBKDF2 description included in the question, the $K_o$ and $K_i$ values are the outer and inner HMAC keys, respectively.

This would then shift the question to: "Why does HMAC use two keys"? This is addressed in other questions:

Another closely related question with a relevant answer: Hash function in PBKDF2.

share|improve this answer
1  
I think the main question was "why was the salt only used once (at the beginning), and not also in each iteration?" –  Paŭlo Ebermann Sep 6 '12 at 7:25
    
Correct. I understand the HMAC construction (which is really more of a workaround to address the length-extension attack weaknesses common to Merkle–Damgård construction hash functions), but the Un = PRF( PW, Un-1 ) construction is specific to PBKDF2. If just happens that if the PRF is an HMAC then the PW (which is typically short & low entropy) is used far more than the salt (which may have much better properties). –  ericball Sep 6 '12 at 14:05
    
OK, I mis-understood the question. Not sure if the answer is on-topic enough to leave. –  B-Con Sep 6 '12 at 16:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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