The scrypt parameters
blog.filippo.io
blog.filippo.io
A common advice is to allocate as much memory as possible, and as much CPU as possible, to make bruteforce attacks as long as possible.
Unfortunately, it only makes sense if a each user is assigned a dedicated server. Which is almost never the case in APIs and web applications.
Doing all the stretching work on a server scales poorly. And predicting how many users will try to log in is impossible, unless you set up drastic limits. One way or the other, this makes the whole service vulnerable to very cheap denial of service attacks.
There are a lot of discussions about password hashing functions and their parameters, but almost none about server relief, which is far more important IMHO.
The idea is to delegate most of the work to the client. The server just provides the salt. It's acceptable to use as much resources as possible for a short time on the client, since it's unlikely to do anything else important at the same time.
The stretched password is sent to the server instead of the actual password, so that it's acceptable for the server to keep the stretching work down to a minimum before storing the password. This also has the advantage that the server doesn't see the actual password.
This solves scalability issues, and drastically reduces to ability to perform cheap resources exhaustion attacks on the servers.
In a webapp, this can be efficiently achieved using WebAssembly, or with WebCrypto's PBKDF2 implementation. Obviously not an issue in native apps either.
Legacy protocols such as FTP and IMAP don't have that luxury, though. There's no way to run a password stretching function on the client. So, while it's nice to see software like Dovecot adopt functions like Argon2 to store passwords, this can actually do more harm than good.
Finally, while password hashing functions are typically described as suitable for storing passwords, they have other usages as well.
Password-authenticated key exchange mechanisms such as SPAKE2 don't get the attention they deserve. They can be extremely useful to add a strong security layer on top of another authentication mechanism, using a simple password. And they also usually leverage password stretching functions.
OTOH, without client-side prehashing, an attacker that has the ability to impersonate the server doesn't have to precompute anything in order to collect all passwords.
There is no way for the server to distinguish a legitimate user trying to login from an attacker trying to hack someone. So if the salt is sent to a legitimate client, the salt will also be sent to attackers.
I'm not sure if sending the salt to attackers is really a vulnerability though.
Another disadvantage is that if changing password also changes salt, by requesting salt over the period of time, the attacker can learn when the password was changed.
Can you point to an example of a (nontrivial) site where a DoS attack against the password hashing service was the primary point of failure? I'm sure it's happened, but it strikes me that most systems will go down hardest and first from pressure on other parts of that system.
> This also has the advantage that the server doesn't see the actual password.
This is the more compelling thing, to me, about this approach. Doesn't play super nicely with the established API tooling out there, but it's something to consider.
Reformulating the question from a different angle: why did all the large sites whose password database got leaked (Yahoo, LinkedIn...) still use regular hash functions?
> This also has the advantage that the server doesn't see the actual password.
Other schemes with that property include augmented PAKEs such as SPAKE2+ (example implementation: https://github.com/jedisct1/spake2-ee) and Tabby PAKE (https://github.com/catid/tabby/blob/master/PASSWORD.md)
Incompetence.
Inertia? Stuff I built in 2001 probably still uses MD5+salt today because nobody's maintained it in over a decade.
Fear of breakage? Going down because of an "unnecessary" change probably reads worse to management than getting owned does (before it happens)--and besides, it's not our data, just users.
I dunno, man. Obviously I have a ton of respect for your crypto work (I mean that, seriously, thank you). Your other points make total sense, this one just feels like overreach
> Other schemes with that property
Well outside my weight class, but you've given me some stuff to read about. No idea how it ends up integrating with existing API tooling, but worth examining for sure.
Here's a vulnerability report from the Django framework where arbitrarily-large passwords could be submitted for checking, tying up server resources in a DoS attack: https://www.djangoproject.com/weblog/2013/sep/15/security/
I'm not sure any real-world sites were affected by this, but had the patch not been applied it certainly would have been possible.
"Wild Keccak" is not a "modern variant of Keccak". I'm not familiar with it, but it looks like an attempt to build a PoW scheme with ROM/RAM hardness using Keccak permutation.
IMAP uses SASL, which can do client-side stretching by using SCRAM-SHA-1. I don't know how common they are, but there must be some servers and clients that support it.
Downside is that upgrading the mechanism becomes hard, and it's difficult to integrate it with an existing user database with hashed passwords.
DoS sttacks on slow password hashes are a phenomenon more heard about than ever seen. Concern about them was raised back in the "salted hash" days, when people resisted deploying bcrypt in favor of "secret salts". In the 10 years since, virtually every major site has switched to some kind of stretched password hash. Many of these companies are (or were) clients. The number of in-reality DoS attacks against password hashes I've heard attributed to these companies: 0. My guess at why: it's trivial to DoS a typical SaaS application anyways, applications don't run hashes on nonexistent accounts, and have to lock out repeated login attempts on existing accounts for other reasons anyways.
Which means, unlike every other vector for application-level DoS, to conduct this attack you need a continuous supply of fresh valid accounts on a continuous supply of untainted IP addresses. Why bother? There's almost certainly a preauth endpoint somewhere that accomplishes the same thing anonymously.
You observe that the server doesn't have to see the password in server-relieved schemes. This is true, in the limited sense that there's no point that the server is required to have the plaintext password resident in memory. But there's two caveats to that benefit: first, that's not how passwords are generally taken from compromised applications (what really happens is that the database of password authenticators is stolen, and that remains the case in server relief designs), second, the assurance that passwords will never appear in server memory vanishes when you stipulate that server relief is implemented in content-controlled code, which can simply arrange to have the password sent on the attacker's behalf.
Of course, the content-controlled language we're talking about here (Javascript) is the classic objection to server-relief, and it's worth recalling the reason why: not that browser Javascript is bad for implementing crypto (though: it is), but that it's the slowest of all the computing parties involved in an attack on passwords. By running adaptive hashes clientside, you reduce the security of those hashes to the lowest common denominator of the servers, attackers, and clients --- in most applications, you'll have to reduce it to the strength of outdated smartphone Javascript.
In serious designs, there are already good reasons to isolate authentication into its own service. More large applications should design and implement auth services, and more and more are. Once you've factored auth out of your monolith app server, it's much easier to scale password hash compute, and do it in ways that allow service providers to take advantage of resources that clients don't have.
Again: I think server relief makes sense in new designs, just like I think PAKEs do. But people read comment threads like these and get it into their head that they should get a PAKE set up for their Django application. That's a terrible idea.
I think I'm on pretty good footing, cryptographically speaking, with everything I've written to this point. This last point I'll make, I acknowledge I sound (to everyone) like a crank. But here goes:
This is my problem with the Password Hashing Competition. In reality, bcrypt turned out to be a uniquely strong, well-designed password hash for the purposes it was most typically being applied for (SaaS app login). For every other application --- particularly general-purpose KDFs --- scrypt got you to something like 99.9% of the optimal outcome. But then, for reasons I don't fully comprehend, we had a giant contest to determine "the best password hash" (the one Argon2 won). The world wasn't asking for it, nothing was really threatening the mainstream password hashes we had before... and now we have a "new" king of password hashes that for most purposes is not materially better than scrypt, and a whole lot of new mechanism being proposed to find reasons to deploy it.
Generally the point I would want to make is that on mainstream platforms, like Django and Rails, the platform defaults are pretty good, and probably all you'll need for the whole lifespan of your application. If you don't know what you're doing, and are mostly going off comments on Reddit and HN, it is possible to do more harm than good by departing from those defaults.
We have more confidence in scrypt because of the analyses PHC fostered. We (well, everyone not named 'cperciva perhaps :)) didn't really have a proper independent framework for analyzing hardness statements. So yes, scrypt is fine, but we say that with a lot more confidence because of PHC research.
PHC also matters for reasons similar to NIST password recommendations. Now if your questionnaire balks that I'm not using $x, I can say "go away, we are following $blessed_practice" as opposed to "we use this thing that this one dude wrote but it's the best we promise". It was the best, but dumb questionnaires still matter even if they're dumb. (Clearly PHC does not carry the same weight as NIST, but at least there's some semblance of authority and academic consensus you can point to.)
I agree that it's regrettable that the outcome of the PHC wasn't just "scrypt is fine, use it". Though a deployment model that isn't "go steal this .c and .h from this one tarball of a different application on this one site" is nice, and now there's significant impetus to make that happen.
> ... and a whole lot of new mechanism being proposed to find reasons to deploy it.
I don't understand what you mean. Can you elaborate?
Just so no-one misconstrues any of my points: I emphatically agree that the vast majority of people should just use what their framework gives them because it's probably totally fine.
Cache line sizes don’t change insignificantly — they change in powers of 2. Cache lines sizes for Intel x86_64 CPUs have not changed at all since 2009, it’s still 64 bytes.
Would it be terrible in that case to just say "screw it", and just go with the old classic salt + single hash (SHA256, probably) instead of scrypt or bcrypt or PBKDF2 or similar?
For that matter, if your passwords really have 238 bits of entropy, you don't even need a salt.
In practice though, users don't.
To make sure users have secure passwords, the server can just generate them and tell the client what their password is. It is, as far as I can tell, entirely a historical accident that this is not how it is generally done.
For web sites, I'm fairly sure this could be done via browser password storage without the user needing to ever see the password if they only use one system to log in (or browser sync between all systems they use). IMO, 21 character random base-64 passwords are good, enough security and still possible to memorize (three groups of seven) over a couple of weeks if necessary.
10k iterations was half a second when we tried it on our server.
10M iterations took 8 minutes for a single hash.
PBKDF2 is a password-based key derivation function (it says so, right in the name), not a data integrity verification function. You should only ever be feeding a password and high-entropy salt into it.
It's something of a disservice to call all these things "hash functions". It makes people think they're interchangeable, but that's very far from true.
[1] The reason I say using it as a MAC is even worse than using it for data integrity is that was never intended to work as a MAC. A KDF doesn't care (in theory) if the salt input can be derived by looking at its output. For the intended use case of a KDF, the salt is stored with the output anyway. So a cryptanalysis of a KDF wouldn't see the revelation of information about the key by the output as a theoretical flaw. But that would be a huge flaw in a MAC, where the output is often conveyed by an untrusted party between two parties who keep the key secret. From a practical standpoint, a KDF that did leak details of its key in its output is inefficient (redundant use of storage space), but it isn't sufficient by itself to break the security properties.
~: time node -p 'crypto.pbkdf2Sync("password", "salt", 10e6, 32, "sha256").toString("hex")'
3c0873fa17659d22450cfcc4a7dd8e51e66db276a0d594cc729baba5af5cedd8
node -p 6.55s user 0.02s system 99% cpu 6.576 total
The code below takes ~15 seconds on 1 year old MacBook running Java 1.8.0_111-b14 and uses no 3rd party libraries:
PBEKeySpec spec = new PBEKeySpec(password.toCharArray(), salt, 10_000_000, 256);
SecretKeyFactory skf = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA256");
byte[] hash = skf.generateSecret(spec).getEncoded();There is a vulnerability in PBKDF2 that halved the amount of operations. New libraries make use of it but it wasn't known at the time.
That 15+ seconds would be 1+ minute back then. Assume the first implementations were poorly optimized and that's multiple minutes.
BlindHash is a completely different approach. I used data as a cost factor — a massive array of random data, which can grow over time but once a bit becomes part of the pool, it never changes.
Here’s how it works;
First, a fast hash (SHA512) and a secure salt (64 byte CSPRN) turns your password into a random number, call it Hash1. That 64 byte value is sent to a BlindHash Server.
On the BlindHash server Hash1 is used to generate 64 uniformly distributed i.i.d indices into the data pool, which imagine is ~100TB of data, and you read 64 bytes from each location. Accumulate those 64 reads into a 4KB buffer, and hash that. Return that result.
Back on the authentication machine, use the result from BlindHash to HMAC your Hash1 to produce a Hash2. Store/Verify the Hash2 value. Hash1 is never stored.
What this accomplished is basically entangling the password hash with an arbitrarily large pool of data, where an attacker needs to steal >90% of the data pool in order to even start attempting an offline attack.
The bigger you make the data pool, the more data an attacker would have to steal, but the faster the system runs — because more data spread across more SSDs increases read bandwidth since the read pattern is perfectly uniform.
The network carries 64 bytes in and 64 bytes out with each BlindHash request. Size the network pipe to handle your desired authentication load, e.g. 64 * 100,000 = 6.4MB/sec.
Divide the data pool by the available bandwidth, e.g. 100TB / 6.4MB = ~180 days. That’s how long it takes to steal the data pool over the network at full line rate. And the attacker needs virtually all of it to even try to start an offline attack.
For large scale secure password storage, BlindHash provides the means to eliminate the possibility of an offline attack. It’s faster and cheaper than burning expensive CPU cycles, and most importantly security (growing the data pool) and performance (logins/sec) are positively correlated, not negatively. It Scales.
Disclaimer: I’m the inventor, patent holder, and CTO of BlindHash, and I’ve been working on productizing this technology for several years now. As a longtime HN member/contributor I do feel like it’s OK to occasionally pitch my company when relevant topics trend on the front page, as long as there’s an interesting technical component to go along with it!
If you’re responsible for securely storing customer passwords at a large corporation, scrypt/bcrypt/argon2 is not the right approach for you. You’re better off spending those cycles mining Monero.
Let me help you eliminate the possibility of a breach and actually save you money in the process. You can have your own on-prem data pool, or share a massive geo-replicated pool with other large corporations at an even lower cost. </pitch>
Hopefully you’ll find this one more informative:
https://www.google.com/patents/US9021269
Part of the reason I’ve been able to raise money and spend several years of my life trying to build and evangelize this new/better way of protecting passwords is because the USPTO has granted us the exclusive right to license it in the US through ~2033.
A longer secret key makes the users cost multiplier linearly increase, while the attackers exponentially increases.
Most people dramatically underestimate the dramatic scaling of the word exponential. It's the kind of "if I have 2048 bits then trying every key takes longer than the age of the universe" type slowdown.
Hence:
* Use long secrets (ie. not human-rememberable passwords)
* Use cheap hash functions.
* Don't use scrypt. It's made for passwords (short keys), which really shouldn't exist in 2018.
Besides slowing down attackers, the other claimed reason for using scrypt is that it is more secure against determined attackers that implement accelerated password crackers because it is a "memory-hard" key derivation function. In fact, the experience with scrypt crypto currency hashing has proven this assumption to be false. Compared with a salted hash function, scrypt like algorithms have a lower energy density when implemented in silicon and therefore actually get higher gain multiples from various levels of hardware acceleration than you observe with straight hash functions like sha256. So a determined attacker would have an even greater edge than the scrypt parameters would lead you to believe.
> KDF adds about 15 bits of work to each guess attempt.
> That's approximately equivalent to adding 6 random
> characters to your password.
Fancy hashing schemes optimize for scenarios that are both relatively rare and fleeting. If you're in a position where they seem defensible, you've already lost the game. Unless your purpose is to check-off some boxes, similar to how until recently IT departments required frequent password resets to check-off NIST's antiquated guidelines.
There is a way to substantially improve the overall security of a password-based system: use a keyed HMAC on a cryptographic HSM for validating passwords. With an HSM (from which we assume the attacker can't actually recover the secret key), you can precisely, reliably, and meaningfully throttle brute-force recovery times without being contingent on any hand-wavy, snake-oily, bike-sheddy hashing scheme with dubious parameters.
Not too good advice if you ask me IMHO.
Here's better advice: https://codahale.com/how-to-safely-store-a-password/
s/bcrypt/scrypt/g if you prefer.
"Replacing libsodium. Libhydrogen focuses on being small and is for environments where libsodium cannot be used."
I imagine the later author wanted things this way.
Since this is relevant to the original topic, the password hashing API is a good illustration of the difference between both libraries. New additions to libsodium must remain consistent with historic APIs, that have limitations and usability issues. Hydrogen learned from this, and tries to model its API after common problems to solve in real-world applications rather than provide interfaces to cryptographic primitives. This will eventually become the base of libsodium 2.x
Of course, there's nothing wrong with using libsodium, if only because it's way more mature and implements conservative designs that you can trust.
But feedback on Hydrogen would also be really great. I really want to avoid doing the same mistakes again, and build the best possible easy-to-use hard-to-misuse APIs that everybody can use confidently.
When RSA 768 came within reach of brute forcing, everybody moved to RSA 2048 and RSA 4096. To make a similar leap in attacker cost for iterative hashing solutions, your login prompt would force users to sit idly for minutes, hours, or maybe even days. And making this change systemically is still underway, taking years.
Because the cost function of iterative hashing is identical between defender and attacker, you cannot pad your security in a way that is robust and generalizable against attacker capabilities in a reasonable future timeframe. How many solutions that use PBKDF, scrypt, etc, have gone back and changed their cost function (i.e. iteration count) after a year? After 3 years? After 5 years?[1] Do they tune their cost function to 8-character passwords? 10-character passwords?
And no amount of iteration within a reasonable time frame is going to prevent an attacker from cracking prototypically insecure passwords. Bitcoin becomes exponentially more difficult to mine over time. As a practical matter there's no limit to the number of bad passwords in a websites database, no matter the length.
Once you've implemented password salting, removing an attacker's ability to exponentially decrease his cost function for the next password cracking attempt, you're just putting lipstick on a pig. For people who care about good passwords, iterative hashing is irrelevant--a few extra random characters adds more cost than the authenticator would ever achieve with an increased iteration count. For all practical purposes, an authenticator's duty to attend to low-level algorithmic details ends at salting. After that, he maximizes security by redirecting all available effort to securing his infrastructure, catching bad passwords, and supplementing or replacing authentication with a passwordless mechanism.
The emphasis on specific hardware is misguided. Real-world attackers don't use FPGAs, they use public clouds and botnets. Perhaps some governments use bespoke hardware, but even then the real gains in performance still come largely from the clustering of commodity hardware. Look at supercomputers--they moved away from bespoke hardware decades ago.
Password hashing solutions that tout memory hardness and the inability to easily create bespoke hardware crackers are something dangerously close to snake oil. The features are technically legitimate but largely irrelevant in the context of real-world security. Like most snake oil, it's not that they don't add any absolute value whatsoever, but rather the magnitude of the benefit is greatly exaggerated, while the opportunity cost in misdirected resources greatly underestimated. Quibbling over a few ephemeral bits of additional attacker complexity is not a place you want to find yourself.
[1] OpenBSD was one of the first, if not the first, to both add a memory hardness aspect to their hashing algorithm and a dynamic cost function with iteration, with iterated Blowfish. But they went years, if not over a decade, before updating the default iteration count. And Blowfish is of course no longer really considered memory-hard. It's more or less an abandoned idea in OpenBSD.
> Because the cost function of iterative hashing is identical
> between defender and attacker
In the real-world, at scale the only relevant metric to his cost is the entropy of the password, which iterative hashing doesn't magically increase.
If you find it cost-effective to slap a `for (i = 0; i < 10^12; i++)` loop around your hash, you should assume it's cost-effective for your attacker as well.
These are fundamental assumption you should make in the absence of very specific exceptions not typically applicable to attack modeling of public internet services.
The use of these overwrought hashing schemes doesn't change the fundamental cost dynamic for brute-forcing password hashes. At best it's the same today as it was 30 years ago. At worst, because of botnets, he can scale must more cheaply than you.
The arguments in favor of these schemes are pragmatic, not scientific. But they're predicated on the defender constantly keeping up to date with hardware advancements as that margin is thin and evolving rapidly. Worse, it completely ignores the fact that if I've recovered the password digest for one account, I've likely recovered the digests for dozens, hundreds, or perhaps thousands of accounts with equivalent authorizations. Because of exponential cost differences between good passwords and bad passwords, and the prevalence of bad passwords, I can profitably filter out the good passwords by setting a fixed absolute per-password cost ceiling, substantially lowering my asymptotic costs.
Iterative and memory-hard password schemes are simply fighting an uphill battle. Once you move beyond salting you're just throwing good money after bad money by attempting to secure bad passwords.
Good passwords are already secure; bad passwords can't be fixed by the hashing scheme du jour.
> If you find it cost-effective to slap a `for (i = 0; i < 10^12; i++)` loop around your hash, you should assume it's cost-effective for your attacker as well.
If your work factor is higher, it takes much longer to brute force a password. On my laptop, bcrypt with work factors 13 and 14 take ~650ms and ~1100ms, respectively. In comparison, SHA256 takes 0.110ms.
A database of passwords hashed with SHA256 will take days, maybe weeks to recover most of the passwords through brute force. With bcrypt, it would take months or years.
This article[1] has some numbers (although they're a bit outdated now):
> How much slower is bcrypt than, say, MD5? Depends on the work factor. Using a work factor of 12, bcrypt hashes the password yaaa in about 0.3 seconds on my laptop. MD5, on the other hand, takes less than a microsecond.
> So we’re talking about 5 or so orders of magnitude. Instead of cracking a password every 40 seconds, I’d be cracking them every 12 years or so. Your passwords might not need that kind of security and you might need a faster comparison algorithm, but bcrypt allows you to choose your balance of speed and security. Use it.
Or it will take seconds on special purposed hardware, not much longer than salted sha256. In the mean time you'll have made poor security decisions based on the invalid assumption that your attacker will need months or years of compute...
EDIT: Besides, bcrypt is not even the "best" hash function we have available. If you're concerned about GPUs and FPGAs, there's argon2id which has much stronger guarantees than bcrypt.
That's not true. Scrypt is designed to make computing it in parallel on the GPU expensive while keeping CPU computation reasonably fast.
Thus attackers are exposed to a much higher slowdown, since just about no login server uses GPUs
It failed at this, FYI. It turns out that scrypt silicon requires larger dies than a straight hash function like sha256, and the larger dies mean better heat dissipation, which means greater performance per watt. Scrypt attackers get a larger advantage vs cpu validators than a salted hash function. Oops.
https://www.reddit.com/r/Bitcoin/comments/3n5nws/research_pa...
https://crypto.stackexchange.com/questions/29890/memory-hard...
Not really. The user only has to wait for the computation once, a few times at most, and it can easily take less time than typing the passwords.
> * Use long secrets (ie. not human-rememberable passwords)
That's very often not the case. Some people like me put truly random passwords on every service. But 99.9% don't.
Also, you can perfectly combine _both_ long keys and expensive hashes.
Scrypt is a bandage which doesn't resolve the core problem - there is insufficient entropy in typical users passwords. If there was enough entropy, the speed of the hash function wouldn't matter.
True, certainly. You're unlikely to get much debate about hardware tokens / certificates / etc being more securable; the reason we still have passwords isn't because they're more securable, it's because their UX for the vast majority of users is much better.
If you're suggesting there's a reasonable path to get from $the_world_today to $the_world_you're_proposing, I suspect that's a more interesting point to make.
For example, you'd want at least one backup. Maybe buried somewhere or in a safe deposit box. But the workflow for keeping it synced would be hilarious.
Ever since then, I can't take anyone seriously on HN who says "we shouldn't have passwords, just hardware key fobs". Not to mention your authentication security doesn't matter when there's a customer support line an attacker can socially engineer.