====== /dev/random discussion at the 201308DevSummit ======

This page was last edited 2015-02-05 19:41:35 by [[/JohnMarkGurney|JohnMarkGurney]].

Whiteboard photos:

  * {{devsummit/201308/security/devrandom/yarrow1.jpg?linkonly|Yarrow1.jpg}}
  * {{devsummit/201308/security/devrandom/yarrow2.jpg?linkonly|Yarrow2.jpg}}
  * {{devsummit/201308/security/devrandom/yarrow3.jpg?linkonly|Yarrow3.jpg}}

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 [[http://www.schneier.com/yarrow.html|Yarrow PRNG]].
    * Go read the [[http://www.schneier.com/paper-yarrow.html|paper]] if you haven't already.
    * markm@ plans to implement Yarrow's successor, [[http://en.wikipedia.org/wiki/Fortuna_(PRNG)|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: 
    * write general purpose code to bring an API for other case (process, probe temperature, crypto, ect..) (random_adaptor framework)
    * feed to yarrow
    * care about /dev/random (use /dev/zero)
    * to be done at runtime
  * 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:

  * 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

----

{{tag>Historical}}