Randomness

[Ben Laurie]

Bill Frantz wrote:

> On Monday 05 May 2003 4:51 pm, Ben Laurie wrote:
> 
>>People might be interested in a paper I've written on randomness:
>>http://www.apache-ssl.org/randomness.pdf. Comments, as always, are more
>>than welcome.
> 
> 
> I assume the people who are using randomness to generate UUIDs are doing so
> in a distributed manner.  (If it was centralized, then a counter would
> provide better assurance of non-duplication.)  I am also going to assume
> that the seed they get from the secure random process which is used to
> support the "void insecureprng(void *out, int nbytes)" function is run
> through a cryptography strong mixing process like MD5 or SHA1.
> 
> The question is, does having only a few bits different in the seed between
> the various instances of the generator compromise the collision resistance
> of the generator?  If it does, how many bits do you need?  (This issue
> seems to me to be closely related to the issue of using a counter as an IV
> in CBC mode encryption.)

The collision resistance is indeed determined by the number of bits
different in the seed. However, sufficient entropy "ensures" (in a
random way) that there are not only a few bits different. In general, if
you want to generate 2^n different IDs, then the number of bits you need
is > 2n (how much greater is determined by how safe you want to be -
exactly 2n gives you about a 1 in 2 chance of a single collision).

> Given you have very little "conditional entropy" (random data unknown to an
> attacker), what is the best way to get "unconditional entropy" (random data
> that may be known to an attacker)?  Clearly time, which has very little
> "conditional entropy", also has a significant risk of duplication between
> two instances started nearly together.

Indeed. This is hard to evaluate without the knowing the properties of
the system. For example, if you happen to know that no two instances are
ever started in the same moment, then time is a fine source of entropy.

However, measurement of entropy is a different, and, IMO, thornier, subject.

> How do you protect against this risk?  Adding in IP address might yield a
> lot of 192.168.0.1s.  Ethernet MAC addresses seem to be good, but not all
> machines have Ethernet cards.

Ethernet MAC addresses are not a good source of entropy if you care
about privacy, as I note. This is because an adversary could potentially
show that your UUID was derived from your MAC address, by brute-forcing
the rest of the entropy.

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com