Why I think using sha256crypt or sha512crypt is dangerous | Hacker News Reader

Why I think using sha256crypt or sha512crypt is dangerous

pthree.org

71 pointsbellinom45 comments

Article opens by claiming "DES-Crypt has a core flaw in that, not only was the algorithm reversible ..."

That's not true in any meaningful sense and points to the fact that the author hasn't any clue what they're talking about. Which doesn't magically invalidate their experiments and data, but it does mean you should probably take their opinion with an extra table spoon of salt.

DES of course is reversible, it's an encryption algorithm, so if you have the key you can just reverse it, that's the whole point. But what DES-crypt does is something else, First it takes the DES algorithm and tampers with the internals, it has 12-bits worth of random data for this, a salt (today obviously we use larger salts, but this one already makes time-space tradeoffs painful, 4096 times worse than normal against a "good" DES crypt). Then it encrypts a bunch of zero bytes using the password, and then it encrypts the result, and that result and so on, 25 times in total.

This isn't a reversible algorithm. You can't take some encrypted DES bytes, and then run DES backwards 25 times to find out what the key was knowing the original was all zero bytes, you quickly get conflicting possibilities.

What you _can_ do, in reasonable time, is try all the plausible passwords in turn, for a particular salt value. This is what DES crackers do, and for passwords like "ksdcunfm" it works pretty well on commodity hardware, which is why we don't use DES Crypt any more.

But that's not reversing the algorithm.

> Article opens by claiming "DES-Crypt has a core flaw in that, not only was the algorithm reversible ..."

> That's not true in any meaningful sense

That's exactly right, and when I published the article, I recognized that I needed to change it, but didn't get to it. I've fixed it. Thanks.

> and points to the fact that the author hasn't any clue what they're talking about.

Ouch.

How is the timing here relevant to attacking shacrypt? The run time is a function of the length of the attacker-provided string containing the password guess. That's totally fine, the attacker already knows that string. The output is a fixed-length string that is then compared to a stored (also fixed-length) hash using a constant-time comparison function.

The run time does not depend on the length of any secrets here. I don't see the issue. How can I use that to determine the length of the actual password? That length isn't even available to the password verification system anymore.

I think the author is arguing that if someone were to send a 1GB password that it could cause a DOS attack on the server performing the sha-hash of the password. Seems to me the simplest solution is to limit the length of password fields to something reasonable.

I always thought you’re supposed to hash on the client side first to avoid sending the password to the server, and then hash again on the server. Even if the password is a billion characters long, the server will only see a 60(?) byte array and hash that.

I'm of the mindset that clients shouldn't be trusted to compute sensitive hashes whether that paranoia is founded or not. Nevertheless, with https its perfectly fine to send the password in plaintext

What? The client already handles the plaintext password which is a lot more sensitive than a hash.

But the client could also see the SALT which makes it possible to use Rainbow Tables to decrypt the hashes. The SALT should be a secret to the client. Furthermore, as an attacker, I could just steal the DB hashes and send those from the client and viola I just bypassed your authentication without decrypting anything. If the server does the hashing, then it will recompute the hash of the hash which wont match.

Salts are designed to be public knowledge. They’re just supposed to be unique per hashed password to prevent rainbow table attacks against all passwords in the DB.

No two users should ever have the same salt, but they’re not a secret. As evidence I cite many of the Password Hashing Competition entries which offer “Server relief” as a feature by giving the salt to any unauthenticated client who asks so most of the hashing can be done on the client followed by a single hash iteration on the server.

A “secret per-server salt” is called “pepper” in the security community and is commonly buried in a binary or config file. Pepper has limited security value. An attacker that can get your password DB usually is able to pivot and snag config files and binaries as well.

To Start, you bring up an excellent point regarding the Pepper issue of a poorly secured salt(aka Cryptographic Key). Also, you are correct that an attacker that can get your password DB is usually able to successfully pivot.

So here's what I propose: Don't store the key anywhere. Instead, have it be computed from something(s) known and done in a very random and complex manner such that there would be no possible way to decompile release mode code in active execution without triggering a segfault and revealing yourself.

See the way you beat a rainbow table is you make the ultimate password large enough to exhaust the practical rainbow table limit since it grows exponentially. So if you do a SHA-256 hash of the password on the client size then you have effectively transformed it into a 64 character password, far larger than any rainbow table could hold. Now it is still susceptible to the direct hash storage in the DB. So I suppose the most secure way is to do it both on the server and on the client.

Good Post TaterSolid!

no that's not how it works.

If the client could simply send a hashed password over as an authenticator, then hashing the password database would provide no protection against theft, because you could simply use the stored hash as the password. This solution would only protect users from password reuse from theft.

Hashing with a negotiated salt and computing client and server side protects the password in transit but means storing the password in plaintext on the server. We use TLS (or SSH, or other encrypted protocols) to protect passwords in-flight instead, and hash passwords on the server to protect them from theft.

(Remember, the original attack password hashing was protecting against was a world readable file that contained all usernames and passwords, /etc/passwd on Unix. Eventually the world moved to "shadowed" passwords, where the hashes were stored in a root-readable-only file called /etc/shadow.)

There are systems where the user enters a key locally and it's not transmitted over the wire. Kerberos and SRP are two of them.

This is the correct way to do it. I would say that a negotiated Salt isn't necessary and infact should be discouraged. Let the Server use its mystery SALT to make it impossible to use rainbow tables should the database get hacked.

> If the client could simply send a hashed password over as an authenticator, then hashing the password database would provide no protection against theft, because you could simply use the stored hash as the password.

I'm not sure I understand this sentence. Are you reading the parent message as proposing hashing client-side using the same algorithm as the server-side hash and comparing directly on the server against the database-stored hash. This would be outrageously stupid of course, but I'm certain the commenter was not proposing that.

They said:

> hash on the client side first to avoid sending the password to the server, and then hash again on the server.

Note, hashing again on the server. To describe this slightly differently, think of the clientside algorithm as effectively being a password generator, with the user inputting their own memorable password as a kind of encryption* key for their "real" auth API password—the main advantage is fighting password reuse.

*encryption!=hashing but I'm just using the term here to illustrate intent.

It's passive observation of a successful authentication session. This may occur if the victim performs authentication over a network where you can observe the authentication traffic (even though it is encrypted in transit), or if you can inject a timing script that can observe when authentication starts and finishes, or if you can gain access to logs of the server performing the password check (containing at minimum e.g. IP addresses and timestamps).

> How is the timing here relevant to attacking shacrypt?

By observing the time on the CPU it takes for the password hashing algorithm to complete, you can learn the length of the password. It's a side-channel timing attack.

But, as mentioned in the post, it's a negligible concern. In the case of md5crypt, the algorithm processes the password in 16-byte blocks. For standard 8-bit ASCII, this is 1-16 characters. Knowing that the bulk of user passwords are 7-10 characters, we aren't really learning anything anyway. We're not assuming here the adversary has the salted password hash. We're strictly talking about observing running processes on the machine.

> The run time does not depend on the length of any secrets here.

For md5crypt, sha256crypt, and sha512crypt, it does. sha256crypt will hash a 10 character random password faster than a 35-character Diceware passphrase. That's the whole point of the post.

> What this clearly demonstrates, is that the only factor driving execution time, is the number of iterations you apply to the password, before delivering the final password hash.

Isn't the reason this is true that bcrypt just truncates the input at 72 characters? And if that's correct, aren't there basically a few options, any of which basically invalidate the argument?

1. Enforce a password length limit. Fixes the unbounded growth of the shacrypt CPU time while simultaneously ensuring bcrypt is not ignoring input.

2. Pre-hash the input to bcrypt by passing it through SHA512. Makes bcrypt now grow in the exact same way as shacrypt.

3. Don't enforce a password limit, but truncate the password. Fixes the CPU time.

I don't know enough about bcrypt in practice to know which of those options is most commonly advised, but it just seems like a bit of a strawman here. Passing 4096 bytes to bcrypt is the same as passing 72 bytes to bcrypt because it ignores the last 4024 bytes right?

> Pre-hash the input to bcrypt by passing it through SHA512. Makes bcrypt now grow in the exact same way as shacrypt.

The pre-hash is only applied once, so the change in runtime is linear and very small compared to bcrypt.

Edit: I stand corrected, the summary in the link below didn't agree with the more detailed steps it went into below. While the hash is used as the input to the next round, it is (for reasons beyond my understanding) repeated if necessary to match the length of the original password. But it still seems like if you're prehashing in both cases the performance issue goes away.

Is that true? I thought shacrypt stretching worked by passing the output of a round of hashing as the input to the next round of hashing, so it would go from 4096 bytes to 64 bytes (e.g.) after the first round.

That's how it's explained here: https://www.vidarholen.net/contents/blog/?p=33. I'd love to be proven wrong.

So it seems shacrypt and bcrypt would be equivalent. Do the expensive work from 4096 to <72 once, then subsequent rounds are all on the same size of input.

I think my point stands, this is comparing apples and oranges unless you pre-hash the input to bcrypt and include that in the benchmark.

Users of sha256crypt and users of bcrypt should all be pre-hashing. That doesn't mean the argument is invalid, it's just flaws to work around.

Tbh I think prehashing should always be done (though not even I do it in practise, especially when I push something through pbkdf2 anyway)

It turns any password into an equal size string which makes your password backend a lot more predictable in code (IMO).

> Isn't the reason this is true that bcrypt just truncates the input at 72 characters? And if that's correct, aren't there basically a few options, any of which basically invalidate the argument?

Let's run a scenario to show by bcrypt from strictly a CPU load perspective is better than sha256/512crypt.

> 1. Enforce a password length limit. Fixes the unbounded growth of the shacrypt CPU time while simultaneously ensuring bcrypt is not ignoring input.

Assume that I know how many authentications per second are happening on my busy authentication server, and I can reliably guarantee 0.25 seconds per request without creating an outage. On my hardware, that's a bcrypt cost of 12. If I pre-hash every password with SHA-256, then base64 encode the hash, and send that to bcrypt, I can guarantee every user any arbitrary length of password, and know that it will not take more than 0.25 seconds.

For sha256crypt, a cost of 250,000 rounds is similar in performance for an 8-character password, executing in about 0.250158 seconds. However, and 36-character Diceware passphrase takes about 0.353884 seconds, and grows from there (70 characters at 0.503353 seconds, etc). Obviously, I can't allow everyone to have 36-character Diceware passphrases with a sha256crypt cost of 250,000 rounds. It would create load problems on my hardware.

I have three options that I see ahead of me if I wanted to stick with sha256crypt:

1. I could decrease the sha256crypt rounds, so those who want longer passwords won't create a CPU outage due to load.

2. Enforce maximum password length limit of 35 characters, to prevent the execution time from taking too long.

3. Make some exceptions in the code, so those with 1-10 characters have a higher sha256crypt cost than those with 11-24, which is still higher than those with 25-36, etc.

If I just stick bcrypt on the server with a cost of 12, I don't have handle these exceptions.

> 2. Pre-hash the input to bcrypt by passing it through SHA512. Makes bcrypt now grow in the exact same way as shacrypt.

No it doesn't. In the graphs on my post, the bcrypt timings are based on https://passlib.readthedocs.io/en/stable/lib/passlib.hash.bc.... bcrypt only grows when the cost is increased. Its execution times are in no way affected by password length.

> 3. Don't enforce a password limit, but truncate the password. Fixes the CPU time.

This is a bad design, and falls back to the security vulnerabilities of DES-Crypt and LM hashes.

> Passing 4096 bytes to bcrypt is the same as passing 72 bytes to bcrypt because it ignores the last 4024 bytes right?

Unless you bcrypt(base64(sha-256(password))), which is a common approach.

> Unless you bcrypt(base64(sha-256(password))), which is a common approach.

If we acknowledge that pre-hashing is acceptable (and almost certainly more secure) for bcrypt, why can't we allow the same for shacrypt? If we do, all of the performance issues about shacrypt go away. You now have a fixed-length password.

shacrypt(sha-256(password))

bcrypt is always fast because it truncates to 72 characters. Because it truncates, you should pre-hash. shacrypt is slow for big inputs because it doesn't truncate. Because it is slow, you should pre-hash. If we accept both of these, there's really no difference in bcrypt and shacrypt is my point. I don't understand why you allow it as an option for bcrypt but not shacrypt.

The sha256/512crypt algorithms, as well as md5crypt, hash the input based on each character in the password. This is why the execution time increases. bcrypt does not do this.

bcrypt is constant-time, not because it truncates at 72 characters. It's constant-time, because it slurps the password and salt once into the state (initial setup), then spends the rest of the time manipulating that state based on the cost (expand key).

Yes, you could pre-hash with sha256crypt or sha512crypt, and that completely works around the password-length performance issue. You pre-hash with bcrypt to get around a maximum length restriction, not to get around a performance bottleneck.

> bcrypt is constant-time, not because it truncates at 72 characters. It's constant-time, because it slurps the password and salt once into the state (initial setup)

And why do you think that initial setup is constant-time? Because it truncates at 72 characters! Otherwise it would be O(n), and so bcrypt overall would be O(n) + O(m) (if n is password length and m is cost factor).

It's quite simply impossible to have any hash function not be at least O(n) without truncation. That would imply that the data does not even need to be read to compute the hash.

Your point is still relevant in that without truncation, shacrypt would be O(n*m) and bcrypt would be O(n) + O(m), but NEITHER is O(m) without truncation. If shacrypt truncated, it would be O(m), just like bcrypt is O(m) with truncation. If both prehash instead of truncate, then both are O(n) + O(m).

From my testing with Python's base64, hashlib, and passlib.hash modules, SHA-256 prehashing and base64 encoding is only approximately one one-hundredths the total execution time of bcrypt_sha256 for a 4 KB "password". This is why slurping in the password during the initial state isn't noticeably adding to the overall execution time of password prehashing with bcrypt, and it is analogous to why PBKDF2, scrypt, and Argon2 all show constant time in execution regardless of password length- slurping in the password during initialization is a fraction of the execution time.

    Passive observation of execution times can predict password length (smaller concern).

Seems like this can radically narrow the focus of a dictionary attack. Also, if you are just trying to get a foothold into a machine, you can focus your energy on short passwords. Of course, I am not sure of all the scenarios where you are privy to how long the encryption took.

Putting the codeboxed quote down as a regular quote for mobile legibility.

> Passive observation of execution times can predict password length (smaller concern).

> Seems like this can radically narrow the focus of a dictionary attack

It does until you look at the charts, or read the text more carefully.

The charts look impressive because they're showing ranges up to hundreds or even thousands of bytes. But look closer and they're very noisy when it comes to narrow ranges. It really is easy to distinguish "The bells, they grow ever closer and I fear this night will be our last fair Susanne, but we must hold fast against the light and promise ourselves that we'll fight on, until the last drop" from "123456". But "password1" versus "ckjones4ever" not so much, which means it's not very practical for any actual bad guys.

This doesn't leak anything about the length of the correct password. This leaks information about the length of the guess, which the attacker already knows.

> Seems like this can radically narrow the focus of a dictionary attack.

It's leaking information, and we don't like this, but it's not fatal. 96% will have passwords less than 16 characters (see https://blog.cynosureprime.com/2017/08/320-million-hashes-ex...). This is within the first "step" in the sha512crypt hashing process, and longer passwords may have enough entropy, so learning their length is not providing any practical advantage in cracking the password, should the database be compromised.

The larger concern is CPU load. There are load jumps between 1-15, and 16-23 characters, and 24-80, etc. Even though 96% of users will fall in the 1-16 range, if you put a minimum length requirement of perhaps 12 characters, you may see that you need to decrease your sha512crypt cost to handle your tested load, because more of your users are passing 16 characters in length (yay) than normal (although most will like do exactly 12 characters).

Does that make sense?

The DoS aspect is mitigated via pam and user management controls in the OS (for creating /etc/shadow entries).

scrypt and bcrypt are a long ways out for supported Linux distros. This depends on glibc to make changes that they have stated they won't make. So for now, sha512 shadow hashes are the best most people will have in their datacenters.

Perhaps wrap that rascal with MFA / 2FA to be the first line of defense as a mitigating or compensating control.

scrypt and bcrypt are a long ways out for supported Linux distros.

Presumably you're referring to some sort of special acceleration for these algorithms? Why is that a prerequisite for using them? Speed isn't more important than security.

Not related to speed at all. glibc needs to add the support for them and it doesn't exist, at least not in the older branches that all the commercially supported distros use.

There is talk of adding support for external libraries. [0]

[0] - https://sourceware.org/bugzilla/show_bug.cgi?id=16814

> This depends on glibc to make changes that they have stated they won't make.

I'm not sure I understand what part of Linux's account security model relies on glibc to make changes. Can't PAM pull in whatever libraries it likes?

If not, then why hasn't (any popular distro of) Linux moved toward the Windows/macOS model of unifying account management + AAA onto a single "directory services only" code-path, where a system that's not "part of a directory" is actually just part of its own "directory of one", with your system running its own little LDAP+Kerberos daemons or what-have-you that your local accounts reside in?

In that sort of model (which, again, is what Windows and macOS both use exclusively nowadays), the kernel, C library, etc. aren't involved in deciding AAA policy; they just implement the simple AAA mechanism of "let users with the right ACL token do the things the ACL token says they can do" and then rely on one or more [local or remote] directory-service servers to actually authenticate users and issue those tokens to them. Drastically smaller attack surface.

There is talk of extending crypt in glibc to support external libraries [0] and that would do exactly as you suggest.

[0] - https://sourceware.org/bugzilla/show_bug.cgi?id=16814

And certainly, if you move the authentication to another service, such as I mentioned with MFA, or LDAP+Kerberos as you mentioned, that could address this, assuming that system supports scrypt / bcrypt.

I’m still confused—why is the idea to extend crypt(3), rather than for PAM to just call something besides crypt(3), pulling in a better hashing library at the libpam level rather than at the libc level?

That is a good question. One use case that comes to mind is sshd. The ssh daemon is not required to use pam.

Lots of services call crypt and it expects a variable length string which describes the stored secret to compare the actual password against. It is //very// possible to update this one place and 'solve' support for MANY dependent programs and libraries.

(towards the bottom of the manual page: http://man7.org/linux/man-pages/man3/crypt.3.html )

Offhand, due to setting up 'active directory' integrations, I'd say that yes, it should be possible to have a third party authentication framework which does not depend on traditional glibc/libc support.

I can't seem to find, in an offhand and quick glance at search results, any library that I know of to accomplish this task. Doesn't mean it can't be or hasn't been done though. I know for a fact that plain text passwords are passable to authentication libraries since that's how AD integration works.

Though there also seems to be some recent interest in implementing support in crypt() https://sourceware.org/bugzilla/show_bug.cgi?id=21421

I think the reason is because glibc is a fundamental OS component that always works, and if not you have bigger problems, you don't want to rely on other daemons or libraries to authenticate the user.

Using a daemon is against UNIX philosophy, and also poses a lot of problems, that daemon is just another piece of software that could fail for many reasons, and when it fails what you do ? You can't login to fix the problem, even as root and even in single user mode! So you are basically screwed.

How many times you had a problem regarding user authentication on Linux ? I never had, I was always able to log in into my system to repair it even when I completely broke it.

>scrypt and bcrypt are a long ways out for supported Linux distros.

Don't you just install libpam-unix2 / an updated version of libpam-unix that supports bcrypt, and configure that?

Source: this is how we use bcrypt password hashes on our one Linux machine.

Sha is a cryptograpic algo used for secure hashing hence the name SHA. The main goal of hashing is confirming the integrity of an object. This mean the object you read now is the same object as when it was stored. The goal was never to encrypt even if its possible to do so.

All hashing functions have the same weakness which is vulnerable to rainbow table attack. I agree with the OP that sha is dangerous if used in the wrong way.

The main goal of hashing is confirming the integrity of an object. [...] The goal was never to encrypt even if its possible to do so.

That is not true, cryptographic hash functions are just cryptographic primitives with certain guarantees about their behavior, they do not imply any usage. There is nothing fundamentally wrong with using a cryptographic hash functions as a building block for an encryption algorithm. The important thing is that almost no use case of cryptography requires exactly and only the guarantees provided by cryptographic hash functions. That is why they are most of the time used as building blocks of more complex algorithms and not on their own.

Ensuring that a file was not modified while you did not look is just an exceptional case where just using a cryptographic hash functions alone may be good enough. But even in this case you might want to consider that an attacker may be able to change the file and its hash together and maybe you actually need an authenticated hash that can not be forged by an attacker. In that case a cryptographic hash functions would again be part of the algorithm but it would not be the only building block.

sha256crypt != sha256

The hash function used here is not the problem. Notably for example scrypt also uses sha256 under the hood.

The article is about sha256crypt, which is a salted, pessimised password hash.

Despite the legacy name "crypt" this isn't about encryption, encrypting passwords isn't what anybody is trying to do here.

Because it uses salt, all time-space trades including rainbow tables are irrelevant. If you struggle to see why, the simplest way to understand it is that you'd need to generate new tables for every single salt. The salts are random and different for each account.

Reply on news.ycombinator.com