I'm trying to generate a bunch of pseudo-random keys for AES using PBKDF2, where the AES ciphers will be used in CTR mode as pseudo-random number generators. My goal is to create a 2-dimensional array, where each entry is a pseudo-random sequence generated by a separate PRNG. The reason for using separate PRNGs is simply because I want each cell to have equal cost to calculate (due to the PBKDF).

So I have two random strings, r1 and r2 (user provided), and I'm generating the AES key for cell (x,y) as PBKDF2(i || r1, r2 || j), where i and j are single characters bijectively mapped to x and y respectively, and || denotes concatenation. I'm using HMAC-SHA256 for the PRF, and nominally 1000 iterations of the PBKDF2. Currently r1 and r2 are 16 bytes each, but I can make them basically any size.

So my questions are:

  1. Is there any weakness in using such closely related inputs to PBKDF2, in particular when used as AES keys for CTR more?
  2. Is there any shortcut for calculating the result of the PBKDF2 for different cells that is any faster than having to calculate it from scratch for each cell?

1 Answer 1

  1. If there would be risk from related inputs one would know that because then HMAC would be target to chosen plaintext attacks and hence PBKDF2 would have been fully obsolete. So there's no weakness in using related inputs.
  2. As each cell basically has a different password there's no faster way than brute-force to find out the values. However, if you know how the mapping takes place and you broke r1 and r2, one can fastly calculate the other entries (as fast as the defender did, as there's no entropy left)
  3. I'd suggest you to increase the iteration count to 1000000 as this is far more secure and still takes less than a second on most pcs.
  4. 16 bytes for the r-values suffices, if you got "high entropy" in them (80 bits + -> >6 bits per byte)
  5. As pointed out correctly in the comments, PBKDF2 is not a viable choice for password hashing. Rather use scrypt or the winner of the PHC (announced within next two months)
  • 2
    $\begingroup$ Also: consider Scrypt rather than PBKDF2; it gives a significantly better protection against ASIC-based brute force attacks for the same cost of legitimate use. $\endgroup$
    – fgrieu
    Apr 12, 2015 at 15:52
  • $\begingroup$ @SOJPM: WRT to point 2: if you know r1, r2, and know how i and j are generated, granted there's no guess work that needs to be done, but can you generate say N cells faster than N times however long it takes to run the PBKDF2? Likewise for scrypt? $\endgroup$ Apr 21, 2015 at 0:55
  • 1
    $\begingroup$ no, you can't generate the contents of the cells faster than calling the function for each cell. (Neither using scrypt nor with PBKDF2) However this is nothing compared to the time you need to find out r1/r2 $\endgroup$
    – SEJPM
    Apr 21, 2015 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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