BLAKE3 1.0
github.com
github.com
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.
But BLAKE3 does seem to offer the best compromise when a cryptographically secure hash is required.
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 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.
The idea being, you might not care about actual cryptographic security but instead only the feasibility of some sort of cheap online collision attack.
$ echo hi | b3sum --no-names
0b8b60248fad7ac6dfac221b7e01a8b91c772421a15b387dd1fb2d6a94aee438I just tried your "hi" against https://connor4312.github.io/blake3/index.html
and get
hi/n - 0b8b60248fad7ac6dfac221b7e01a8b91c772421a15b387dd1fb2d6a94aee438
hi - 85052e9aab1b67b6622d94a08441b09fd5b7aca61ee360416d70de5da67d86ca
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.
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".
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.
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.
Can you explain this?
h = SHA-256(k || m1)
SHA-256(k || m1 || m2) = F(h, m2)
As a result of that, I asked for rustls to default to AES instead of the previous ChaCha20 default [1]
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/
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.
Mind you,
https://github.com/BLAKE3-team/BLAKE3/blob/b404c851c284ed01f...
I peeked at the reference impl (380 lines of safe Rust) and found this. It has a 1,728-byte array for tree state, which is enough for 2 ^ 64 bytes.
So in practice it's also fixed.
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)
[1] https://github.com/openssl/openssl/issues/11613#issuecomment...
a comment in blake3_neon.c: // TODO: This is probably incorrect for big-endian ARM. How should that work?
Netbsd releases big endian versions that work on various ARM boards. Here's an announcement showing it works on an Rpi3 and below, for example: https://mail-index.netbsd.org/port-arm/2020/12/03/msg007117....
They said at the time that it's not yet working on the Rpi4 because of issues getting BE mode and UEFI to work together.
I don't know that it's used often, but it does exist.
Or perhaps very slightly more efficient networking code, since big endian is the default order for many operations there?
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.
Rust ecosystem is already overthinking 1.0 releases, which results in tons of crates having 0.x versions while being depended on as de-facto stable.
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.
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".
The algorithm itself hasn't changed, which is great!
https://developer.arm.com/documentation/101028/0012/5--Featu...
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.
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).
IIRC, just simple random byte strings with a couple of specific bits forced to 0 and another couple of specific bits forced to 1.
Isn't this problem fixed by simply dropping some bits from the end? See SHA-224 for instance.
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.
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.
[1]: https://blog.infogulch.com/2021/07/15/Merklist-GF.html
[2]: https://math.stackexchange.com/questions/4200988/using-rando...
Using 8x8 Binary Matrices as a hash - https://math.stackexchange.com/questions/1902462/using-8x8-b...
Finding Prime Binary Matrices - https://math.stackexchange.com/questions/1914853/finding-pri...
let mut chunks = ArrayVec::<&[u8; CHUNK_LEN], NUM_INPUTS>::new();
I probably should not comment to everyone one-by-one, so thank you all for the answers!
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 :)
[0]: https://doc.rust-lang.org/1.30.0/book/first-edition/generics...
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.
See https://doc.rust-lang.org/book/ch10-01-syntax.html for a better explanation.
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.
1. https://docs.rs/arrayvec/0.7.1/arrayvec/struct.ArrayVec.html
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.
[1] https://docs.rs/arrayvec/0.7.1/arrayvec/struct.ArrayVec.html
Aren't some variants of SHA-2 secure against length extension (like SHA512/256)?
This prevents length extension because you've thrown away 256 bits the attacker needs to perform their attack.
On CPUs with hardware SHA256 (AMD Zen, 64-bit ARM, some recent Intel CPUs), SHA256 is faster.
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.
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.