Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:57
Berke Durak (berke@gsu.linux.org.tr)
Mon, 10 Aug 1998 20:15:02 +0300 (EEST)
On Mon, 10 Aug 1998, Mok-Kong Shen wrote:
> I was sort of asking people to find an analysis method to
> obtain the two input streams. If these can't be found, then
> it doesn't matter whether they are individually cryptologically
> weak or strong, since if one can't obtain them individually
> one can't infer their parameters.
If I did not misundersood: you have two PRNGs; you obtain a new sequence by
adding their output modulo 1 (if their output is real, in the range [0,1[,
i.e. you add them up and take the decimal part) or modulo 2^n (if you are
working on machine words of size n). You are asking if even in the case of
PRNGs of doubtful quality, it is possible to recover the internal state
("parameters") of both of them, given the combined output.
Well, it seems to me that not being able to break them individually does not
imply, in the most general case, that the resulting stream is strong, if
this is what we are after.
I'm far from having the mathematics to analyse even the simplest
congruential generators.
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) ?
Berke Durak - berke@gsu.linux.org.tr - http://gsu.linux.org.tr/kripto-tr/
PGP bits/keyID: 2047/F203A409 fingerprint: 44780515D0DC5FF1:BBE6C2EE0D1F56A1
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:57