On the darwin-users list I began asking about examination of Darwin's
/dev/random, and eventually reported that (especially for large reads)
Darwin's /dev/random seemed at first glance to have great apparent
unpredictibility and incompressibility. However, chi-square analysis
of output from Darwin's /dev/random invited closer examination. I
poked in the code and was surprised to be reminded that actual entropy
collection in Darwin is undertaken not within the kernel but by a
userland daemon (the Security Server). (I had assumed this was
possible due to kernel pre-emption and had not initially investigated
it.)
I also noticed that Darwin's /dev/random is actually exactly the same
as its /dev/urandom:
/*
* also make urandom
* (which is exactly the same thing in our context)
*/
devfs_make_node(makedev (ret, 1), DEVFS_CHAR,
UID_ROOT, GID_WHEEL, 0666, "urandom", 0);
The man page on urandom makes it clear that Apple's /dev/random is
identical to its /dev/random, so Apple is aware of this and apparently
does not comprehend the problem it invites, instead calling those
concerned about this problem "paranoid" and trying to suggest programs
which depend on /dev/random should take steps to acquire better entropy
if /dev/urandom is not good enough. The reason this is a problem can
be illustrated with reference to the origin of Apple's /dev/random, and
is less related to paranoia than to math.
Darwin possess an outstanding /dev/urandom, which provides
incompressibly irregular output of arbitrary length without great
demand on the kernel. The decision to use this code also in Darwin's
/dev/random was grounded in -- and my source is the now-closed bug
tracker through which Apple used to provide a window on its internal
Darwin development -- (a) a bug filed that "Darwin has no /dev/random"
(at a time in which there was no /dev/urandom either), (b) Wilfredo's
assurance of Apple engineers that a /dev/random was not a Unix joke but
a genuine OS feature depended upon by porters of serious crypto
projects, and that absence of a quality /dev/random was a legitimate
problem, and (c) a supervisor closed the bug on the strength of the
argument that a prng based on Yarrow code was "better" than the
/dev/random in FreeBSD and that this Yarrow-based prng would be used
for Darwin's /dev/random.
So, what exactly is wrong with using /dev/urandom instead or
/dev/random for an entropy source in crypto tools?
People creating and using cryptographic keys of any substantial length
will certainly request entropy which greatly exceeds the size of the
key from which Darwin generates its output, even if Darwin doubles or
quadruples the key length from that in the Yarrow-160 code on which
Darwin's prng is based. This is especially true on machines creating
HTTPS connections or otherwise generating keys, which will require many
key creations between re-seeds of the Yarrow-based prng. Thus,
1024-bit and 2048-bit PGP/GPG keys may reflect actual entropy of, say,
160 bits (based on the Yarrow-160 code; I have not compared Apple's
code to the originally published Yarrow code to determine if Apple's is
slightly larger or not, but it looks like Security Server's re-seed is
based on a read of eight values of). Successive keys made before
re-seeding will also have a capped limit of their actual entropy
content, but the situation is worse: they will be using the exact same
entropy used for every other key in the between-reseeding period. The
very Yarrow paper, by the authors of the Yarrow-160 code on which
Darwin's /dev/random code is based, expressly warns against use of the
Yarrow prng for the purposes to which a /dev/random device is put:
"Like any other cryptographic primitive, a Yarrow generator has a
limited strength which we express in the size of the key. Yarrow-160
relies on the strength of three-key triple-DES and SHA-1, and has an
effective key length of about 160 bits. Systems that have switched to
new cryptographic mechanisms (such as the new AES cipher...) in the
interest of getting higher security should use a different version of
Yarrow to rely on those new mechanisms. IF A LONGER KEY IS NECESSARY,
THEN A FUTURE "LARGER" VERSION OF YARROW SHOULD BE USED; IT MAKES NO
SENSE TO USE A 160-BIT PRNG TO GENERATE A 256-BIT KEY FOR A BLOCK
CIPHER, IF 256 BITS OF SECURITY ARE ACTUALLY REQUIRED"
<http://schneier.com/paper-yarrow.ps.gz> (emphasis added); see also
<http://www.counterpane.com/yarrow.html>
Thus, Yarrow by its nature is a supplier of /dev/urandom and should in
no circumstance be advertised as /dev/random, which the ordinary
cryptographic user will mistake for a source of actual entropy with a
number of bits of entropy virtually identical to the number of bits
read (even if several KB are read). (One fix is to provide, with
respect to /dev/random reads, an enforced re-seeding every N bits,
where N is not greater than the entropy in the Yarrow prng key)
Indeed, making a PGP/GPG key with Darwin's /dev/random as an entropy
source guarantees that the key will fall victim to the very first
pitfall identified in the Yarrow paper: overestimation of the entropy
actually present in the "random" input used to generate keys.
The distinction between /dev/random and /dev/urandom is not lost on
programmers, as the (languishing) systrace code created for MacOS X
(complete with Cocoa GUI!) demonstrated with its example allowing
iTunes to query /dev/urandom (iTunes' shuffle feature works with this
systrace policy, proving iTunes actually reads /dev/urandom and not
/dev/random). Thus, dice-rolling programs (and first-person shooters,
Asteroids, etc.) query /dev/urandom at leisure without straining the
kernel or threatening the system's entropy pool, but when actual
bit-for-bit strong entropy is required of a certain length, an actual
/dev/random should be available to supply the expected entropy (and not
merely 160 bits of entropy served, and served as leftovers, and then
reheated again after being frozen, to appear to unsuspecting guests as
2048 bits of entropy).
Solutions appear to be (a) modifying /dev/random to demand re-seed once
for every N bits of output demanded before giving out more than N bits,
where N is the amount of entropy in the Yarrow generator's key
[downside: on a busy SSL site or other frequent key-creating system,
this will demand the userland Security Server be busy, or cause delays
until the Security Server wakes and writes entropy into /dev/random;
can the kernel really wait for the userland process? Am I mistaken
that Darwin is the only place entropy is written to /dev/random from
outside the kernel?], or (b) taking BSD-licensed code known to produce
actual entropy from /dev/random and using that for free. Am I missing
any alternate theories?
Has anyone got an analysis they believe vindicates the recycling of
entropy for crypto input?
