devsummit:201308:security:devrandom

This is an old revision of the document!

/dev/random discussion at the 201308DevSummit

Whiteboard photos:

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.
    • Go read the paper if you haven't already.
    • markm@ plans to implement Yarrow's successor, Fortuna, in 11.
  • 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.

Unblocking:

  • 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.

Additional sources:

  • markm:
  • rwatson:
    • 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

Embedded:

  • Both Yarrow and (especially) Fortuna are relatively memory- and CPU-intensive.
  • Embedded
    • 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?

Conclusions:

  • devsummit/201308/security/devrandom.1423165295.txt.gz
  • Last modified: 2015/02/05 19:41
  • by JohnMarkGurney