Greg probably didn't spend much time on it,[...]
do you know what i think:
every public cripto sys are broken by definition;
is it more chanches that KISS is not now breakable
than all other "cripto secure" RNG are not breakable
don't know if above is true, but i think it.
| I wrote a paper cryptanalyzing the original KISS,
| available at http://eprint.iacr.org/2011/007 .
| (I emailed it to your FSU address some months ago,
| don't know if you got that or not.) In terms of
| cryptanalysis, the MWC is definitely the hard nut
| to crack. This new generator might be practically
| secure (in the sense that it is impractical to
| recover the huge state), but it is definitely
| not cryptographically practical (because of the
| huge state!) nor cryptographically secure (since
| the work to recover that huge state is certainly
| much less than enumeration of the state
There has been at least two (maybe four) KISS
generators since the 1993 version(s) that you analyzed,
having significantly longer tables and periods than
that one.
Which I claim makes them even less
cryptographically useful. A period in excess of
about 2^80 doesn't contribute anything to real
world use. But large states/keys have to be dealt
with securely.
Before you make claims like and "certainly much less"
and "might be", wouldn't it be better to have actually done
such an analysis on the two new generators?
OK. Looking just at the "32-bit MWC generator",
which I repost here for convenience:
static unsigned long Q[4194304],carry=0;
unsigned long b32MWC(void)
{unsigned long t,x; static int j=4194303;
j=(j+1)&4194303;
x=Q[j]; t=(x<<28)+carry;
carry=(x>>4)-(t<x);
return (Q[j]=t-x);
}
#define CNG ( cng=69069*cng+13579 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<5) )
#define KISS ( b32MWC()+CNG+XS )
Let's assume that the contents of Q, cng and xs
are initialized completely randomly and
independently of each other. Note that the initial
value of carry is explicitly set to zero.
We assume that the output stream from KISS
is known to the attacker (standard cryptographic
assumption); call this output stream Z_i, for i = 1 ...
Some observations:
1) at every stage, carry will usually be only 28
bits in length. The exception is when the high
order 28 bits of the input Q value are all zero,
carry will (almost never, but depending on the
input carry value) become 0xFFFFFFFF. This is
rare enough not to worry about in the attack
below.
1a) if you know the input value Q[t], the output
carry value is almost entirely defined by the most
significant 28 bits. 15/16ths of the time, whether
the optional subtraction of 1 happens is determined
by comparing the least significant and most
significant 4 bits of the input Q[t], independent
of the input carry.
2) at every stage t, the output of b32MWC will be
the input value of Q[t mod 2^22] to the
calculation of b32MWC 2^22 steps later. (In case
anyone hadn't noticed, 4194304 == 2^22. Let's call
R=2^22 for simplicity later.)
3) CNG and XS are easily invertible (see my paper).
4) b32MWC is also invertible; if you know both the
input Q[j] and the output Q[j] not only can you
derive the output carry, you can also derive the
input carry.
5) given (3) and (4), you can run the generator
backwards if you need to.
Now an attack:
1. Start by guessing (enumerating) the 2^64 possible
pairs (xs_0 and cng_0).
2. Run the subgenerators CNG and XS forward R+3 rounds,
and calculate M_{i-1} = Z_i - cng_i - xs_i (for 1 <= i <= R+3).
These are possible candidate values for the Q[i-1 mod R]
values.
3. If we guessed the initial values correctly in the
first step, then M_0 should be the input Q[0], and M_R
should be the output Q[0] after R steps. From these, we
can calculate carry_R, and from carry_R and M_{R+1}
(which we hope equals output Q[1]) we can check
whether, in fact, the computation given input and output
Q[1], and what we just calculated, agree with each other.
If they don't, go back to step 1. If they do (which might
happen randomly), do the same for R+2, and R+3. At this
point, if all checks worked, with pretty overwhelming
probability we must have guessed CNG and XS correctly.
4. Run b32MWC backwards to recover the initial settings
of Q.
Now the expected work to do this is about 2^85 times
the work to generate output words, which is a pretty
normal measure. (That's 2^64 / 2 (since you expect to
search half the values) times about 2^22 words generated
(because of the huge state space.).
Another way to look at it is that it's about 2^63 times
the cost of doing a key setup (independent of how you
actually set up that huge key!).
Either way, it is not cryptographically secure. The same
attack strategy works for the 64-bit version, but of course
the complexity roughly doubles to 2^126.
Now this is almost exactly the opposite of the way I
did the attack on the original KISS. That's because
increasing the size of one of the sub-generators
just made the other ones the weak point.
Greg.
--
Which I claim makes them even less
cryptographically useful. A period in excess of
about 2^80 doesn't contribute anything to real
world use. But large states/keys have to be dealt
with securely.OK. Looking just at the "32-bit MWC generator",
which I repost here for convenience:static unsigned long Q[4194304],carry=0;unsigned long b32MWC(void)
{unsigned long t,x; static int j=4194303;
j=(j+1)&4194303;
x=Q[j]; t=(x<<28)+carry;
carry=(x>>4)-(t<x);
return (Q[j]=t-x);
}#define CNG ( cng=69069*cng+13579 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<5) )
#define KISS ( b32MWC()+CNG+XS )Let's assume that the contents of Q, cng and xs
are initialized completely randomly and
independently of each other. Note that the initial
value of carry is explicitly set to zero.
We assume that the output stream from KISS
is known to the attacker (standard cryptographic
assumption); call this output stream Z_i, for i = 1 ...Some observations:1) at every stage, carry will usually be only 28
bits in length. The exception is when the high
order 28 bits of the input Q value are all zero,
carry will (almost never, but depending on the
input carry value) become 0xFFFFFFFF. This is
rare enough not to worry about in the attack
below.1a) if you know the input value Q[t], the output
carry value is almost entirely defined by the most
significant 28 bits. 15/16ths of the time, whether
the optional subtraction of 1 happens is determined
by comparing the least significant and most
significant 4 bits of the input Q[t], independent
of the input carry.2) at every stage t, the output of b32MWC will be
the input value of Q[t mod 2^22] to the
calculation of b32MWC 2^22 steps later. (In case
anyone hadn't noticed, 4194304 == 2^22. Let's call
R=2^22 for simplicity later.)3) CNG and XS are easily invertible (see my paper).4) b32MWC is also invertible; if you know both the
input Q[j] and the output Q[j] not only can you
derive the output carry, you can also derive the
input carry.5) given (3) and (4), you can run the generator
backwards if you need to.Now an attack:1. Start by guessing (enumerating) the 2^64 possible
pairs (xs_0 and cng_0).2. Run the subgenerators CNG and XS forward R+3 rounds,
and calculate M_{i-1} = Z_i - cng_i - xs_i (for 1 <= i <= R+3).
These are possible candidate values for the Q[i-1 mod R]
values.3. If we guessed the initial values correctly in the
first step, then M_0 should be the input Q[0], and M_R
should be the output Q[0] after R steps. From these, we
can calculate carry_R, and from carry_R and M_{R+1}
(which we hope equals output Q[1]) we can check
whether, in fact, the computation given input and output
Q[1], and what we just calculated, agree with each other.
If they don't, go back to step 1. If they do (which might
happen randomly), do the same for R+2, and R+3. At this
point, if all checks worked, with pretty overwhelming
probability we must have guessed CNG and XS correctly.4. Run b32MWC backwards to recover the initial settings
of Q.
Now the expected work to do this is about 2^85 times
the work to generate output words, which is a pretty
normal measure. (That's 2^64 / 2 (since you expect to
search half the values) times about 2^22 words generated
(because of the huge state space.).Another way to look at it is that it's about 2^63 times
the cost of doing a key setup (independent of how you
actually set up that huge key!).Either way, it is not cryptographically secure. The same
attack strategy works for the 64-bit version, but of course
the complexity roughly doubles to 2^126.Now this is almost exactly the opposite of the way I
did the attack on the original KISS. That's because
increasing the size of one of the sub-generators
just made the other ones the weak point.Greg.
--
I had an insight the other day that speeds up
this attack by a factor of about 2^22. I don't
know why I didn't think of it earlier. Quoting
from the updated paper:
...However this attack can be significantly
optimized. First we note that most of the
generated values of from CNG and XS are not used
in the important validation step; of the $R+3$
pairs of values generated, only the first three
and last three are used. Secondly, we note that
both generators can be jumped forward a known
amount (in our case $R$ steps) with very much less
complexity than simply evaluating the functions
$R$ times. In the case of XS, we can precompute
the update matrix, and compute $xs_R$ by
multiplying $xs_0$ by it. Similarly, CNG can be
jumped forward using a modular ``square and
multiply'' exponentiation calculation.
When enumerating the possible initial values of XS
and CNG, there is no reason to enumerate them as
counters. Since the values all fall on cycles (a
single cycle in the case of CNG) the values can be
enumerated in the sequence produced by the cycle.
For example, we start with $cng_0 = 0$, and
quickly calculate $cng_R$ from that. By iterating
CNG we easily calculate $cng_1 .. cng_3$ and
$cng_{R+1} .. cng_{R+3}$ as required above. After
testing this value (and presumably failing), we
can test the next value by discarding $cng_0$,
using the old $cng_1$ as the new $cng_0$,
similarly rolling over $cng_R$ and so on. The
different cycles of XS (as detailed in Appendix
\ref{app:shr3}) can be handled in basically the
same way. Only once the correct values for $cng_0$
and $xs_0$ have been identified is it necessary to
run the generators $R$ steps to recover the
initial values of the $Q$ array. Parallelization
of this attack is a bit more tricky, but still
easy. With this optimization, about $2^{63}$
operations on average can be expected to recover
the key. Since the $Q$ array is so large, this
corresponds to about $2^{41}$ key setup
operations.
Greg.
--- Hide quoted text -
- Show quoted text -
scattered said:Are you aware that the OP, George Marsaglia, died in February a few
weeks after starting this thread?
A sudden heart attack while walking on the grounds of Capital City
Country Club in Tallahassee on [2011-02-15] took the life of Dr.
George Marsaglia. He was born to John and Mabel Marsaglia in Denver,
Colorado, in 1924.
weeks after starting this thread? I just found out last week and was
thus quite surprised when I saw this thread which was started by him.
I missed the start of the thread when it was current and didn't pick
up on the January dates when I first glanced at it today. For a second
I thought that somebody had made a sick practical joke on Wikidpedia
(where I read about his death) and that he was alive after all -- but
then I noticed the date of the original post. Sad. It is impressive
how he stayed intellectually active long after his retirement. It
seems appropriate that he began this thread (which google shows to be
his second to last post) by refering to his desire to climb
mathematical Mount Everests.
I was unaware of his death, and sorry to lose
a great person.
Having said that, cryptology is made stronger
by attacking the algorithms, and I hope people
understand that I was not attacking Marsaglia
himself.
Greetings.
Are you aware that the OP, George Marsaglia, died in February a few
weeks after starting this thread?[snip]
BTW, I believe it is correct that one good use of PRNGs with huge
periods is to appropriately combine them with other PRNGs (xor etc.)
so that one obtains sequences of huge periods that are much more
difficult to analyze in cryptological sense than the original PRNGs.
Well, I disagree, for the previously stated
reasons. But to reiterate them:
1) to get huge periods you require huge states,
which for cryptographic purposes is an albatross
around your neck,
2) I think I have demonstrated that even with
combined PRNGs, you often still don't get
cryptographic security. So it shouldn't be
claimed or even hinted at, lest people believe
it.
Greg.
--
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.