3
$\begingroup$

Is there any reason to use something stronger than SHA-1 with PBKDF2 if my input is fairly low entropy? I.e. if the passwords being hashed are only about 30-bits of entropy.

I can't find it now, but someone stated if you want to preserve the entropy of high entropy intput, then use PBKDF2 with a higher SHA. So I'm wondering if the inverse is true, that there is no real gain to using SHA-512 if your input is low entropy.

I've seen one case mention that using SHA-512 would increase the memory requirements for attackers. In some cases, I know that increasing memory requirements will make GPU hashing less effective. Not sure if that's true in this case. https://cryptosense.com/blog/parameter-choice-for-pbkdf2/

Improve this question
$\endgroup$
6
  • $\begingroup$ No matter how many times you hash, it cannot increase the entropy. Also, 30-bit entropy is too low for secure passwords. $\endgroup$
    – kelalaka
    Nov 8, 2019 at 18:18
  • $\begingroup$ True, but not really trying to increase entropy. Just trying to see if there's any decision points on SHA-1 vs SHA-512 in this context. $\endgroup$
    – AaronLS
    Nov 8, 2019 at 18:22
  • $\begingroup$ For entropy preservation to matter even theoretically in the first case, you would at least need close to 160-bit entropy. With that kind of input, you don't need PBKDF2. (Not with more than one round, anyway.) A fast, preimage-attack-resistant function is good enough for password authentication. Key derivation is only slightly more nuanced. It still wouldn't matter if you used a fast KDF with that much entropy. $\endgroup$
    – Future Security
    Nov 9, 2019 at 5:42
  • $\begingroup$ For low entropy inputs it only matters how expensive it is to crack a hash. That's primarily a question of hash function's performance characteristics, not really it's security properties. There are many variables that effect that cost. How much memory a function uses is just one variable. You need to use orders of magnitude more memory for it to be significant on it's own. $\endgroup$
    – Future Security
    Nov 9, 2019 at 5:49
  • $\begingroup$ @Future "For low entropy inputs it only matters how expensive it is to crack a hash." We agree, and that's the premise of the question. "There are many variables that effect that cost." Yes, and some of them can put GPUs at a disadvantage, which is usually desirable because the CPU based application is in an arms race with attackers leveraging GPUs. The benchmarks demonstrate that algorithm selection can put GPUs at a disadvantage. $\endgroup$
    – AaronLS
    Nov 11, 2019 at 20:18

2 Answers 2

Reset to default
4
$\begingroup$

I've seen one case mention that using SHA-512 would increase the memory requirements for attackers. In some cases, I know that increasing memory requirements will make GPU hashing less effective. Not sure if that's true in this case.

If you're going to use PBKDF2 (instead of, say, Argon2) and you have the option to use SHA-512, you should definitely pick it, for the reason you give—since the computation requires more memory, it's disadvantageous to GPU-based password crackers. Here's from one arbitrarily-picked Hashcat benchmark:

Hashtype: SHA1

Speed.Dev.#1.:  8538.1 MH/s (96.95ms)
Speed.Dev.#2.:  8511.0 MH/s (97.22ms)
Speed.Dev.#3.:  8625.6 MH/s (97.79ms)
Speed.Dev.#4.:  8599.6 MH/s (96.85ms)
Speed.Dev.#5.:  8617.4 MH/s (97.89ms)
Speed.Dev.#6.:  8560.9 MH/s (97.30ms)
Speed.Dev.#7.:  8640.8 MH/s (97.61ms)
Speed.Dev.#8.:  8677.5 MH/s (97.22ms)
Speed.Dev.#*.: 68771.0 MH/s

Hashtype: SHA256

Speed.Dev.#1.:  2865.2 MH/s (96.18ms)
Speed.Dev.#2.:  2839.8 MH/s (96.65ms)
Speed.Dev.#3.:  2879.5 MH/s (97.14ms)
Speed.Dev.#4.:  2870.6 MH/s (96.32ms)
Speed.Dev.#5.:  2894.2 MH/s (96.64ms)
Speed.Dev.#6.:  2857.7 MH/s (96.78ms)
Speed.Dev.#7.:  2899.3 MH/s (96.46ms)
Speed.Dev.#8.:  2905.7 MH/s (96.26ms)
Speed.Dev.#*.: 23012.1 MH/s

Hashtype: SHA512

Speed.Dev.#1.:  1071.1 MH/s (96.43ms)
Speed.Dev.#2.:  1063.9 MH/s (96.40ms)
Speed.Dev.#3.:  1084.2 MH/s (96.25ms)
Speed.Dev.#4.:  1076.9 MH/s (96.03ms)
Speed.Dev.#5.:  1080.2 MH/s (96.64ms)
Speed.Dev.#6.:  1074.1 MH/s (96.16ms)
Speed.Dev.#7.:  1086.3 MH/s (96.01ms)
Speed.Dev.#8.:  1088.1 MH/s (95.91ms)
Speed.Dev.#*.:  8624.7 MH/s

This GPU can only compute SHA-512 about 13% as fast as SHA-1, and 37% as fast as SHA-256. And 64-bit CPUs can compute SHA-512 quicker than SHA-256, so it's an even bigger win.

Note those results are for raw SHA-*, when use PBKDF2 the iterations slow the attacker down further, for example (from same page):

Hashtype: PBKDF2-HMAC-SHA1

Speed.Dev.#1.:  3233.9 kH/s (67.40ms)
Speed.Dev.#2.:  3198.7 kH/s (68.17ms)
Speed.Dev.#3.:  3286.2 kH/s (67.40ms)
Speed.Dev.#4.:  3275.8 kH/s (67.07ms)
Speed.Dev.#5.:  3305.3 kH/s (66.98ms)
Speed.Dev.#6.:  3239.7 kH/s (67.85ms)
Speed.Dev.#7.:  3302.3 kH/s (66.97ms)
Speed.Dev.#8.:  3314.4 kH/s (66.78ms)
Speed.Dev.#*.: 26156.2 kH/s

Hashtype: PBKDF2-HMAC-SHA256

Speed.Dev.#1.:  1173.1 kH/s (81.39ms)
Speed.Dev.#2.:  1171.6 kH/s (85.26ms)
Speed.Dev.#3.:  1194.3 kH/s (77.60ms)
Speed.Dev.#4.:  1182.9 kH/s (80.93ms)
Speed.Dev.#5.:  1182.3 kH/s (86.08ms)
Speed.Dev.#6.:  1174.8 kH/s (81.28ms)
Speed.Dev.#7.:  1191.0 kH/s (77.58ms)
Speed.Dev.#8.:  1203.1 kH/s (80.72ms)
Speed.Dev.#*.:  9473.2 kH/s

Hashtype: PBKDF2-HMAC-SHA512

Speed.Dev.#1.:   431.4 kH/s (88.54ms)
Speed.Dev.#2.:   425.8 kH/s (89.24ms)
Speed.Dev.#3.:   432.5 kH/s (89.37ms)
Speed.Dev.#4.:   433.5 kH/s (89.18ms)
Speed.Dev.#5.:   433.4 kH/s (90.16ms)
Speed.Dev.#6.:   427.2 kH/s (85.02ms)
Speed.Dev.#7.:   432.7 kH/s (88.89ms)
Speed.Dev.#8.:   433.7 kH/s (88.67ms)
Speed.Dev.#*.:  3450.1 kH/s

I can't find it now, but someone stated if you want to preserve the entropy of high entropy intput, then use PBKDF2 with a higher SHA. So I'm wondering if the inverse is true, that there is no real gain to using SHA-512 if your input is low entropy.

The word "entropy" is very technical and tends to confuse people. One useful practical way to think about it in this context is that the entropy of a password is a way of estimating how many attempts it takes an attacker to guess it. If you look at it this way, it should be clear that slowing down the rate at which the attacker can attempt guesses is good as long as it doesn't impose unreasonable costs on the defender. Running openssl benchmark sha1 sha256 sha512 on my computer I get:

type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
sha1            111320.78k   284724.68k   566193.99k   754458.21k   867765.68k   884538.07k
sha256           67121.90k   161239.47k   297468.75k   357967.84k   383634.68k   404701.29k
sha512           46691.15k   181327.42k   330951.90k   501714.45k   523881.21k   582528.17k

So using the 16 and 64 byte numbers, SHA-512 is 40-60% as fast as SHA-1 on my 64-bit CPU. But as we saw above, SHA-512 was only about 12.5% as fast as SHA-1 in the GPU benchmark we looked at. So for a modest cost in CPU time you're imposing a much bigger cost in GPU time. This is what you want to see!

Improve this answer
$\endgroup$
4
  • $\begingroup$ "since the computation requires more memory, it's disadvantageous to GPU-based password crackers" This was my understanding, and I appreciate the effort you put into obtaining benchmarks to backup the claim, since others seemed to believe the memory usage would not make a difference. $\endgroup$
    – AaronLS
    Nov 11, 2019 at 20:31
  • 1
    $\begingroup$ @AaronLS It's not that I believe the memory usage makes no difference—it's just a small difference, and there's no parameters for scaling it according to the resources the legitimate user has available: the only way to adjust attack costs is to choose a different algorithm altogether. In contrast, with Argon2, if the user has (say) 256 MB of RAM available, and four CPU cores, they can use that with the same user-visible latency as PBKDF2-HMAC-SHA256—say 1 sec to log in—but tremendously higher cost for the same GPU throughput or tremendously lower GPU throughput for the same cost. $\endgroup$
    – Squeamish Ossifrage
    Nov 11, 2019 at 21:54
  • $\begingroup$ (To be clear, @LuisCasillas gave a better answer than I did to the specific question you asked; I'm just putting the question into a broader context by suggesting Argon2 instead of PBKDF2.) $\endgroup$
    – Squeamish Ossifrage
    Nov 11, 2019 at 21:56
  • 1
    $\begingroup$ @AaronLS: The memory usage makes a big difference in the context of GPU-based password cracking, which is the most popular kind by far in the present day. If you take a broader look than that and consider other types of hardware that could be used, or perhaps even hypothetical future GPUs, the picture could change. Which is the point for why to look at Argon2 instead of PKBDKF2 if you can; the fact that PBKDF2 w/SHA-512 is so much more effective against GPUs than with SHA-1 is an accident, not something that was carefully designed for. $\endgroup$
    – Luis Casillas
    Nov 12, 2019 at 18:07
3
$\begingroup$

There is not much of a substantive difference between using SHA-1 or SHA-256 with PBKDF2 to hash a password: they use nearly the same amount of memory (20 bytes vs. 32 bytes of state, plus 8 bytes of message length and 64 bytes of input buffer), and SHA-512 uses only double what SHA-256 uses (64 bytes state, 16 bytes length, 128 bytes buffer).

If you can, forget PBKDF2 and consider using Argon2id instead, so that if you have (say) 128 MB free for password hashing—and perhaps a few extra CPU cores—you can use it all to drive up an adversary's costs.

Improve this answer
$\endgroup$

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.