Greg,
Thanks so much for the help - I learn just a tad with every message on this
thread, and I truly do appreciate the help. Like Lenny noted, it's pretty
important that I get this right, as I'm dealing with healthcare data.
I tried a simple test to experiment with the code you sent me, and to make
things go faster (knowing that it would not yield good results) I took out
the Sleep calls. Of the 65,536 samples taken, over 65,000 were either 4, 5,
or 6, with a few scattered samples at other values. The thing says I have
something like 750 bits of entropy! What gives?
-----Original Message-----
From: Gregory Stark [mailto:[EMAIL PROTECTED]]
Sent: Thursday, June 22, 2000 2:46 PM
To: Bill Rebey
Cc: Gregory Stark
Subject: Re: Cipher question...
Bill,
First of all, don't be discouraged; the problem of getting a good seed
for a randomizer is very difficult. Many applications out there solve the
problem by doing a lousy job. I commend you for asking your questions so out
in the open.
Secondly, randomness is very hard to judge 'bye eye'. It is also very
hard to do by experiment in cryptography because so many bits of randomness
are needed. It is not enough, but still very expensive, to verify by
experiment that your seeding algorithm has at least 64 bits of entropy. It
is better to find out by experiment how much entropy is in some atomic event
and then analyze whether successive samples of this event are independent.
If you are lucky and/or smart, you will find a way to sample multiple
independent events to create your seed.
Thirdly, a common mistake is to attempt to use only a few bits from each
sample. You use 1 bit in your case. The correct way is to use all the bits
in the data and run a secure hash over them.
Here are some concrete examples of what I mean.
Atomic random events: The value of the Windows performance counter after
a call to Sleep(2).
Experiment: Estimate how many bits of entropy are in this event by
something like the following program:
#define LEN 65536
unsigned counts[LEN];
unsigned i;
double entropy = 0.0; // entropy in bits
LARGE_INTEGER start, finish;
for(i=0; i<LEN; i++) counts[i] = 0;
for(i=0; i<LEN; i++) {
unsigned diff;
Sleep ( 5 ); // Allow things to 'settle'
QueryPerformanceCounter ( &start );
Sleep ( 2 );
QueryPerformanceCounter ( &finish );
// diff = (unsigned) (finish - start); // this may be slightly
more difficult depending on the compiler; use __int64 on VC++
if (diff >= LEN) {printf("Difference bigger than expected, use
a different entropy estimator algorithm\n"); exit(1);}
counts[diff]++;
}
for(i=0; i<LEN; i++) {
if (counts[i] > 0) {
double prob = (double) count[i] / ( (double) LEN);
entropy += -log(prob) / log(2.0);
}
}
printf("Entropy estimate is %f bits\n", entropy);
}
The above code makes a number of simplifying assumptions but may work.
Now suppose the above experiment showed there were 10 bits of entropy in the
event. Then you could hope that by collecting 13 events, you would have 130
bits of entropy. Alas, there is no way to guarantee this because subsequent
events my be dependent on prior ones. You need to do more experimentation
and analysis, but this should give you a start.
Finally, instead of masking off the low bit of the value of the
performance counter, just hash the whole thing into a running SHA1 hash
object (I don't know right now how you'd do this in openSSL), something like
SHA1 hashSeed;
SHA1Init ( &hashSeed );
... // code snipped out here
QueryPerformaceCounter ( &val );
SHA1Update( &hashSeed, val, sizeof(val) );
Sleep (2);
QueryPerformaceCounter ( &val );
SHA1Update( &hashSeed, val, sizeof(val) );
...// more code snipped here
SHA1FinishHash ( &hashSeed );
// now extract the seed from the 20 byte array hashSeed.hash[] or
whatever it is called
Oh, and take out the Random() call from inside the Sleep() function. It
probably adds nothing buts makes everything harder to analyze.
Greg Stark
Chief Security Architect
Who?Vision Systems, Inc.
[EMAIL PROTECTED]
----- Original Message -----
From: "Bill Rebey" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Thursday, June 22, 2000 12:40 PM
Subject: RE: Cipher question...
> Brian (et al),
>
> Here's what I'm doing. I'm using the RTL's random number generator in
this
> thing, but what I'm counting on more than the randomization of the Sleep
> times is the fact that Windows takes a different amount of time to
complete
> each system call, code segment, etc. (and hence each Sleep) due to time
> slicing, interrupt handling, or whatever else causes such discrepancies.
> I've run many batches of 100 of these seed algorithms and collected and
> compared the results and they produced a pretty reasonable distribution of
> apparently random data.
>
> Because of the uncertainty about the amount of time it takes a given set
of
> instructions to complete, I think it would be very difficult for someone
to
> reproduce the results, even if they knew this algorithm, the RTL
randomizer
> algorithm, and even the RTL randomizer seed (thus reproducing the exact
same
> "random" sequence of Sleep times that I did when I generated the seed
data).
>
>
> In fact, to test this theory, I changed all of these to just "Sleep(1)"
(no
> random sleep time) to remove the RTL randomizer from the equation
> altogether, and the results from consecutive trials are very different and
> appear just as random and unpredictable.
>
> As far as the Performance Timer itself goes, it's standard - you have it.
>
> If anybody sees any fundamental flaw in this, I would appreciate another
> heads up to alert me to the folly of my ways. I like it because it runs
in
> just a few seconds on a 500MHz PIII with NT4 and I can make it part of my
> startup code so that it's different every time without taking forever to
> start up. Does this work, or am I in the weeds again? (Snake-Oil the
> Sequel?)
>
> Thanks!
>
> unsigned char seed[64];
> randomize ();
>
> for (int ii = 0; ii < 64; ii++)
> {
> LARGE_INTEGER val;
>
> // use only the low bit 8 times over instead of
> using all 8 at once
> QueryPerformanceCounter (&val);
> seed[c][ii] = (unsigned )(val.LowPart & 0x01) << 7;
> Sleep(random(2));
>
> QueryPerformanceCounter (&val);
> seed[c][ii] |= (unsigned )(val.LowPart & 0x01) << 6;
> Sleep(random(2));
>
> QueryPerformanceCounter (&val);
> seed[c][ii] |= (unsigned )(val.LowPart & 0x01) << 5;
> Sleep(random(2));
>
> QueryPerformanceCounter (&val);
> seed[c][ii] |= (unsigned )(val.LowPart & 0x01) << 4;
> Sleep(random(2));
>
> QueryPerformanceCounter (&val);
> seed[c][ii] |= (unsigned )(val.LowPart & 0x01) << 3;
> Sleep(random(2));
>
> QueryPerformanceCounter (&val);
> seed[c][ii] |= (unsigned )(val.LowPart & 0x01) << 2;
> Sleep(random(2));
>
> QueryPerformanceCounter (&val);
> seed[c][ii] |= (unsigned )(val.LowPart & 0x01) << 1;
> Sleep(random(2));
>
> QueryPerformanceCounter (&val);
> seed[c][ii] |= (unsigned )(val.LowPart & 0x01);
> Sleep(random(2));
> }
>
> RAND_seed (seed, sizeof (seed));
>
>
> -----Original Message-----
> From: Brian Hatch [mailto:[EMAIL PROTECTED]]
> Sent: Thursday, June 22, 2000 10:01 AM
> To: Bill Rebey
> Subject: Re: Cipher question...
>
>
>
> > I've changed my original snake-oil RNG seed generator to use the results
> of
> > the Window Performance Counter (a very high resolution clock). The
trials
> > that I've run and compared side by side appear to generate a pretty good
> > mess of data that doesn't appear to offer up any sort of patterns or
> > consistency.
>
> Don't suppose you'd like to let the rest of us in on what
> you're using now, eh? Is 'windows performance counter'
> something extra, or does it come with all versions of windows?
>
>
>
> --
> Brian Hatch Email returned
> Systems and to sender --
> Security Engineer insufficient
> http://www.ifokr.org/bri/ voltage.
>
> Every message PGP signed
> ______________________________________________________________________
> OpenSSL Project http://www.openssl.org
> User Support Mailing List [EMAIL PROTECTED]
> Automated List Manager [EMAIL PROTECTED]
>
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
