Re: strengthening /dev/urandom

From: Mok-Kong Shen (mok-kong.shen_at_t-online.de)
Date: 08/31/04


Date: Tue, 31 Aug 2004 21:00:22 +0200


Guy Macon wrote:

> Mok-Kong Shen <mok-kong.shen@t-online.de> says...
>
>
>>The trouble is that (perfect) TRNG doesn't exist (or more
>>exactly, it may exist but we don't know having such a one,
>>in case we do have one in our hand). That makes any
>>theoretical and pedantically rigorous arguments problematic.
>
>
> No it doesn't. It makes them easier. Look at my XOR examples.
> they are much easier to follow if you assume 100% and 0% entropy.
> Once you agree on the basic concept, you can introduce the real
> world. EEs do this all of the time, assuming perfect capacitors
> etc. Geometry is the same way with its perfectly straight one
> dimensional lines.

No problem with that. In crypto, an (ideal) OTP is just that
and its utility for the theory is well recognized. The point
is however that your arguments couldn't find a 'real' and
rigorously exact correspondence in reality but only an
approximation. That means that the conclusions must also be
approximations. See also below.

>>>>Second, If there were a software that could discard portions
>>>>of input that have no entropy, then, assuming that the software
>>>>does that correctly, I think there could indeed be a method to
>>>>pinpoint a source that has zero entropy: Feed the software with
>>>>all sources and then repeat the experiment (with the same data)
>>>>but with all sources but the one that one suspects to have zero
>>>>entropy. If the results are the same, then one's conjecture
>>>>must be right.
>>>
>>>XOR a TRNG (100% entropy) with a good PRNG (0% entropy).
>>>
>>>Does the output have 100% entropy? Yes.
>>>
>>>Repeat the experiment without the PRNG.
>>>
>>>Are the results (the actual data out) the same? No.
>>>
>>>Does the output have 100% entropy? Yes.
>>
>>See above.
>
>
> I did, and disproved it by counterexample.
>
>
>>(You are virtually doing the same as people
>>do in religions. Assert that God exist, then you could
>>derive many other assertions, of course.) The point is
>>that in this practical world, there is not much sense
>>to argue about theoretically conceivable perfect/ideal
>>scenarios. One must be ready to accept 'approximations'
>>of ideal stuff and strive to get as good approximations
>>as technically feasible and economically justifiable.
>
>
> You and I both know that if you replace the 100% and 0%
> entropy sources in my counterexamples with 1% and 99%
> sources the XOR function still distills entropy.

But you then couldn't show that the result has 100% entropy,
couldn't you?

Theory and practice are different. This is well-known
and also well accepted by everybody, I believe. However,
the existence of imperfections should nonetheless be
kept in one's conscious mind.

BTW, for practical purposes I would 'guess' that cases
where one really 'objectively' needs lots of full (or
extremely high concentration) entropy are fairly rare.
Could someone kindly give a few examples where such true
randomness couldn't be substituted with good pseudo-
randomness, e.g. AES in CTR? Thanks.

M. K. Shen



Relevant Pages

  • Re: True Random Number Generator
    ... keystream be greater than the redundancy of the plaintext? ... be perfectly random - just sufficiently random. ... it sufficies to combine it with a stream having an entropy of 0.9 per ... Of course, in practice one wouldn't ...
    (sci.crypt)
  • Re: diehard and ent results quesion
    ... I should try to see what happen, although iirc using that entropy value ... any generator has the same "entropy". ... > concrete device/algorithm that is capable in practice ... Also the NIST test uses that formula, but, at least, it gives a p-value ...
    (sci.crypt)
  • Re: diehard and ent results quesion
    ... >> But assigning full entropy to MT is obviously not o.k. ... >> concrete device/algorithm that is capable in practice ... of a sequence from a source not having full entropy, ... This is an extreme dilution. ...
    (sci.crypt)
  • Re: [PATCH 7/14] random: Remove SA_SAMPLE_RANDOM from network drivers
    ... and this is what I dislike so much about theoretical people. ... show you what can be done theoretically, yet never in practice with ... /dev/random's entropy counting scheme sole reason to exist is to ... defend against theoretical future attacks against its cryptographic ...
    (Linux-Kernel)
  • Re: strengthening /dev/urandom
    ... they are much easier to follow if you assume 100% and 0% entropy. ... Assert that God exist, then you could ... One must be ready to accept 'approximations' ... entropy sources in my counterexamples with 1% and 99% ...
    (sci.crypt)