Why does PBKDF2 xor the iterations of the hash function together?

Question

The definition of PBKDF2 states that I obtain a derived key ⁽¹⁾ by calling a pseudorandom function a bunch of times recursively:

$U_1 = PRF(password, salt)$
$U_2 = PRF(password, U_1)$
…
$U_n = PRF(password, U_n-1)$

The standard then defines the actual key material K as

$K = F(password, salt, n)$

where F is $U_1 \oplus U_2 \oplus \cdots U_n$

I don't understand what the purpose of XORing the blocks together is. Assuming that PRF is a cryptographically strong function, how does XORing the blocks help? Why is $U_n$ not strong enough key material by itself?

The standard mentions that the blocks are XORd together “to reduce concerns about the recursion degenerating into a small set of values” but I guess I don't understand how that can happen since the password is being fed back into the function at each iteration.

If the recursion can degenerate into a small set of values, doesn't that mean there is a short cycle in the hash function? Isn't that a bad thing for cryptographic hash functions?

_{⁽¹⁾ Assume for simplicity that the key is the same length as the hash function output.}

Answer 1

The XOR is indeed meant as a protection against hypothetical short cycles. For a given password $P$, the sequence of $U_i$ should make a "rho" structure: at some point in the sequence, a cycle is entered. For a $n$-bit hash function and random password, on average, there will be a single "big" cycle of size about $2^{n/2}$ and for almost all possible salt values, that cycle will be entered after following a "queue" of average length $2^{n/2}$. However, there can exist passwords for which the central cycle is smaller than that, and there can also be some extra small cycles. Finding a password which yields a small central cycle, or hitting a salt value which leads to an alternate small cycle, is overwhelmingly difficult, and no known example of that is known. Yet the PBKDF2 designers thought that the XOR was a cheap way to cope with such a risk: in effect, this means that the $U_i$ will depend on the queue as well as on the cycle itself.

There is a potentially important point here: when you apply the PRF, i.e. jump from $U_i$ to $U_{i+1}$, the space "shrinks": not all $n$-bit values are possible as output of the PRF. The further you go, the more the space shrinks, until you reach the "central cycle". This implies that if $F$ used only $U_c$ (the last $U$ value), then the space of the generated $n$-bit key blocks would be less than $2^n$; in other words, you would use a hash function with a $n$-bit output and you would not get your $n$ bits worth of security. The XOR aims at counteracting this effect.

Nevertheless, the PBKDF2 structure has never been, to my knowledge, proven in any way, so I would recommend using it only with a hash function which outputs $2n$ bits, if $n$-bit security is to be achieved. E.g., for 128-bit security (a sensible level), use SHA-256. Thus, the big central cycle size will be, by itself, sufficient, regardless of whether the extra XOR is really beneficial or not.

Answer 2

@D.W. is probably closest to the real reason (this was fifteen years ago, so things get a bit hazy), there was some concern about short cycles, and it was effectively free - you're already iterating the hashing deliberately to slow things down so speed isn't an issue - so why not do it? You've also got to remember the historic context, when replacements for PKCS #5v1 were being thought about, HMAC didn't exist yet, so you couldn't just drop in a black box with "PRF with certain provable properties" written on it. For example here's one concept from back then:

key = {};
state = hash( algorithm, mode, parameters, userKey );

for count = 1 to iterations
    state = hash( state );
    key ^= hash( state || userKey );

Note the absence of HMAC in that (incidentally, the reason for hashing in the algorithm parameters at the start was so that a key-recovery on a 40-bit RC4 key - remember those? - wouldn't also recover most of a 56-bit DES key if you repeated the salt, which is a mistake that's occurred a number of times).

@Marsh: That too. Hans Dobbertin's dual-pipe design for RIPEMD-160 had just come out about then, and that was somewhat influential. Another concern, arising from the long-running is-DES-a-group issue, was whether you could somehow collapse n iterated hashes H() to a single hash H'(). Extracting data at each hash step would prevent that. Overall though, it was a long time ago, and all sorts of ideas got thrown around, so picking apart what lead to what is probably impossible at this point.

Note: I'm not the author of PKCS #5v2, I was just involved in the discussion of KDFs at the time.

Answer 3

To be honest, there's no good reason why the XOR is needed. My suspicion is that, most likely, the designers included it because they thought, "hey, why not? it can't hurt". But if the designers had left out the XOR, everything would have been just fine.

In particular, if PRF() is a secure pseudorandom function, and if we stick with typical parameters, then you are right: we don't need to XOR things, just using U_n would be fine.

As @Thomas Pornin mentions, one could worry about short cycles or entropy loss. It turns out that, if PRF is a secure pseudorandom function (and if we avoid funky parameter choices that no one would ever use in practice), then one can show that these aren't a problem. So the designers would have been perfectly justified to just use U_n.

Now I can imagine some designer might have said, hey, what if the PRF turns out to be flawed, then maybe short cycles or entropy loss could become a problem; to deal with that possibility, maybe it'd be nice to have some fallback, and maybe the XOR could provide some fallback protection even if the PRF is flawed. I could imagine some designer thinking that way. I don't know of any formal basis in support of this (I don't know of any hard evidence that, if the PRF is flawed, then the XOR is likely to be more secure), but I also don't know of any formal basis that would recommend against this. So this seems like a harmless variant. It might help security. I wouldn't rely upon it to help security, and we don't know whether it actually helps, but hey, why not, it's cheap? And if the PRF truly is secure, it doesn't harm anything.

So I can imagine some designer following that thought process when they introduced the XOR. They could have left out the XOR and just used U_n, and that also would have been fine too. Most likely this is just a slight tweak to try to optimize the security of the scheme in the event of an unexpected failure of the PRF.

(There is another possibility. The other possibility is that the designer was confused: namely, that the designer wasn't aware of the results showing that short cycles and entropy loss aren't a problem in practice, if the PRF is secure, and incorrectly thought that it would be insecure to just use U_n. I suppose that's a possibility. But I don't like to assume ignorance when there's an alternative explanation that's perfectly good.)

Answer 4

I agree with you. The XOR seems utterly pointless. A short cycle in the hash chain seems no more likely nor more unlikely than a short cycle in the hash/XOR chain. If one can degenerate into a sequence where additional iterations don't change the value, so can the other. If one can't, neither can the other.

Answer 5

Leaving aside the question of whether or not this is a useful feature, my theory is the designer of PBKDF2 were familiar with the design changes made from MD5 to SHA-1 and felt that it might be beneficial to introduce a parallel data channel like the SHA-1 key expansion array (also constructed with XOR). With negligible overhead, the XOR doubles the bandwidth of the narrowest part of the data flow graph over PBKDF1. At the time this probably seemed unlikely to hurt and might even contribute a bit of safety.

Answer 6

I disagree with the other answers in that I think taking XOR of the blocks was a useful addition, no matter the reason it was originally put in.

Suppose we had a KDF defined as PBKDF2, but taking the last block instead of a XOR of all blocks. Let's ignore multi-block support and define it simply as:

$$\begin{align} U_1(p, s) &= H_p(s) \\ U_i(p, s) &= H_p(U_{i-1}(p, s)) \ \ ||\ i>1 \\ K(p, s) &= U_n(p, s) \end{align}$$

Now, the reason we have the salt $s$ there is that we want $K(p, s_1) \not= K(p, s_2)$ when people use the same password. How likely is that?

Given $s_1 \not= s_2$ and $P(H_p(s_1)=H_p(s_2)) = 2^{-b}$, we have:

$$\begin{align} P(U_1(p, s_1) &\not= U_1(p, s_2)) = 1 - 2^{-b} \\ P(U_2(p, s_1) &\not= U_2(p, s_2)) = (1 - 2^{-b})^2 \\ P(U_3(p, s_1) &\not= U_3(p, s_2)) = (1 - 2^{-b})^3 \\ ...\\ P(U_n(p, s_1) &\not= U_n(p, s_2)) = (1 - 2^{-b})^n \approx 1 - n*2^{-b}\\ \end{align}$$

If $n = 2^k$ we have a collision probability of $2^{k-b}$ between just two uses of the same password. At the very least that means that given two users with equal password hashes you can guess that they have the same password. And that applies globally, regardless of site specific salts or peppers, because the salts were already assumed to be different.

Even if the size of HMAC-SHA-256 – or even HMAC-SHA-1 (used in original definition) – makes that not matter in practice with realistic $k$, there's something wrong with your hash getting weaker the more iterations you add.

Now, suppose Alice is trying to brute force crack a huge password database. Each guess can be compared against all the password hashes, because if it matches one it's most likely the same password, since those collisions are much more likely. So the password hash doesn't achieve the purpose that passwords have to be attacked independently.