Why does PBKDF2 xor the iterations of the hash function together? The definition of PBKDF2 states that I obtain a derived key (1) 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?

(1) Assume for simplicity that the key is the same length as the hash function output.
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.