3
$\begingroup$

Assume we have a password and add a unique salt to prevent various precomputation attacks.

Why don't we do this:

SHA256(SHA256(SHA256 ...(Password || Salt)))   

So, we have n iterations (like in PBKDF2) and because of the iterations, it should take much longer to compute the hash for a password, which is key stretching.

Can someone explain to a newbie like me why we don't use specific algorithms like scrypt, PBKDF2, or Argon2 and do this?

$\endgroup$
  • 2
    $\begingroup$ What you propose is exactly PBKDF1. $\endgroup$ – CodesInChaos Jun 29 '18 at 7:48
7
$\begingroup$

What's proposed, and PBKDF2 alike, give significantly less protection than scrypt or Argon2. That's because adversaries trying many passwords on parallel hardware can do so at lesser cost, for a given time or CPU × time on the legitimate user's side. With scrypt or Argon2, but not the question's construct or PBKDF2:

  • A significant amount of memory is required to compute the function. This implies that the adversary has to invest in that memory for each instance of password searcher, and can't use GPUs efficiently. Password cracking for PBKDF2 (or worse) entropy stretching is common practice, using GPUS, FPGAs, I guess ASICs. I conjecture government agencies do this routinely. Bitcoin mining ASICs are close to being usable to attack the question's construct at high rate (but are not AFAIK), and PBKDF2 has comparable complexity.
  • Multiple CPUs on the legitimate user's side are leveraged. This allows to perform more work on the legitimate side for a given user's wait (raising attack cost correspondingly). That's useful when the limiting factor for parametrization of the effort per password is the user's waiting time.

The question's construct is close to PBKDF1 and comparable to PBKDF2. The main operational differences are that

  • PBKDF1 and PBKDF2 have variable size output; PBKDF1 has built-in truncation, and PBKDF2 additionally allows large output. That makes them usable in more situations. But large output is immaterial for password storage, and PBKDF2's way of generating large output is poor, as noted by CodesInChaos in comment.
  • The question's construct (and PBKDF1) has the dubious property that for all $\mathsf{password}$, $\mathsf{salt}$, and bytestring $b$, it holds $F(\mathsf{password}\mathbin\|b,\mathsf{salt})=F(\mathsf{password},b\mathbin\|\mathsf{salt})$, which PBKDF2 avoids. This is typically immaterial for password storage, but conceivably could be an issue in some other uses of PBKDF2. However PBKDF2 used with HMAC (as it almost always is) has another potentially undesirable regularity, as noted in said comment: a long $\mathsf{password}$ and its hash are equivalent.
  • For 1 iteration of SHA-256 and uniform random input, the (likely) entropy in the output is only about $256-0.827\dots$ bit (see this), and that keeps on decreasing as the number of iterations grows (see this and this). That contrasts with PBKDF2-HMAC-SHA-256 for 256-bit output (probably) next to fully and uniformly covering it's output space, with no marked decrease as the number of rounds increases, for near 256-bit entropy. However that effect in the question's construct and PBKDF1 remains beyond experimentally observable as far as we know (that would imply an attack on SHA-256), nearly disappears anyway for significantly truncated output, and has no practical significance.
$\endgroup$
  • 2
    $\begingroup$ PBKDF2 messed up the first two "improvements" over PBKDF1. The variable length output is practically unusable because it runs the whole KDF for each output block, so you should to go with HKDF-Expand anyways. And the missing domain separation between salt and password is replaced by trivial collisions/second pre-images in the password input. $\endgroup$ – CodesInChaos Jun 29 '18 at 8:09
  • $\begingroup$ @CodesInChaos: Yes! And because parameter dkLen is never hashed, the mess in the first improvement is such that if we know (some of) a long result and salt, but not key/password, a key can be tested at a fraction of the cost of computing the long result. One redeeming side effect is to allow easy definition of a fixed-width parallelizable version (apply a final hash to the output with dkLen the hash width times the number of CPUs). The mess in the second improvement is one in HMAC, which is the typical PRF used with PBKDF2 (formally, not the only one). $\endgroup$ – fgrieu Jun 29 '18 at 8:40
  • $\begingroup$ So the entropy being reduced by multiple hash functions is the reason the password is injected into each HMAC invocation! That makes more sense! $\endgroup$ – forest Jul 3 '18 at 3:30
1
$\begingroup$

In your construction it seems the password and salt are only mixed at the first iteration. We prefer to mix them in again on every iteration. This makes sure we don't end up loosing any of the entropy in the password originally.

But fundamentally this is a good construction for password hashing. not great but good. I would prefer bcrypt as it was designed to be slow and for this purpose while sha256 was designed to fast.

Argon and scrypt give an extra layer of security requiring memory reaources and not only computational resources.

$\endgroup$
  • $\begingroup$ Entropy loss is negligible. Hash functions are not one-to-one functions, but over a small set of inputs you can treat them as such in practice. If they're not one-to-one then you have a collision. The set of real world passwords isn't large enough to expect collisions. Multiplying that set size by a 1000 or even 1 million to include intermediate hashes isn't enough to make us expect collisions. If no collisions happen in practice, then the function is practically one-to-one. One-to-one means the function is lossless. Therefore the expected entropy loss is zero. $\endgroup$ – Future Security Jul 1 '18 at 23:02
  • $\begingroup$ I agree, and yet still mix in the password and salt in every round. $\endgroup$ – Meir Maor Jul 2 '18 at 0:10

Your Answer

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

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