[boost] Re: Proposal: random number library

From: Mark Borgerding (mborgerding_at_[hidden])
Date: 2000-02-18 11:58:36

"greg colvin" <gcolvi-_at_[hidden]> wrote: 
original article:http://www.egroups.com/group/boost/?start=2198
> From: Mark Borgerding <mborgerding_at_[hidden]>
> > ...
> > Just an observation about random_device -- if you use buffering, you
> > may get higher throughput for your benchmark tests, but I think
there
> > are a couple of reasons it is a bad idea to use
ifstream("/dev/random")
> > , or FILE* with /dev/random
> > 
> > 1) Responsiveness -- a class user who only wants a single byte would
> > need to wait for the entire buffer to fill (this will likely be
several
> > K).
> > 2) Loss of system entropy -- randomness is gathered fairly slowly,
> > filling up a buffer with random data that is not really needed will
> > quickly drain the entropy pool.
> 
> Yes, but if you can do it when otherwise idle it might store up
entropy
> for when you need it.

But /dev/random is not a normal file.  Bytes read from it into a
fstreambuf will never be used again.  So creating a a random_device
that uses an ifstream could waste almost an entire buffer of random
data.

> 
> > Using /dev/random is great for systems that have it, but what about
the
> > other systems?  What do you think of adding a default random_device
> > implementation for systems that do not have /dev/random?  The
following
> > is platform-independent code, but unfortunately the quality of the
> > numbers it creates is somewhat platform dependent.  Perhaps it can
be
> > improved.  The idea is based upon an algo from Schneier's Applied
> > Cryptography.  Count until some system parameter changes (e.g.
clock()
> > ), and then use the lsb of the counter as a random bit.
> > 
> > unsigned char rand_byte(int nbits)
> > {
> >    unsigned char result = 0;
> >    if (nbits>8)
> >       nbits=8;
> > 
> >    for (int i=0;i<nbits;++i) {
> >       unsigned int counter=0;
> >       clock_t start = clock();
> >       do {
> >          ++counter;// keep counting until the clock changes
> >       }while (start == clock());
> > 
> >       result <<= 1;  // left shift 1 bit
> >       result |= (counter&1);
> >       // put the LSB from the counter into the LSB of the result
> >    }
> >    return result;
> > }
> 
> Have you tested this against any of usual tests for randomness?
> I suspect that on an otherwise unloaded system this might be not
> too random.
> 
> A non-standard but useful test is just to feed the output to a
> compression program like pkzip or gzip and see it gets smaller.

It takes a long time to get enough data for the diehard tests, but
preliminary test seem okay. 

With a ~30k file from the above method: 
"gzip --best" inflated the data by .7% 
"bzip2 --repetitive-best" inflated the data by 1.6%.
There is a slight bias toward zero bits P(1) = 0.492
The average of the average entropies for words between 1 and 16 bits is
Ae=0.9980358309 .  This is okay, but I'd like to see it much closer to 1

These numbers were obtained on a p233 linux box that was idle except
for seti_at_home running at nice 19.

Since the behavior of process scheduling and clock() is platform
dependent, there is no guarantee that other platforms would behave this
well.

If anybody wants the code or data files, email me directly
mborgerding_at_acm.org.

> 
> > Another idea (not sure where I heard it first, maybe Schneier also)
is
> > to have a rng that the user can churn with randomness from the
system. 
> > This randomness would get added into the mix.
> > 
> > This won't compile, since it depends upon having some hash function
> > class.
> 
> Another candidate for Boost -- I think there are some MD5
implentations
> in the public domain.

Many countries still have some pretty strict crypto laws.  I think we
should think carefully before putting crypto into boost.  This niche
may already be filled by the cypherpunks.  

I live in the US and I don't feel like being a civil disobedient, so I
cannot write anything for general export stronger than an egg
scrambler. 

The are some good pd libraries out there.  Wei Dai has a pretty
unencumbered one called crypto++.  http://www.eskimo.com/~weidai/cryptl
ib.html
It seems to be pretty platform indy, he has a breakdown on his webpage.

Nikos Mavroyanopoulos has mcrypt(GPL), libmcrypt(LGPL), and shash(GPL).
I like mcrypt a lot, it has just about every cipher I've ever heard of
and allows default algos to be specified by environment variables.

There may be others, but I am only familiar with these two.

Mark