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)
Mon, 8 Feb 1999 23:06:24 -0800 (PST)
On Mon, 8 Feb 1999, David R. Conrad wrote:
> 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.
> >
> > > * 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.
>
> 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.
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.
Yarrow is similar only it uses SHA1 for both deriving output and mixing
the internal pool. It keeps them from being exactly the same by appending
the previous bit of output to the pool's state before hashing to get the
next pool state, while it simply hashes the pool state unchanged for the
next chunk of output.
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. For that reason, you maintain a
separate entropy collection area outside the pool, and only mix it in when
the amount of entropy in it is large enough. I *think* the way yarrow does
this is that it has a collection area 160 bits long, and whenever it gets
some new entropy, it hashes it and xors the collection area with the
result. Whenever a sufficient amount of entropy has been added, it xors
the pool with whatever's in the collection area and resets the collection
area to all zeros. (That technique works just fine anyway, even if it
isn't what yarrow does.)
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 (it's very easy to have a string
which contains many fewer bits of entropy than it's length.) Probably the
easiest way to deal with this would be to have an assumed amount of
entropy in data fed into /dev/random - half a bit per bit, say. Of course,
this should be decided on and documented rather clearly.
Actually, the collection technique I mentioned above is designed for the
extremely pessimistic scenario of, say, being handed a 1 megabyte file and
being told it only contains 1 bit of entropy. A completely practical
scheme might be to assume each intput bit has at least a certain amount of
entropy, and allocate an array to put intput into it until there's enough,
at which point you hash whatever's in the array and xor the pool with the
result.
> > 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?
Yes.
> 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.
I think very few people have actually thought deeply enough about what
'random' means to be clear on the difference between something which is
'truly' random and something which merely contains enough bits of entropy
that it appears random. For that reason, I suspect that altering
/dev/random to behave as /dev/urandom is documented will draw complaints
from just about nobody. Further, I think a /dev/prandom just add confusion
for most people. It might, however, be a convenient implementation hook to
use - a little background process could be created whose sole purpose in
life would be to read from /dev/prandom and write the output to
/dev/random. (But it might introduce possibilities for a massive security
hole if you do something foolish like send all mouse events to
/dev/prandom.)
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.
It is true that this level of paranoia is possibly overkill for a desktop
machine operating under normal circumstances. If, however, you consider
the case where linux might be ported to an incredibly small device, the
possibility of entropy being hard to come by makes a lot more sense.
(Someone got a linux web server running on a device the sice of a matchbox
- yeesh.)
> 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)
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.
It's very good that there are some size/speed tradeoffs for SHA-1. It is
however a significant omission that RIPEMD-160 isn't supported.
(RIPEMD-160 and SHA-1 have the same block and output size, so either can
be used, and some people prefer RIPEMD-160 for political and technological
reasons.)
-Bram
(Who's been writing java for so long he has to stop himself from saying
'throws an IOException' whenever talking about an I/O problem.)
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:27