2
$\begingroup$

I'm attempting to diagram PBKDF2 for a school project and I'm not 100% sure how to represent the XOR step. Specifically, I'm confused as to whether the output of the XOR step is used in subsequent rounds or if it is calculated each round in order to make all rounds identical. Here's a diagram showing what it might look like if the answer is that the output of the XOR step is not used as an input to later rounds. Is this correct?

enter image description here

This diagram is based on the one on the very excellent blog post here: https://stewilliams.com/serious-security-how-to-store-your-users-passwords-safely-2/

$\endgroup$
  • $\begingroup$ That blog is unclear and somewhat ambiguous, but you can look at the actual standard tools.ietf.org/html/rfc2898#section-5.2 and learn the iterated PRF outputs, which you label "Intermediate Salt 1,2..?" (except you mislabeled N as 1) and the standard labels "U_1,2..c" (_ means subscript), are nominally all XORed together, in practice by XORing each in turn into an "accumulator", which you could well show as a chain down the right. Also this whole process is for one block of derived key material and is repeated for longer actual keys, which is not needed for password hashing. $\endgroup$ – dave_thompson_085 Dec 3 '14 at 5:56
2
$\begingroup$

So, I've been interested in building a diagram myself, and I find your diagram slightly misleading. I don't know if it's a mistake, or intentionally hiding specific pieces of the algorithm, but I think it could benefit from more granularity.

According to RFC 2898, the algorithm is as follows:

  • Take the ceiling of the division the desired key length (dkLen) by the digest size. This will give you the number of intermediate keys to concatenate at the end.

So, for a 512-bit key, using HMAC-SHA-256 as the hashing function, we will only need 2 intermediate keys to concatenate, each 256-bits in size:

CIEL(512/256) = 2
  • For each intermediate key T_i, apply F(P, S, c, i), where F() is a generic function defined below, P is your password, S is a salt, c is the number of rounds, and i is the intermediate key index.

Thus, T_1 = F(P, S, c, 1), and T_2 = F(P, S, c, 2). The final key will be those concatenated:

T = (T_1 || T_2) = (F(P, S, c, 1) || F(P, S, c, 2))
  • F() is defined as the exclusive-or sum of the first c iterates of the underlying pseudorandom function applied to the password and the concatenation of the salt and the block index i.

Thus, F(P, S, c, 1) = U_1 XOR U_2 XOR ... U_c and F(P, S, c, 2) = U_1 XOR U_2 XOR ... U_c. In other words, each intermediate key is processed with c rounds. Thus, for 2 intermediate keys, we are doing 2c rounds to build the final key. Generically, for n-intermediate keys, we are doing n*c rounds to build the final key.

  • U_i is defined as the most granular function, giving us the interface to the pseudorandom hashing function. U_i is processed c times using its previous output as the "salt" for the next input

Note that at the first round, we concatenate the intermediate index counter to the salt, thus ensuring that U_1 is always unique for each intermediate key.

U_1 = PRF(P, S || i)
U_2 = PRF(P, U_1)
...
U_c = PRF(P, U_c-1)

So, if we specificed c=100, then:

T_1:
  U_1 = PRF(P, S || 1)
  U_2 = PRF(P, U_1)
  ...
  U_100 = PRF(P, U_99)
T_2:
  U_1 = PRF(P, S || 2)
  U_2 = PRF(P, U_1)
  ...
  U_100 = PRF(P, U_99)

Finally, concatenate the intermediate keys, producing the desired key length:

T = T_1 || T_2

Thus, in your diagram, I think you should specify that "PRF" is doing c-rounds of XOR with to produce the intermediary key.

I think this flowchart might be a bit more thorough:

PBKDF2 Flowchat

| improve this answer | |
$\endgroup$

Your Answer

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