building a true RNG

[bear]

On Tue, 30 Jul 2002, James A. Donald wrote:

>
>Randomness is of course indefinable.  A random oracle is however
>definable.
>
>If SHA-1 is indistinguishable from a random oracle without prior
>knowledge of the input, then we would like to prove that for an
>attacker to make use of the loss of entropy that results from the
>fact that it is not a random oracle, the attacker would be need to
>be able to distinguish SHA-1 from a random oracle without prior
>knowledge of the input.


The above sentence is unsound.  You cannot take an assumption
(If SHA-1 is indistinguishable....) and then use its negation
to prove something else (... then we would like to prove that
... the attacker would need to be able to distinguish...),
unless you prove your something else for both the TRUE and FALSE
values of the assumption.

Euclid was all over that, and George Boole after him.

Now, for the TRUE value of your assumption, which I
think you may have meant:

IF (A) SHA-1 is indistinguishable from a random oracle without
       prior knowledge of the input,
   AND
   (B) We can prove that in order to succeed in an attack, an
       attacker would need to distinguish SHA-1 from a random
       Oracle without prior knowledge of the input,
   THEN
   (C) The attacker will not succeed in that attack.

But for the FALSE value of your assumption A, we get

   IF (B) AND (~C) THEN (~A)

And

   IF (B) AND (~A) THEN (C) OR (~C).



So if we take B as an axiom, then we did not prove
anything about A unless given ~C and we did not prove anything
about C regardless of our assumptions about A.


				Bear






---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com