Re: Good enough for crypto?

From: Mok-Kong Shen (mok-kong.shen_at_t-online.de)
Date: 11/29/03 

Date: Sat, 29 Nov 2003 18:47:23 +0100

Terry Ritter wrote:
>
> Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:
>
> [...]
> >If a PRNG is so
> > good that it passes all (currently) available statistical
> > tests,
>
> First of all, a PRNG which always passes statistical tests
> is bad, not good.

There is an accepted meaning of passing statistical tests,
I suppose. If a PRNG fails a cetain test, it is certainly
not good (relative to the chosen criteria of that test).
If follows that a very good PRNG must pass all (currently)
available statistical tests. If there is one that does
so, then it is among the best that one can have, as far
as PRNGs are concerned.

>
> A good PRNG will reproduce the ideal null distribution
> for each test. That will necessarily produce the same
> level of failure as whatever significance has been chosen
> (often, 5 percent).

A statistical test never says anything absolute. It only
allows one to (reasonably) decide at a chosen confidence
level whether to reject a certain null hypothesis or
not to reject it.

> >then one (without knowledge of the generation
> > process) would hardly be able to know that there is in
> > fact very little entropy. (On the other hand, it seems
> > to me to be justified that such a superb pseudo-random
> > source could very well substitute a true random source
> > in practical applications.)
>
> Even a superb pseudo-random source is still deterministic,
> thus potentially predictable. While statistics may be
> happy with just a good value distribution, cryptography
> further demands effective unpredictability, which
> statistical tests do not measure.
>
> It is instead necessary to understand the design of the
> generator, and somehow extrapolate an opinion that the
> internal state cannot be developed from the resulting
> sequence. Alas, such opinions are often wrong.

But if you don't have or can't use good true randomness,
you have to resort to pseudo-randomness. It seems that
many consider AES in CTR mode to be good. But who knows
that it is 'really' secure (there being no really rigorous
and practical measure of crypto security for real-world
ciphers)?

M. K. Shen

Relevant Pages

  • Re: Good enough for crypto?
    ... a PRNG which always passes statistical tests ... Even a superb pseudo-random source is still deterministic, ... and somehow extrapolate an opinion that the ...
    (sci.crypt)
  • Re: Way for computing random primes in standard C.
    ... statistical tests. ... I think the general principle still holds that my seeding the ... I should have said "the main reason the ability to seed the PRNG ... scientific applications in which I would be comfortable using it ...
    (comp.lang.c)
  • Re: cidd/rcrx is my cipher
    ... You cannot say that if you pass tests X, Y, Z your generator is secure, ... attempts to guess the "next-bit" bof the pseudo-random sequence. ... Yao's Theorem states that a PRNG passes all next-bit tests if and only if it ... passes all statistical tests so if a random instance passes it should also ...
    (sci.crypt)