Re: strengthening /dev/urandom

From: Guy Macon (http://www.guymacon.com)
Date: 08/30/04 

Date: Mon, 30 Aug 2004 01:14:56 -0700

Mok-Kong Shen <mok-kong.shen@t-online.de> says...

>I used symbols, attempting to make it clear. Now look at
>another formulation: Suppose one has n input streams that
>in their uncompromised cases all have some entropy. Suppose
>that one succeeds with some deterministic mechanism to
>combine them into a stream of full entropy. It could clearly
>be assumed that all streams are 'contributing' to the final
>result. For, if not, then there would be a design flaw and
>the non-contributing ones could be taken out. Now, the
>attacker compromises one or more streams such that these
>have zero entropy and hence become non-contributing. It's
>obvious that this has an impact on the quality of the output
>stream, isn't it? Analogy: If one has an ochestra, then all
>musicians are contributing to the whole performance. If one
>of them is absent, the performance naturally suffers.
>Certainly, in case a violine player falls out, the effect
>would be normally fairly small, for there are quite a number
>of violine players, but the effect is certainly there, even
>if one's ear fails to detect it.

You are assuming mixing, not distillation. With distillation,
the inputs are putting in a lot more bits than the output is
sending out. If you have a distillation function that takes
10 input streams at 200KB/sec and 50% entropy and from them
produces a single output stream at 1KB/sec and 100% entropy,
if one of the input streams breaks and starts sernding 0%
entropy, it is still posssible for the output to have 100%
entropy.

Whether such a distillation function exists is beyond my limited
abilities to even speculate on, but I know that increasing the
percentage of entropy while reducing the total number of bits
(AKA distilling entropy) is possible: an XOR function operating
with independent sources on the inputs does that - and in some
special cases can be shown to increase the percentage of entropy
at the output to 100%. So distilling entropy is *not* impossible.
  

Relevant Pages

  • Re: strengthening /dev/urandom
    ... >presumes distinguishing streams with from streams without ... Distillation DOES NOT presume the ability to determine which input stream ... contains or does not contain entropy. ... willing to put up with in order to guard against a compromise of an input ...
    (sci.crypt)
  • 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 ... 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