Password Hashing Competition | Hacker News Reader

Password Hashing Competition

password-hashing.net

72 pointsLaSombra19 comments

I'm no cryptoexpert but I was under the impression that slow password hashes were best, as they are harder to generate rainbow tables for and brute force the algorithm. Many of these algos are put aside for being too slow or praised for speed, and CPU/GPU optimization seems to be a big goal.

Slow to the extent affordable (thus, must be tunable) yet highly efficient on defender's hardware is best. (warbiscuit is correct on this.)

"Hard" is a wrong word to use - we're not trying to make things hard to do (as this would only increase the initial investment needed for attacks), we're trying to increase the attackers' cost per candidate password tested.

"Rainbow tables" are made irrelevant by proper use of salts. It's kindergarten stuff, as far as PHC is concerned.

"Too slow for its memory usage" refers to some of the schemes that claim to be (and possibly are) memory-hard (see the scrypt paper). For those, it is desirable to be able to tune them such that their memory usage is maximized for a given running time or hashes per second throughput. For example, a scheme that can be tuned to achieve 1000 hashes/s at 16 MB memory usage per hash computed might win competition over a scheme that only achieves at most 10 hashes/s at the same memory usage on the same server. The latter happens not to be usable for password authentication on a server at that memory cost setting.

Of course, there are also applications where the absolute maximum memory usage is not desirable - e.g., 1 second of running time might be affordable for deriving an encrypted filesystem key, but only e.g. 256 MB of free RAM might be available on a mobile device. There are PHC finalists that can be tuned to limit their memory usage as well, even if tuned to run for a long time, or that don't use much memory at all.

Disclosure: I am the submitter of yescrypt. I also participate on the PHC panel (non-voting, because of having my own submission), along with many others.

It's not necessarily "slow is best", but rather minimizing the ratio between how fast your production server can calculate them multiple hashes while under load, vs how fast your attacker can crack them on dedicated hardware.

Which, for example, is why something based on SHA3 is bad, because your typical server is just going to be doing SHA3 hashes via CPU. Except SHA3 was chosen to be ASIC-friendly, so your attacker will be able to calculate SHA3 faster than you. As long as the attacker has no faster calculation method than the one you're using, the absolute speed doesn't matter. This is why scrypt, bcrypt (and to a lesser extent pbkdf2-hmac-sha256) are doing well, because running them on GPU or ASIC isn't meaningfully faster than the CPU implementation the defender is using.

All that's left at that point is making it as expensive as possible for them to parallelize their attack. Which is what scrypt and other things attempt to do -- require as many non-CPU resources (memory, hd space, etc) so that the attacker's parallelization cost is also maximized.

(Personally, I've been playing around with the idea of incorporating random accesses to a 2-tb file of random data, so that the attacker would have a HUGE amount of data to steal before my hashes would work. And they'd have to establish shared access to all the CPUs/etc they're attacking with)

yescrypt has ROM capabilities [1], which function like your large file idea.

[1] https://password-hashing.net/wiki/doku.php/yescrypt#read-onl...

Ooh, that looks interesting ... and not just for ROM feature. They've packed a TON of things into there. Even SCRAM support!

I'm really intrigued by one of the planned features... "Hash upgrades to higher cost settings without knowledge of passwords". I can think of a way to implement that alone, but to pack that all in with those other features will be really impressive. And would be a huge boon to systems w/ infrequently logging-in users.

"Hash upgrades" have been added with the just-published v1 of the yescrypt submission to PHC. There is not yet an implementation of an "upgrade this hash" function (also, hash encoding needs to be finalized, including encoding of the upgrade count parameter), but now it's a matter of writing this additional code outside of the actual password hashing code (already capable of computing possibly-upgraded hashes).

Unfortunately, with memory-hard schemes such upgrades involve an efficiency loss in terms of normalized area-time, and there's a tradeoff between granularity of upgrades and efficiency. For Catena (another PHC finalist that supports these), the time granularity is 2x to 3x, with efficiency down to 33.3%+ of non-upgraded hashes (after many upgrades). For yescrypt, it's 4x to 5x granularity and 60%+ efficiency, respectively. (I felt that 33.3%+ is just not good enough - in my opinion, it's usually better to postpone the upgrade until 60%+ can be achieved rather than upgrade early and prevent it from ever being achieved. The next easy step would be 77.7%+, but the granularity would be too high.)

At the same time, support for ROM access frequency tuning (and thus for ROM-on-SSD, as opposed to ROM-in-RAM) has been dropped from yescrypt for now. The rationale is that builtin ROM-on-SSD didn't make enough sense without also having a ROM-in-RAM (in use cases for the former, the latter would also be easily affordable, including complexity wise, and would provide significant extra defense), and supporting two ROMs at once would be further beyond the comfort level for complexity of a hashing scheme in PHC (yescrypt is already somewhat beyond the comfort level). Support for two ROMs along with access frequency tuning might be re-added in an extended revision of yescrypt for specialized use cases at a later time, but this will be outside of PHC.

> random accesses

That's fairly simple to do:

Do a standard password hash as usual (with salt, of course), then use the hash as an index into the data (or the low/high N bits of the hash, whatever) and use that as the final password hash. Just don't lose the data!

Effectively using your password/salt as the key to a hashmap containing random data.

Yep... that was roughly my starting approach. Current one I'm playing with uses multiple samples (chosen as a function of the initial hash and the previous samples), to ensure the attacker has to actually take the whole file... otherwise the attacker gets away w/ 10% of file & 100 hashes, they've got good odds that one of those hashes only needs the first bit of the file.

Still trying to play with it to see if I can make it harder to parallelize assuming attacker does get the file. But that gets into designing an entire password hash, not just a friendly wrapper, which is more than I'm prepare to chew on right now :)

You should take a look at:

http://www.openwall.com/presentations/ZeroNights2012-New-In-...

https://medium.com/@TapLink/the-password-defense-league-c416...

(I'm not happy with how Jeremy re-purposed the words "blind hashing" to mean essentially the approach I had recommended as a better alternative to his original "blind hashing", which I criticized in the ZeroNights talk, but other than that I agree with what he wrote.)

To "make it harder to parallelize assuming attacker does get the file" (actually, to increase the cost per candidate password tested, not to make anything literally "hard to do"), I propose that "best of both worlds" approach (see my ZeroNights slides). And you're right, this means "designing an entire password hash, not just a friendly wrapper" (thus, different from Jeremy's work, and more similar to my work on yescrypt).

I'd just do pointer-chasing through the file, xored with the initial hash each time.

I.e. out = hash xor data[hash] xor data[hash xor data[hash]] ...

Alternative phrasing: out_n = data[hash xor out_(n-1)] xor out_(n-1), where out_1 = data[hash] xor hash

"Random" accesses throughout the file - not the easiest to run in parallel.

(That being said, I haven't checked to see if this is breakable)

Thanks, that was a great answer!

Any hashing algorithm can be made slower by stretching (repeatedly running the algorithm), so speed on its own is kind of meaningless

Ideally you want algorithms that are hard to design custom hardware for, or in other words, are very efficient on general purpose hardware (CPU/GPU). You can then stretch the algorithm to take 200ms on your server without it being doable in nanoseconds by dedicated hardware

I'm not entirely sure what "too slow for its memory usage means", but I would guess that it doesn't use enough memory which means ASICs/FPGAs are relatively easier to make for it

"Too slow for its memory usage" means that that in order to use large amounts of memory, it becomes impractically slow.

One of the non-finalists (Centrifuge) was criticised for byte-grained random memory accesses. A random access to main memory causes a row activation delay of roughly 50ns, so one should access many nearby bytes to make up for that.

That slows it down on general-purpose CPUs, but not on special-purpose ASICs. That's the exact opposite of what's desired.

Slow is relative to today's tech. What is slow today may not be tomorrow. That is why you see password hashing algorithms with a 'work factor' to modify how slow it is.

Are there any pure Python implementation of these algorithms? I am looking for something that would work with Google App Engine.

I wonder how these compare with bcrypt and scrypt. Anyone have any insight?

Differently! The goal of PHC is to improve upon the current state-of-the-art, which includes bcrypt and scrypt, but there are many tradeoffs involved. A scheme that is better in one aspect might be worse (or just different) in another.

These finalists try to improve upon scrypt (increase attack/defense cost ratio or/and avoid cache-timing side-channels while building upon ideas from scrypt and more): Argon, Catena, Lyra2, yescrypt, and maybe POMELO. Ditto for some non-finalists: Gambit, RIG, TwoCats. (Arguably some other non-finalists fall in this category as well.)

These finalists include bcrypt-like components or properties while being scalable (to a varying extent) to larger than bcrypt's memory usage: battcrypt, POMELO, Pufferfish, yescrypt. And a non-finalist: TwoCats. Unlike bcrypt itself, battcrypt is likely to be implementable in scripting languages that offer native Blowfish.

These finalists are totally different from bcrypt and scrypt, not trying to improve upon them nor even be on par with them: Makwa and Parallel. They are for different applications than bcrypt and scrypt. Parallel can be said to try to improve upon PBKDF2, though.

As to more specific comparisons, with benchmarks and cost estimates for various settings on various types of hardware, this goes beyond a comment reply like this (or I'd need to focus on one PHC candidate, like mine, which would be unfair). It is a topic for the PHC discussions list and for materials included with each PHC candidate (some do include various numbers or/and claims to this extent).

Yescrypt is derived from scrypt with extra tunable parameters.

As for security margins? That remains to be seen.

Reply on news.ycombinator.com