Re: new /dev/random

From: Bill Unruh (unruh_at_string.physics.ubc.ca)
Date: 10/11/04 

Date: 11 Oct 2004 16:59:48 GMT

s_vinder@mail.com (S. Vinder) writes:

]unruh@string.physics.ubc.ca (Bill Unruh) wrote in message news:<ckbk17$5af$1@nntp.itservices.ubc.ca>...
]> s_vinder@mail.com (S. Vinder) writes:
]>
]> ]unruh@string.physics.ubc.ca (Bill Unruh) wrote in message news:<cka1hv$fr1$1@nntp.itservices.ubc.ca>...
]> ]> s_vinder@mail.com (S. Vinder) writes:
]> ]> ]x = sample from a physical source (for instance, mouse movements);
]> ]> ]output = D(x) XOR x;
]> ]>
]> ]> ]This way the amount of entropy will not decrease even if the
]> ]> ]distillation function is (partially) flawed.
]> ]>
]> ]> Well, no. Say D(x)=x for some range of x.
]>
]> ]Well, if D() was for instance SHA-512, the probability you would get
]> ]D(x)=x is 2**-512 (which would hardly be something to worry about).
]> ]However, if this is a concern, the unwanted effect of zeroing the
]> ]output by XORing the same values can be eliminated by replacing XOR
]> ]with addition modulo 2**n (for a n-bit hash). Then, if you
]> ]modulo-added two identical values, the output would not be zeroed.
]>
]> What I was saying was that combining D with x in this way is NOT proven not
]> to decrease the entropy. It all depends on the behaviour of D. In the
]> modulo addition, if D for example produced -x modN, the again the output
]> would be zero. D=-xmodN would be a perfectly good function which can be
]> proven not to decrease entropy. But D(x)+x modN is a perfectly destructive
]> function.
]> If yuo really knew that SHA produced D(x)= x with that probablility, then
]> SHA could probably also be proven to be a good mixer function on its own,
]> without any additions. the problem is that that proof is not existant. It
]> is suspected that SHA produces uniform output from uniform input, but not
]> proven. It could be that SHA is contractile, and maps inputs of length say
]> 512 to outputs of effective entropy 64 bits. those 64 bits numbers could
]> themselves be uniformly distributed amongst the 512 bit numbers, so it
]> would not be at all obvious it was doing so. This is the concern that
]> people have about the mixer function in /dev/random. I think most, if they
]> had to put money on it, would bet that it does not do this.

](A true RNG *can* sometime produce all-zero strings too. There is
]nothing wrong with that.)

]If, instead of a hash function, we use a cipher we can safely assume
]that D(x)=x will not occur. If we assumed it *could* happen, we could
]not use AES for encryption. Therefore, for instance,

]output = AEShash(x) XOR x

]should be secure (should not reduce entropy contained in x, and should
]conceal possible patterns and correlations in x).

A cypher is one to one. A hash is not. A hash is known to destroy entropy,
a cypher is known to preserve it. The question with a hash is how much
entropy it destroys. Ie, give it say 2N random bits, is the output N random
bits, where N is the output size of the hash. Or is it N/2? How could you
tell?
I am not arguing that the hash sometimes produces strings such that xoring
with x will produce 0-- of course it would. The question is whether this is
true in general. For example it could be that the middle 7 bits of the
output of the hash are always the same as the input. Then D xor x would
always produce zeros there. All I was countering was your claim that xoring
with x could not decrease the entropy of the output of D(x). It can.

Relevant Pages

  • Re: new /dev/random
    ... ]output by XORing the same values can be eliminated by replacing XOR ... to decrease the entropy. ... SHA could probably also be proven to be a good mixer function on its own, ...
    (sci.crypt)
  • Estimating entropy of a stream
    ... I'm trying to set up a system to use audio static from a clock radio ... random number generator. ... I'm familiar with the general entropy ... to the output of the hash, then use the output as my random bits. ...
    (sci.crypt)
  • Re: Estimating entropy of a stream
    ... random number generator (getting that static through the sound card). ... I'm familiar with the general entropy ... hash function. ... Entropy Randomness Generator: ...
    (sci.crypt)
  • Re: Running SHA repeatedly
    ... I assumed he meant the pool is the same size as the hash output. ... don't know what it means to run SHA repeatedly over a 1 KB pool. ... I have read a lot about SHA distilling entropy, ... What's the chance that H== H? ...
    (sci.crypt)
  • Re: Estimating entropy of a stream
    ... random number generator. ... I'm familiar with the general entropy ... to the output of the hash, then use the output as my random bits. ... processed data, but my instinct has been wrong in the past. ...
    (sci.crypt)
Quantcast