[Date Prev][Date Next]
[Chronological]
[Thread]
[Top]
Re: DIGEST-MD5 and {nonce,cnonce}
Mihai Ibanescu wrote:
> On Mon, 25 Oct 1999, Kurt D. Zeilenga wrote:
>
> > At 09:01 PM 10/25/99 +0300, Mihai Ibanescu wrote:
> > > Okay, I already have seen propositions on some options
> > >(/dev/random, which seems the most reliable, and a PRNG started with a
> > >seed derived from gettimeofday, all of them hashed with MD5 or something
> > >like that). Any other alternatives?
> > > I'd like to implement it.
> >
> >
> > If you hash the value read from /dev/random, you will LOSE entropy.
> > That is, you could read 128 bits of entropy from /dev/random.
> > Hashing it to a 64-bit quanity will result in at least half these
> > bits being lost. Even where you read exactly 64-bits from /dev/random,
> > hashing the value can only reduce the amount of entropy.
>
> Yes, but this is a quote from
> /usr/src/linux/drivers/char/random.c, the source for /dev/random:
>
> Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998
> ...
>
> * Computers are very predictable devices. Hence it is extremely hard
> * to produce truly random numbers on a computer --- as opposed to
> * pseudo-random numbers, which can easily generated by using a
> * algorithm. Unfortunately, it is very easy for attackers to guess
> * the sequence of pseudo-random number generators, and for some
> * applications this is not acceptable. So instead, we must try to
> * gather "environmental noise" from the computer's environment, which
> * must be hard for outside attackers to observe, and use that to
> * generate random numbers. In a Unix environment, this is best done
> * from inside the kernel.
> *
> * Sources of randomness from the environment include inter-keyboard
> * timings, inter-interrupt timings from some interrupts, and other
> * events which are both (a) non-deterministic and (b) hard for an
> * outside observer to measure. Randomness from these sources are
> * added to an "entropy pool", which is mixed using a CRC-like function.
> * This is not cryptographically strong, but it is adequate assuming
> * the randomness is not chosen maliciously, and it is fast enough that
> * the overhead of doing it on every interrupt is very reasonable.
> * As random bytes are mixed into the entropy pool, the routines keep
> * an *estimate* of how many bits of randomness have been stored into
> * the random number generator's internal state.
> *
> * When random bytes are desired, they are obtained by taking the SHA
> * hash of the contents of the "entropy pool". The SHA hash avoids
> * exposing the internal state of the entropy pool. It is believed to
> * be computationally infeasible to derive any useful information
> * about the input of SHA from its output. Even if it is possible to
> * analyze SHA in some clever way, as long as the amount of data
> * returned from the generator is less than the inherent entropy in
> * the pool, the output data is totally unpredictable. For this
> * reason, the routine decreases its internal estimate of how many
> * bits of "true randomness" are contained in the entropy pool as it
> * outputs random numbers.
>
> My point here is that I should hash the content, not for the
> entropy's sake, but to hide the real contents of /dev/random, just in
Umm, from reading the above and looking at the code, I understand that this
hash is already perform for you. No need to hash it again.
>
> case... AFAIK SHA1 is a 128-bit hash, and after all I can diversify the
SHA1 is a 160 bit hash, MD5 is 128 bit.
>
> generation (have no idea about SHA1, but with MD5 I can do something like:
>
> int lutil_entropy(char *buf, int nbytes)
> {
> struct lutil_MD5Context ctx;
> int i, retval;
> int rndfd;
> struct timeval tval;
> char digest[16];
> char buffer[16];
> /* I won't initialize digest[], this may be a source of randomness */
>
> for (i = 0; i <= nbytes / 16; i++) {
> lutil_MD5Init(&ctx);
> lutil_MD5Update(&ctx, digest, 16);
> rndfd = open("/idev/urandom", O_RDONLY);
> if (rndfd < 0)
> rndfd = open("/idev/random", O_RDONLY);
> if (rndfd > 0) {
> retval = read(rndfd, buffer, sizeof(buffer));
> lutil_MD5Update(&ctx, buffer, retval);
> close(rndfd);
> }
> retval = gettimeofday(&tval, NULL);
> if (retval == 0)
> lutil_MD5Update(&ctx, (char *)&tval, sizeof(struct timeval));
> lutil_MD5Final(digest, &ctx);
> memcpy(buf + 16 * i, digest, (16 * i < nbytes) ? 16 : nbytes - 16
> * i);
> }
> if (rndfd > 0)
> close(rndfd);
> return nbytes;
> }
>
> The idea is that I first try to read random bytes from
> /dev/urandom or /dev/random. I compute the digest and store it in the
> first 16 bytes of the result. The 16-bytes digest is used to further
> compute the next digest, with another call to a read from /dev/random.
> Just in case there is no /dev/urandom or /dev/random available, I append
> the result of gettimeofday(). While one call to gettimeofday() may be
> predictable, I assume a series of calls to gettimeofday are not that
> predictable anymore, since a context change may increase the difference
> between two calls.
> I cannot be sure how much randomness is in the method described
> above; however, I wrote 16383 bytes obtained via lutil_entropy and gzipped
> (-9); the result was 16411 bytes, which make me think the method is pretty
> reliable. The result was the same without reading bytes from /dev/random
> (just hashing the results of gettimeofday()).
> Since there is a SHA1 implementation in liblutil, I may change MD5
> to SHA1. This should be better, IMHO.
> If it's OK with you, I'll send the source.
>
> > Hashing should only be applied to values that have some entropy
> > but where you are unsure how the entropy is distributed within
> > the value. That is, a crytographic hash is used as a means to
> > extract bits of entropy from the input. You must, of course,
> > be sure not to assume the hash has more bits of entropy than
> > provided by the input.
> >
> > I would suggest that your initial implementation provide:
> > /dev/random
> > highly-portable fallback
> >
> > Others can then contribute codes which extend the implementation
> > to support other mechanisms.
>
> Cheers,
> Misa