Re: Strong PRNG with AES or 3-DES

Mok-Kong Shen (mok-kong.shen@stud.uni-muenchen.de)
Mon, 10 Aug 1998 19:47:25 +0100

• Next message: Lewis McCarthy: "Fwd: cryptography list"
• Previous message: Berke Durak: "Re: Strong PRNG with AES or 3-DES"

Berke Durak wrote:

> However, if we take the following absurd example, let one PRNG give outputs
> x_1,x_2,...,x_n, let the second PRNG give outputs
> -x_1,-x_2,...,-x_n. The resulting PRNG would give all zeroes, which is of course
> not strong, yet you still don't have a means to recover
> the original PRNGs.
>
> This shows that you need to at least be more precise on the types of PRNGs
> you could combine this way.
>
> As a more real-word example, if you take two linear feed back shift register
> PRNGs (as these require simply linear algebra and a bit of polynomial
> arithmetic to understand, at least superficially, they are more at the reach
> of an undergrad) having the same register size, XORing the two would not
> give a PRNG any stronger, since XORing is the same linear operation used in
> both PRNGs, and solving the _resulting_ PRNG is trivial using matrix
> inversion modulo 2 (see the section "Known-plain text attacks on Hill
> ciphers" in Stinson).
>
> So compatibility issues between the operations used to combine the PRNGs and
> the internal operations of these PRNGs can even weaken the composed output.
>
> Of course, recovering the internal state of the PRNGs is sufficient but not
> necessary for a successful attack, finding appropriate relations in their
> output would be enough (for ex. that the low-order bits follow some regular
> pattern, which seems to be common on linear congruential generators).
>
> What about hashing the concatenation of outputs from weak PRNGs (possibly
> having mutually prime periods) ?

What you point out is true. However, apart from such special cases,
I don't think that there are viable methods of deriving the two
input streams, espcially when these are statistically sufficiently
good (though cryptologically weak, like linear congruential PRNGs).
I guess that hashing as you suggested also gives excellent results
in the same context. (It may be noted that addition mod 1 of two
streams in [0,1) generally results in a stream having a more uniform
distribution.)

M. K. Shen

• Next message: Lewis McCarthy: "Fwd: cryptography list"
• Previous message: Berke Durak: "Re: Strong PRNG with AES or 3-DES"