BLAKE3 is a successor to BLAKE2 (used by wireguard for example) a really fast crypto hash function. It uses binary trees and other approaches that allow to use SIMD and multithreading.
Would a future version of the Wireguard protocol and implementations benefit from switching to BLAKE3? Enough so that it would make sense for them to make the switch either, as the only difference between now and then, or alongside other changes they may have in mind? And if it makes sense, are they planning on doing it?
It's unlikely, since part of the design of WireGuard is not to allow negotiation of primitives. They'd version the whole protocol, and BLAKE2->BLAKE3 is not a strong incentive to do that.
This is awesome. We have been using BLAKE3 in Wasmer for more than a year [1] and has been working great for us.
We were trying to find a hash function for WebAssembly files that is crypto-safe. The only alternatives that were fast enough (>1Gbps) were not crypto-safe (ahash, murmur, crc32), so BLAKE3 was the obvious choice to not sacrifice on speed while getting a cryptographic hash function.
> a highwayhash is only cryptographically strong (but not cryptographically secure)
Can you let me know what you mean by strong vs. secure? When would you use one vs. the other? I've heard both of these terms used but they seem almost interchangeable[1].
I've also heard things like "this would be suitable for encrypting a password which is stored at rest" vs. "this could be suitable for a short lived one-time key", but I don't know what the correct terminology is there.
It's weird terminology. highwayhash aims to be cryptographically secure for its problem domain. But it's designed by (afaik) non-cryptographers, has weird security claims (they gauge security from statistical tests) and hasn't (afaik) received any formal peer review; it can also be instantiated in sub-secure hash sizes. You shouldn't use it to protect secrets, beyond the kind of incident secrecy you'd ask from something like SipHash.
It would be better if people would be clear about this stuff; you see the same thing from the PCG RNG people, who say that their generator isn't a CSPRNG, but is somehow more secure than other non-CSPRNGs.
Without intending to endorse the wording, I suspect what's being communicated might be something related to the difficulty for an attacker to derail your system by cheaply predicting hashes. IIRC, the standard Java runtime HashMap implementation was susceptible to this at one point - an attacker could easily and cheaply force all values into only a few buckets.
The idea being, you might not care about actual cryptographic security but instead only the feasibility of some sort of cheap online collision attack.
I've noticed in my shells that when I do this I get the newline, so be wary of that if you are passing this hash around. I think echo -n should fix that on most platforms.
If I had a BLAKE3 implementation available in the programming language of choice, is there any reason to still prefer the SHA family over it (for integrity checks, not for password hashing, as mentioned in the readme)?
Aside from the various technical reasons others have given, I would like to say please have a look at the underlying design of SHA-3 - it’s really elegant, with so many applications beyond just hash functions. Ironically, I feel like SHA-3 should obsolete block ciphers like AES more than it obsoletes SHA-2.
> look at the underlying design of SHA-3 - it’s really elegant
Yes, I imlemented a whole pile of hash functions, and I agree wholeheartedly. Whereas md5/sha seem to be have been designed by pouring a hodgepodge of complexity into a algorithm until something indecipherable turned up sha3 is simple. It's just a small number of easily understood operations, each with a clear purpose.
Actually, it looked to me like it's been an evolution. md5 is insanely complex and the sha2 family got simpler, then then we get t sha3.
Symmetric algorithms look to be going the same way. DES is insanely complex, AES less so, and Speck in almost unbelievably simple (look at the source code on Wikipedia https://en.wikipedia.org/wiki/Speck_(cipher)). It seems to be an unfashionable viewpoint, but in my mind that simplicity makes Speck seem more worthy of trust that a lot of it's rivals.
SHA-3 is extremely slow compared to common ciphers like AES and ChaCha20. Sponge functions might someday become the building blocks of symmetric ciphers, but it's unlikely that SHA-3 will (without hardware acceleration).
For historical reasons the SHA-3 standard made extremely conservative choices with its security parameters, particularly the number of rounds. The result is that SHA-3 is slower than SHA-2 in a lot of cases, but it didn't have to be that way. The same team of cryptographers published the KangarooTwelve hash in 2016, with half the number of rounds. I think that implies that SHA-3 could've been twice as fast with no loss in security. KangarooTwelve also introduces a tree structure, which enables a lot of the same optimizations that you see in BLAKE3, and the two designs are interesting to compare. (See section 7.6 of the BLAKE3 paper.)
Well SHA-3 is a hash function, and indeed somewhat slow in software. But the team have since enormously expanded the primitives based on the same core design, with much better performance: https://keccak.team/sw_performance.html
You can also look at things like the Strobe framework, which builds essentially all of its symmetric crypto out of the SHA-3 core permutation: https://strobe.sourceforge.io/
BLAKE3 has a large state, it's a tree hash, so you need to keep the tree of hashes, which is proportional to logarithm of the message size. SHA has fixed state for any message.
Security-wise they are roughly equivalent. While SHA has had more eyes on it I doubt either construction will ever be practically broken at hash sizes like 384 or 512 bits. Someone may find an "academic break" at some point.
BLAKE3 is faster, sometimes a lot faster, on hardware without SHA instructions. On hardware with SHA instructions SHA may be faster. Same as the AES story where AES is faster than ChaCha on CPUs with dedicated hardware but slower otherwise.
I'd like to see the benchmarks, including power draw. I suspect it is similar to soft ChaCha vs hard AES. A ChaCha software implementation can achieve similar speed as the AES hardware at the cost of significantly higher power draw due to pushing the AVX units at near maximum utilization.
I benchmarked hardware AES vs software ChaCha20, and the former showed an overall performance improvement of an end to end QUIC software stack of more than 50%. The pure crypto difference is probably even higher. That's a huge gap - even thought it might totally be possible that the ChaCha20 implementation of Ring is still improvable.
As a result of that, I asked for rustls to default to AES instead of the previous ChaCha20 default [1]
Some implementations (IIRC Firefox is one of them) choose it dynamically: if hardware AES is available, AES is ordered before ChaCha20, otherwise ChaCha20 is ordered first. Last time I looked, at least for Intel the i3 didn't have hardware AES (but the i5 and i7 have it), so it was not uncommon for lower-end hardware (which needs speed the most) to have AES slower than ChaCha20.
It should be noted that chacha20 has insanely comfortable security margin. With a more accurate estimate chacha8 has a security margin similar to that of AES, and chacha20 has 2.5 times more rounds, see if it's worth the cost.
And if you're designing hardware (or on an FPGA) ChaCha (and BLAKE2/3) are actually really freakin' fast for the die area they take. IIRC ChaCha20 beats AES in hardware. It's just extremely rare (FPGA only) to find it in hardware, since there's not enough demand. I expect that to eventually change.
Probably. With a barrel shifter easily. Barrel shifters are a bit slower than wired shifts though, so for ultimate speed you'd end up with hardware shift amounts.
The advantage would be a single instruction that implemented the core of a wide range of things including BLAKE2, BLAKE3, Salsa, ChaCha, Speck, and more.
One aspect of security is also the misuse resistance. You can of course create a secure MAC with SHA256 in the HMAC configuration, but it usually takes a masters level course on cryptography to know what is Merkle-Damgård construction, and why it's design is imperfect:
You can't just do SHA256(key + message) to generate a safe MAC. With BLAKE (and all SHA3 finalists) you can do that safely.
It's true every time you make the algorithm more misuse resistant, the universe will come up with a more dunning Kruger, but despite that, it's something that can actually improve, the security is already more than adequate: Like Schneier so eloquently put it, "we're building a fence for sheep, it doesn't matter if the fence pole is a mile or two miles high".
Good point. Misuse resistance is also why I am a fan of SIV constructions for stream ciphers, since "repeat a nonce = instant death" is a footgun.
Repeating a nonce is easier than you might think if you are using threads and accessing a nonce counter non-atomically, have a bad RNG, are on an embedded platform with bad RNG seeding, have a bug that overwrites some memory used to generate nonces, or just transfer a ton of data with the same key (birthday attack). SIV makes nonce reuse fairly benign. The only consequence is that if you happen to reuse a nonce with two identical messages, an attacker could tell that you sent the same message twice. That's generally not catastrophic and statistically is far less likely than repeating a nonce with different messages. Repeating a nonce with different messages generally does nothing in SIV.
You could theoretically use SIV with no nonce, with the only consequence being that an attacker could always tell if you sent duplicate messages. Not sure why you'd do that though.
IMHO since we now have ciphers that are probably "unbreakable for the foreseeable future" (e.g. AES and ChaCha) we should probably concentrate on creating and popularizing misuse-resistant constructions as much as possible. It's good to remove footguns.
Hadn't really looked into SIV as I've only written stuff that always generates XChaCha nonces with getrandom but yeah I can totally see why the platform etc. could cause issues that lead to nonce-reuse. This was most informative post, thank you so much!
SIV is usually done with AES/GMAC constructions but you could do it with ChaChaPoly just fine.
The big downside is that it requires two passes on encrypt: one to create the MAC and derive the IV and another to encrypt. The overhead for this is small for message/packet based systems though since after pass one the data will be sitting hot in the processor's L0 cache. Decryption can be done in one pass.
A Sha256 hash is just a dump of the internal state of the function. If you know the hash, you can keep running the hash function for more data and calculate a new hash for the original data with new data appended.
One thing I was wondering about, OpenSSL 1.3 dropped support for SSL compression. Would that mean the compression function in BLAKE2 and future BLAKE3 integration couldn't be used or is this a different layer?
https://en.wikipedia.org/wiki/BLAKE_(hash_function)
The compression function in a hash function has nothing to do with the general data compression that TLS got rid of; it's a component of the hash that takes n bits and outputs less than n bits in an as unstructured manner as possible.
It won't be added to OpenSSL until it's standardized (see [1]). However there's an external provider available of somewhat dubious quality that adds support for it ([2]).
> 1.0 is not the last and final version of a product.
Of course, but if you bother to do semantic versioning, it should strive to be a stable one and not a "we are still experimenting" release.
IMHO knowing that something doesn't work, or isn't even implemented yet and will be addressed in the next release is OK for an 0.x.y release, but you shouldn't rush towards 1.0.0, already planing to release it "unfinished" and complete it later on in 1.0.1. That IMO kind of misses the point of the versioning semantics.
Big-endian ARM basically does not exist in the wild. It is very much an edge case of an edge case, and definitely not something that should be a blocker for a 1.0 release.
Imho, just having a stable API that works on x86-64 without optimizations would be enough for a 1.0 release. Having a stable API with highly optimized implementation for x86 and common ARM systems is a lot for a 1.0 release. The limitations on ARM BE could be better documented though.
Of course! But you need a well defined feature set you want to have for 1.0 and stick to that. The scope of that is up to the people who run the project, I did not make any demands what this specific software should include in their 1.0 release. I did not say that it needs to be perfect, include all bells and whistles imaginable, all possible CPU optimizations and smell nice in order to merit an 1.0 release. What I'm saying is, that you should make an effort to ensure that the implementation of this feature set is somewhat stable.
So rather to the contrary, I would also suggest to keep the scope of a 1.0 release smaller than that, just like you suggested:
> Imho, just having a stable API that works on x86-64 without optimizations would be enough for a 1.0 release.
Releasing an un-optimized reference implementation as 1.0, or maybe only one optimized code path for x86_64 would IMO be perfectly fine. If they decide they really want optimizations for all kinds of CPUs in the 1.0 release, also fine with me. What the scope for 1.0 should or should not be is their choice. And it's also completely besides my point.
I'm specifically arguing against doing what pornel seems to imply: My point is, you shouldn't release an implementation you know misbehaves in some cases, because "we can fix it later".
I'm a fan of semantic versioning. And I firmly believe that in addition to API & ABI stability, for a major version release, some effort should be taken to iron out the implementation of that API as well. Of course bugs can, and will, crop up later and can be fixed with a patch level release, but IMO you shouldn't rush towards a 1.0 release with a backlog of known bugs for the next release. That's what I meant with "kind of misses the point of the versioning semantics".
What it being 1.0 means is that the API is stable. There might still be bugs in the implementation (no software is perfect), but once it's reached 1.0, it's hoped that the API is good enough and will not have to change for quite some time. If you look at these release notes for 1.0.0, they were all API changes.
This is a good point, and I'd like to fix it. When I look for endianness macros, it doesn't seem like there's a common standard. Is there an approach you'd recommend?
It seems that you're right - ISO C doesn't have standard macros for this. That said, since this code is ARM-specific, and you are already leveraging the ACLE header <arm_neon.h>, I think that a negative test for __ARM_BIG_ENDIAN is appropriate.
TMS570 dual-lockstep automotive safety controllers are hardwired to be big-endian.
Their close cousins the RM57 line look like nearly identical parts that are little-endian. I believe, but cannot prove, that the only difference in silicon is a factory one-time-programmable setting (fuse).
"Why would anyone want to build a BE machine?" In this case, they are trying to gain market-share from big-endian POWER microcontrollers.
It used to be much more common than it is nowadays; commonality between desktop systems used for development and production has slowly got rid of it. I know certain TVs and set-top boxes at least used to use big-endian, but mostly them long-ago migrated to little-endian nowadays.
So what are the next steps for cryptographic hash functions? Is it going to just be "make even faster" ? Or are we chasing new properties, or stronger guarantees (or hopes?) of existing properties?
Variants of "make even faster" (including "making keys smaller" or "allow to run on more limited hardware") is most of what drives new core cryptographic primitives. There's a tweet from one of the BLAKE authors (@veorq) saying what I think a bunch of cryptography engineers believe, that it's unlikely that SHA2 will ever be directly broken.
There are security improvements in new primitives, often based on a notion of "misuse-resistance". SHA2 isn't broken; it remains quite strong. But it's a classic Merkle Damgard design, which means you can take the output of SHA2 and hash more data into it, which breaks simple keyed hash constructions like H(k, m) (this is why we have HMAC!). SHA3 and other modern hashes don't have this property; you can safely build simple keyed hash constructions out of them. You can see the same thing with AEADs (the SIVs vs. GCM) and with curves (Curve25519, for instance, where keys are --- don't @ me --- just simple random byte strings).
There is also more/different functionality (e.g., designing a permutation or a tweakable blockcipher instead of a plain blockcipher, or a hash based on those), or better analyzability---making primitives that are simpler to "prove" (or make an argument for) secure against some classes of attacks.
And these days there are also the primitives purposefully designed to run in blockchain....whatever it is, using large GF(p) or GF(2^n) field operations as components. This mostly falls under the "more limited hardware" umbrella.
Yes, though in a MAC construction, you'd just use HMAC anyways. People still use HMAC with SHA3, even though it's unnecessary, and I don't see anything wrong with that either.
An associative / non-commutative hash function over lists. This would mean that the hash of a list, H(list1), could be "concatenated" with another hash, H(list2), to find the hash of the concatenation and be equivalent to H(list1+list2). I think such a construction could be huge for cryptographic verification of data in data structures while avoiding baking in incidental details about the data structure itself.
I hesitate to link to it because I already know of a potential attack, but I played around with an implementation that does this with matrix multiplication over galois field elements of reinterpreted hash digests [1]. I mean, the associative / non-commutative part works nicely, but I expect that factoring the matrix is possible which makes it utterly useless as a cryptographic primitive [2]. "don't roll your own crypto" would apply, but I'm obviously not using such an academic exercise in production.
This is super interesting, thanks! I just wrote a related note in http://canonical.org/~kragen/dernocua.git in text/hash-consing-ropes.md, linking to those two notes; my interest is using it for hash consing, like symbol interning but for all your strings.
Something that might interest you even more is the related questions by Jason Hise that I linked to. They explored using 8x8 bit-element matrices as an associative hash of a string and apparently it works pretty good as a hash for string keys in a hashmap. Both questions, answers, and comments all have some interesting context, and Jason answers some questions I had about their usage in comments on the second question.
It's a pretty interesting idea! If you were implementing it in hardware, it would probably be faster. In software, I suspect that my suggestion of composition of linear forms in the ring ℤ/nℤ would be more efficient.
Not an expert, but it would be nice to provide security proofs. Not a must-have thing, perhaps, but certainly nice to have. One such example of a "provably secure" hash function is this one: https://en.wikipedia.org/wiki/SWIFFT#:~:text=In%20cryptograp.... Unfortunately, it's quite slow, and can't be used as a "random oracle".
A lot of security proofs assume the random oracle model (but not for hash functions though, which are supposed to implement the "random oracle"). Strictly speaking, the model is incorrect, because a hash function is never a random oracle. I don't know if a suitable substitute has been found.
Could someone explain how these versions in hash algorithms work please? As I understand it version 0.3.7 from last year would produce the same hashes as version 1.0, so is the algorithm itself finished long ago and it's just the tooling that got updated over time?
Platform support is one aspect, another is re-implementing the algorithm in constant time to prevent side channel leaks. Also perhaps the code was edited to be stable under different fuzzers. Note: this is all speculation and generalization; I haven't looked at BLAKE3 commits at all.
It's not the version of the BLAKE3 hash algorithm (which has been finished a long time ago and won't change anymore), it's the version of the reference implementation. The changes from 0.3.7 were just fixing a build issue on MSVC (this was release 0.3.8), and breaking changes to the API of the reference implementation, mostly removing parts of the API of the reference implementation which weren't stable enough for a 1.0 release.
So `ArrayVec::<T, const CAPACITY: usize>` is an ArrayVec of items of type T, with capacity CAPACITY (of type usize, think size_t). An ArrayVec is a vector backed by a fixed-size array. Basically an array with convenience methods on it.[1]
In this case, T is `&[u8; CHUNK_LEN]` and `CAPACITY` is `NUM_INPUTS`. `&[u8; CHUNK_LEN]` is roughly equivalent to a `uint8_t* array[CHUNK_LEN]`.
So to simplify even more it's a fixed-size vector of byte arrays. The details of why it's not quite equivalent to that C code (how Rust checks the safety) are beyond the scope of this comment.
In Rust, <> are used for type arguments. E.g. if you make a function with a generic type, it would be `fn my_func<T>(arg1: T) { ... }`
Now, what we have here is commonly referred to as the Turbo Fish[0] operator (the `::<>` syntax). In this case it's there to help let the compiler know which concrete type you want to create your new `ArrayVec` with :)
It is the opening of a generic type parameter. In this case ArrayVec[1] takes two, a type T for the element type and a const for the maximum size of the ArrayVec. The use of ::<> is affectionately known as "the turbofish" and is a way to give the compiler type information when it can't infer it.
Foo<T> supports more types, often limited with certain traits they must support.
Here it's passing the actual type on instantiation, in that case there are two types: an u8 slice and a number of inputs, just guestimating the latter as I did not check the original definition in the source.
<> is used in Rust similar to how C++ uses them in templates.
ArrayVec::new() is a generic function that takes two generic arguments: a type (&[u8; CHUNK_LEN]) and a value (NUM_INPUTS). So ArrayVec is the structure, <...> are the generic arguments (I replaced stuff with ellipses for brevity), and new() is the function call. :: is used as a "path" separator to syntactically differentiate between all these different parts.
That looks like a template instantiation to me. It's "<&[u8; CHUNK_LEN], NUM_INPUTS>" So the angle brackets are wrapping two arguments to the template.
So SHA224 and SHA384? They're not exactly common. SHA256 is pretty much the standard and SHA512 is usually used for hashing larger files due to the larger block size and thus faster speed. I don't think I've ever seen 224/384 used anywhere.
Importantly SHA-512/256 does not mean "Either of these two different functions" but instead another function, which is similar to (but slightly different from) performing SHA-512 and then throwing away all but 256 bits.
This prevents length extension because you've thrown away 256 bits the attacker needs to perform their attack.
SHA224, SHA384, and SHA512/256 (yes, that's NOT the same as SHA512/SHA256, it's SHA512 truncated to 256 bits) are the truncated versions of SHA2. Rarely used. Confusingly named (in the case of SHA512/256).
For processors that have hardware SHA256 (AMD Zen, most 64-bit ARM, some Intel models), SHA224 can be computed with the same instructions.
For 64-bit CPUs without hardware SHA256, SHA512 & SHA384 are the fastest and they have identical speed (as only the values of some constants differ, while the algorithm is the same).
Most libraries and hash utilities implement all these variants, so any variant can be chosen without problems.
xxHash is not cryptographic, whereas BLAKE3 is. You can use the former for things such as file integrity from errors checking, and the latter for file integrity from malicious intent checking. Or, one is for the file system and the other is for the internet. You should use something altogether slower like bcrypt for passwords though, because then you don't want to have speed in case someone has a copy of your database with a million passwords and tries to dictionary attack those million.
I like to check smhasher for comparison of many hash implementations: https://github.com/rurban/smhasher. It’s a bit clunky to search for the exact items you want to compare, but there’s lots of data and a good summary under the table.
Oh. Well you said "in there too now" so I thought you were saying it was like xxhash in being insecure and fast. Even if that wasn't your intent, I wanted to make it clear to other people.
> Could you please expand upon what the main use cases are for non-cryptographic hashes?
Very fast hashes are good for hash maps, or even critical for them. That covers a huge amount of uses. And judging by the list on xxhash's website, a bunch of file transfer programs use it as well as bloom filter implementations, along with the databases that are probably using it for various maps.
