7 ms·
Why is it not SHA2 which would be faster still with hardware support?
by garmaine 5y ago
Why is it not SHA2 which would be faster still with hardware support?
- normaler 5y agoBecause Hardware support is not available in alot oft devices and then blake2 beats sha2.
- willis936 5y agoI wonder if there are more virtual machines than bare metal hosts. There must be, right? Even with paravirtualization as an option I feel like many users of VMs would opt for the advantages of full virtualization.
- yjftsjthsd-h 5y agoMy vague understanding was that KVM-accelerated virtualization still let you use Virtio RNG, although I guess I don't know what the relative performance looks like at that point.
- loeg 5y agoVirtio-rng is good for getting quality seed material into the guest, but you don’t want to use it for bulk generation. Some hypervisor environments impose arbitrary and low throttles on guest virtio-rng use (think kB/s).
- cperciva 5y agoBetter question, why not use whatever hash is fastest on the system in question? We're talking about a RNG here -- it's not like we need to make sure that two different systems produce the same random numbers!
- nerdponx 5y agoMaybe this is a silly question, but why should RNG even be part of the kernel in the first place? It's convenient having it in a device file, but why couldn't that be provided by some userspace program or daemon?
- lisper 5y agoNot a silly question at all. It's because having a reliable and uncompromised source of randomness is essential for cryptographic applications. Having the RNG in user space would make it more vulnerable to attack.
- tptacek 5y agoTwo good reasons: 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.
- foxfluff 5y agoThe kernel needs randomness too. If it's done there right once, why duplicate the effort in userspace (and watch all the hilarious ways userspace solutions fail)? getrandom was motivated by the fact that using device files has many failure modes.
- tptacek 5y agoOh, nice, a good 3rd security reason! A userland CSPRNG is essentially just an additional single point of failure, since you're going to end up depending on secure randomness in the kernel already. It's a good question!
- Mehdi2277 5y agoI normally care about reproducible rng results and do try to seed all rngs used. There are lots of applications where randomness is used but you still want repeatable behavior. ML experiments is one situation where randomness is common, but is also intended to be repeatable. I think python standard library/several of data science library rngs are platform independent.
- tptacek 5y agoThis is not that kind of RNG; this is the system secure random number generator. Secure random numbers aren't seeded.
- SAI_Peregrinus 5y agoI wouldn't say the lack of a seed is the difference between a CSPRNG and a PRNG. That's more the difference between a CSPRNG and a stream cipher, where the "seed" is called a "key" and "IV". 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.
- fault1 5y agoI think you are talking about a psuedo-rng.
- akerl_ 5y agoBasically every RNG you interact with on general purpose computers is a pseudo random number generator. The kernel RNG being discussed here is a CSPRNG, as was the one it replaced.
- espadrine 5y agoThe title mentions performance, but it is not the primary motivation AFAICT. It is only mentioned to say “it is not slower”. 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.
- tptacek 5y agoThe argument here is that many (most?) Linux systems have access to a hardware SHA2, which is equally secure (in this setting) but faster. Attacks on SHA2 or Blake2 (really, of SHA1, for that matter) aren't how viable real-world attackers on the LKRNG are going to happen. It's good to see SHA1 getting swept away for other reasons though!
- loeg 5y agoDo most Intel (and by extension, Linux) machines have SHA2, though? I think it’s a pretty recent extension and at least initially, they were only shipping it in their low-end embedded models.
- Kubuxu 5y agoMost Intel processors don't have the extension, it is only Goldmont (low power) and 10th gen and up. All AMD Zen processors have the extension.
- str4d 5y agoMy answer to that is "maintainability". The more flexibility and moving parts we add to the RNG, the more things that can break. The delta from "one hash function" to "two hash functions" would involve not just adding a second hash function, but also a bunch of configuration code, target-specific logic, fallback handling, etc. There are plenty of places in the kernel that need to care about this kind of logic, but I don't believe the RNG is one of them, and I don't particularly want to require the RNG maintainers to spend their time caring about it. 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).
- pedrocr 5y agoSpeed was probably not the criteria otherwise blake3 seems like an even better choice: https://github.com/BLAKE3-team/BLAKE3 https://github.com/BLAKE3-team/BLAKE3
- tptacek 5y agoI think speed is definitely a big part of this, though the speedup comes primarily from getting rid of superfluous calls to RDRAND. Blake2s is already in the kernel (after a fashion) for WireGuard itself; I don't think Blake3 is. An additional nerdy point here is that the extraction phase of the LKRNG is already using ChaCha (there's a sense in which a CSPRNG is really just the keystream of a stream cipher), and Blake2s and ChaCha are closely related.
- pedrocr 5y agoSo should we expect a blake3 switch sometime in the future? It seems to be a refinement of blake2 to make it more amenable to optimization while keeping most (all?) its qualities. Being well suited for optimization across architectures would also make it ideal for the kernel and it seems the reference implementation has already done a lot of the heavy lifting.
- tptacek 5y agoI doubt it, but who knows?
- Kubuxu 5y agoBlake3 will 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.
- oconnor663 5y ago> 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.html https://docs.rs/blake2s_simd/1.0.0/blake2s_simd/many/index.h....)
- wahern 5y agoAFAICT, BLAKE2s (previously SHA-1) is only being used for the forward secrecy element, in this case mixing a hash of the pool back into the core state, which is actually still using ChaCha20 for expansion. From quick inspection (never read this code before) I think the number of bytes in the pool is 416 (104 * 4). (See poolwords defined at https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/drivers/char/random.c?h=v5.16-rc7#n433 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...) For such relatively small messages and based on the cycles-per-byte performance numbers from https://w3.lasca.ic.unicamp.br/media/publications/p9-faz-hernandez.pdf https://w3.lasca.ic.unicamp.br/media/publications/p9-faz-her... (SHA-NI benchmarks), https://www.blake2.net/blake2_20130129.pdf https://www.blake2.net/blake2_20130129.pdf (BLAKE2 paper), and https://bench.cr.yp.to/results-hash.html https://bench.cr.yp.to/results-hash.html (comprehensive table of measurements), I don't see any performance reasons for choosing BLAKE2s over SHA-256. Rather, software SHA-256 and BLAKE2s seem comparable (and that's being charitable to BLAKE2s), and SHA-NI is definitely faster. 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.
- maqp 5y agohttps://github.com/BLAKE3-team/BLAKE3/blob/master/media/speed.svg https://github.com/BLAKE3-team/BLAKE3/blob/master/media/spee... argues BLAKE2s is twice as fast compared to SHA256. 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.