en Copyright 2015 Java http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#179f6280 random(4): Fortuna: allow increased concurrencyAdd experimental feature to increase concurrency in Fortuna. As thisdiverges slightly from canonical Fortuna, and due to the securitysensitivity of random(4), it is off by default. To enable it, set thetunable kern.random.fortuna.concurrent_read="1". The rest of this commitmessage describes the behavior when enabled.Readers continue to update shared Fortuna state under global mutex, as theydo in the status quo implementation of the algorithm, but shift the actualPRF generation out from under the global lock. This massively reduces theCPU time readers spend holding the global lock, allowing for increasedconcurrency on SMP systems and less bullying of the harvestq kthread.It is somewhat of a deviation from FS&K. I think the primary difference isthat the specific sequence of AES keys will differ if READ_RANDOM_UIO isaccessed concurrently (as the 2nd thread to take the mutex will no longerreceive a key derived from rekeying the first thread). However, I believethe goals of rekeying AES are maintained: trivially, we continue to rekeyevery 1MB for the statistical property; and each consumer gets aforward-secret, independent AES key for their PRF.Since Chacha doesn't need to rekey for sequences of any length, this changemakes no difference to the sequence of Chacha keys and PRF generated whenChacha is used in place of AES.On a GENERIC 4-thread VM (so, INVARIANTS/WITNESS, numbers not necessarilyrepresentative), 3x concurrent AES performance jumped from ~55 MiB/s perthread to ~197 MB/s per thread. Concurrent Chacha20 at 3 threads went fromroughly ~113 MB/s per thread to ~430 MB/s per thread.Prior to this change, the system was extremely unresponsive with 3-4concurrent random readers; each thread had high variance in latency andthroughput, depending on who got lucky and won the lock. "rand_harvestq"thread CPU use was high (double digits), seemingly due to spinning on theglobal lock.After the change, concurrent random readers and the system in general aremuch more responsive, and rand_harvestq CPU use dropped to basically zero.Tests are added to the devrandom suite to ensure the uint128_add64 primitiveutilized by unlocked read functions to specification.Reviewed by: markmApproved by: secteam(delphij)Relnotes: yesDifferential Revision: https://reviews.freebsd.org/D20313 List of files: /freebsd-13.1/sys/dev/random/hash.h Mon, 17 Jun 2019 20:29:13 +0000 Conrad Meyer <cem@FreeBSD.org> http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#d0d71d81 random(4): Generalize algorithm-independent APIsAt a basic level, remove assumptions about the underlying algorithm (such asoutput block size and reseeding requirements) from the algorithm-independentlogic in randomdev.c. Chacha20 does not have many of the restrictions thatAES-ICM does as a PRF (Pseudo-Random Function), because it has a cipherblock size of 512 bits. The motivation is that by generalizing the API,Chacha is not penalized by the limitations of AES.In READ_RANDOM_UIO, first attempt to NOWAIT allocate a large enough bufferfor the entire user request, or the maximal input we'll accept betweensignal checking, whichever is smaller. The idea is that the implementationof any randomdev algorithm is then free to divide up large requests inwhatever fashion it sees fit.As part of this, two responsibilities from the "algorithm-generic" randomdevcode are pushed down into the Fortuna ra_read implementation (and any otherfuture or out-of-tree ra_read implementations): 1. If an algorithm needs to rekey every N bytes, it is responsible for handling that in ra_read(). (I.e., Fortuna's 1MB rekey interval for AES block generation.) 2. If an algorithm uses a block cipher that doesn't tolerate partial-block requests (again, e.g., AES), it is also responsible for handling that in ra_read().Several APIs are changed from u_int buffer length to the more canonicalsize_t. Several APIs are changed from taking a blockcount to a bytecount,to permit PRFs like Chacha20 to directly generate quantities of output thatare not multiples of RANDOM_BLOCKSIZE (AES block size).The Fortuna algorithm is changed to NOT rekey every 1MiB when in Chacha20mode (kern.random.use_chacha20_cipher="1"). This is explicitly supported bythe math in FS&K §9.4 (Ferguson, Schneier, and Kohno; "CryptographyEngineering"), as well as by their conclusion: "If we had a block cipherwith a 256-bit [or greater] block size, then the collisions would nothave been an issue at all."For now, continue to break up reads into PAGE_SIZE chunks, as they werebefore. So, no functional change, mostly.Reviewed by: markmApproved by: secteam(delphij)Differential Revision: https://reviews.freebsd.org/D20312 List of files: /freebsd-13.1/sys/dev/random/hash.h Mon, 17 Jun 2019 15:09:12 +0000 Conrad Meyer <cem@FreeBSD.org> http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#403c0413 random(4): Add regression tests for uint128 implementation, Chacha CTRAdd some basic regression tests to verify behavior of both uint128implementations at typical boundary conditions, to run on all architectures.Test uint128 increment behavior of Chacha in keystream mode, as used by'kern.random.use_chacha20_cipher=1' (r344913) to verify assumptions at edgecases. These assumptions are critical to the safety of using Chacha as aPRF in Fortuna (as implemented).(Chacha's use in arc4random is safe regardless of these tests, as it islimited to far less than 4 billion blocks of output in that API.)Reviewed by: markmApproved by: secteam(gordon)Differential Revision: https://reviews.freebsd.org/D20392 List of files: /freebsd-13.1/sys/dev/random/hash.h Mon, 17 Jun 2019 14:59:45 +0000 Conrad Meyer <cem@FreeBSD.org> http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#ab69c485 Fortuna: Add Chacha20 as an alternative stream cipherChacha20 with a 256 bit key and 128 bit counter size is a good match for anAES256-ICM replacement.In userspace, Chacha20 is typically marginally slower than AES-ICM onmachines with AESNI intrinsics, but typically much faster than AES onmachines without special intrinsics. ChaCha20 does well on typical modernarchitectures with SIMD instructions, which includes most types of machinesFreeBSD runs on.In the kernel, we can't (or don't) make use of AESNI intrinsics forrandom(4) anyway. So even on amd64, using Chacha provides a modestperformance improvement in random device throughput today.This change makes the stream cipher used by random(4) configurable at boottime with the 'kern.random.use_chacha20_cipher' tunable.Very rough, non-scientific measurements at the /dev/random device, on aGENERIC-NODEBUG amd64 VM with 'pv', show a factor of 2.2x higher throughputfor Chacha20 over the existing AES-ICM mode.Reviewed by: delphij, markmApproved by: secteam (delphij)Differential Revision: https://reviews.freebsd.org/D19475 List of files: /freebsd-13.1/sys/dev/random/hash.h Fri, 08 Mar 2019 01:17:20 +0000 Conrad Meyer <cem@FreeBSD.org> http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#51c68d18 Fortuna: push CTR-mode loop down into randomdev hash.h interfaceAs a step towards adding other potential streaming ciphers. As well as justpushing the loop down into the rijndael APIs (basically 128-bit wide AES-ICMmode) to eliminate some excess explicit_bzero().No functional change intended.Reviewed by: delphij, markmApproved by: secteam (delphij)Sponsored by: Dell EMC IsilonDifferential Revision: https://reviews.freebsd.org/D19411 List of files: /freebsd-13.1/sys/dev/random/hash.h Fri, 01 Mar 2019 19:21:45 +0000 Conrad Meyer <cem@FreeBSD.org> http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#3aa77530 * Address review (and add a bit myself). - Tweek man page. - Remove all mention of RANDOM_FORTUNA. If the system owner wants YARROW or DUMMY, they ask for it, otherwise they get FORTUNA. - Tidy up headers a bit. - Tidy up declarations a bit. - Make static in a couple of places where needed. - Move Yarrow/Fortuna SYSINIT/SYSUNINIT to randomdev.c, moving us towards a single file where the algorithm context is used. - Get rid of random_*_process_buffer() functions. They were only used in one place each, and are better subsumed into those places. - Remove *_post_read() functions as they are stubs everywhere. - Assert against buffer size illegalities. - Clean up some silly code in the randomdev_read() routine. - Make the harvesting more consistent. - Make some requested argument name changes. - Tidy up and clarify a few comments. - Make some requested comment changes. - Make some requested macro changes.* NOTE: the thing calling itself a 'unit test' is not yet a proper unit test, but it helps me ensure things work. It may be a proper unit test at some time in the future, but for now please don't make any assumptions or hold any expectations.Differential Revision: https://reviews.freebsd.org/D2025Approved by: so (/dev/random blanket) List of files: /freebsd-13.1/sys/dev/random/hash.h Sun, 12 Jul 2015 18:14:38 +0000 Mark Murray <markm@FreeBSD.org> http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#d1b06863 Huge cleanup of random(4) code.* GENERAL- Update copyright.- Make kernel options for RANDOM_YARROW and RANDOM_DUMMY. Set neither to ON, which means we want Fortuna- If there is no 'device random' in the kernel, there will be NO random(4) device in the kernel, and the KERN_ARND sysctl will return nothing. With RANDOM_DUMMY there will be a random(4) that always blocks.- Repair kern.arandom (KERN_ARND sysctl). The old version went through arc4random(9) and was a bit weird.- Adjust arc4random stirring a bit - the existing code looks a little suspect.- Fix the nasty pre- and post-read overloading by providing explictit functions to do these tasks.- Redo read_random(9) so as to duplicate random(4)'s read internals. This makes it a first-class citizen rather than a hack.- Move stuff out of locked regions when it does not need to be there.- Trim RANDOM_DEBUG printfs. Some are excess to requirement, some behind boot verbose.- Use SYSINIT to sequence the startup.- Fix init/deinit sysctl stuff.- Make relevant sysctls also tunables.- Add different harvesting "styles" to allow for different requirements (direct, queue, fast).- Add harvesting of FFS atime events. This needs to be checked for weighing down the FS code.- Add harvesting of slab allocator events. This needs to be checked for weighing down the allocator code.- Fix the random(9) manpage.- Loadable modules are not present for now. These will be re-engineered when the dust settles.- Use macros for locks.- Fix comments.* src/share/man/...- Update the man pages.* src/etc/...- The startup/shutdown work is done in D2924.* src/UPDATING- Add UPDATING announcement.* src/sys/dev/random/build.sh- Add copyright.- Add libz for unit tests.* src/sys/dev/random/dummy.c- Remove; no longer needed. Functionality incorporated into randomdev.*.* live_entropy_sources.c live_entropy_sources.h- Remove; content moved.- move content to randomdev.[ch] and optimise.* src/sys/dev/random/random_adaptors.c src/sys/dev/random/random_adaptors.h- Remove; plugability is no longer used. Compile-time algorithm selection is the way to go.* src/sys/dev/random/random_harvestq.c src/sys/dev/random/random_harvestq.h- Add early (re)boot-time randomness caching.* src/sys/dev/random/randomdev_soft.c src/sys/dev/random/randomdev_soft.h- Remove; no longer needed.* src/sys/dev/random/uint128.h- Provide a fake uint128_t; if a real one ever arrived, we can use that instead. All that is needed here is N=0, N++, N==0, and some localised trickery is used to manufacture a 128-bit 0ULLL.* src/sys/dev/random/unit_test.c src/sys/dev/random/unit_test.h- Improve unit tests; previously the testing human needed clairvoyance; now the test will do a basic check of compressibility. Clairvoyant talent is still a good idea.- This is still a long way off a proper unit test.* src/sys/dev/random/fortuna.c src/sys/dev/random/fortuna.h- Improve messy union to just uint128_t.- Remove unneeded 'static struct fortuna_start_cache'.- Tighten up up arithmetic.- Provide a method to allow eternal junk to be introduced; harden it against blatant by compress/hashing.- Assert that locks are held correctly.- Fix the nasty pre- and post-read overloading by providing explictit functions to do these tasks.- Turn into self-sufficient module (no longer requires randomdev_soft.[ch])* src/sys/dev/random/yarrow.c src/sys/dev/random/yarrow.h- Improve messy union to just uint128_t.- Remove unneeded 'staic struct start_cache'.- Tighten up up arithmetic.- Provide a method to allow eternal junk to be introduced; harden it against blatant by compress/hashing.- Assert that locks are held correctly.- Fix the nasty pre- and post-read overloading by providing explictit functions to do these tasks.- Turn into self-sufficient module (no longer requires randomdev_soft.[ch])- Fix some magic numbers elsewhere used as FAST and SLOW.Differential Revision: https://reviews.freebsd.org/D2025Reviewed by: vsevolod,delphij,rwatson,trasz,jmgApproved by: so (delphij) List of files: /freebsd-13.1/sys/dev/random/hash.h Tue, 30 Jun 2015 17:00:45 +0000 Mark Murray <markm@FreeBSD.org> http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#133cdd9e Constify the AES code and propagate to consumers. This allows us toupdate the Fortuna code to use SHAd-256 as defined in FS&K.Approved by: so (self) List of files: /freebsd-13.1/sys/dev/random/hash.h Mon, 10 Nov 2014 09:44:38 +0000 Dag-Erling Smørgrav <des@FreeBSD.org> http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#10cb2424 This is the much-discussed major upgrade to the random(4) device, known to you all as /dev/random.This code has had an extensive rewrite and a good series of reviews, both by the author and other parties. This means a lot of code has been simplified. Pluggable structures for high-rate entropy generators are available, and it is most definitely not the case that /dev/random can be driven by only a hardware souce any more. This has been designed out of the device. Hardware sources are stirred into the CSPRNG (Yarrow, Fortuna) like any other entropy source. Pluggable modules may be written by third parties for additional sources.The harvesting structures and consequently the locking have been simplified. Entropy harvesting is done in a more general way (the documentation for this will follow). There is some GREAT entropy to be had in the UMA allocator, but it is disabled for now as messing with that is likely to annoy many people.The venerable (but effective) Yarrow algorithm, which is no longer supported by its authors now has an alternative, Fortuna. For now, Yarrow is retained as the default algorithm, but this may be changed using a kernel option. It is intended to make Fortuna the default algorithm for 11.0. Interested parties are encouraged to read ISBN 978-0-470-47424-2 "Cryptography Engineering" By Ferguson, Schneier and Kohno for Fortuna's gory details. Heck, read it anyway.Many thanks to Arthur Mesh who did early grunt work, and who got caught in the crossfire rather more than he deserved to.My thanks also to folks who helped me thresh this out on whiteboards and in the odd "Hallway track", or otherwise.My Nomex pants are on. Let the feedback commence!Reviewed by: trasz,des(partial),imp(partial?),rwatson(partial?)Approved by: so(des) List of files: /freebsd-13.1/sys/dev/random/hash.h Thu, 30 Oct 2014 21:21:53 +0000 Mark Murray <markm@FreeBSD.org> http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#3e8957ea Add missing include guards and move the existing ones out of theimplementation namespace. List of files: /freebsd-13.1/sys/dev/random/hash.h Wed, 09 Oct 2013 09:11:14 +0000 Dag-Erling Smørgrav <des@FreeBSD.org> http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#f8530155 Snapshot of current work;1) Clean up namespace; only use "Yarrow" where it is Yarrow-specificor close enough to the Yarrow algorithm. For the rest use a neutralname.2) Tidy up headers; put private stuff in private places. More couldbe done here.3) Streamline the hashing/encryption; no need for a 256-bit counter;128 bits will last for long enough.There are bits of debug code lying around; these will be removedat a later stage. List of files: /freebsd-13.1/sys/dev/random/hash.h Mon, 26 Aug 2013 18:29:51 +0000 Mark Murray <markm@FreeBSD.org> http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#e7806b4c Reorganise the entropy device so that high-yield entropy sourcescan more easily be used INSTEAD OF the hard-working Yarrow.The only hardware source used at this point is the one insidethe VIA C3 Nehemiah (Stepping 3 and above) CPU. More sources willbe added in due course. Contributions welcome! List of files: /freebsd-13.1/sys/dev/random/hash.h Fri, 09 Apr 2004 15:47:10 +0000 Mark Murray <markm@FreeBSD.org> http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#bbf09ad8 Upgrade the random device to use a "real" hash instead of buildingone out of a block cipher. This has 2 advantages:1) The code is _much_ simpler2) We aren't committing our security to one algorithm (much as we may think we trust AES).While I'm here, make an explicit reseed do a slow reseed insteadof a fast; this is in line with what the original paper suggested. List of files: /freebsd-13.1/sys/dev/random/hash.h Mon, 15 Jul 2002 13:58:35 +0000 Mark Murray <markm@FreeBSD.org> http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#e1199601 Massive lint-inspired cleanup.Remove unneeded includes.Deal with unused function arguments.Resolve a boatload of signed/unsigned imcompatabilities.Etc. List of files: /freebsd-13.1/sys/dev/random/hash.h Sun, 03 Mar 2002 19:44:22 +0000 Mark Murray <markm@FreeBSD.org> http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#02c986ab Very large makeover of the /dev/random driver.o Separate the kernel stuff from the Yarrow algorithm. Yarrow is now well contained in one source file and one header.o Replace the Blowfish-based crypto routines with Rijndael-based ones. (Rijndael is the new AES algorithm). The huge improvement in Rijndael's key-agility over Blowfish means that this is an extremely dramatic improvement in speed, and makes a heck of a difference in its (lack of) CPU load.o Clean up the sysctl's. At BDE's prompting, I have gone back to static sysctls.o Bug fixes. The streamlining of the crypto stuff enabled me to find and fix some bugs. DES also found a bug in the reseed routine which is fixed.o Change the way reseeds clear "used" entropy. Previously, only the source(s) that caused a reseed were cleared. Now all sources in the relevant pool(s) are cleared.o Code tidy-up. Mostly to make it (nearly) 80-column compliant. List of files: /freebsd-13.1/sys/dev/random/hash.h Sat, 10 Mar 2001 12:51:55 +0000 Mark Murray <markm@FreeBSD.org> http://172.16.0.5:8080/history/freebsd-13.1/sys/dev/random/hash.h#4d87a031 Large upgrade to the entropy device; mainly inspired by feedbackfrom many folk.o The reseed process is now a kthread. With SMPng, kthreads are pre-emptive, so the annoying jerkiness of the mouse is gone.o The data structures are protected by mutexes now, not splfoo()/splx().o The cryptographic routines are broken out into their own subroutines. this facilitates review, and possible replacement if that is ever found necessary.Thanks to: kris, green, peter, jasone, grog, jhbForgotten to thank: You know who you are; no offense intended. List of files: /freebsd-13.1/sys/dev/random/hash.h Sun, 10 Sep 2000 13:52:19 +0000 Mark Murray <markm@FreeBSD.org>