Date: Tue, 13 Apr 1999 15:33:45 -0700 (PDT) From: Steve Reid <sreid@alpha.sea-to-sky.net> To: freebsd-security@freebsd.org Subject: /dev/random's entropy_count estimate considered too generous (fwd) Message-ID: <Pine.LNX.3.95.iB1.0.990413153020.29155A-100000@alpha.sea-to-sky.net>
next in thread | raw e-mail | index | archive | help
Forwarded without permission...
----- Forwarded message from David Honig <honig@sprynet.com> -----
X-BlackMail: toad.com, toad.com, <coderpunks-errors@toad.com> SIZE=5908, 140.174.2.1
X-Authenticated-Timestamp: 11:18:32(PDT) on April 12, 1999
X-Sender: honig@m7.sprynet.com
X-Mailer: QUALCOMM Windows Eudora Light Version 3.0.5 (32)
Date: Mon, 12 Apr 1999 09:11:57 -0700
To: "Ge' Weijers" <ge@Progressive-Systems.Com>,
"William H. Geiger III" <whgiii@openpgp.net>, coderpunks@toad.com
From: David Honig <honig@sprynet.com>
Subject: /dev/random's entropy_count estimate considered too generous
Cc: cypherpunks@openpgp.net, mgraffam@idsi.net, steven.soroka@mts.mb.ca
In-Reply-To: <19990412102200.A542@progressive-systems.com>
Precedence: bulk
I dug into the /dev/random code this weekend to try to answer WHGIII's
query about analyzing that subsystem. The entropy estimation
strikes me as more generous than one would like.
An Analysis of the FreeBSD /dev/random:
Entropy_count Calculation is Probably Too Generous
David Honig <honig@sprynet.com> rev A
Intro
This document discusses BSD's implementation of /dev/random.
The entropy_count estimation appears to be insufficiently conservative.
This is impossible to observe from its output, which is whitened with MD5.
Random Pool
The file /usr/src/sys/i386/isa/random_machdep.c implements BSD's /dev/random
and corresponding system calls. This subsystem can use system interrupts
designated by the "rndcontrol" utility or during kernel configuration.
These interrupts yield raw entropy which is mixed, along with timing
entropy, into a global pool of 128 32-bit integers. (All integers will be
32 bits hereon.)
Random Output
To obtain random values, this pool is fed to MD5. 9 hashes are required
for every 16 bytes out of /dev/random. The number of bytes requested and
the time of the request is also used in one final stir just before using
the pool.
Interrupt Processing
When a designated interrupt occurs, the following happens. A number
representing the interrupt's origin (e.g., the keyboard character) is
passed as an integer to add_timer_randomness. This function also mixes in
two timers: one derived from "timercounter", the other from "ticks". These
are kernel timers with resolutions XXX
Entropy Count
The add_timer_randomness() call also increases the global "entropy_count",
which is used to limit the number of random bytes emitted by the blocking
random reads. (We ignore nonblocking access, where estimated entropy is
ignored. In this case, /dev/random is just a
PRNG and not cryptographically strong.) Add_timer_randomness() makes two
calls to add_entropy_word(), which quickly stirs the entropy pool with a
LFSR variant.
Entropy Estimation
It is this "entropy_count" estimate that I examine. The entropy count
controls the "compression" or "distillation-factor": for every 32 bits
(plus two timers) passed to add_timer_randomness(), we emit N bits. The
minimal entropy_count increment is 2.
More bits may be allowed depending on the size of the smallest of the last
two time deltas. A crude log (base 2) of the smallest delta (actually,
half the smallest delta, don't know why) is added to entropy_count. For
instance, suppose the smallest delta is 1. Then no extra output bits are
allowed. But if the smallest delta is tens of thousands of clocks, then
dozens of *output* bits will be permitted by this single interrupt.
This looks generous. The entropy estimation also fails to take into
account periodicity, ie, if delta is close to last_delta.
Suggestions
The code in add_timer_randomness() could easily be changed, however, this
code is executed during kernel interrupt handling, so what you can do there
is limited. The entropy-estimating portion of add_timer_randomness() could
be removed; better to err conservatively here.
If necessary, the size of the random pool could be enlarged. (The maximum
entropy_count is the size of the pool, in bits.) This is essentially an
entropy caching strategy. However, the extract_entropy() runtime depends
on the pool size: the MD5 function is run POOLSIZE/16 times for each 16
bytes output. Also, you would have to choose a different polynomial (the
taps) in add_entropy_word().
Other strategies include acquring more data, see Gutmann on Stronger PRNGs
where system data structures (heaps, performance counters, etc.) are mined.
Or using a higher bandwidth cheap physical sources, e.g., a media stream.
You could also xor N /dev/random bits for every bit of "true" entropy that
you want, where N depends on how much entropy you think is *really* there.
With this technique you could even assume fractional-bits per interrupt.
This way you can override the assumptions built
into the kernel without kernel mods.
Although this seems paranoid, the raw entropy input has not been
characterized.
Therefore, one is subject to the hazard of overestimating input uncertainty.
NB: to measure the entropy of the actual raw input to /dev/random, you'd
modify add_entropy_word(r,num) to store "num" somewhere; eventually dump
the stored values to a file for analysis. Or you could implement MUST in
that function; but be careful, this is interrupt processing.
Distribution: Unlimited
Security Implications: Well, duh. :-) MD5 hides a lot.
----- End forwarded message -----
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-security" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.LNX.3.95.iB1.0.990413153020.29155A-100000>