EDP (entropy distribution protocol), userland PRNG design

Travis H. solinym at gmail.com
Wed Oct 12 05:49:43 EDT 2005

I am thinking of making a userland entropy distribution system, so
that expensive HWRNGs may be shared securely amongst several machines.
 Here's the algorithm from generation to use:

1) Entropy harvested from HWRNG.

2) Entropy mixed with PRNG output to disguise any biases present in
source.  The Mersenne Twister suggests itself due to its extremely
long period.  (Is XOR sufficent and desirable?)

3) Entropy used as "truly random" input in an extractor to map
"somewhat random" input (interrupt timing, memory contents, disk head
settling times) into "strongly random" output.

4) Entropy passed through OWF to occlude state of previous systems in
this chain.

5?) Entropy ciphered with a randomly-generated key (taken from the
previous step), rotated periodically.

6) Entropy transmitted over the network.

7) Recipient ciphers the entropy with a randomly-generated key,
rotated periodically.  The randomly-generated key is taken from the
output of step 8 so that data on the wire is never used directly to
cipher future data sent over the wire (requiring an attacker to be
able to accurately model step 8).

8) Recipient repeats steps 2-4 locally.

9) Entropy is used in an application needing it.

Here's my claims:

1) There is no key distribution to worry about.

2) Eavesdropping only gets you known-ciphertext.  You still have no
idea about the plaintext, which is random, so you have no general way
to recognize a successful brute-force attempt on the
randomly-generated key used by the recipient.

3) You'd have to figure out how some part of the transmitted data was
used by the recipient, and work forward with each trial key to see if
the results match in order to recognize a successful guess at the key
used in step 7.  Would re-ordering data randomly on the recipient be
useful to thwart this, or is it unnecessary?

4) The most effective way to compromise such a distribution system
that I can think of would involve cracking the recipient system, and
if the enemy can do that, no crypto can help you.

I deliberately used the term cipher instead of en/decrypt because I am
not sure it matters which direction we go, as long as it doesn't
introduce any detectable statistical biases in the entropy (weakening
it).  What properties should I look for, and what level of assurances?

Can you see any weaknesses or unnecessary steps in this model?  I'm
not sure 5 is necessary (it was just suggested by symmetry).

Regarding the userland PRNG daemon, I was thinking of replacing  the
/dev/urandom functionality with a userland daemon, because:

(a) cryptographic operations can be slow, and putting them in the
kernel, which cannot block, is not desirable
(b) development is easier, this will encourage people to tinker with it more
(c) having the kernel perform HTTP requests to get random numbers from
web sites is inappropriate

What I want to do is:

1) Mix various sources of "untrusted" entropy in such a way as to make
a strong claim as to the mixture.  For example, these web sites offer
free random numbers:


Why shouldn't I download some numbers from these sites periodically,
and combine them with the pool?  I don't have to update the entropy
count (indeed, this is a PRNG and so tracking "actual" entropy is
somewhat irrelevant).  The way I see it, if I XOR numbers from these
sites with my PRNG output, even if an attacker eavesdrops on this
traffic, I'm no worse off than if I hadn't used them at all. 
Unpredictability XORed with predictability is still unpredictable.

Similarly, I also would like to use ID Quantique's HWRNG based on
optics, but their modules are sealed and opaque.  What I want to do is
explore what kind of assurances I can make about the output, based on
assumptions about the attacker's ability to control, predict, or
observe one of the sources.

2) Occlude common biases in the HWRNG, which is the main input to the daemon.

3) Combine PRNG components in novel ways.

4) Create a plug-in framework for PRNG components.

5) Do it in a language not as prone to security-relevant errors as C
and containing support for large numbers and bitstrings as first-class
objects.  I'm leaning towards python, heard good things about ruby,
and open to suggestions that something very different like ocaml might
be better.

Stumbling blocks that I can see:

1) Lack of standardization in the naming or semantics of kernel
facilities, such as the names of devices in /dev.

2) Lack of support for sockets in the target language.

3) The use of ioctls for interfacing to sources of entropy in the kernel.

4) The use of tty devices to interface to HWRNGs

5) Multiple clients petitioning the daemon for random bits at once. 
However, this is also a good thing; two consecutive values used by a
client may not be consecutive outputs from the PRNG subsystem.

http://www.lightconsulting.com/~travis/  -><-
"We already have enough fast, insecure systems." -- Schneier & Ferguson
GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

More information about the cryptography mailing list