9 ms·

The scrypt parameters

123 points by FiloSottile 9y ago

Ruud-v-A 9y ago
“Cache line sizes have not significantly increased since 2009, so 8 should still be optimal for 𝑟.” 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.
londons_explore 9y ago
An "expensive" hash function like scrypt provides both the user and the attacker the same slowdown/cost multiplier. 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.
- adrianN 9y ago
  Even though it's nearly 2018 everything except the machines I ssh into is protected by passwords. I would like it very much if the passwords weren't stored with unsalted md5.
  - garmaine 9y ago
    So? Use a properly salted sha256. Don’t use scrypt.
    - frankpf 9y ago
      Definitely do not use SHA256, it's designed to be fast. That's the opposite of what you want when storing passwords. I don't understand what's the problem with scrypt, but if you don't want to use it there's also bcrypt and argon2i.
      - garmaine 9y ago
        Read the grand parent post for the context of my post.. fast is good. Slowing down the key derivation function, as scrypt et al does, has a linear cost to both the verifier and the attacker. Using scrypt with standard parameters for an authentication KDF adds about 15 bits of work to each guess attempt. That's approximately equivalent to adding 6 random characters to your password. Making your password that much longer is just as good, while not requiring you to burn a half second of CPU time and thrash memory every time you authenticate. 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.
        brians 9y ago
        Can you expand on what you see as the y-intercept for those cost functions? I think you’re assuming zero for attacker and defender. I can imagine arguments that the defender has a small positive y-intercept, and that makes all the difference.
        wahern 9y ago
        > KDF adds about 15 bits of work to each guess attempt. > That's approximately equivalent to adding 6 random > characters to your password. A better way of putting it is that it's equivalent to adding 15 bits of entropy to your users' passwords, which in the grand scheme of isn't actually much of a marginal improvement in overall security. Adding 15 bits to an already strong password provides a small, largely irrelevant marginal gain. Adding 15 bits to a bad password has more marginal benefit, but you're typically still in the window where brute-force cracking is tolerable, especially considering typical attack models--in most scenarios attackers only need to crack the weakest password among an often large set of passwords. 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.
    - endymi0n 9y ago
      sha256 hashing rate on a modern graphics card is about 23GH/s: https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a270c40 https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a27... Not too good advice if you ask me IMHO. Here's better advice: https://codahale.com/how-to-safely-store-a-password/ https://codahale.com/how-to-safely-store-a-password/ s/bcrypt/scrypt/g if you prefer.
      - LaGrange 9y ago
        It's 2017, use libsodium: https://download.libsodium.org/doc/password_hashing/ https://download.libsodium.org/doc/password_hashing/.
        jedisct1 9y ago
        It's almost 2018, use libhydrogen: https://github.com/jedisct1/libhydrogen/wiki/Password-hashing https://github.com/jedisct1/libhydrogen/wiki/Password-hashin...
        LaGrange 9y ago
        Hm, seems less active, and in the non-goals: "Replacing libsodium. Libhydrogen focuses on being small and is for environments where libsodium cannot be used."
        marcosdumay 9y ago
        > libsodium ... libhydrogen ... seems less active I imagine the later author wanted things this way.
        SAI_Peregrinus 9y ago
        They're from the same author (jedisct1).
        garmaine 9y ago
    - adrianN 9y ago
      For less than $3k you can buy hardware that can do ~13 terahashes per second, thanks to Bitcoin. That lets you brute force ten letter passwords with a 64 symbol alphabet in about a day.
      - wahern 9y ago
        And? 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.
- hanbura 9y ago
  >An "expensive" hash function like scrypt provides both the user and the attacker the same slowdown/cost multiplier. 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
  - garmaine 9y ago
    > That's not true. Scrypt is designed to make computing it in parallel on the GPU expensive while keeping CPU computation reasonably fast. 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.
    - java-man 9y ago
      Interesting. Can you point to the source on this? Thanks!
      - garmaine 9y ago
        You can calculate yourself the efficiency of scrypt ASICs vs CPU mining based on published performance numbers. For an explanation of the many reasons why this is the case, here's two starting points for that rabbit hole: https://www.reddit.com/r/Bitcoin/comments/3n5nws/research_paper_asymmetric_proofofwork_based_on/ https://www.reddit.com/r/Bitcoin/comments/3n5nws/research_pa... https://crypto.stackexchange.com/questions/29890/memory-hard-proof-of-work-are-they-asic-resistant https://crypto.stackexchange.com/questions/29890/memory-hard...
- DiThi 9y ago
  > An "expensive" hash function like scrypt provides both the user and the attacker the same slowdown/cost multiplier. 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.
  - londons_explore 9y ago
    Passwords shouldn't exist at all. Web services should use OAuth. Oauth providers should use two factor where one factor is a 2048 bit key (Yubikey/Client Cert/etc.). Point to point connections (ssh, VNC, network shares) should use client certificates or centralized auth (Kerberos or active directory). 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.
    - akerl_ 9y ago
      This is a bit like saying "human-driven cars shouldn't exist: the roads would be much safer". 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.
      - always_good 9y ago
        I looked into Yubikey but it seems absolutely impractical for day-to-day authentication unless you only use it for a finite amount of sites. 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.
jedisct1 9y ago
Password hashing functions are very useful, but can cause operational issues. 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.
- ricardobeat 9y ago
  Doesn't sending the salt to the client void a whole layer of security?
  - eropple 9y ago
zaroth 9y ago
Iterative password hashing functions need to be slow to be secure. Their cost factor is borne through consumption of real-time resources such as CPU cycles and memory bandwidth, and therefore cost is roughly synonymous with latency. 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>
user5994461 9y ago
To illustrate the level of idiocy we reached with slow hash functions. The official NIST recommendation #800-132 is to use 10k iterations for PBKDF2, or 10M iterations for important keys. 10k iterations was half a second when we tried it on our server. 10M iterations took 8 minutes for a single hash.
- chowells 9y ago
  Were you using it to hash data for integrity? Or even worse, were you abusing it as a MAC [1]? That's the only way I can see it being so slow. 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.
  - user5994461 9y ago
    It's hashing a password. It's used exactly the way it's supposed to be.
- minitech 9y ago
  > 10M iterations took 8 minutes for a single hash. ~: 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 10 million iterations in 6.5 seconds on a cheap laptop. Not sure what caused your numbers, but spending a few seconds on a password hash is not “idiocy”.
tzs 9y ago
Assume that all clients for a site use password managers with good random password generators, which they use to generate their site password. They are all, say, 40 characters chosen from [a-z][A-Z][0-9], so about 238 bits. 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?
- cperciva 9y ago
  No, that would be just fine. The sole purpose of password based key derivation functions is to maintain robustness in the presence of weak(er) passwords. For that matter, if your passwords really have 238 bits of entropy, you don't even need a salt.
- sbierwagen 9y ago
  Well, sure, if all users were guaranteed to use a strong password that wasn't reused for any other site, we wouldn't need a lot of password safety rules. Heck, you could just store them in plaintext. In practice though, users don't.
  - joveian 9y ago
    A single hash is still a good idea since otherwise anyone who steals the password database can log in as any user. Sure if someone can steal the password database they may be able to steal passwords as users log in, but that is at least harder. 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.

123 points by FiloSottile 9y ago

“Cache line sizes have not significantly increased since 2009, so 8 should still be optimal for 𝑟.” 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.

londons_explore 9y ago

An "expensive" hash function like scrypt provides both the user and the attacker the same slowdown/cost multiplier. 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.

adrianN 9y ago
Even though it's nearly 2018 everything except the machines I ssh into is protected by passwords. I would like it very much if the passwords weren't stored with unsalted md5.
- garmaine 9y ago
  So? Use a properly salted sha256. Don’t use scrypt.
  - frankpf 9y ago
    Definitely do not use SHA256, it's designed to be fast. That's the opposite of what you want when storing passwords. I don't understand what's the problem with scrypt, but if you don't want to use it there's also bcrypt and argon2i.
    - garmaine 9y ago
      Read the grand parent post for the context of my post.. fast is good. Slowing down the key derivation function, as scrypt et al does, has a linear cost to both the verifier and the attacker. Using scrypt with standard parameters for an authentication KDF adds about 15 bits of work to each guess attempt. That's approximately equivalent to adding 6 random characters to your password. Making your password that much longer is just as good, while not requiring you to burn a half second of CPU time and thrash memory every time you authenticate. 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.
      - brians 9y ago
        Can you expand on what you see as the y-intercept for those cost functions? I think you’re assuming zero for attacker and defender. I can imagine arguments that the defender has a small positive y-intercept, and that makes all the difference.
      - wahern 9y ago
        > KDF adds about 15 bits of work to each guess attempt. > That's approximately equivalent to adding 6 random > characters to your password. A better way of putting it is that it's equivalent to adding 15 bits of entropy to your users' passwords, which in the grand scheme of isn't actually much of a marginal improvement in overall security. Adding 15 bits to an already strong password provides a small, largely irrelevant marginal gain. Adding 15 bits to a bad password has more marginal benefit, but you're typically still in the window where brute-force cracking is tolerable, especially considering typical attack models--in most scenarios attackers only need to crack the weakest password among an often large set of passwords. 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.
  - endymi0n 9y ago
    sha256 hashing rate on a modern graphics card is about 23GH/s: https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a270c40 https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a27... Not too good advice if you ask me IMHO. Here's better advice: https://codahale.com/how-to-safely-store-a-password/ https://codahale.com/how-to-safely-store-a-password/ s/bcrypt/scrypt/g if you prefer.
    - LaGrange 9y ago
      It's 2017, use libsodium: https://download.libsodium.org/doc/password_hashing/ https://download.libsodium.org/doc/password_hashing/.
      - jedisct1 9y ago
        It's almost 2018, use libhydrogen: https://github.com/jedisct1/libhydrogen/wiki/Password-hashing https://github.com/jedisct1/libhydrogen/wiki/Password-hashin...
        LaGrange 9y ago
        Hm, seems less active, and in the non-goals: "Replacing libsodium. Libhydrogen focuses on being small and is for environments where libsodium cannot be used."
        marcosdumay 9y ago
        > libsodium ... libhydrogen ... seems less active I imagine the later author wanted things this way.
        SAI_Peregrinus 9y ago
        They're from the same author (jedisct1).
        garmaine 9y ago
  - adrianN 9y ago
    For less than $3k you can buy hardware that can do ~13 terahashes per second, thanks to Bitcoin. That lets you brute force ten letter passwords with a 64 symbol alphabet in about a day.
    - wahern 9y ago
      And? 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.
hanbura 9y ago
>An "expensive" hash function like scrypt provides both the user and the attacker the same slowdown/cost multiplier. 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
- garmaine 9y ago
  > That's not true. Scrypt is designed to make computing it in parallel on the GPU expensive while keeping CPU computation reasonably fast. 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.
  - java-man 9y ago
    Interesting. Can you point to the source on this? Thanks!
    - garmaine 9y ago
      You can calculate yourself the efficiency of scrypt ASICs vs CPU mining based on published performance numbers. For an explanation of the many reasons why this is the case, here's two starting points for that rabbit hole: https://www.reddit.com/r/Bitcoin/comments/3n5nws/research_paper_asymmetric_proofofwork_based_on/ https://www.reddit.com/r/Bitcoin/comments/3n5nws/research_pa... https://crypto.stackexchange.com/questions/29890/memory-hard-proof-of-work-are-they-asic-resistant https://crypto.stackexchange.com/questions/29890/memory-hard...
DiThi 9y ago
> An "expensive" hash function like scrypt provides both the user and the attacker the same slowdown/cost multiplier. 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.
- londons_explore 9y ago
  Passwords shouldn't exist at all. Web services should use OAuth. Oauth providers should use two factor where one factor is a 2048 bit key (Yubikey/Client Cert/etc.). Point to point connections (ssh, VNC, network shares) should use client certificates or centralized auth (Kerberos or active directory). 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.
  - akerl_ 9y ago
    This is a bit like saying "human-driven cars shouldn't exist: the roads would be much safer". 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.
    - always_good 9y ago
      I looked into Yubikey but it seems absolutely impractical for day-to-day authentication unless you only use it for a finite amount of sites. 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.

jedisct1 9y ago

Password hashing functions are very useful, but can cause operational issues. 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.

ricardobeat 9y ago
Doesn't sending the salt to the client void a whole layer of security?
- eropple 9y ago

zaroth 9y ago

Iterative password hashing functions need to be slow to be secure. Their cost factor is borne through consumption of real-time resources such as CPU cycles and memory bandwidth, and therefore cost is roughly synonymous with latency. 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>

user5994461 9y ago

To illustrate the level of idiocy we reached with slow hash functions. The official NIST recommendation #800-132 is to use 10k iterations for PBKDF2, or 10M iterations for important keys. 10k iterations was half a second when we tried it on our server. 10M iterations took 8 minutes for a single hash.

chowells 9y ago
Were you using it to hash data for integrity? Or even worse, were you abusing it as a MAC [1]? That's the only way I can see it being so slow. 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.
- user5994461 9y ago
  It's hashing a password. It's used exactly the way it's supposed to be.
minitech 9y ago
> 10M iterations took 8 minutes for a single hash. ~: 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 10 million iterations in 6.5 seconds on a cheap laptop. Not sure what caused your numbers, but spending a few seconds on a password hash is not “idiocy”.

tzs 9y ago

Assume that all clients for a site use password managers with good random password generators, which they use to generate their site password. They are all, say, 40 characters chosen from [a-z][A-Z][0-9], so about 238 bits. 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?

cperciva 9y ago
No, that would be just fine. The sole purpose of password based key derivation functions is to maintain robustness in the presence of weak(er) passwords. For that matter, if your passwords really have 238 bits of entropy, you don't even need a salt.
sbierwagen 9y ago
Well, sure, if all users were guaranteed to use a strong password that wasn't reused for any other site, we wouldn't need a lot of password safety rules. Heck, you could just store them in plaintext. In practice though, users don't.
- joveian 9y ago
  A single hash is still a good idea since otherwise anyone who steals the password database can log in as any user. Sure if someone can steal the password database they may be able to steal passwords as users log in, but that is at least harder. 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.