-----BEGIN PGP SIGNED MESSAGE-----
[ To: Sandy Harris, Perry's Crypto List ## Date: 07/12/99 ##
Subject: Re: Yet another random number generator ]
>Date: Sun, 11 Jul 1999 13:10:56 +0000
>From: Sandy Harris <[EMAIL PROTECTED]>
>To: [EMAIL PROTECTED]
>Subject: [long] Yet another random number generator
>Proposal:
>
>Could we do a large part of this with a fairly simple chip,
>all digital, without diodes etc.? A system bus has typically
>at least 32 data and 32 address lines plus a bunch of
>control signals. Perhaps 80 bits that can be sampled at
>perhaps 100 MHz. 10 Mbytes/sec. Crunch that down to 10K
>highly random bytes?
>
>Some bits have dreadful entropy of course: e.g. on systems
>with under a gig of RAM, top two address lines are always 0.
>On any system, bottom two are usually 0 for aligned access.
>All ASCII characters have top bit 0, much numeric data is
>small integers, etc. Interrupt lines should spend most of
>their time in the non-asserted state.
So, if I understand correctly, the entropy is based on
everything that passes over the system bus, right? What is
the source of entropy when the system is quietly humming
away running the screensaver, while the user is downstairs
drinking his morning coffee? It looks to me like your
entropy will be *very* uneven.
Would this kind of sampling get TrueRand-type phase drift
between CPU clock and time clock? I can't see how. What
other sources of entropy would be available? (Maybe hard
drive timings for page swaps and such.)
>I have a crunching mechanism to propose. Nyberg showed that
>perfect s-boxes (all columns and all linear combinations of
>columns are bent boolean functions) can be built whenever
>there are twice as many input bits as output bits. Build a
>substitution-permutation network with perfect s-boxes.
Wait a second, here! Nyberg's perfect S-boxes can give you
provable security against standard differential and linear
attacks, but I don't see why this is relevant, here. We're
trying to crunch this huge stream of data down into a
fixed-length buffer, presumably with some kind of arguments
for entropy-preservation. We don't care much here about
an attacker controling our inputs--he would have to be in
control of our system bus!
Anyway, I think your entropy-gathering proposal ought to be
kept separate from the crunching mechanism. I claim that we
can design a reasonable crunching mechanism using existing
components, probably block ciphers or hash functions. Is
there a reason why (say) treating the buffer as circular,
and continually processing inputs by XORing them into the
buffer, and then CBC-mode encrypting the resulting blocks
with a fixed key, wouldn't suffice?
>Details would depend on analysis of input entropy (how much
>crunching is needed) and of target chip technology (what is
>pratical) but it might look something like:
Wouldn't the entropy on the system bus vary depending on
what was going on? I mean, if I get to load all the
software onto your machine and have you start it up and run
it, there won't be much going over the system bus that will
be of much interest. (Maybe you'll get phase jitter between
the CPU clock and the RNG's clock.)
[ Lots of design ideas deleted.]
>Comments?
The entropy collection method is interesting. The crunching
method is interesting. It seems like they are more-or-less
independent, though.
- --John Kelsey, Counterpane Internet Security, [EMAIL PROTECTED]
NEW PGP print = 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>
iQCVAwUBN5AqUSZv+/Ry/LrBAQGUUgP+LWIqCZ8JDuYmO3M/d8f1/JhgFAm3c7xp
lXTiMz2VgYfGS3ohY3mreEcOF1+Tw3tnGM+5hDIY4070ItD3d7iSG5+cNTvriWGn
tKixWWBNR9PPrjSKxyE5RwBih/Zc/eqW17aUi9jeeh5wuyCLB+gGOtOsUl88NF9D
/+YoShdtP68=
=WiyW
-----END PGP SIGNATURE-----
