4
$\begingroup$

I want a key stretching system that's as strong as the stronger of scrypt and PBKDF2. The consensus now is that scrypt is by far the better system, but that might change if in the future, a weakness is found in Salsa20. Here is a proposed system that I dreamed up, does it seem like a good idea?

First run scrypt and produce twice as much key material as needed. Use $N$, $r$ and $p$ parameters as normal.

$k_0 = \mathrm{scrypt}(\mathrm{key},\mathrm{salt},2 \cdot \mathrm{len},N,r,p)$

Then split the key $k_0$ into to equal pieces, $k_1$, and $k_2$. Now run PBKDF2, picking a sizable $c$ parameter:

$k_3 = \mathrm{PBKDF2}(k_2, \mathrm{salt}, \mathrm{len}, c)$

Finally, output $k_1 \oplus k_3$.

I was thinking that advantage of this construction over a more naive one (or just turning up the $c$ parameter in the PBKDF2 final round of scrypt) is that the original key isn't used as an input to the weaker PBKDF2, and that the output of PBKDF2 can't weaken the output of scrypt. However, if scrypt turns out to be easier than expected due to a Salsa20 weakness, then it still is necessary to brute-force PBKDF2.

$\endgroup$
2
  • 2
    $\begingroup$ One theoretical issue with the construction is that a weakness in PBKDF2 could affect scrypt, since scrypt heavily uses PBKDF2 internally. As of practice, the password is much more likely to leak in other ways than a theoretical attack on scrypt; e.g. eavesdropping, reuse of the same password on another system, very poor password choice allowing brute force attack. $\endgroup$
    – fgrieu
    Nov 19, 2013 at 6:59
  • $\begingroup$ Right, there are two uses of PBKDF2 --- the first to stretch the original key into $128rp$ bytes to seed $\mathrm{smix}$, and the second to stretch the output of $\mathrm{smix}$ into $\mathrm{dkLen}$ bytes. In both cases, the iteration count is $c = 1$. If you ask for $\mathrm{dkLen} \le 32$, then the second call to PBKDF2 is simply a call to HMAC-SHA-256. $\endgroup$
    – Max Krohn
    Nov 19, 2013 at 12:18

1 Answer 1

2
$\begingroup$

scrypt uses PBKDF2 internally, so it's absolutely crucial to prevent nasty interactions. My suggestion would be a simpler scheme (using simplified syntax):

$k = \mathrm{scrypt}(\text{key}, \text{salt} \mathbin\| 0x0) \oplus \mathrm{PBKDF2}(\text{key}, \text{salt} \mathbin\| 0x1)$

This does exactly what you want - that is, the output key has exactly the strength of the stronger of the two, without nasty interactions. Your construction may or may not have the same property, but the close relationship of scrypt and PBKDF2 makes me rather nervous.

$\endgroup$
5
  • $\begingroup$ One could potentially look for something that uses bcrypt and scrypt. $\:$ $\endgroup$
    – user991
    Nov 19, 2013 at 10:53
  • $\begingroup$ I prefer the simplicity of your construction, but I wonder why $H(salt)$ as an input to PBKDF2? Is the idea to have independent inputs to the two functions? If so, the first step in both scrypt and PBKDF2 is HMAC-SHA256, so we can get away something like: $k = \mathrm{scrypt}(key||\mathtt{0x1},\,salt||\mathtt{0x1}) \oplus \mathrm{PBKDF2}(key||\mathtt{0x2},\,salt||\mathtt{0x2})$ $\endgroup$
    – Max Krohn
    Nov 19, 2013 at 14:24
  • $\begingroup$ Additional benefit of this construction is running on dual core devices: it is possible to run scrypt and PBKDF2 on different cores in parallel. Thus, the combined stronger function executes (in theory) in the same time than any of these functions alone, right? $\endgroup$
    – user4982
    Nov 21, 2013 at 15:06
  • $\begingroup$ @user4982 Yes, it can be executed in parallel. Note that this is not any stronger than either of the functions, just equal to the strongest of the two. $\endgroup$
    – orlp
    Nov 21, 2013 at 15:32
  • $\begingroup$ @nightcracker scrypt's strength in Colin Percival's paper is measured in $$$. Theoretically, I would think that to break combination of password hashes would cost as much as combination of costs to break scrypt and PBKDF2. Of course, if the scrypt lives up to its promise, adding $160M to cost of $43B does not really do much and main cost remains on scrypt. (This is of course insignificant as in cryptography we usually only consider order of magnitude or few more to be meaningful.) $\endgroup$
    – user4982
    Nov 21, 2013 at 16:16

Your Answer

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

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