Randomness

[Bill Frantz]

At 1:26 PM -0700 5/7/03, 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 relation between this mode of PRNG and IVs has been eating away at my
brain.  Let me try an analysis:

Under our assumptions, a one bit change in the seed will change about half
the bits of the output of the mixing process.  Given that there is feedback
in the mixing process, so these differences continue to influence the
output, the one bit difference should be enough to get probabilisticly
different UUIDs.

In the case of the one bit different IV, we must consider the case where
the plaintext also has a single bit difference, and in the same bit
position.  (This situation might occur if the plaintext starts with a
message serial number in ASCII.)  In this case, the XOR if the IV and the
plaintext block followed by encryption will result in the same cyphertext
block.  Since that cyphertext block is the "IV" for the next block of
encryption, this error allows an attacker to determine where the messages
first differ, an unpleasant wedge into the crypto system.

Cheers - Bill


-------------------------------------------------------------------------
Bill Frantz           | Due process for all    | Periwinkle -- Consulting
(408)356-8506         | used to be the         | 16345 Englewood Ave.
frantz at pwpconsult.com | American way.          | Los Gatos, CA 95032, USA



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