Blake3 is 10 times faster than SHA-2 | Hacker News Reader

Blake3 is 10 times faster than SHA-2

nextjournal.com

198 pointstosh159 comments

A lot of people in the comments are wondering about using SHA-2 vs Blake3 for password hashing. The answer is, neither of these is suitable by itself for password hashing. Sadly there’s still a lot of advice on the internet (and, sadly, real systems) which do things like store md5(password) in a database and call it a day.

Blake2/3, SHA-2/3, and other cryptographic hash functions are meant to be fast, while also effectively guaranteeing no collisions or any way of reversing the hash (pre-image attack). This makes them ideal for stuff like checking file integrity, message authentication, inputs for cryptographic signatures and the like. But since they’re meant to be fast, they’re very poor choices for hashing low-entropy data such as passwords - attackers can test vast numbers of passwords (even if you salt!!) on GPU hardware.

For low-entropy data, you want a hash function that is slow and hard to parallelize. Use a specialized password hashing algorithm like bcrypt, scrypt or Argon2, and tune it so it’s slow enough without impacting overall usability (e.g. takes 50ms on your server). These algorithms are resistant to parallelization, so attackers will only be able to test a small number of passwords per second. This slows attackers down and can prevent them from recovering passwords that might be recoverable if stored using SHA-2, etc.

> tune it so it’s slow enough without impacting overall usability (e.g. takes 50ms on your server)

I want to insist that this is a very important part. If you are 99.9% of applications or websites out there, the only time you need to run that hash is at registration, login and password change. All of these case will be fine if it's a bit slow. Don't lowball it.

Also informationally I would like to add that as part of their "meant to be slow" job, algorithm like bcrypt are built in a way that makes it extremely hard if not impossible to run on cheap massively parallelized hardware (eg: CUDA on GPU).

Also you can do the stretching in the browser client (“server relief”) without losing security. Historically this would have meant a big performance penalty (and thus an advantage for attackers, who don't need to use your code) but JS and wasm are fast enough now that the price is fairly low.

Can you elaborate? This doesn't sound right to me but I don't know much about this.

It is indeed surprising; it took me a long time to be sure it was safe. Google “server relief”.

Interesting read:

http://ithare.com/client-plus-server-password-hashing-as-a-p...

That is pretty interesting, but doesn't actually offer up a solution that provides server relief, unless I missed something. In every case they still require that HSrv be a slow hash function.

My take away was that the server relief comes from reducing the ability of clients to trigger disproportionate amounts of server resource consumption.

I don’t see how that follows. If HSrv is expensive or slow, a malicious client could just submit nonsense hashes that only look like they might have come from HCli - the server shouldn’t be able to tell the difference.

Requiring client-side JavaScript for your login system seems fraught. I would much rather have an approach that does server side hashing exclusively, but gates it behind some kind of DDoS protection or rate-limiting.

You do the slow (bcrypt, argon2 or whatever) hash in the browser, and then the server can do the hyper-fast hash (SHA256).

You can still flood the server, but you're flooding it with things that take microseconds to compute, instead of 50ms.

That's not what the article states, though it's not very explicit about why you shouldn't do what you suggest.

If you’re going to do this, make sure you still hash the client’s hash output on the server (you can use SHA-2 in this case since the client’s hash output will effectively be high-entropy if salted). Otherwise you will be vulnerable to a “pass the hash” attack where an attacker in possession of your stored password hashes simply passes the hash to login.

I didn't think hashing the hash would be helpful here, and couldn't think of a way to mitigate against this attack.

After reading more it seems the only mitigation is Layers of Security.

https://en.m.wikipedia.org/wiki/Pass_the_hash#Mitigations

No, hashing the hash solves the problem.

I see, clever. Thanks!

It's important to understand why this is so: it's because the hash is big, so while it might be possible to mount a brute force preimage attack against a password, it is not practical to do so against a hash. So hashing a hash (once) is secure even though hashing a password (once) isn't.

Almost. That construction is still vulnerable to chosen input attacks without inner and outer padding, which is basically rediscovering HMAC, which also isn’t suitable for storing passwords. Don’t roll your own crypto if you don’t know what you’re doing. Use a PBKDF like argon2, scrypt, bcrypt or PBKDF2 as they are intended because they are far, far stronger than hashing a couple of times.

I believe what we’re discussing is having a client compute a PBKDF of the password, and then having the server hash the PBKDF output one more time to obtain the thing that’s actually inserted into the database. The idea is that if the database leaks, the attacker gets H(PBKDF(password)) which is hard to bruteforce due to the PBKDF, and can’t be used directly as a login token because of the extra H(). I don’t see where this would be subject to a chosen input attack.

It's not server relief, but there's also a technique called delegated hashing, i.e. allowing the client to do part of the work of computing the actual hash. This was one of the main selling points of the Makwa candidate for the password hashing competition.

It did not win, and I believe it is only CPU hard and not also memory hard unlike argon2. Nevertheless techniques to do this have been explored academically and might make it into future designs.

In case it isn't obvious, please continue to use argon2 (I'm just mentioning this as a point of interest).

Lots of advice in these threads and no one has mentioned anchoring yet so I'll staple it here; if you're a big company who can afford an HSM and the overhead of the key ceremony stuff to manage it (managed stuff like AWS cloud HSM simplifies this a fair bit) a great option is using an HSM as an anchored one-way function.

For whatever reason this seems to be seldom discussed but the general idea is as follows in hand-wavey fashion:

Set up HSM with a non-exportable symmetric key, set key usages to "encrypt only" and as one step of the hashing scheme you use, encrypt your hash through the HSM. Protected HMAC key would work too.

The result is that an attacker who compromises your password db cannot perform offline attacks on your passwords anymore - they now need to do key extraction on your HSM or remain in your infrastructure and keep running guesses through the HSM where it is relatively easy to monitor what is going on and they can't do a bajillion operations per second anymore.

Wish everyone running large user dbs like yahoo or linkedin etc applied anchoring to their password hashing - it's a relatively simple measure for an org "at scale" to make hash dumps alone useless.

Fair warning, mine isn't advice, just a comment about a technique that requires experienced cryptographers to use. I wouldn't attempt to use it myself :)

But you also need to be careful. The slow password hashing can be exploited for Denial of Service attack. You may want to rate-limit the APIs that use the hash algorithm.

This is a good time to ask for a question I have always wondered about these slow hash functions: are they slow because they are computationally intensive or is it that they have other tricks that makes them slow without costing too much load on your server (like needing RAM access, syscalls or anything that add latency but not much CPU load). If it's the former, isn't it a good DOS target, making your server busy hashing random crap and unable to process other requests?

They are computationally slow, no tricks. The purpose is to prevent attackers from calculating the plain passwords if they actually got access to the content of your DB. They are not that slow (let's say less than a second to calculate) - fast enough for your user to not notice , slow enough so that attacker can't do gazillion tries per second with their GPU or something.

As per DOS: rate limit per ip and account, and it's not an issue.

> They are computationally slow, no tricks

They have to and do use tricks, they aren't just slow. You could trivially make sha256 slow by just applying it a million times (that's not even parallelizable as well), but scrypt et al improve on that by making the algorithm also require a lot of RAM, use complex instructions (hard to recreate on a GPU or FPGA) and so on.

It's really hard to do very well, look at cryptocurrencies trying to be ASIC resistant: They want every normal person to be able to mine it, and don't want companies to be able to build a machine that can eclipse the mining power of everyone which means centralization.

They are computationally expensive. scrypt and Argon2 also depend on RAM access for their slowness, since that's much harder to parallelize (compute is easier to scale than RAM bandwidth). When your CPU can do hyperthreading that property might help recover some of that execution time.

It is a good DOS target, you should definitely rate limit logins to mitigate that. Other strategies are requiring captchas for login or letting the client execute the hash function and just doing a simple (fixed time) comparison on the server side.

> are they slow because they are computationally intensive...

In general, no. Most "slow" hashing schemes are designed to be memory-hard and highly serial (more threads = more contention, not throughput). Some of the earlier approaches just try to maximize computational requirements, but modern research acknowledges the march of computing power makes that an inherently poor choice for long term sensitive data. Argon2 is just one of the more advanced versions of a memory-hard scheme, building on prior research. I could try to give a poor explanation, but instead I'll link you the spec which is very readable: https://github.com/P-H-C/phc-winner-argon2/blob/master/argon...

Thanks!

I get md5 is pretty weak now, but what's wrong with sha-256 and a salt?

Salting only protects against rainbow tables, but does next to nothing against brute force attacks because the salt is usually stored adjacent or even as part of the stored password hash.

The md5 weakness (that everyone talks about) is about collision resistance, which isn't relavent to password hashing.

Generally you want slow, high cpu & memory hash functions for password hashing. This is the opposite of what md5/sha/blake aim for, as they want to be fast as possible. A fast hash allows the attacker to make many guesses very quickly (i think you can get something like 2 billion sha256 hashes a second with high end gpus). A slow hash makes it harder for the attacker to take lots of guesses (adding high mem usage helps protect against using alternate architectures like fpgas to speed things up).

Anyways, for passwords use something like argon2.

The Bitcoin network can perform some 10^20 SHA-256 hashes per second. That’s one 11-character upper/lowercase alphanumeric password PER SECOND.

A practical password cracking rig can probably do upwards of 10^11 hashes per second. The same rig can only do 10^5 bcrypt hashes per second.

And we should all use bcrpyt to hash password. We all should have had it long long time ago, and people are still rolling out their own password hashing with salting mechanism. Biggest facepalm in the industry in my eyes.

not processing plaintext passwords on your server >> argon > scrypt > bcrypt > pbkdf2 >>> any hash

There is an algorithm to authenticate without sharing the plaintext password from client to server, nor server to client - SRP. I know Apple uses it.

Unless any of your users ever try and use a >72 character password.

TBF that's super easy to work around: just prehash the key.

In fact, an other risk of bcrypt is that any nul byte will truncate the key, so you probably want to hash the password with something else (SHA384 or SHA512/256 for instance) then base64/base85-encode it before passing it to bcrypt.

The correct term is PBKDF.

And more succinctly:

crypto hash fn != authenticated hash fn (like HMAC constructions) != PBKDF

The correct term is KDF, PBKDF is a specific KDF algorithm.

>For low-entropy data, you want a hash function that is slow and hard to parallelize. Use a specialized password hashing algorithm like bcrypt, scrypt or Argon2, and tune it so it’s slow enough without impacting overall usability (e.g. takes 50ms on your server).

For most of the 2010s I've been under the impression that password hashing was a solved problem and that this is the solution.

And yet I still see comments online saying to hash passwords with a salt + 10,000 rounds of PBKDF2. Why bother when you can just b/scrypt it? Is there still some benefit of the former over the latter?

There are two principal benefits of sticking with PBKDF2:

1) It's a NIST standard. This may be necessary in some environments, typically just to check a box. (Yeah, I know...)

2) It's necessary for SCRAM (RFCs 5802, 7677), which is a much better login method based on passwords. This is applicable if your system uses GSS-API or SASL (e.g. dovecot IMAP logins).

If neither applies, my advice is to migrate to Argon2.

Also PBKDF2 is really easy to implement if you have a cryptographic hash (even more so with a ready-made HMAC), which is useful if you can't or don't want to pull in dependencies.

The official Blake3 site / repo actually covers this itself:

> NOTE: BLAKE3 is not a password hashing algorithm, because it's designed to be fast, whereas password hashing should not be fast. If you hash passwords to store the hashes or if you derive keys from passwords, we recommend Argon2.

Argon2 is a recent entry which won the password hashing competition in 2015 and is slowly getting included in recent versions of languages like PHP 7.2 as an alternative to bcrypt.

https://password-hashing.net/

As stated in the parent, integrity check hashing (should be fast) and password hashing (should be slow) are very different things and should not be mixed to use wrong implementations.

As bcrypt and argon2 both have specific prefixes, you can still keep bcrypt hashes and verifier can work on both (assuming it supports argon2) while using argon2 for newer entries stored in a database. (Preferably update the old bcrypt into argon2 on next login or something.)

JP Aumasson just announced Blake3 at Real World Crypto a few days ago during the lightning talks. This was also right after he presented on "Too Much Crypto"[1] which argues that we use too many rounds in symmetric constructions: our security margins are too high and don't match any of the best "practical" attacks. We're too paranoid for our own good. He suggests reducing the number of rounds for a number of constructions like AES, SHA-3, Blake2, etc.

[1]: https://eprint.iacr.org/2019/1492.pdf

Blake3 is in part a reduction of number of rounds (so it's faster), it's also a bit of a design change (the round function, and the parallelization), and it's now just one multi-purpose function (instead of several instances) that takes an arbitrary-length input and gives an arbitrary-length output.

My questions are:

* what are standards using Blake2 (like Noise) going to do?

* what do cryptanalysts think?

* is it really that fast? (I'll have to benchmark this for my own use-case.)

> which argues that we use too many rounds in symmetric constructions: our security margins are too high and don't match any of the best "practical" attacks. We're too paranoid for our own good. He suggests reducing the number of rounds for a number of constructions like AES, SHA-3, Blake2, etc.

This seems a quite dangerous way of thinking. New attacks, methods to attack crypto are discovered regularly. A view years ago people also said SHA-1 will never get broken to the degree it just got broken a recently.

So the only think we can do is to be slightly paranoid, everything else would be strongly negligent.

Especially if we consider how long it often takes in practice to update software and phase out previous encryption and hash methods without having to worry about e.g. downgrade attacks or similar.

Sure software should be possible to be updated asap, but honestly how long will it take until SHA-1 is phased out?

EDIT: Through that also means if you believe you will always be able update the _deployed_ relevant parts of your software ASAP (which can't work for libraries) and you are sure that you will follow the crypto community close enough and you believe some one else does so to if you are unavailable because of sickness, then yes go ahead and use less paranoid/secure crypto.

Agreed. We are not just securing for today, we are securing for perhaps decades into the future. If we don't know for sure what the threat is, then the right measure of paranoia is as much as we can afford.

We are not just securing ourselves, but our social network too. Something you do can be used to discredit your kids and grand-kids a long time from now.

Why not increase the rounds then? What makes the current security margins acceptable but not smaller margins?

I don't know a reason for why they are acceptable. AES256 is considered quantum-proof, but there exists another theoretical quantum computer design which seems to raise the bar again. I don't know if there exists a theoretical limit for how powerful quantum computers can get.

What other theoretical quantum design?

AES256 is considered quantum proof because grover's algorithm can in theory basically half they key size, and aes128 is secure on normal computers [we are still very very very very far away from a quantum computer that can use grover's algorithm to bruteforce aes128].

I'm not an expert on the subject but i believe a new quantum algorithm that could break aes256 would be a very major breakthrough in designing quantum algorithms.

The basic intuition behind symmetric cryptography is that once your input bits are "thoroughly mixed", there's no way to un-mix them besides brute-force.

On the other hand, we don't have a solid theory of computational complexity yet. Even basic questions like P = NP are still unanswered, so we have no idea what "thoroughly mixed" actually means, how to measure it, how to achieve it, or even if it exists.

Whatever it is, a single round of BLAKE certainly isn't "thoroughly mixed". Is 10 rounds enough? Nobody knows. On the other hand, we suspect that a thousand rounds are no better than a hundred - there's probably a plateau of "maximum entropy", and once you get there, extra mixing doesn't help.

So, since we don't actually know what we are doing, we pick a safety margin, like 1.4x or 2x, and just use that. It's all just guesswork until the theoretical side catches up, so your opinion is as good as mine. On the other hand, picking a safety margin of 1 seems rash. If you have practical attacks in the round before, you probably aren't anywhere near the plateau of maximum entropy!

This seems a quite dangerous way of thinking. New attacks, methods to attack crypto are discovered regularly.

It's not, really, because there is obviously some security margin that is too high. It makes a lot of sense to consider and try to quantify what that is. If all we have is some vague 'well, there are always new attacks' then how do we know the current margins are enough? Why not double the rounds, crank up the hash sizes, etc? It's not really a meaningful response to Aumasson's work.

1. As a community: Because you have to balance cost and security. Maybe we could increase them a bit without it stinging too much. But we can't do it boundlessly.

2. As an individual: Because I'd probably mess it up and pick a number of rounds that is e.g. divisible by 23 which weakens the system for some number theoretical reason that's far beyond my understanding.

I don't know what his arguments are, and I don't have much of a clue about crypto, but perhaps his argument could go along the lines of "a secure algorithm shouldn't be secured just by increasing the number of rounds too much"?

His argument is that since a cryptosystem has a set of different algorithms, each of which could compromise the whole system, the number of rounds should be chosen to match the margins across the primitives used, since strengthening one primitive does not improve the overall margins of the system.

Specifically at the end of the paper he argues that the choice of AES rounds is close to reasonable (and warrants little round reduction), and that ChaCha8 matches a reasonable number of rounds on AES (yielding a substantial 2.5x improvement in throughput vs. ChaCha20).

Following from these conclusions, I guess you could say that ChaCha12 is already quite ludicrously good, so ChaCha20 is downright wasteful. Not totally sure I agree yet with the specific numbers, but he makes a good point.

The paper also includes some helpful advice for those attempting to read cryptanalysis papers.

> This seems a quite dangerous way of thinking. New attacks, methods to attack crypto are discovered regularly.

He does actually address this counterargument in his paper. In fact most of his paper is a rebuttal to this argument (the status quo wisdom, so to speak).

This is not good advice at all. Reducing rounds to increase performance is going to significantly weaken the cipher if obfuscation is the key. And new attack vectors, especially with the advent of cheap cloud storage (rainbow tables), advances in GPU performance, and quantum computing are all necessary factors to consider. I wouldn't use Blake3 for anything after reading the above.

This is a bit pointless, since it does not say on which platform the comparison is made.

In any case, KangarooTwelve [1][2] (on AVX-512) is also 10x faster than SHA-256.

KangarooTwelve is a fast hash function of the Keccak family (from which the SHA-3 derives from), and it is clearly what BLAKE3 tries to catch up with.

However, KangarooTwelve probably benefits from the more extensive scrutiny that SHA-3 has received and will receive, and (from a performance standpoint) from future HW extensions that will speed it up even more (the first one appeared on ARMv8.2).

[1] https://keccak.team/files/KangarooTwelve.pdf

[2] https://www.cryptologie.net/article/393/kangarootwelve/

There is a comparison of Blake3 to various hash functions (including SHA-2 and SHA-3 families) on AWS c5.metal; see the chart here: https://github.com/BLAKE3-team/BLAKE3

Yes, and it didn't go unnoticed that KangarooTwelve (which - mind - does not belong to the SHA-3 family right now) is not included on that prominent comparison diagram, while it is considered in the BLAKE3 paper.

That's a good point; I was just giving you a handy chart with an explicitly called out platform :)

I felt it would've been unfair to include KangarooTwelve in that particular bar chart, because at 16 KiB of input it hasn't reached its peak throughput. At the same time, the goal was to focus on more widely used algorithms.

BLAKE was a SHA-3 finalist and received similar scrutiny to Keccak. Blake2 is, AFAIK, more widely adopted in software than SHA-3 and KangarooTwelve combined. Part of this is that Keccak, as specified in SHA-3, is incredibly slow in software -- NIST not only encouraged a ridiculous number of rounds, but also biased their decision-making in favor of hardware implementations.

I'm not sure to what extent we'll see significant SHA-3 adoption outside of any future FIPS software requirements. You are probably correct about the additional scrutiny SHA-3 will receive, just as a side effect of its use in future FIPS-compliant software.

Speed comparison from the BLAKE3 authors: https://github.com/BLAKE3-team/BLAKE3/

I hadn't heard of BLAKE3 before (I thought BLAKE2b was the latest and greatest), judging by commits from the repositories of that user it's about half a year old now.

Paper's abstract starts with:

> BLAKE3 [is] an evolution of the BLAKE2 cryptographic hash that is both faster and also more consistently fast across different platforms and input sizes. BLAKE3 supports an unbounded degree of parallelism, using a tree structure that scales up to any number of SIMD lanes and CPU cores. On Intel Cascade Lake-SP, peak single-threaded throughput is 4× that of BLAKE2b, 8× that of SHA-512, and 12× that of SHA-256, and it can scale further using multiple threads. BLAKE3 is also efficient on smaller architectures [like] 32-bit ARM1176

In the introduction, the reason for BLAKE3 is described:

> A drawback of BLAKE2 has been its large number of incompatible variants. The performance tradeoffs between different variants are subtle, and library support is uneven. BLAKE2b is the most widely supported, but it is not the fastest on most platforms. BLAKE2bp and BLAKE2sp are more than twice as fast on modern x86 processors, but they are sparsely supported and rarely adopted. BLAKE3 eliminates this drawback. It is a single algorithm with no variants

Paper: https://github.com/BLAKE3-team/BLAKE3-specs/ (By the way, the download doesn't work for me in the latest Firefox on Linux and GitHub's rendering is plain awful. Not sure if anyone else can reproduce that or if my Firefox is broken.)

The reason you haven't heard of it before now is that it was released 2020-01-09, last Thursday at the time of writing, at Real World Crypto.

The only author of BLAKE3 that spoke there was JP (@veorq). The day matches but the title of his talk is "Too Much Crypto". Is that where it was announced? (Quick link to program: https://rwc.iacr.org/2020/program.html#day-2020-01-09)

It was announced in a lightning talk following that session

That doesn't sound very official. Most text in the paper seems to date from August, so it looks like this has been out for a while and was not only just announced, even if it was mentioned or officially "announced" (while being already released) in a surprise talk at that conference.

yup, Blake3 is 1-day old (released yesterday).

JPA and I announced BLAKE3 at the RWC lightning talks, after JPA's Too Much Crypto talk, and we published all the repos and crates.io packages about 30 minutes prior to that. The commit history that you see in the repos was private until January 9.

You would be mistaken.

An A4 booklet of the paper, if you're into printing out the interwebs: https://mbarkhau.keybase.pub/pdfs/blake3_a4_booklet.pdf?dl=1

Do the runtime tests decouple from I/O times e.g. file and memory caching aren't affecting the results?

Surprised because I'd expect a big file like that to be I/o bound in practice

There is a tech talk about Bao (I think it’s the same author) where he prefaced the talk by describing a few caveats like “benchmarks are lies” and he mentioned that you should always run a timed process a second time to tease out bias from cached/pages instructions and data.

The core reason this method is faster than traditional SHAs is because Blake3 is a binary tree where the leaf blocks can be hashed in parallel and SHA is entirely sequential

> you should always run a timed process a second time

I should hope that anyone doing benchmarks does them multiple times to avoid crap like popcon or adobe reader update randomly keeping the system busy during one of the two algorithms' benchmarks. I don't expect that the author ran this only once and decided to make a blog post based on that, even if the post doesn't show multiple runs.

Author here, I did run it a few times but you don’t have to take my word for it, you can rerun the notebook yourself if you sign up for Nextjournal and remix my notebook. Full disclosure: I’m also a Cofounder of Nextjournal.

But I wouldn’t suggest to use Nextjournal for serious benchmarking (yet). We’re running on Google Cloud and it’s not suited for benchmarking unless you pay for a (big) sole tenant instance. In the future we plan to offer dedicated instances for benchmarking.

To be clear, "benchmarks are nothing but lies" is an exaggeration to get my point across. (And a good way to get a laugh at the start of a talk.) But take a look at Figure 3 from the Performance section of the BLAKE3 spec: https://i.imgur.com/smGHAKA.png. Even ignoring things like caching and compiler settings and different hardware, that's a complicated graph! The lines cross all over each other. I count 5 different functions in that graph that are, for at least some input, the "fastest hash function". (I think BLAKE2sp just baaarely passes below BLAKE2bp, just prior to 8 KiB.) It's hard to give a simple summary of a complicated picture. For the big red bar chart at the top of the BLAKE3 repo, we certainly cherry-picked a point where BLAKE3 looks good. But you could also cherry-pick points where it looks bad.

Is "faster" always a good thing in hashing algorithms?

Suppose a hashed password database falls into wrong hands. If they're hashed with a faster algorithm wouldn't it be easier to try a dictionary attack to discover the real passwords?

Blake3 is not for use in a password hashing algorithm; those have different goals. Check out Argon2 or bcrypt for that.

Ok, thank you.

I understand that it is for implementing things like dictionaries/hash tables.

Or integrity checking for non-authenticated encryption modes (wouldn't want file encryption or https to be slow).

No, Blake3 is a cryptographic hash algorithm, not for dictionaries or hash tables. It is intended for cryptographic signatures, file/data integrity, message authentication codes, etc.

For dictionaries/hash tables you'd typically use a very fast hash algorithm like xxHash, murmurHash, etc. Those are tuned for speed but can have collisions (typically they have very short outputs - 32 or 64 bits - so that they're easy to compare and compute with).

For cryptographic purposes (authenticity, integrity) you'd use a medium speed algorithm like SHA2/3, Blake2/3, etc. which are reasonably fast and essentially guarantee there won't be collisions (i.e. it's computationally hard to come up with collisions). These are meant to be computed quickly and potentially in parallel because you want to be able to verify data fast.

For password hashing you'd use a slow algorithm like bcrypt/scrypt or Argon2. These are designed specifically to be slow; some also use lots of memory specifically to slow down parallel attackers. You want password hashing to be relatively slow because you need to protect low-entropy data (a typical password only has a few dozen bits of security). By making the algorithm deliberately slow you would ensure that an attacker can't quickly guess the password, even if they have the hash.

These are the three major categories of hash; knowing which one to use in which application is pretty important. Don't mix them up!

In any situation where a hashcode is cacheable (which seems to me to cover all situations where a hashcode even makes sense) a cryptographic hash function might not be such a bad idea (especially if you're IO bound in any way).

With a bad hash function you can end up with a high level of bucket utilisation, significantly reducing the efficiency of the structure.

With user defined data there's even the possibility of maliciously crafted input attempting to force collisions as part of a DOS attack.

You can salt your input, and pretty much eliminate the issue - but as far as I can tell, you'll just end up rolling your own crypto.

Actually, a counter-point: there might be situations where you want an anti-cryptographic hash function - where similar inputs produce generally similar hashes.

It could have some application as a preprocessing step in clustering (if it could be done efficiently).

Easy: for n-byte output, separate input into n equally-sized chunks (pad with zeroes if not enough). For each chunk, XOR all the bytes together.

Those are called fuzzy or locality-sensitive hashes; they’re used a lot in image processing for similarity testing, for example. I don’t consider them to be in the same category as normal hashes, though, because fuzzy hashes have vastly different properties.

The term for this is locality sensitive hashing, and it's very useful in some contexts.

Cryptographic hash functions can be orders of magnitude slower than functions tuned for hashtables and dictionaries. If you’re using them as hash table indexes, then you have to take the big cryptographically secure number and mod it by a small bucket count - and then you’re going to have collisions. If you don’t salt, then an attacker is going to predict the bucket indexes no matter how strong your hash function is, and since you can’t have that many buckets, they can just brute force to find collisions.

Salting is the way to deal with these issues, and for hash tables it works well even if your hash function isn’t cryptographically secure. Hence, for hash tables, salt+fast hash function should be sufficient.

Thanks.

Blake3 is explicitly not a password hashing algorithm. For that use Bcrypt or Scrypt or Argon2. The authors of Blake3 point this out in the README of Blake3.

For general purpose algorithms yes. Blake3 is not a password hashing algorithm it’s a general purpose one, used for checksums or verifying 2 files are the same etc.

For password hashing you’re correct they should be slow, bcrypt for example.

> For password hashing you’re correct they should be slow, bcrypt for example.

Slowness is not the quality of a hashing algorithm that guarantees anything :)

Guarantee, I agree.

Resistance to quickly creating a rainbow table with significant coverage, however, is a reasonable property.

The mentioned bcrypt library allows you to “tighten the ratchet” over time as average computing power increases to make hashing a single password in 2010 take about the same amount of time on average modern computing hardware as in 2020 (assuming you correctly increase the number of iterations)

You're being pointlessly pedantic.

The commenter above obviously meant "slow to brute-force".

You're pedantically interpreting it to mean "slow for a given implementation, even if there are some scenarios under which it would be faster to brute force".

What the parent comment meant is clear enough I think, and it's accurate in that context. The whole point of modern hashing algorithms that require memory and have scaling difficulty factors is to make it slower for an attacker with certain kinds of resources to brute force it.

If you have a very slow hashing algorithm implementation of a fast hashing algorithm (say 'sleep 5, echo 1'), that's not slow by the parent's comment definition because it's not slow to brute force.

Similarly, if the hashing algorithm has predictable output that allows the attacker to derive information about the input, that obviously is also faster to brute-force.

That sort of pedantry is arguably somewhat useful if you also choose to provide a more precise definition or explanation. It's definitely not constructive if you just add a little smiley face and do it as an asinine "hah look at how smart I am".

Wow, so offensive. Didn't mean it that way, but if it turned out that, what a heck then. What I wanted to say was that slowness is not necessary attribute, unless we really seek it. If we could get very good and quick algorithm without being it slow, we would use it. Thanks for misinterpreting my smiley too. Have a good evening there.

> If we could get very good and quick algorithm without being it slow, we would use it.

No, that's simply not true, and that's what the person you replied to was trying to say. For a password hashing algorithm, you actively want it to be slow - to have a mathematically guaranteed minimum amount of time that each attempt takes, regardless of implementation. This is a security property of a password-hashing algorithm. It is a necessary attribute - you can't have a "good" password-hashing algorithm whose output can be computed arbitrarily quickly.

What you might be saying is that if an inefficient implementation is slow, we'd like to speed it up. Sure. The requirement of a good algorithm is that the most efficient implementation possible is slow.

I guess Most would use rainbow tables so it wouldn't matter.

You can always make a fast hashing algorithm into a slow-enough password hashing algorithm by repeating it multiple times (as with PBKDF2) or better yet using a construction that also uses a minimum amount of memory, not just computational time. For most cryptographic applications (signing data in transit, signing data at rest, computing things like Merkle trees for applications like git and dm-verity), you want a hash that is fast to compute. It's basically only password hashing and cryptocurrency mining that needs to be slow.

BLAKE3's readme says: (https://github.com/BLAKE3-team/BLAKE3)

NOTE: BLAKE3 is not a password hashing algorithm, because it's designed to be fast, whereas password hashing should not be fast. If you hash passwords to store the hashes or if you derive keys from passwords, we recommend Argon2.

Argon2 (https://github.com/P-H-C/phc-winner-argon2/blob/master/argon...) is based on BLAKE2b.

Faster is always a good thing for a hashing primitive.

For hashing passwords, you should not directly use a hashing primitive but instead stretch/iterate it through a higher-level algorithm, such as Argon2, that will (1) slow it down and (2) salt it.

Different hashing functions have different purposes. More specifically a hashing function used for authenticating data must be fast, so should never be used for password hashing.

Password hashing should always be performed using a hashing function designed specifically to prevent high speed execution - for that reason modern password hashing functions are both computationally slow (because of course), but also use large amounts of memory (to inhibit parallel execution).

We often use 'hash' as a sort-hand way of saying 'Key Derivation Function' when talking about secrets like passwords. https://en.wikipedia.org/wiki/Key_derivation_function

These functions usually use hashes as a primitive, but there is more to them than that. Using a plain hash to store passwords is usually a red flag that the storage is insecure. I see it when doing source code audits: some legacy software using md5 without a salt.

To be precise I think security community should make an effort to separate the two terms more often. I've been trying to be more precise when writing and reviewing assessment reports.

Unfortunately, not all password hashing algorithms are key derivation functions. That's just a common design and closely related.

I've never really understood the difference between a KDF, hashing function, password hashing function, though it's relevant to know when writing reports (I work for a security company). We recommend Argon2/scrypt/bcrypt for password storage of course, but we call them KDFs and I'm not sure if it's correct. From my understanding, a KDF can be fast, but a PBKDF must be slow. Could you elaborate or do you know a good resource (short of a whole book on low level crypto details)?

When talking about passwords specifically in our reports (I work at a security company too), I tell our team to use the same language as NIST 800-63B, since its the best "standard" for passwords and authentication I can find.

The relevant bit here is this:

Verifiers SHALL store memorized secrets in a form that is resistant to offline attacks. Memorized secrets SHALL be salted and hashed using a suitable one-way key derivation function. Key derivation functions take a password, a salt, and a cost factor as inputs then generate a password hash.

They are specific about the type of KDF required: "one-way key derivation function".

The examples given later are PBKDF2 and Balloon.

That's one of the reference documents we also use. Somehow I still feel like KDF (or "one-way KDF") describes a broader set of algorithms than we truly mean, but you make a good point that if some official body writes it this way, the terminology is probably at least correct enough.

I don't know of a good source beyond textbooks or papers which focus precisely on the low level crypto details you (rightly) want to avoid. There just isn't much of a need for that kind of nuance most of the time. I also (gently) reject the premise; as far as practical security is concerned, if your team is recommending Argon2/scrypt/bcrypt to developers then that's far more important than being able to explain the difference between key derivation and keyless password hashing.

It's essentially like rectangles versus squares. You can create a key derivation function out of anything which passes all the criteria of a password hashing function. But it won't be a particularly performant or useful key derivation function. Likewise you can create a password hashing algorithm out of a dedicated key derivation function, but that's insufficient on its own.

There's no need to get bogged down in the details, just continue recommending a reputable implementation of these algorithms. On the other hand, if you'd like to learn more out of intellectual curiosity, Boneh & Shoup's textbook is good (work in progress) [1]. Galbraith's textbook includes chapters which cover the topic to a depth that's beyond what you're looking for, but you'll learn whatever it is you want to know [2].

Finally, more accessible, informal answers that get the basic idea across are [3], [4].

1. https://toc.cryptobook.us/

2. https://www.math.auckland.ac.nz/~sgal018/crypto-book/main.pd...

3. https://security.stackexchange.com/questions/95410/what-is-t...

4. https://crypto.stackexchange.com/questions/70716/key-derivat...

The HKDF paper[1] has a good definition of a KDF:

    A Key derivation function (KDF) is a basic and essential component of cryptographic systems: Its goal is to take a source of initial keying material, usually containing some good amount of randomness, but not distributed uniformly or for which an attacker has some partial knowledge, and derive from it one or more cryptographically strong secret keys.

Not all KDFs are hash functions, or hash-function based. There are block-cipher based KDFs, stream-cipher based KDFs, etc.

Hash functions take arbitrary length input (well, up to some very large maximum size) and provide fixed-length output.

eXtensible Output Functions (XOFs)take arbitrary length input (up to some very large max) and provide arbitrary length output (up to some very large max).

Password Hashing Functions take (at least) three inputs: a unique salt, a secret password, and a tuning parameter (or set of parameters). They use the tuning parameter(s) to change the amount of work needed to compute their outputs. For any set of inputs they produce a deterministic output. The output may or may not be directly suitable for use as a cryptographic key, and may or may not be variable length.

Some password hashing functions are KDFs, taking effectively arbitrary input length and producing effectively arbitrary output length. PBKDF2 and Argon2 are KDFs.

Some password hashing functions are NOT KDFs, having limits on their input & output sizes. Bcrypt is not a KDF and not a hash function: it has a maximum 56-byte input (55 bytes if taking a null-terminated string, 72 bytes max in newer implementations) and a 60-byte output. It's suitable for logins where the password is hashed and compared to the stored hash, but not for directly deriving key material. And it's not necessarily suitable for non-ASCII passwords/passphrases, due to the short input.

[1] https://eprint.iacr.org/2010/264

This is a great comment, but I just want to point out:

> Bcrypt is not a KDF and not a hash function

This is true, but it's also a good example of what I was saying in my other comment. bcrypt is an example of a password hashing function which is not itself a KDF, but which can be used to construct a KDF.

All password hashing functions can be used to construct key derivation functions or simply are key derivation functions. But not all password hashing functions are key derivation functions. Whether or not it would be advisable to use a given password hashing function as a KDF depends, of course. In bcrypt's case you can construct a reasonable KDF. For example: https://github.com/pyca/bcrypt/blob/master/README.rst

You are right. I still think we should call "Password Hashing Algorithms". "One-way password storage" maybe. Or something. Just get rid of the word hashing.

Edit: NIST uses "one-way key derivation function" in their requirements, which I like, but that perhaps unfairly excludes other potential functions.

you are not supposed to use a hash to store a password (because hash functions are super fast), but a password hashing function instead like Argon2.

Another way of making it "slower" is to require more memory to compute your algorithms. The idea being that lots of memory is expensive no matter how clever you are with the computation.

I don't think it's a coincidence that BLAKE3 has been released shortly after the latest SHA-1 news. Many SHA-1 users would rather avoid the performance impact of SHA-2/3.

Reducing 10 rounds in Blake2 to 7 in Blake3.. huh?

The entire industry is going in exactly the opposite direction of this, to increase the complexity and depth of the attack surface of cryptographic methods and algorithms due to advances in quantum computing. Cloudflare, Microsoft Research etc are all investing heavily into post-quantum cryptography technologies, almost exactly the opposite of what this guy is promoting. Makes no sense. ‾\_(ツ)_/‾

This is completely pointless, but there's so many random things I share a name with, and somehow I've only met a few PEOPLE named Blake in real life.

What are the criteria for choosing an integrity checking hash? Speed is always desired, and longer output makes collisions due to random bit swaps less likely.

Even CRC32 is still used in embedded systems for short pieces of data.

Is there anything else important for detecting transmission errors if the data was sent encrypted, or is something like MD5 still sufficient for such uses?

Is Blake3 even worth considering for such a use case?

Never use MD5 except for compatibility.

This. There are hash functions that are faster than MD5, so it's not the fastest, and everyone knows (since 1996, actually[1]) that MD5 is insecure.

If you want transmission error checking, use CRC32 or Siphash or whatever. If you want an actual, cryptographic hash function, then BLAKE3 is one of the options, though it's a very young one so unless you really know what you're doing, you should probably not use this for another few years. Heck, if anything in this comment is new to you, you'll want to steer clear of such low-level decisions and just use a library that makes the decision for you.

[1] https://en.wikipedia.org/wiki/MD5 "In 1996, Dobbertin announced a collision of the compression function of MD5 (Dobbertin, 1996). While this was not an attack on the full MD5 hash function, it was close enough for cryptographers to recommend switching to a replacement, such as SHA-1 or RIPEMD-160."

> Heck, if anything in this comment is new to you, you'll want to steer clear of such low-level decisions and just use a library that makes the decision for you.

This reads very condescending: I posed the question to learn something, not be told off.

I'm sorry, I hate it when others do that and don't notice when I do it myself apparently.

It was really just meant to be read in the literal sense and not as that such a person is of less value or stupid. It can easily (and has) lead to security breaches if assumptions are made about this. I'm not saying you don't know the difference between md5 and crc32, but if anyone doesn't yet know that, then it's risky to make decisions about these things until they learn more. Cryptographers commonly advise non-experts to use a library to do things for you (even those that know a bit more) since cryptography can be very subtle, but clearly I should have phrased that better.

> Cryptographers commonly advise non-experts to use a library to do things for you

On the high level, the problem is that libraries are usually "CRC32", "MD5", "SHA256", etc. There's no guiding resource that I have found that matches use cases to libraries, which is where the initial question comes from.

That is, unless you meant a library that covers the entire use case, but there isn't always one.

That's part of why NaCl, Libsodium, and Libhydrogen have the APIs they do: they cover secure ways to use the primitives, make those ways easy, and make it harder to misuse things. It's also why so many security professionals like the "noise" protocol: it doesn't leave any of the difficult choices open to be misused.

This benchmark is not a comparison between BLAKE3 and SHA-2, it’s a comparison between b3sum and sha2sum. Things like file access pattern, hiding io latency, distributing work to cores, etc can make huge differences that have nothing to do with the hash functions themselves.

Unless you have SHA-NI in your processor... in which case Blake3 is slower than SHA-2.

I look forward to a future point in time where Blake7 is released.

https://twitter.com/dchest/status/1215751501567709185

1978 isn't on the graph. (-:

Hint: andybak was making a joke.

Straight talk, should I watch this show? :)

Are you prepared to cope with the idea that, more than 7 centuries from now, a tetchy oblong plastic computer will be able to easily find collisions in any hash algorithm that you can come up with and take over any system that strikes its fancy?

... and that it is in the hands of Kerr Avon?

A friend recently wrote a re-watch review: https://nwhyte.livejournal.com/tag/tv:%20blakes%207

I would like to see the performance of KanagarooTwelve in the same tree structure as BLAKE3, with AVX-512, on the same hardware (AWS c5.metal).

Take a look at Figure 3 in the Performance section of the BLAKE3 spec: https://i.imgur.com/smGHAKA.png. That graph doesn't account for differences in the tree structure, but it compares the performance of both with AVX-512.

Uhhh, I have an idea how sha-256 works but not blake3. Is blake3 better for storing passwords? If not, what is the go-to recommended hash for password storage of say, a simple front-facing app for consumers.

Neither is especially good for storing passwords.

Better use specialized password hashing functions like Argon2 or bcrypt.

SHA-256 is absolutely not recommended for storing passwords, and it was never designed for that purpose. If you are storing passwords with SHA-256 you should immediately migrate them to a password hashing algorithm. See “Upgrading Legacy Hashes” in the link below.

https://cheatsheetseries.owasp.org/cheatsheets/Password_Stor...

Recommended algorithms:

- Argon2

- PBKDF2

- Bcrypt

Is it better in preventing hash collisions?

It might be slightly worse as it reduced the number of rounds from 10 to 7.

Compared to?

MD2, MD4, MD5, SHA-1, etc.: There are collisions known, so yes.

SHA-2, SHA-3, BLAKE2b, Skein, Whirlpool, etc.: We don't have any collisions for these, so it doesn't get any better than that.

> SHA-2, SHA-3, BLAKE2b, Skein, Whirlpool, etc.: We don't have any collisions for these, so it doesn't get any better than that.

There are important differences; some of those primitives are definitely more trustworthy than others.

SHA-2 and Whirlpool use the old Merkle–Damgård construction, which has fallen out of favor because of unfortunate properties.

They are vulnerable to length extension attacks, such that it can be misused. For instance, if you want to use it as a keyed hash, you cannot just do sha2(key + message) (where + is concatenation). You have to use something like HMAC for that.

Skein is much better, but has a bit of an aged design now, and an insane 72 rounds. It doesn’t have as much love as BLAKE2 for instance, which makes it unlikely that people will build things competitive with BLAKE3 with it.

SHA-3, BLAKE2b and BLAKE3 are the best. Like Skein, they are not vulnerable to length extension attacks, so they have a trivial keyed hash function construction.

SHA-3 in particular has an elegant new design, the Sponge construction, which yields precise cryptographic protections in terms of the number of bits of security. It has displaced Merkle–Damgård as The Way We Do Things™ now; many modern hashes use it, eg Gimli relied on it to make comparisons.

One of the great things about this form is that it makes it a XOF: you can make your hash as long as you desire. (BLAKE also shares this property, but with a different construction.)

However, SHA-3 is slow, so if you want speed, use BLAKE2b (or Kangaroo12) over SHA-3, and BLAKE3 over them both.

If you want to be conservative about security and don't care about speed, a safe bet is still SHA-512/256, which is safe against length extension attacks.

That was informative, thanks! It matched my gut feeling about the algorithms and I knew some of these things, but not everything :)

> a safe bet is still SHA-512/256, which is safe against length extension attacks.

I would like to add here that this does not mean "SHA-512 or SHA-256" (I remembered that SHA-256 was not length-extension resistant and looked up the details). Instead, it means the version of SHA-512 that gets truncated to 256 bits. This is apparently relatively new (or at least added after I last read up on SHA-2):

> In March 2012, the standard was updated in FIPS PUB 180-4, adding the hash functions SHA-512/224 and SHA-512/256, and describing a method for generating initial values for truncated versions of SHA-512.

-- https://en.wikipedia.org/wiki/SHA-2#Hash_standard

I feel like that notation could have been chosen better by NIST.

The hash function "SHA-512/256" has different initial constants than "SHA-512", so it is not equivalent to truncating a "SHA-512" hash value.

SHA-224 and SHA-384 are somewhat resistant to length-extension attacks because they output a truncated state.

Yeah, the slash in the names are an unfortunate choice that hurts clarity.

If you hash the password, and then use that hash as the key to encrypt(AES/ChaCha20) the original password it self, isn't this good?

I always shake my head when performance is touted for new functions/constructions. It’s more important to minimize the costs of legitimate use while maximizing the costs of software and hardware attacks. Minimizing the former inevitably leads to minimization of the latter in brute force (cloud cluster, ASIC, FPGA, etc.) attacks. The fundamental impetuses of scrypt (a PBKDF rather than an unauthenticated hash function) was a righteous and necessary advance that must never be forgotten with each fashionable iteration of newness that seems to lose sight of how faster or newer isn’t always automatically better.

I can write a fast digest algorithm. Doesn't mean it's safe for anything more than triviality.

I have a project I couldn’t use SHA-2 on because of speed and because it was a 224bit or 256bit result.

Is there a way to use Blake3 in a reduced hash result way? Like 12-16 byte results. (IIRC, you can not truncate hashes for smaller results)

SHA-224 is literally truncated SHA-256. There's no security proof this is safe, but only in the sense there is no proof SHA does what it claims to do at all. Hash truncation is in the design of SHA-2. There's even an appendix of one of the FIPS documents explaining how to do the truncation for arbitrary sizes.

But be very careful to make sure that you only need preimage resistance...

A 224 bit output is going to be collision resistant too, though, for the foreseeable future. And when it comes to preimage resistance, even md5 is safe for the time being. (With the usual qualifier that there's absolutely no justification for using it with better hashes available.)

He's talking about 12 to 16 byte outputs though, which is 96-128 bits of preimage resistance, and only 48-64 bits of collision resistance.. which would be very broken today.

Mostly.

There are 12-16 byte hash or hash-like results are plenty secure. They’re keyed though.

The output from HMAC and AEAD ciphers with no encryption (think the additional data portion of ChaCha20-Poly1305 in a Nonce-MAC mode)... or maybe I’m wrong because these require nonces and keys.

Whether you are using it in a keyed authentication mode is orthogonal to collision resistance.

Not really. It's even 2x slower than SHA256-NI, the builtin.

b3sum is much faster than sha256sum, and blake3 is about 2x faster than blake2.

http://rurban.github.io/smhasher/doc/table.html

Just exactly what does the "insecure" flag mean in your tables? I'm curious about the kind of definition you are using for security whereby sha2 fails but farmhash passes.

"insecure" means that it fails any of the security tests.

SHA2NI and many other hashes fail most of those unless they are hardened, e.g. by support for adding random seeds, being insensitive to added \0 and such. No crypto hash supports random seeds out of the box btw.

Not sure why you are downvoted. Your table looks more factual than the blake3's github.

RE: the downvotes; while I didn't partake, I know there is history between the BLAKE/BLAKE2/BLAKE3 author, JP Aumasson, and Rurban, in particular related to differing opinions over the publication of SipHash.

Differing opinions here means that most of the cryptographic community agree that SipHash clears its claims as a PRF, while Rurban indicated he has found undisclosed vulnerabilities that he wishes not to publish.

RE: the table; a point to note is that BLAKE3's main implementation, in Rust, benefits a lot from multithreading on large files, which SHA2 cannot. The C version, which Rurban copied, does not leverage multithreading: https://github.com/BLAKE3-team/BLAKE3/blob/master/c/README.m...

Comparing single threaded speeds is also very valid for tons of contexts. Of course if one algo can't be multithreaded, maybe it will be better to use one that can instead, if that's interesting for a particular application, but it won't be necessarily interesting for all applications. So there is no single ordering about which is faster, in this case. If you sometimes needs to compute hashes on a computer that would have multiple unused cores at that moment, the multithreaded hash will have an advantage. If you are always loaded, you better consider the total amount of work; and maybe likewise if you want to prioritize energy efficiency (although it will not be completely linear)

The tone of the comment was unnecessarily dismissive, and it is kinda expected that hw implementation beats sw implementations. If anything, it's pretty impressive how close blake3 gets without dedicated instructions.

> I.e. the usage of SipHash for their hash table in Python 3.4, ruby, rust, systemd, OpenDNS, Haskell and OpenBSD is pure security theatre.

This seems like a noteworthy claim, and the hflounge link is unfortunately broken!

Is it possible to you to provide more information about this, that Siphash would be essentially broken?

I never said that Siphash is broken, read what I said. It's not broken, it's just theatre,and way too slow to be useful for anything. And it doesn't protect against hash table attacks. Proper protections need to be done at the collision handling step, not in the hash function.

http://perl11.org/blog/seed.html https://news.ycombinator.com/item?id=13361860

Why doesn't sha256sum use sha-ni?

On the other hand, seems like sha-ni became widely available only with cannon lake and zen, while blake3 should be fast on any hw even if it benefits from avx512

Reply on news.ycombinator.com