> ah, the catch. blake3 targets 128 bit security. It competes with SipHash for speed and security.

No no, BLAKE3 is a general-purpose cryptographic hash just like BLAKE2, SHA-2, and SHA-3. The confusion here is that a hash function's security level is half of its output size, because of the birthday problem. BLAKE3, like BLAKE2s and SHA-256, has a 256-bit output and a 128-bit security level. (BLAKE3 also supports extendable output, but that doesn't affect the security level.)

> holy moly it really is fast

Thank you :)

>security level is half of its output size

A hash can have different security levels against different attacks. BLAKE3 appears to have 128 bits of security against all attacks.

SHA3-256 was originally designed to have 128 bits of collision security and 256 bits of preimage security. NIST then made a change to it giving it 128 bits of security against all attacks. A lot of people got mad. Then NIST caved and changed it back to 128 bits of collision security and 256 bits of preimage security.

It looks like BLAKE3 agrees with how NIST wanted SHA3 to be. I wonder if people will be mad at BLAKE3.

https://en.wikipedia.org/wiki/SHA-3#Capacity_change_controve...

For a more fair performance comparison against SHA3, you should compare against SHAKE128(256). That is, the version with 128 bits of security all around and a 256 bit output (how NIST wanted it). Although maybe it's pointless, because according to Wikipedia SHAKE128(256) is only 8% faster than SHA3-256 for large inputs.

> BLAKE3 appears to have 128 bits of security against all attacks.

That's not accurate. The best pseudo-preimage attack on BLAKE2s has complexity 2^{253.8} against 6.75 rounds (section 3.2 of https://eprint.iacr.org/2019/1492.pdf ). The best full-preimage attack on BLAKE2s is against 2.75 rounds. BLAKE3's round function is identical to BLAKE2s (although used in a different mode). Currently there isn't any known classical preimage attack on BLAKE3 better than these ones against reduced BLAKE2s. This should be interpreted with caution since the design has only just been published.

[Disclosure of interest: I know Zooko and work for Electric Coin Company. This is only based on a cursory review of the paper, though; I had not seen it prior to publication.]

-- Daira Hopwood

>Although maybe it's pointless, because according to Wikipedia SHAKE128(256) is only 8% faster than SHA3-256 for large inputs.

This is mainly due to SHA3's humongous 1600-bit state, which is not very friendly to embedded systems. In sponge constructions with smaller states, or generally primitives with smaller states, the difference is much larger.

Also in general I would say that small message performance is usually more important than large message performance, since large messages with desktop/laptop CPUs are so incredibly fast anyway with most hash functions that the bottleneck goes somewhere else. (Storage, network, etc.)

I mentioned large message performance because that appeared to be what BLAKE3's benchmarks were focusing on.

They're probably right to be upset by that change. Collisions require a lot more resources than simply trying every input on a GPU/ASIC, and as https://news.ycombinator.com/item?id=22007810 points out, an attacker that can only cover some fraction of the key space is massively more disadvantaged when they're performing a collision attack. You need more raw bits of preimage resistance to make the attacks equally hard.

I don't know if you need twice as many bits of preimage resistance, but I'd feel a lot more comfortable with an extra 32.

> Collisions require a lot more resources than simply trying every input on a GPU/ASIC

Would a 128 bit difficulty preimage attack against SHAKE128(256) be as simple as trying every single input? Trying every single input would be a 256 bit difficulty attack I would assume. To get it to a 128 bit attack I would think the attack would need something more advanced.

Yeah, I should have stuck with my initial wording about having major space requirements and not just time requirements.

You do need a more complex calculation to try to mount a preimage attack. But from what I can figure out it still tends to use big blocks of standalone arithmetic, something that's still very easy to accelerate with limited I/O.

Thanks for clarifying that.

> BLAKE3, like BLAKE2s .. has .. a 128-bit security level.

Skimming and interpreting the Too Much Crypto paper[1], the security target is strictly less than 128-bit security. If it maintained 128-bit security, it would be considered too many rounds.

[1] https://news.ycombinator.com/item?id=21917505

> ah, the catch. blake3 targets 128 bit security

Not really. 128 bits for collision (using a 256 bit hash) is not the same as 128 bits for key recovery or preimage. It is much, much stronger.

Preimage and key recovery attacks have a linear drop off: halving the number of tries halves your chances of success. Collisions have a quadratic drop off: halving your number of tries divides your chances of success by four.

Moreover, it is easier to find one key if you have many keys to try (finding 1 key among N is N times easier than finding any specific key). No such considerations for collisions: finding any collision is just as hard as finding one collision among many.

512-bit hashes were never needed for their security levels. Though in some circumstances (deriving multiple keys, EdDSA), bigger digests come in handy.

That's an interesting point I hadn't thought of before. If someone says "I want < 1% chance of an attack" then 128 bits of collision resistance will be stronger than 128 bits of preimage resistance.

On the other hand if someone says "I want < 99% chance of an attack" then 128 bits of preimage resistance will be more secure. But people probably don't have this goal, so 128 bits of collision resistance is better overall.

But another aspect is once you start finding collisions, you're likely to find more faster (whereas with preimages they keep coming linearly). This would actually be a worse point for collision resistance.

> (finding 1 key among N is N times easier than finding any specific key)

Yes, but only up to a point. You have to compare the cost of computing a hash vs comparing the hash. If the time to hash is 10000x the time to compare, then no matter how large N is, you'll never get faster than a 10000x speedup. This is essentially Amdahl's law. But this speedup is still quite significant.