Re: strengthening /dev/urandom

From: John Cochran (jdc_at_smof.fiawol.org)
Date: 08/30/04 

Date: Mon, 30 Aug 2004 11:51:41 GMT

In article <cguokm$qj0$03$1@news.t-online.com>,
Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>
>That was an argument I put forth in a previous post. Distillation
>presumes distinguishing streams with from streams without
>entropy. If someone could show that's rigorously feasible and
>have that incorporated in /dev/random, then everything would
>have been fine.
>
>M. K. Shen

Distillation DOES NOT presume the ability to determine which input stream
contains or does not contain entropy. Attempting to carry the physical
analogy of distillation where you selectively extract desired molecules
from a mixture of desired and undesired molecules too far seems to be
causing you problems. Programatic distillation does not select 1 bit over
another. You've been shown that with multiple input streams being mixed
with an XOR function, the resulting output will be random if at least 1 input
stream is random. The XOR function doesn't know or care which input stream
is the random one. That argument all by itself invalidates your statement
"Distillation presumes distinguishing streams with from streams without
entropy." If you have a function that accepts 200,000 bits of input with
an average of 50% entropy and produces 1,000 bits of output with 100% of
entropy. Then it DOES NOT MATTER if 10,000 or for that matter if 99,000 bits
of the input is compromised and has zero entropy. In the uncompromised state,
you have 100,000 bits of entropy and you effectively loose 99,000 bits just
to be safe. Having a compromised stream does not affect the quality of the
output as long as there is at least 1,000 bits of entropy available for all
of the remaining streams. To my way of thinking, the main trade off you
have to do with entropy distillation is deciding how much inefficiency you're
willing to put up with in order to guard against a compromise of an input
stream. The description with 200,000 bits of 50% entropy could generate
100,000 bits of output with 100% of entropy. But doing this would leave
the system vulnerable to attack if any of the input is compromised. However,
if I'm willing to throw away efficiency and I'm willing to only generate
1,000 bits of output, then I'm much safer against the possibility of an
input being compromised. Determining which stream has been compromised is
not and never was an issue with distillation.

Relevant Pages

  • Re: strengthening /dev/urandom
    ... in their uncompromised cases all have some entropy. ... be assumed that all streams are 'contributing' to the final ... attacker compromises one or more streams such that these ...
    (sci.crypt)
  • Re: strengthening /dev/urandom
    ... >in their uncompromised cases all have some entropy. ... >be assumed that all streams are 'contributing' to the final ... You are assuming mixing, not distillation. ... 10 input streams at 200KB/sec and 50% entropy and from them ...
    (sci.crypt)
  • Re: strengthening /dev/urandom
    ... >>in their uncompromised cases all have some entropy. ... >>be assumed that all streams are 'contributing' to the final ... not distillation. ... If you have a distillation function that takes ...
    (sci.crypt)
  • Re: new /dev/random
    ... >distillation, in the context of quantum information theoretic. ... >distill them down to a set of bits of near maximal entropy. ... Alice and Bob want to extract a secret S that Eve knows nothing about. ... perfect source of uniform bits, then yup, we could use this. ...
    (sci.crypt)
  • Re: strengthening /dev/urandom
    ... > Distillation DOES NOT presume the ability to determine which input stream ... > contains or does not contain entropy. ... > stream is random. ... > willing to put up with in order to guard against a compromise of an input ...
    (sci.crypt)
Quantcast