/dev/random discussion at the 201308DevSummit
The premise is:
The current state of /dev/random is not entirely optimal, especially the way we support HWRNGs.
- obrien@ recently committed a huge patch from Arthur Mesh (Juniper) which was then reverted at so@'s request; part of the patch was reviewed and approved by secteam@ and re-committed.
Everybody agrees that /dev/random needs overhauling, but this is too risky to do when 10.0 is right around the corner.
Specifically, we must not do anything that changes the statistical properties of /dev/random output.
- We do however need to fix a number of problems that we know about.
How /dev/random works today:
The primary source of randomness is the Yarrow PRNG.
Entropy is fed into the Yarrow through random_harvest(9), which hashes arbitrary data + a timestamp into the accumulator—via a queue, because random_harvest(9) may be called from interrupt context, and hashing data into the Yarrow accumulator is computationally expensive.
- Entropy is harvested from:
Data written to /dev/random, e.g. by /etc/rc.d/initrandom.
- Keyboard and mouse activity.
- Network activity.
Hardware interrupts, conditional on a bit (IH_ENTROPY) in the interrupt handler descriptor, so timer interrupts, for example, are not fed into Yarrow.
- Software interrupts. This is disabled by default, but can be enabled with a sysctl.
- The final source is labelled PURE: data obtained from a HWRNG.
Known problems with entropy harvesting:
- Direct write:
A simple close(open("/dev/random", O_RDWR)) will unblock Yarrow (see below) even if no useful entropy has been fed into it yet.
- Network entropy:
- On 64-bit machines, a lot of what it feeds into Yarrow is all-bits-zero. A fix is available and will soon be committed.
- Entropy from network events can easily swamp the entropy queue.
- As mentioned above, the input queue is easily swamped. It should be reimplemented as a circular buffer where, if the buffer is full, new data is simply hashed into existing data; would XOR be adequate for this purpose? This is done in interrupt context, so whatever we choose has to be very, very fast.
- Perhaps we should have per-CPU input queues.
Both Yarrow and Fortuna need to accumulate a certain amount of entropy before they can start generating random numbers. Until that happens, reads from /dev/random will block.
pjd@ has a patch which feeds timing information from device_attach(), allowing Yarrow to be unblocked much earlier in the boot process, and eliminating the need for /etc/rc.d/initrandom. There were concerns about overestimating the amount of entropy being harvested; des@ has gathered empirical data which tends to support this. The original patch estimates the entropy to be log2(delta) - 10; des@ suggests log2(delta) / 2 instead, or (log2(delta) - c) / 2 for a suitable (small) value of c.
We currently have a cron job that regularly dumps data from /dev/random into a file which is then fed back into it at boot time.
- If the loader knew to look for this file and read it into a memory location where Yarrow could get hold of it, we could unblock Yarrow much earlier.
- However, we must avoid reusing the same entropy file over and over again. It should be deleted after use. The loader can't do that.
- dealing with ssh keys, probably identical keys in the world because of the entropy?
- markm when boot and don't have good results or RNG fail :
- block (seems the solution ssh-keygen block), crap entropy/pig randomness or panic (not appropriate will be same after next reboot)
- pdj: fallback on yarrow but if non yarrow ?!
- adrian: on mips can't do pid randomness (base on arc4random())
- rc4 vs /dev/random
- Both Yarrow and (especially) Fortuna are relatively memory- and CPU-intensive.
- adrian come up with embedded problem (time attach is low on his board), boot part ?!
- des background noise on wireless device/stack
- markm kill the input queue
- rwatson think we need to focus on desktop and servers to provide good documentation and good pratices by default, provide guidance and clearance
- Yarrow vs Fortuna
- Y:256 bit hashes into fast and slow buffer, value as a key for encryption function (PRNG + hardware device to change the seed) + 2 pool
- F: 32 pool each event seperatly and evenlty spread each pool from source + bitmaps counter, advantage: counter mode
- rwatson: queue per cpu core
- Davis-Meyers hash
rwatson: sson did FIPS tests for Apple and MacOS
- rwatson: multi socket ?! cpu socket ?! will be a problem high thread...
pjd: Yarrow limited to one CPU => don't scale because of the LOCK
reading scalable => feed directly to the pool and not use queue
- XORing doesn't loose entropy
- markm: we need to do the hash in pool !
- sbz: test diehards
- des: test vritual machine (vbox)
Schema => take picture
HW: rvy.c + nehemiah.c boot: sysctl yarrow: device driver
Schema propose by pjd
- proxy mixer component which take entropy from real rand device and network?
- Fix the change NET/PURE/INTERRUPT/?
- Fortuna not in 10.0
- No new framework bugs ?!
- Do not lose entropy with update to current + random_adaptor framework
- YARROW unconditional
- Pawel patches includes
- fixes entropy estimation
by overestimated (des send everything and test the range => less variation, device attach slowly)
- des test regarding attach times:
17:38 <@EvilDES> http://people.freebsd.org/~des/attachtimes-bin.txz
17:38 <@EvilDES> http://people.freebsd.org/~des/attachtimes-text.txz
17:38 <@EvilDES> http://people.freebsd.org/~des/attachtimes-total.txz