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

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)
...


The standard then defines the actual key material K as

K = F(password, salt, n)


where F is U_1 XOR U_2 XOR ... 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.

-
I wonder why they don't also hash the counter i for U_i? –  starblue Jul 16 '11 at 7:38

The XOR is indeed meant as a protection against hypothetical short cycles. For a given password P, the sequence of Ui 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 2n/2 and for almost all possible salt values, that cycle will be entered after following a "queue" of average length 2n/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 Ui 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 Ui to Ui+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 Uc (the last U value), then the space of the generated n-bit key blocks would be less than 2n; 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.

-
Nice comprehensive answer! Thanks! –  Cameron Skinner Jul 16 '11 at 20:04
When I glanced at it the other day, it looked to me like when it was used with HMAC, the combined internal structure would allow an attacker to precompute the (k^ipad) and (k^opad) hash blocks from his dictionary, as they depend only on the password. So the attacker can save himself work proportional to (output block count + 1) over a naive implementation by the defender. This may have been an intentional design to allow the use of noniterated HMAC keying, but seems to be an undocumented consideration. –  Marsh Ray Aug 3 '11 at 0:16
The space does shrink, but not enough to matter in practice (this can be proven). Similarly, cycles will be of length 2^n/2, but in practice this doesn't matter. One can prove that if the PRF is secure, then it is vanishingly unlikely to stumble upon a cycle short enough to cause security problems (for typical parameters choices). Of course, if the PRF is insecure, then all bets are off -- but if the PRF, the construction might be insecure, even with the XOR, so it behooves you to do everything possible to ensure the PRF is secure. –  D.W. Aug 15 '11 at 4:09
@Thomas Pornin +1 good post, why don't you have any interest in proving PBKDF2? Perhaps you don't rely upon it. –  Rook Aug 17 '11 at 17:09

@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.

-

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.)

-