4 ms·

> 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 pre

> 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.

Thorrez 7y ago
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.

Thorrez 7y ago

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.