Randomness

[Ben Laurie]

Bill Frantz wrote:
> 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.

If you really only have 1 bit of entropy, then you're dead anyway, but
this is one good reason to mix your entropy before deriving an IV from
it (which is the usual practice anyway).

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