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:27
bram (bram@gawth.com)
Wed, 10 Feb 1999 14:11:10 -0800 (PST)
On Wed, 10 Feb 1999, David R. Conrad wrote:
> On Mon, 8 Feb 1999, bram wrote:
>
> > On Mon, 8 Feb 1999, David R. Conrad wrote:
> >
> > > 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.
> >
> > Ah, but there's a chance you can. There's an attack on hamsters where you
> > can get them to repeat the same output over and over again by sending them
> > messages with a specific pattern. RSAREF is similar to the above except it
> > uses addition instead of polynomials, and a number of people have figured
> > out a rather practical attack on it. There's probably a similar attack on
> > using a polynomial mixing function.
>
> References?
The only one I know of is at
http://www.counterpane.com/pseudorandom_number.html
I think this topic hasn't been addressed much in the literature, although
it has been discussed a fair amount on this list.
> > There's another whole piece which is missing as well. You never ever want
> > to add entropy of only a bit or so directly to the pool, because that
> > would allow for continuation attacks.
>
> Here I get to reveal my ignorance; what's a continuation attack? I can't
> find this term in AC2 or the Yarrow docs.
A continuation attack is where the attacker has already breached security
and discovered the internal state of the hamster, then continues to be
able to deduce the internal state of the internal state of the hamster
despite new entropy being added.
For example, say you make the mistake of mixing in information with only a
single bit of entropy into the pool. Note that the length of the
information has little to do with the amount of informaiton in it - if you
pick randomly between mixing in the encyclopedia brittanica and webster's
unabridged, there are still only two possibilities, hence only one bit of
entropy. If the attacker knew the previous state of your pool, she could
now simply read out some purportedly random numbers, and check each of the
two possibilities to see which one would have yielded the given result. As
a result, she can deduce what the current internal state of the hamster is
and what it's output will be in the future.
> > Come to think of it, there's a bit of an implemention question here - the
> > API for adding to the pool should really include information about how
> > much entropy is in the data being added....
>
> I'm not sure, but I suspect it doesn't trust the bits it's fed to contain
> any entropy, and only trusts the keyboard/mouse/etc events to have some
> predefined number of bits per event.
That might be perfectly reasonable behavior, although it would be good to
also have a system call which you could pass an array and an amount of
entropy, to make it easier to write drivers for 'real' entropy sources.
> > The I/O problem possibility I was talking about was one of API - if
> > /dev/random doesn't have enough stuff in the pool, it blocks, but you as a
> > developer might want to view insufficient entropy as a very serious
> > problem and fail immediately instead of blocking until such time as
> > entropy might become available.
>
> Erm, couldn't you just look for this with select(2) and/or O_NONBLOCK and
> then handle as necessary? You might even be able to do something similar
> in Java with java.io.FileInputStream.available().
I'm unfamiliar with all the different calls for file reading using C in
UNIX, so I'll talk about the Java case, which I actually know something
about.
I've found available() to be largely advisory - just because available()
says a certain amount is there doesn't mean that amount will actually be
read next time you try reading, and just because available() said only a
certain amount was there doesn't mean more won't be read. The main thing
you use available() for is to find out when you've hit EOF (it returns -1
at that point.)
One *could* make it so that for the random input stream it would return
Integer.MAX_VALUE if there was entropy available and 0 if there wasn't,
but there's a (brief) period of time between when available() and read()
get called, and the available entropy could expire during that time
(if, for example, you have a policy that reseeding needs to occur with a
certain frequency.) The IOException mechanism has all the implementation
benefits of exceptions in general, and works atomically as well.
> > If you're using SHA-1, there's no point in having a pool of more than 160
> > bits, since that's how much output SHA-1 gives anyway.
>
> Huh? Why would you want to limit the pool in this way? Then it could
> never return more than 20 bytes without blocking.
If you're using Yarrow, after you spit out the first 20 bytes, you re-mix
the internals of the pool using SHA1 (and a little appending trick) and
spit out another 20 bytes, then remix the pool again ...
> I think limiting the size of the pool to 160 bits is an amazingly bad
> idea. IMNSHO.
This is similar to why it's not beneficial to have symmetric key lengths
in the thousands of bits - if SHA1 could be inverted, the hamster could
probably be broken, and since you only need 2^160 computing power to do
that, there wouldn't be much benefit in making 2^300 computing power be
necessary to guess the internal state of the pool.
160 bits of entropy would be enough to power the entire world for many
years to come. As long as you have that much, you could continue spitting
out random numbers pretty much forever. Re-seeding is really just done to
stop continuation attacks.
-Bram
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:27