Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:26
David R. Conrad (drc@adni.net)
Mon, 8 Feb 1999 06:05:17 -0500 (EST)
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On Sun, 7 Feb 1999, bram wrote:
> In the midst of all the confusion about acronyms, I'm going to use the
> following term for this post:
>
> hamster - a creature who's entire purpose in life is to eat and poop, for
> example a cryptographically strong continuously seeded pseudo random
> number generator.
>
> On Sun, 7 Feb 1999, David R. Conrad wrote:
>
> > * /dev/random ... will only return a maximum of the number of
> > * bits of randomness (as estimated by the random number generator)
> > * contained in the entropy pool.
>
> Nothing particularly strange there ...
>
> > * The /dev/urandom device does not have this limit, and will return
> > * as many bytes as are requested. As more and more random bytes are
> > * requested without giving time for the entropy pool to recharge,
> > * this will result in random numbers that are merely cryptographically
> > * strong. For many applications, however, this is acceptable.
>
> Well, it will behave that way when it's replaced with a hamster, anyhow. I
> wonder what 'cryptographically strong' trickery is in the code for urandom
> right now.
As I understand it, and from *briefly* looking over the code, both devices
work from the same entropy pool. They obtain entropy from keyboard and
mouse events, interrupt timings, and timing the finishing times of block
requests. Also, from anything written to either device. They mix this
entropy into a pool using polynomials (see below), and maintain an
estimate of the current number of bits of entropy that the pool contains.
When they are asked to return random bits, they apply SHA-1 to the pool,
do some mixing of the pool so that it'll never return the same thing
twice, and decrement the count of bits in the pool as appropriate. Thus,
you can't directly control the bits in the pool by writing to it, and you
can't learn the state of the pool by reading from it.
If reading from /dev/random and the number of 'good' bits in the pool is
too low, it blocks until it gets enough bits. But if you're reading from
/dev/urandom, it'll keep hashing and mixing the pool to produce output.
This relies on SHA-1 and the mixing functions, which is why they say that
it's 'cryptographically strong'.
So, as you can see, it is already a 'hamster' (ASPRNG). But it may not be
as nice a hamster as Bruce Schneier's Yarrow, and there is apparently some
talk of replacing the current driver with one based on Yarrow.
> This introduces an interesting dilemma - if you're going to hamsterize the
> linux random code, should you replace /dev/random, or should you stick to
> what the documentation says and just replace /dev/urandom? I'd say the
> former, since most applications read from /dev/random and they *never*
> really need 1 bit of 'real' entropy per 1 bit of output (The
> cryptographically strong substitution is indistinguishable so long as the
> amount of entropy in the pool is sufficiently high.)
As I said, the linux random code is already a 'hamster' (ASPRNG) to an
extent that should be sufficient for most purposes.
> Unfortunately, neither random nor urandom is documented as possibly
> encountering an IO problem when there just plain isn't any entropy around,
> which is a behavior one certainly might want.
Well, what is real entropy? Do you mean from a physical source? I
believe someone suggested a /dev/prandom for such a purpose, if a system
had an actual physical source of random bits. In any case, I'm sure there
is quite a lot of randomness in the timings of my keystrokes as I type
this, so I feel comfortable trusting /dev/(u)random on my system. And
there is a simple method for carrying entropy over across reboots.
Lastly, I said "(see below)" above when referring to the mixing functions
used by the linux random driver. Here are a few more quotes from the
source code, giving more details on the internals:
#define POOLWORDS 128 /* Power of 2 - note that this is 32-bit words */
#define POOLBITS (POOLWORDS*32)
/*
* The pool is stirred with a primitive polynomial of degree POOLWORDS
* over GF(2). The taps for various sizes are defined below. ...
They provide "taps" for up to POOLWORDS == 2048, BTW.
* For the purposes of better mixing, we use the CRC-32 polynomial as
* well to make a twisted Generalized Feedback Shift Reigster
Some other interesting comments just after this point, but I don't want to
quote too much as I'm not sure how many readers are still interested at
this point. Besides, the source is available if anyone wants to read it.
* This function adds a byte into the entropy "pool". ...
* The pool is stirred with a primitive polynomial of the appropriate degree,
* and then twisted. We twist by three bits at a time because it's
* cheap to do so and helps slightly in the expected case where the
* entropy is concentrated in the low-order bits.
- From extract_entropy():
* First, this feeds the output back into the pool so
* that the next call will return different results.
* Any perturbation of the pool's state would do, even
* changing one bit, but this mixes the pool nicely.
I was fascinated to discover that there are a number of configurable
options. First, the POOLWORDS, which as I said can be increased up to
2048 from the default of 128, second, several unrolled versions of SHA-1
which make size/speed tradeoffs (or you can even use MD5 rather than
SHA-1, not that you'd want to), and, finally, ROTATE_PARANOIA which seems
to add some rotates to the mixing function if it is defined (it is not by
default). Does anyone have more info on that one?
David R. Conrad <drc@adni.net> PGP keys (0x1993E1AE and 0xA0B83D31):
DSS Fingerprint20 = 9942 E27C 3966 9FB8 5058 73A4 83CE 62EF 1993 E1AE
RSA Fingerprint16 = 1D F2 F3 90 DA CA 35 5D 91 E4 09 45 95 C8 20 F1
Note: Due to frequent spam abuse, I accept no email from *.da.uu.net.
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBNr7FHYPOYu8Zk+GuEQItoACgu44WVGQh6aYK5QUHeVuIXiTObksAoO3W
F9h5fBGOe+Ky77/JFNH/y2CR
=TDW3
-----END PGP SIGNATURE-----
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:26