Linux Kernel RNG is now Blake2 instead of SHA1 and 3x faster
twitter.com
twitter.com
The @zx2c4 Filippo is referring to is Jason Donenfeld, of WireGuard fame. It was news to me that he'd taken over the Linux kernel random driver! But it's welcome news indeed.
And all this is before the actual winner of SHA3 comes into the picture. With parameters as specified by SHA3 it's a lot slower than BLAKE3, but it is my understanding (IANAC) that
(1) The SHA3 security margin can safely be decreased, as NIST set the security requirements too high. This is one of the reasons for the speed difference.
(2) The sponge-based crypto popularized by Keccak (the SHA3 winner) is much more amenable to cryptanalysis than the more traditional crypto such as the functions in the Blake family. This means that Blake's security would be less sure even had it received the same level of scrutiny. But AFAIK Blake received much less scrutiny than Keccak, or even other sponge-based functions, such as the ones in the NIST Lightweight Crypto competition.
B) blake3, afaik, is not yet as thoroughly vetted as b2.
C) I think some of the hype around b3 is deserved. It's crazy fast. If you don't care about crypto at all (e.g. file dedup), it's absolutely phenomenal. But the main downside of B3 right now is just novelty. Cryto algos are like fine wines.
D) I don't know enough about Keccak vs Blake, but just because Blake2 has received less scrutiny, doesn't mean it's insufficient. I'm sure there are tradeoffs that the kernel editors have chosen.
E: here's a link to some discussion:
https://crypto.stackexchange.com/questions/31674/what-advant...
On other platforms, where people haven't written such (or, IME, even on ARM when using their NEON version), it's nothing to write home about.
While the sponge framework is popular, it's rather inflexible, e.g. its sequential structure permits limited parallelism. There are more general sound hashing frameworks that still offer provable security, such as this one which blake3's analysis is based on: https://www.cs.ru.nl/~bmennink/pubs/18fsenew.pdf
This is subjective, but in my mind the question of "how important is it for crypto to be fast?" is closely related to the question of "how many crypto options should we give people?" Like, should we design "slower, maximum-security, military-grade crypto for top secret material" and "faster, cheaper, less secure crypto for less sensitive stuff"?
I think we've all learned our lesson over the past few decades of watching real applications try to deploy crypto: Options are dangerous. This stuff is complicated enough as it is, and asking callers to choose between a bunch of alphabet soup standards that they don't understand makes things substantially worse. (AES-GCM or AES-ECB?!) It's important to be able to give clear, simple advice: Just use X.
So while it's true that most applications aren't bottlenecked by cryptography, pushing the margins of "most" benefits everyone, by putting more weight behind common standards that we know are safe.
[1] SHA-512/256 protects us from key extension attacks, but has much less deployment than SHA-2. We can mandate using SHA-2-256 in HMAC mode when we use it with a secret the attacker does not know.
[2] https://csrc.nist.gov/projects/post-quantum-cryptography/wor...
[3] SHA-2 is called a “hash”, as is “SipHash”, but they are different use cases. SHA-2 is generally for having a long hash where generally both the user and attacker know how to make a given string have a given hash. “SipHash” is to be used for the compression function for a hash table [4] where performance is critical, the hash is shorter, but it is protected by a secret key.
[4] https://en.wikipedia.org/wiki/Hash_function
[5] If you ask me what my favorite cryptographic hash and stream cipher is, I would say RadioGatún[32]. It has roughly BLAKE2’s speed with the added benefit of enhanced hardware performance. It was the only Extendable-Output Function (XOF) which existed back in 2007—the last time I revised which crypto primitives my own open-source software uses—and remains unbroken as we enter 2022. It know it’s hardly mainstream, but it is Keccak’s direct predecessor, and it has been analyzed by world renowned cryptographers.
But, it hasn’t been standardized by NIST and consequently doesn’t have a FIPS standard. The only non-standard algorithm I put on that “use only this crypto” list is SipHash, simply because no one has ever bothered to make a FIPS standard for a fast and secure keyed hash bucket chooser.
I also like how BLAKE3 just said “we are only using 32-bit operations”, because there’s a lot of embedded places where 64-bit really isn’t an option, and because SIMD ISAs have fast 32-bit operation support on 64-bit architectures.
People are very opinioned about cryptographic algorithms but more often than not they tend to be kinda clueless (not saying that this is the case here).
ECC: There was a lot of controversy because one of the FIPS (Edit: NIST) curves apparently has a back door (Edit, it was Dual_EC_DRBG), so just stick with RSA until we have standardized post-quantum public key cryptography.
AES192: If I had to choose one key size, AES192 comes off as the best compromise between speed and security; larger keys result in more AES rounds. Also: AES-256 is weaker with related key attacks than AES-192, and AES-192 is approved for Top Secret (not just Secret) information, while AES-128 isn’t.
SHA512: It uses 64-bit addition operations, which is less than optimal on certain low end embedded processors. Same reason BLAKE3 dropped the 64-bit variant BLAKE and BLAKE2 have; but I will let @oconnor663 speak on why they dropped the 64-bit version.
For a block cipher mode of operation, I would probably choose GCM, since it looks secure and is approved over at https://csrc.nist.gov/projects/block-cipher-techniques/bcm (ECB is still approved, strangely enough).
GSM instead of GCM was a typo, and I believe it’s against the Ycombinator guidelines to make a correction like that a personal attack, and I believe we’re getting really close to crossing that line, so let’s just calm down and chill out.
This isn’t in any way a personal attack—I’m familiar with and have a lot of respect for your security auditing skills—but just an observation things are getting kind of heated here and it serves no one’s interests to have an out of control flame war.
It is very rational to follow their guidelines, while at the same time being wary of backdoored products. You could have done a lot worse than picking AES during the past two decades.
Even if it’s a large document. Sweet32 really only works for CFB mode; while there are Sweet32-based attacks against CTR mode, they are a lot more difficult and often times not practical. I’m, of course, not advocating using 3DES, Blowfish, IDEA, or any other 64-bit block size cipher in a new system in 2022, but even ancient 3DES documents would still be secure today in many use cases.
"If I had to choose one key size, AES192 comes off as the best compromise between speed and security"
Did you test the speed differences? Especially when aesni is involved.
If I were to make a short list of approved algorithms, I stick with FIPS, not because they are necessarily the best, but because they are standardized. Non-standard algorithms have their place—I use RadioGatún[32], of all things, for a cryptographic secure PRNG as well as for a cryptographic strong password generator—but not in a corporate context of making a “use only these algorithms” list so people don’t make novice mistakes like using MD5 to encrypt passwords or a block counter in ECB mode.
I mean, yeah, DNScurve would had been better than the DNS-over-HTTPS which won instead, but standards sometimes win simply because the standardization process for what won is perceived as being more cooperative.
As an aside, I actually like DJB’s software. I used Qmail and djbdns back in the day, and in fact I currently maintain a branch of djbdns which is, as far as I know, the only djbdns fork which is actively maintained here in the 2020s: https://github.com/samboy/ndjbdns
[1] https://csrc.nist.gov/News/2017/Transition-Plans-for-Key-Est...
Let’s just breathe in deeply and calm down. This is not a personal attack directed at anyone here but merely a note that emotions seem to be flairing up and I don’t think it serves anyone’s interests for this to become a Reddit or Twitter style flame war.
In cases where people know the risks, have read Applied Cryptography cover to cover, know why not to use MD5 or ECB in production code, etc. DJB algorithms are just fine. That’s the case with Wireshark and that’s the case with TLS.
What I am saying is this: In a corporate context, where you have programmers who would otherwise make novice mistakes like use simple MD5 to encrypt passwords—I’ve seen that in the real world, for the record—I would put mainly FIPS approved algorithms on a short list.
[1] https://github.com/samboy/lunacy
[2] https://github.com/samboy/ndjbdns
[3] Solar Designer did use MD5 to encrypt passwords for Wordpress about 15 years ago, but he did it in a way to minimize security risks (still secure today, though Argon2 or bcrypt are better), but that was in an era when the only cryptographic primitive PHP had was the now-broken MD5.
It's OK to not really know all of this stuff. Other people can know it for you. The question mark comes in really handy in situations like this. It's not a challenge where you start with the distinction between FIPS and NIST and then axiomatically derive all of modern cryptography.
Pretty sure they were just asking a small clarifying question.
NSA CNSA says to use 256:
* https://en.wikipedia.org/wiki/Commercial_National_Security_A...
* https://www.keylength.com/en/6/
> […] so just stick with RSA until we have standardized post-quantum public key cryptography.
The folks that will approve the post-quantum stuff were also the ones the approved the 'pre-quantum' stuff, including the supposedly worrisome ECC standards. If you're not going to trust them now, why should you trust them in the future?
There’s a difference between something being developed by a third party and rubber stamped and made a FIPS by NIST (e.g. Rijndael which became AES or Keccak which became SHA-3) and something developed internally by NIST. The post quantum stuff is being developed outside of NIST, so there isn’t really a place for NIST/NSA to put a backdoor like they did with Dual_EC_DRBG.
SHA-2 was in fact developed behind closed doors by NIST/NSA, but since the magic constants are square roots and cube roots of primes, and since it’s been around and analyzed for over two decades, it’s extremely unlikely to have a backdoor.
DES was developed by a third party (IBM, IIRC) and it was altered by NIST/NSA before its final form was approved. Turns out it was altered to maker it stronger against an attack no one publicly knew about at the time.
Things could potentially be approved that are mostly strong, except against an attack(s) that are only known in classified circles.
The most important thing to us was that there should be just one version. It's simpler for everyone. But we actually did go back and forth about which version it would be, 64-bit or 32-bit. "PCs and servers will all be 64-bit for the foreseeable future" was definitely a big point in favor of choosing 64-bit words. Section 7.2 of our paper goes into detail about why we went with 32-bit anyway.
The author of the comment you're replying to certainly knows what SipHash is.
If you make cryptography "fast enough" to be used by default and without much worry than you remove the need to make this decision.
This use case is a perfect example. If you make the kernel RNG fast enough that people just use it instead of trying to make their own decision about what algorithm to use you end up with software that is more secure overall.
Plus since the kernel RNG isn't specified to use a specific algorithm so it could potentially be tuned based on your paranoia level and patched if the current algorithms are found to be insecure. If it is "too slow" less software use it and these features will be less useful.
Keccak (SHA-3) is actually a good deal faster than BLAKE(1) in hardware. That’s the reason why they chose it: It has acceptable performance in software, and very good performance in hardware.
KangarooTwelve / MarsupilamiFourteen are Keccak variants with fewer rounds; they should smoke BLAKE2 and probably even BLAKE3 in dedicated hardware. Also, they have tree hashing modes of operation like the later BLAKE developers.
The BLAKE family is best in situations where you want the best possible software performance; indeed, there are cases where you do not want hardware to outperform software (e.g. key derivation functions) where some Salsa20/ChaCha20/BLAKE variant makes the most sense. The Keccak family is when one already has dedicated hardware instructions (e.g. ARM already has a hardware level Keccak engine; Intel is dragging their feet but it is only a matter of time) or is willing to trade software performance for more hardware performance.
Keccak code is here: https://github.com/XKCP/XKCP
That's certainly possible, but there are subtleties to watch out for. To really take advantage of the tree structure in K12, you need a vectorized implementation of the Keccak permutation. For comparison, there are vectorized implementations of the AES block cipher, and these are very useful for optimizing AES-CTR. This ends up being one of the strengths of CTR mode compared to some other modes like CBC, which can't process multiple blocks in parallel, at least not for a single input.
So one subtlety we have to think about, is that the sponge construction inside SHA-3 looks more like CBC mode than like CTR mode. The blocks form a chain. And that means that a vectorized implementation of Keccak can't benefit SHA-3 itself, again at least not for hashing a single input. So if this is going to be provided in hardware, it will have to be specifically with other constructions like K12 in mind. That could happen, but it might be harder to justify the cost in chip area. (At this point I'm out of my depth. I have no idea what Intel or ARM are planning. Or maybe vectorized hardware implementations of Keccak already exist and I'm just writing nonsense.)
Performance has nothing to do with whether a hash function is "cryptographic"
> I know that BLAKE received some scrutiny in this regard
BLAKE was one of the most, if not _the_ most, analyzed SHA3 entries.
"Keccak received a significant amount of cryptanalysis, although not quite the depth of analysis applied to BLAKE, Grøstl, or Skein"
https://nvlpubs.nist.gov/nistpubs/ir/2012/NIST.IR.7896.pdf
> making the claims to security less and less sensible.
BLAKE2/3 are not completely new algorithms. They fine tune features from the previous version to be more lightweight while still remaining cryptographically sound
> The SHA3 security margin can safely be decreased, as NIST set the security requirements too high. This is one of the reasons for the speed difference.
BLAKE and Keccak have roughly equal security margins, which is one reason why BLAKE2/3 can still be secure while being faster than BLAKE.
> This means that Blake's security would be less sure even had it received the same level of scrutiny.
So since it arguably received more, does that balance things out?
Addition being slower in hardware and much more expensive to mask against side channels is a serious argument against ARX constructions, but that isn't really relevant here
Change to BLAKE2s:
> This also has the advantage of supplying 16 bytes at a time rather than SHA1's 10 bytes, which, in addition to having a faster compression function to begin with, means faster extraction in general. On an Intel i7-11850H, this commit makes initial seeding around 131% faster.
RDRAND call removal:
> Removing the call there improves performance on an i7-11850H by 370%. In other words, the vast majority of the work done by extract_crng() prior to this commit was devoted to fetching 32 bits of RDRAND.
Most of the performance metrics people cite when discussing hash functions are for large messages. For small message sizes hash initialization and finalization costs tend to dominate, and costs one might otherwise ignore, such as function calls, can become noteworthy.
To quote Wikipedia:
>BLAKE2 removes addition of constants to message words from BLAKE round function, changes two rotation constants, simplifies padding, adds parameter block that is XOR'ed with initialization vectors, and reduces the number of rounds from 16 to 12 for BLAKE2b (successor of BLAKE-512), and from 14 to 10 for BLAKE2s (successor of BLAKE-256).
https://en.wikipedia.org/wiki/BLAKE_(hash_function)#BLAKE2
Reducing the rounds by 4 might raise eyebrows wrt security, but Aumasson's 'Too Much Crypto' discusses BLAKE vs BLAKE2 among other things: https://eprint.iacr.org/2019/1492.pdf
Why kernel devs didn't go with BLAKE3, I can't say.
Maybe people just liked it better that way?
It also seems to be almost as fast according to the BLAKE3 specs PDF (page 11).
https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blak...
but it just BLAKE2, BLAKE3 got a nope
SHA1's a long time gone, that crypto's a slowpoke
Why did BLAKE3 and SHA1 get the works?
That's nobody's business, even Turks!
It would only result in small incremental perf improvement due to reduced number of rounds (10 to 7).
Majority of Blake3's perf benefit manifests from merkle-tree structure and SIMD processing of multiple input streams at the same time.
To add to this: BLAKE2 is derived from BLAKE only, whereas BLAKE3 is derived from Bao AND BLAKE2.
> Why kernel devs didn't go with BLAKE3, I can't say.
I think tptacek has it right: this thing is used very infrequently (period 300 seconds) and blake2 was already in the kernel, so they just reused it. It’s adequately fast, even if blake3 would be marginally faster.
To sum up: BLAKE3 has no advantages over BLAKE2 when it comes to the Linux kernel[1], plus BLAKE2 is already in the kernel (with tests and everything), while BLAKE3 is not (at all). That, and BLAKE3 is still fairly new.
[1] It is faster than BLAKE2 due to parallelism, which is not suitable for the Linux kernel; you want to restrict computation to a single thread instead of making all the cores busy. FWIW, the C reference implementation is not multi-threaded either.
• Use something FIPS approved and tried and true (RSA, SHA-256, AES in GCM, maybe a NIST/FIPS curve, although Google “Dual_EC_DRBG” first, etc.)
• Use a cryptographic primitive developed by Daniel J. Bernstein (Curve25519—which, yes, is NIST if maybe not FIPS approved, [1] ChaCha20 and its derivative BLAKE2, etc.)
These are two camps, and there is some tension between the two camps (as can be seen elsewhere in this discussion) about which approach is better, with very heated emotions. While heated, as someone who remembers the BIND-vs-djbdns and Sendmail-vs-Qmail flame wars of 20 years ago all too well, [2] I find an old fashioned to-DJB-or-not-to-DJB heated discussion a refreshing blast from the past compared to the kind of toxic cancel culture, doxxing, and hideous political attacks dominating social media here in the 2020s.
For a brand new project using crypto, I would use libsodium, which is firmly in the DJB school of thought w.r.t. cryptographic algorithms used, simply because, while newer, it doesn’t have the security history OpenSSL has had, and looks to be quite secure and actively maintained by multiple developers.
[1] https://csrc.nist.gov/News/2017/Transition-Plans-for-Key-Est...
[2] I used Qmail and djbdns during that era before transitioning to my own MaraDNS. I only made MaraDNS because of the concerns about djbdns’ then-not-open-source license and the lack of open source diversity w.r.t. DNS servers back then. All moot, now that Qmail/djbdns are public domain, both NSD/Unbound and KnotDNS have come out, and Postfix has become the most common non-Sendmail email daemon. Actually, w.r.t. email, I use an online service here in the 2020s (mxroute), because the headaches of bypassing spam filters are now such it’s best left to someone devoted to just that one problem.
[3] My preferences tend to win the NIST standardization workshops. I liked Rijndael the most during the AES process because it, unlike the others, has a variable block size, so can be used for stuff like AEShash-256. I liked Keccak the most during the SHA-3 process because it was the only unbroken extensible output function (XOF) which ran decently on 32-bit hardware; the only other unbroken XOF, Skein, was pretty much 64-bit only, and BLAKE didn’t have an XOF mode at the time. I still wish BLAKE had a sponge-style “rehash to generate more random bits” XOF mode to make fast forwarding its XOF computationally infeasible.
I'm glad we're on Blake2 and seeing the benefits, but why not go straight to Blake3?
What are the differences and why do they matter in this instance?
Inside the kernel and especially in something running continuously like the RNG, you do not want to make all the cores busy without any reason, so the hash computation should be restricted to 1 thread.
In that case, BLAKE3 does not have any important advantages.
When restricted to a single-thread, BLAKE3 is slower than hash algorithms that have hardware support on the CPU, e.g. SHA-256 on most recent CPUs. (But the Linux kernel must support many older CPUs without hardware for hash algorithms, so BLAKE2 is a better choice).
In comparison with the hardware instructions for SHA-2 or SHA-3, on those CPUs which have them, BLAKE3 is not faster, because those instructions also use the same SIMD registers, processing the same number of bits per operation.
I use every day BLAKE3, for file checksumming. For this application, on my Zen 3 with hardware SHA-2, BLAKE3 greatly outperforms everything else, but only due to multithreading.
On older CPUs, without SIMD SHA instructions, you are right that BLAKE3 can be faster than other algorithms even in single-thread, by exploiting the parallelism of the BLAKE3 algorithm with a SIMD implementation.
For other hashes, SIMD may not accelerate the computation of a single hash, but when you need to compute multiple hashes you can interleave their computations and obtain similar speedups with SIMD instructions.
On the other hand, support for SHA-256 and for SHA1 (still useful for non-secure applications) is widespread, in almost all 64-bit ARM CPUs, in all AMD Zen and in some of the Intel CPUs, e.g. Apollo Lake, Gemini Lake, Jasper Lake/Elkhart Lake, Alder Lake, Tiger Lake and Ice Lake.
If the encrypted data is indistinguishable from white noise, then the CSPRNG you built on top of it can also be made indistinguishable.
https://blog.filippo.io/the-ecb-penguin/
Low entropy means predictability in the input versus the output. Properly encrypted data has high entropy, which is why you can’t compress it after encryption. Random number generators need to be high entropy, which is where the idea of CSPRNGs comes from.
The cryptanalysis of Meow Hash[1] is instructive, since it's a weak hash and actually vulnerable in full.
There's also a good Differential propagation analysis of Keccak[1] paper, using a reduced-round Keccak.
There's also Rotational cryptanalysis. Here's a paper on Keccak uses that technique.[3] It was first formally defined by Khovratovich and Nikolić.[4]
[1] https://peter.website/meow-hash-cryptanalysis
[2] https://eprint.iacr.org/2012/163.pdf
[3] https://eprint.iacr.org/2012/546.pdf
[4] https://www.iacr.org/archive/fse2010/61470339/61470339.pdf
In essence hash functions are frequently used as Pseudo Random Functions as hash functions are PRFs with input compression.
Cryptographically speaking, the problem of taking a small secret and extracting a very large number of cryptographically unpredictable bytes is pretty fundamental to the whole project --- you know, of, like, cryptography. But for the fact that you'd like to be able to theoretically recover from a bug that discloses your random state (your "key"), you wouldn't really need more than a "seed"'s worth of entropy to run the CSPRNG indefinitely.
Since then, I've used the AES-CTR trick for non-critical random generators for many user space fuzz test harnesses, and it's helped speed them up while also being stronger than a PRNG, without a repeating period.
1. There might be more than one source. In that case, it's natural to want the output to be secure as long as any of the inputs are secure. For that, you need some way to securely mix two sources of randomness together, and hash functions are good at that.
2. Truly random numbers coming from lava lamps or thermometers or whatever aren't necessarily uniformly random. They might be, say, 1/3 zeros and 2/3 ones. Who knows. That's still useful randomness, but callers want uniformly random bytes, so again we reach for some sort of pseudorandom mixer like a hash function. In this case I think this step is called "whitening".
A responsible approach to crypto should be quite shy. It might drop it's drawers and bare all (source code) but no more. It might show some ankle towards some beefy hardware but only when escorted.
A software crypto thingie cannot and should not assume that hardware is trustworthy. However, you can stir some randomness from an untrustworthy source into your entropy pool and not find your knickers around your ankles, if you are careful.
Feel free to present your credentials.
Even with paravirtualization as an option I feel like many users of VMs would opt for the advantages of full virtualization.
1. The kernel has access to unpredictable events that make good key fodder for the CSPRNG itself, which would be more annoying and less efficient to percolate into userland.
2. The kernel can assure all the processes on the device that they're getting random bits from a known source of unpredictable bits, and refuse to deliver those bits if its state hasn't been sufficiently populated; this has been a recurring source of systems vulnerabilities in programs with userland CSPRNGs.
To that, add the convenience factor of always knowing how to get random bits and not having to set up userland dependencies and ensure they're started in the right order &c.
You should generally use your kernel's CSPRNG in preference to other ones, and break that rule of thumb only if you know exactly what you're doing.
getrandom was motivated by the fact that using device files has many failure modes.
It's a good question!
Assigning free ports to applications that listen on a socket is also random, not sure why, feels like it could be sequential unless you want to deliberately obscure what ports are being used.
2. Userspace programs cannot be made as robust to accidental or malicious failures. Even if you have a userspace RNG daemon that randomly open files or sockets to extract entropy, what happens if that daemon crashes? Or it fails to open a file or socket? Or an exploit gets an RCE into the daemon to read privileged files? By contrast, the kernel is already performing all these operations for userspace processes, so it might as well measure those things and stick the results into its own entropy pool to hand out to other processes on request.
The kernel also has the hardware access that is used as entropy sources. If the RNG was in user space the kernel would have to provide some way of securely exporting that entropy to user space. It is simpler and more secure to just export the end result of random numbers through a simple API.
All modern OS have made the same decision of having a kernel-based CSRNG, for the same reasons.
I think python standard library/several of data science library rngs are platform independent.
PRNGs (Pseudo Random Number Generators) are predictable. CSPRNGs (Cryptographically Secure Pseudo Random Number Generators) aren't (if they're working). HWRNGs (Hardware Random Number Generators) that aren't debiased via a CSPRNG or similar produce nonuniform output (not suitable for cryptography or most other uses directly). TRNGs (True Random Number Generators) might not exist in this universe (deterministic interpretations of quantum mechanics are consistent with observation), it's safer to assume they don't and avoid the term entirely.
The main concern was security, so it makes sense to use BLAKE2, which benefits from existing cryptanalysis of the ChaCha20 permutation, which is already used in the RNG for number generation.
(And it makes sense to use BLAKE2s in particular, to support non-64-bit systems without penalty.)
Using a single hash (instead of picking one at runtime) simplifies the attack surface IMO.
All AMD Zen processors have the extension.
This is incorrect. Intel only launched their 11th gen desktop processors March 30, 2021. The 10th gen and earlier desktop processors do not have the SHA instructions. You can still buy a new i9-10900k from Newegg today.
(Note that 10th gen Intel mobile/laptop processors are a different micro-architecture, and do support SHA.)
Edit: Perhaps you're thinking of the AES instructions? They've been around a lot longer.
> The argument here is that many (most?) Linux systems have access to a hardware SHA2
Additionally, it's not just the hash function that would matter for speed here, but also the expansion. Linux RNG uses ChaCha20 for that, so if you were going all-in on target-specific speed, you'd need additional logic for swapping that out for a hardware-accelerated cipher (probably AES, which would introduce even more considerations given that it has a 16-byte block size, vs ChaCha20's 64-byte blocks).
Majority of Blake3's perf benefit manifests from merkle-tree structure and SIMD processing of multiple input streams at the same time.
Just in case this isn't clear, BLAKE3 breaks a single large input up into many chunks, and it hashes those chunks in parallel. The caller doesn't need to provide mulitple separate inputs to take advantage of the SIMD optimizations. (If you do have multiple separate inputs, you can actually use similar SIMD optimizations with almost any hash function. But because this situation is rare, libraries that provide this sort of API are also rare. Here's one of mine: https://docs.rs/blake2s_simd/1.0.0/blake2s_simd/many/index.h....)
Perhaps there were other considerations at play. Maybe something as simple as the author's preference. One thing that probably wasn't a consideration is FIPS compliance--the core function is ChaCha20 so FIPS kernels require a completely different CSPRNG, anyhow.
One aspect switching from SHA1 to BLAKE2s does is it increases the total entropy a single compression operation adds to ChaCha20. This increases speed when folded BLAKE2s adds 128 bits per operation instead of folded SHA-1 that adds 80 bits. So that's two calls instead of four (I'm assuming they kept the folding). Another speedup comes from the fact the hash function constants aren't being filled with RDRAND inputs for every call.
Finally, I'm not completely sure if increasing the hash size itself adds computational security against an attack where the internal state is compromised once, and the attacker tries to brute force the new state based on new output; My conjecture is the reseeding operation is atomic, i.e. that ChaCha20 won't yield anything until the reseed is complete. There shouldn't thus be any difference in this regard. I'd appreciate clarification wrt this.
That's for 16KiB inputs.
> One aspect switching from SHA1 to BLAKE2s does is it increases the total entropy a single compression operation adds to ChaCha20. This increases speed when folded BLAKE2s adds 128 bits per operation instead of folded SHA-1 that adds 80 bits.
But the question was why BLAKE2s instead of SHA-256, not SHA-1. SHA-256 has the same digest length as BLAKE2s.
Oh that's a good point.
>But the question was why BLAKE2s instead of SHA-256, not SHA-1. SHA-256 has the same digest length as BLAKE2s.
Two things come to mind. Firstly, does it really matter to speed? The reseeding interval of ChaCha20 DRNG (i.e. BLAKE2 call frequency) is 300 seconds and it runs in the order of milliseconds. Best bang for buck at this point would result from ChaCha-NI.
Secondly, there's the aspect of reducing reliance on an algorithm that suffers from length extension attacks. While LRNG itself doesn't directly benefit from BLAKE2s's indifferentiability, it helps in phasing out SHA-2 which is less misuse-resistant, and that might be misused elsewhere.
(Finally, no more pointless flame wars about "An algorithm created by the NSA is being used in the LRNG!!")
I would guess microseconds.
BLAKE3 needs 16 KiB of input to hit the numbers in that bar chart, but BLAKE2s doesn't. It'll maintain its advantage over SHA-256 all the way down to the empty string. You can see this in Figure 3 of https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blak.... (BLAKE3 is also faster than SHA-256 all the way down to the empty string, but not by as large a margin as the 16 KiB measurements suggest.)
On the other hand, these measurements were done on machines without SHA-256 hardware acceleration. If you have that (and Intel chips from the past year do), then SHA-256 does a lot better of course.