7 ms·
BLAKE2: “Harder, Better, Faster, Stronger” Than MD5 (2014)
- dcomp 5y ago
- PrimeDirective 5y ago
- goldenkey 5y ago
- sshine 5y agoIn the meantime, https://github.com/BLAKE3-team/BLAKE3 https://github.com/BLAKE3-team/BLAKE3
- encryptluks2 5y agoHoping to see a BLAKE3 implementation in whatever library is necessary for distros like Arch to verify package checksums soon.
- 2bluesc 5y agoWow, totally unaware of the performance speed-up 5x over sha1 and blake2b. Even more for others! Are there cases where the benchmark doesn't hold true? Different architectures? I'm inclined to use this on some less security sensitive things I need a hash for.
- staticassertion 5y agoThere shouldn't be any meaningful reduction in security afaik. Most of the performance comes from reducing the number of rounds used because it was shown that it was unnecessary iirc.
- searealist 5y agoBLAKE3 only reduces the rounds to 7 from 10 in BLAKE2. That only accounts for a 1.42x speedup, not the > 5x speedup seen in BLAKE3 for a single thread. Most of the speedup comes from the hashing mode which breaks the input into a tree of independent chunks and then using SIMD to hash several of them in parallel. Additionally, the Rust implementation even allows even more parallelism using threads.
- staticassertion 5y agoGotcha, I wasn't sure if it was the parallelism or the reduced rounds that made the bigger difference.
- anfilt 5y agoStill BLAKE3 still is not a ton faster for short data inputs especially if your implementation has a lot overhead for parallelism like threading like you mentioned in a rust implementation. Good for files and similar if your data stream is long enough to effectively use the tree structure.
- rowanG077 5y agocheck out https://github.com/Cyan4973/xxHash https://github.com/Cyan4973/xxHash for I use it for performance sensitive non-crypto stuff.
- oconnor663 5y ago> Are there cases where the benchmark doesn't hold true? Different architectures? Yes, that 5x figure represents a big speedup that comes from using SIMD (specifically AVX-512) to compress multiple blocks in parallel. To take full advantage of AVX-512, BLAKE3 needs to have at least 16 KiB of input. So for any input shorter than that, the speedup compared to BLAKE2b/s will be smaller. For inputs less than 2 KiB, the only speedup is the ~1.4x that you get from the round reduction. Architectures other than x86 tend to have less in the way of SIMD. ARM has NEON, but that's currently only 128 bits wide. So the big single-threaded speedups are only on x86 today. (For multithreading speedups, the architecture doesn't matter as much. Just the number of cores you have.) > I'm inclined to use this on some less security sensitive things I need a hash for. This makes sense insofar as BLAKE3 is a new design, and it pays for cryptographic applications to be conservative. But to be clear, if BLAKE3 turns out not to uphold the same security properties as SHA-2 or BLAKE2s, that would represent a catastrophic failure of the design. (It's possible that some flaw could be discovered that affects BLAKE2 and BLAKE3 equally, but that the lower round count of BLAKE3 would make the flaw more severe. In that case, I'd expect everyone would also want to migrate off BLAKE2 pretty quickly anyway.)
- bradknowles 5y agoInteresting then that the latest Intel chips are dropping AVX-512. Makes me wonder if BLAKE3 will be changed to suit, or if Intel chips are just going to suck when it come to performance with the standard?
- oconnor663 5y agoI'm not sure any changes are necessary. The implementations will use AVX-512 where it's available, and they'll fall back to something else (often AVX-2) if it's not.
- cm2187 5y agoBut isn't sha256 hardware accelerated on most modern intel CPU? Is it faster than a hardware accelerated sha256?
- flatiron 5y agoNah. It’s like chacha it’s only faster than aes on non equipped cpus. I still use sha2 everywhere.
- oconnor663 5y agoThe performance story here is more complicated than you might think. ChaCha and AES (in the typical AES-CTR or AES-GCM modes) have a lot in common structurally. In both cases, different blocks can be computed in parallel. Software and hardware implementations can both take advantage of that parallelism to improve performance. The story is different with SHA-2, which is entirely serial by design. There's no possibility of parallelism between different blocks of a single SHA-2 input. That means that there's little incentive to create a parallelized hardware implementation of SHA-2, and I'm not aware of any. In contrast, BLAKE3 is more like AES-CTR and ChaCha in that (given a long enough input) it can take full advantage of any degree of parallelism. For this reason, given reasonably modern SIMD support like AVX-2, BLAKE3 tends to be faster than hardware-accelerated SHA-256, even before multithreading gets into the picture.
- loeg 5y ago> isn't sha256 hardware accelerated on most modern intel CPU No. Most Intel CPUs lack SHA-NI extensions. It looks like they may have finally started adding it to their 2020+ mainstream CPUs, but for a long time it was only present on their low-end Atom and similar CPUs. AMD CPUs have all had SHA-NI support since Zen. https://en.wikipedia.org/wiki/Intel_SHA_extensions https://en.wikipedia.org/wiki/Intel_SHA_extensions
- jamesfinlayson 5y agoOh neat - I was doing some file matching on the weekend (check if files are the same by comparing size and SHA-256) and the file hashing certainly didn't help it's speed. This should give me a nice speed boost.
- Hanschri 5y agoI found the footnote quite interesting: > Some software, notably git, is still using SHA-1, and relying on the fact that the best publicly-known method of generating SHA-1 collisions costs 2⁶⁹ computations, which is expensive. I think it is unwise to rely on this for two reasons. One is that there could be more efficient techniques to compute SHA-1 collisions that we don’t know about. Another is that the cost of doing 2⁶⁹ computations is falling rapidly—at the time of this writing (March 22, 2014), the Bitcoin network is performing enough computation to generate SHA-1 collisions every 131 minutes! By guesstimating from just looking at the graph to the linked site, it seems the Bitcoin network was at about 100 PH/s, with the network at 185 EH/s, which is close to a 2000x in hashrate since this blogpost went live.
- staticassertion 5y agoAnd Linus was told of this and, in typical Linus fashion, he dismissed it.
- stickfigure 5y agoIs there some way of co-opting the bitcoin network into calculating specific hash collisions?
- loeg 5y agoNo; it's a different algorithm.
- drexlspivey 5y agoYou would need 6 zettabytes per second to even store all the hashes generated by the BTC network. That’s many times the world’s storage capacity generated every second.
- Dylan16807 5y agoAnd was he wrong?
- 5y ago
- londons_explore 5y agoCan we have a hash function that is theoretically secure, rather than just "we shuffled a bunch of bits, and nobody yet knows how to unshuffle them, but in 20 years someone might discover how to"? For example, encrypting the data with a public key where nobody knows the private key ought to do the job, for example, public key=pi. Then use the encrypted data as the 'hash' (or some shortened version of it by discarding bits). Yes, I know it would be slower, but it might be better to pay the performance cost than to have to move everything to a new algorithm every 20 years.
- capableweb 5y ago> Yes, I know it would be slower, but it might be better to pay the performance cost than to have to move everything to a new algorithm every 20 years. What if your way reveals to be insecure as well in 20 years? Who knows what will happen in that time-frame, it's a long time in our interconnected world. What if instead of trying to find something that works forever, you embrace change and make it easy to change the algorithm instead? So when you need to change in the future (not "if"), you can easily just switch a value to change to the new one. Have solid testing created already for. Don't assume invariants that changes between the different hash functions, like length or what bytes there will be in them.
- TillE 5y agoWhat's different about encryption algorithms that make them not fundamentally "shuffling a bunch of bits"? Anyway, BLAKE is based on ChaCha.
- ogogmad 5y agoThere's this (called SWIFFT): https://en.wikipedia.org/wiki/SWIFFT#:~:text=In%20cryptography%2C%20SWIFFT%20is%20a,the%20LLL%20basis%20reduction%20algorithm https://en.wikipedia.org/wiki/SWIFFT#:~:text=In%20cryptograp.... There are also trivial constructions that exploit the difficulty of Discrete Log. But they are slow. You do have to be careful when using these hash functions, because they satisfy potentially undesirable properties like H(a + b) = H(a) + H(b), which make them unusable as random oracles. There haven't appeared any cracks in SHA2 for the nearly two decades in which it's existed. So unless it's possible to have a sudden and totally inexplicable break, we'll probably be safe for many decades hence.
- bawolff 5y agoWell i'm sure there are usecases where it matters, in general sha-256 is already really fast. Why bother with something faster?
- degenerate 5y agoThat's Internet Explorer levels of shortsightedness, my friend.
- chrisseaton 5y ago> in general sha-256 is already really fast. Why bother with something faster? Have you never sat there waiting for a hash to finish computing? I regularly do and I'm not even dealing with large data. It's very slow, and worse than that it's both very slow and also entirely sequential! (So is BLAKE2 - BLAKE3 is parallel.) Worse than that - it's an astronomical waste of energy if we could be doing the same thing in less time. I wonder how many hashes humanity runs a day?
- _zllx 5y agoI heard the problem is so prevalent that they started making custom ASIC boards for calculating SHA-256 and building big farms full of them. At least we know that each and every one of the hashes calculated were useful and necessary, right?
- chrisseaton 5y agoI don't know why you're being snarky at me? We need cryptographic hashes for many legitimate applications completely outside crypto-currencies, many of which protect critical things like national security and personal privacy.
- _zllx 5y agoSnarky is directed at the people who do proof-of-work cryptocurrency, not snarky directed at you. My bad for not putting a winky face or something.