RNGs with periods exceeding 10^(40million).

G

geo

I offer here a MWC (Multiply-With-Carry) RNG whose
period I cannot determine---nor is it likely that
anyone else can---but that unknown period is almost
certainly greater than 10^40000000, i.e, 10^(40million).
Versions for either 32- and 64-bit integers are given,
as well as suggestions for similar versions with
periods as great or even greater magnitude.

MWC RNGs are ordinarily based on primes of the form
p=ab^r-1, with b=2^32 or 2^64 and a<b. They generate,
32- or 64-bits at a time, and in reverse order, the
binary expansions of rationals j/p, 0<j<p and the
period of that binary expansion is the order of 2 mod p.
The key part of the MWC process is: given 32-bit a,x,c,
extract the top and bottom 32 bits of a 64 bit a*x+c,
or, for given 64-bit a,x,c, extract the top and bottom
64 bits of a 128-bit a*x+c.

I have put various computers to work establishing the
order of 2 for MWC primes of the form ab^r-1, b=2^32,
or CMWC (Complimentary-Multiply-With-Carry), p=ab^r+1.
For example, it took 24 days on an early laptop to
establish that the order of 2 for p=54767*2^1337287+1
is (p-1)/2^3, and just last week I put a Samsung 64-bit
laptop to finding the order of 2 for the 11th largest
known prime, p=27653*2^9167433+1; in CMWC form,
p=14158336*b^286482+1. I expect it may take months.

Such searches are motivated by more than a Mt. Everest
syndrome, as extremely-long-period RNGs not only seem to
perform very well on tests of randomness, but have uses
for cryptography. For example, suppose, from a random
set of seeds, you have observed 100000 successive 32-bit
numbers from a CMWC RNG based on p=14158336*b^286482+1.
You will then be somewhere in an immense loop that has
over 10^(2million) appearances of exactly that same
sequence of 100000, leaving you virtually no chance of
finding your particular location and thus able to
predict forthcoming values.

Of course, if you can observe 286482 successive values,
then, after a little modular arithmetic to determine
the carry, you are OK. It is ensuring a large exponent
for b that makes the RNG desirable---the larger the better.

But in seeking large exponents for b and record periods,
why bother with an Everest when there are ranges with
peaks far beyond surveyor's skills but certain
to be several times as tall?

Such ranges come from considering, for very large r,
composites of the form m=ab^r-1, rather than primes of
that form. The example for this posting: the composite
m=(2^28-1)*2^(2^27)-1=(2^28-1)*b^(2^22)-1.
m has no prime divisors less than 21000000, and order(2,m)
is the lcm of the orders mod the prime divisors of m.
We cannot---and may never be able to--factor such an
m>10^40403570, but for primes q, the average value of
order(2,q)/q is around .572. Thus, even if m has, say,
40 prime factors, since (.572)^40>10^(-10), we can only
expect to "lose" around ten 10's, and perhaps ten more
through common factors for the lcm, providing an estimate
around 10^40403550 for the order of 2 mod m.

That the order of 2 mod m is less than 10^(40million)
seems extremely unlikely; we would have to "lose" over
400thousand 10's, when something in the range
of three to sixty 10's seems more likely.

So users should feel confident that the periods of the
following MWC RNGs far exceed 10^(40million). Based on
m=(2^28-1)b^(2^22)-1=(2^28-1)b^4194304-1 with b=2^32,
m=(2^28-1)B^(2^21)-1=(2^28-1)B^2091752-1 with B=2^64,
they are simple and very fast.
You would have to observe more than 134 million
successive bits produced be these MWC RNGs
in order to get close to cracking them.

Note that choosing a=2^i-1 in m=ab^r-1 makes finding
the top and bottom 32 bits of a purported 64 bit
a*x+c feasible using only 32-bit arithmetic,
or, within 64-bit arithmetic, finding the top
and bottom 64 bits of a purported 128 bit a*x+c.

Here are C versions using, for 32-bit integers,
an unsigned long array Q[41943104], and for 64-bits,
an unsigned long long array Q[2091752].
Try them and see if you get the same results I do.

--------------------32-bit MWC version-------------------

#include <stdio.h>
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 )

int main(void)
{unsigned long int i,x,cng=123456789,xs=362436069;
/* First seed Q[] with CNG+XS: */
for(i=0;i<4194304;i++) Q=CNG+XS;
/* Then generate 10^9 b32MWC()s */
for(i=0;i<1000000000;i++) x=b32MWC();
printf("Does x=2769813733 ?\n x=%lu\n",x);
/* followed by 10^9 KISSes: */
for(i=0;i<1000000000;i++) x=KISS;
printf("Does x=3545999299 ?\n x=%lu\n",x);
return 0;
}

---------------- 64-bit MWC version ---------------------

#include <stdio.h>
static unsigned long long Q[2097152],carry=0;

unsigned long long B64MWC(void)
{unsigned long long t,x; static int j=2097151;
j=(j+1)&2097151;
x=Q[j]; t=(x<<28)+carry;
carry=(x>>36)-(t<x);
return (Q[j]=t-x);
}

#define CNG ( cng=6906969069LL*cng+13579 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<43) )
#define KISS ( B64MWC()+CNG+XS )

int main(void)
{unsigned long long i,x,cng=123456789987654321LL,
xs=362436069362436069LL;
/* First seed Q[] with CNG+XS: */
for(i=0;i<2097152;i++) Q=CNG+XS;
/* Then generate 10^9 B64MWC()s */
for(i=0;i<1000000000;i++) x=B64MWC();
printf("Does x=13596816608992115578 ?\n x=%llu\n",x);
/* followed by 10^9 KISSes: */
for(i=0;i<1000000000;i++) x=KISS;
printf("Does x=5033346742750153761 ?\n x=%llu\n",x);
return 0;
}

---------------------------------------------------------

Note that I advocate the KISS, (Keep-It-Simple-Stupid),
principle. Even though the MWC RNGs perform very well on
tests of randomness, combining with Congruential (CNG)
and Xorshift (XS) probably provides extra insurance
at the cost of a few simple instructions, (and making
the resulting KISS even harder to crack).

Also note that for unsigned integers such as in Fortran,
the C instruction -(t<x) means: subtract 1 if t<s,
and can be implemented for signed integers as t'<s',
where the ' means: flip the sign bit.

Full random seeding of the carry and the Q[] array
calls for more than 17 megabytes of random bits.
For ordinary randomness testing, filling, as above,
the Q[] array with Congruential+Xorshift may serve, but
for stronger crypto uses, many more than the random 64-
or 128-bits that CNG and XS require are needed.
Random seeding of the carry and the Q[] array amounts to
producing, either 32- or 64-bits at a time, the reverse-
order binary expansion of j/m for some 0<=j<=m. Indeed,
for m=ab^r-1, given the carry and the Q[] array, that j is

j=carry+a*sum(Q*b^i),i=0..r-1.

There are phi(m) such j's with period order(2,m).
Since m has no prime factors less than 21000000, with
probability close to 1 a random seeding of Q[] should
produce a j that is relatively prime to m and thus
produce the full period---unknown but almost certainly
far in excess of 10^(40million). Even if random
seeding of carry and Q[] provides a j with gcd(j,m)>1,
the period is still likely to exceed 10^(40million).
There are two exceptions:
All Q=0, carry=0 yields j=0 and the binary expansion
0/m=.00000000000000000...
All Q=b-1=2^32-1 and carry=a-1=(2^28-2) yields j=m
and the binary expansion
m/m=.11111111111111111...

Almost any choice of m=(2^i-1)*2^(2^27)-1 is likely
to provide an immense order for 2 mod m.
Choices i=16,18,22,28 resulted in m's that have no
factors<10^7. Memory seems to be the key restriction
for the resulting Q[] array. With enough memory,
one might seek i's for which m=(2^i-1)*2^(2^28)-1
has no small factors, or even m=(2^i-1)*2^(2^29)-1,
boosting the unknown and unknowable periods of
MWC RNGs to ranges beyond 10^(40million).

George Marsaglia
 
D

David Bernier

geo said:
I offer here a MWC (Multiply-With-Carry) RNG whose
period I cannot determine---nor is it likely that
anyone else can---but that unknown period is almost
certainly greater than 10^40000000, i.e, 10^(40million).
Versions for either 32- and 64-bit integers are given,
as well as suggestions for similar versions with
periods as great or even greater magnitude.

MWC RNGs are ordinarily based on primes of the form
p=ab^r-1, with b=2^32 or 2^64 and a<b. They generate,
32- or 64-bits at a time, and in reverse order, the
binary expansions of rationals j/p, 0<j<p and the
period of that binary expansion is the order of 2 mod p.
The key part of the MWC process is: given 32-bit a,x,c,
extract the top and bottom 32 bits of a 64 bit a*x+c,
or, for given 64-bit a,x,c, extract the top and bottom
64 bits of a 128-bit a*x+c. [...]

---------------- 64-bit MWC version ---------------------

#include<stdio.h>
static unsigned long long Q[2097152],carry=0;

unsigned long long B64MWC(void)
{unsigned long long t,x; static int j=2097151;
j=(j+1)&2097151;
x=Q[j]; t=(x<<28)+carry;
carry=(x>>36)-(t<x);
return (Q[j]=t-x);
}

#define CNG ( cng=6906969069LL*cng+13579 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<43) )
#define KISS ( B64MWC()+CNG+XS )

int main(void)
{unsigned long long i,x,cng=123456789987654321LL,
xs=362436069362436069LL;
/* First seed Q[] with CNG+XS: */
for(i=0;i<2097152;i++) Q=CNG+XS;
/* Then generate 10^9 B64MWC()s */
for(i=0;i<1000000000;i++) x=B64MWC();
printf("Does x=13596816608992115578 ?\n x=%llu\n",x);
/* followed by 10^9 KISSes: */
for(i=0;i<1000000000;i++) x=KISS;
printf("Does x=5033346742750153761 ?\n x=%llu\n",x);
return 0;
}

---------------------------------------------------------

Note that I advocate the KISS, (Keep-It-Simple-Stupid),
principle. Even though the MWC RNGs perform very well on
tests of randomness, combining with Congruential (CNG)
and Xorshift (XS) probably provides extra insurance
at the cost of a few simple instructions, (and making
the resulting KISS even harder to crack).

Also note that for unsigned integers such as in Fortran,
the C instruction -(t<x) means: subtract 1 if t<s,
and can be implemented for signed integers as t'<s',
where the ' means: flip the sign bit.

Full random seeding of the carry and the Q[] array
calls for more than 17 megabytes of random bits.
For ordinary randomness testing, filling, as above,
the Q[] array with Congruential+Xorshift may serve, but
for stronger crypto uses, many more than the random 64-
or 128-bits that CNG and XS require are needed.
Random seeding of the carry and the Q[] array amounts to
producing, either 32- or 64-bits at a time, the reverse-
order binary expansion of j/m for some 0<=j<=m. Indeed,
for m=ab^r-1, given the carry and the Q[] array, that j is

j=carry+a*sum(Q*b^i),i=0..r-1.

There are phi(m) such j's with period order(2,m).
Since m has no prime factors less than 21000000, with
probability close to 1 a random seeding of Q[] should
produce a j that is relatively prime to m and thus
produce the full period---unknown but almost certainly
far in excess of 10^(40million). Even if random
seeding of carry and Q[] provides a j with gcd(j,m)>1,
the period is still likely to exceed 10^(40million).
There are two exceptions:
All Q=0, carry=0 yields j=0 and the binary expansion
0/m=.00000000000000000...
All Q=b-1=2^32-1 and carry=a-1=(2^28-2) yields j=m
and the binary expansion
m/m=.11111111111111111...

[...]
With the GCC compiler, adding an optimization flag
such as -O2 or -O3 brought the time down from 29 seconds
to about 11 seconds on an Intel Core 2 Quad Q6600 at 2.4 GHz.

The best compilation options for me seem to be
with
gcc -O3 -march=x86-64 , the second flag indicating
the processor architecture.

The seeding time is negligible. Both the
B64MWC() and KISS values match what it should be.

In a modified program, I computed 11 billion KISS
values. The time difference with 1 billion is
61 seconds, for 10 billion more KISS values.
That results in almost 164,000,000 KISS values
computed per second.

If I'm not mistaken, with the 64-bit version,
each KISS value amounts to 64 pseudo-random bits ...

2^64 - 1 in hex should be: 0xffff ffff ffff ffff
or 0xFFFFFFFFFFFFFFFF . A mask for the low 32 bits
would be: 0x00000000FFFFFFFF , i.e
(x & 0x00000000FFFFFFFF) would select for the low 32 bits.

And (x & 0xFFFFFFFF00000000 )>>32 should select for
the high 32-bits.

====

I don't really understand what's going on in the
B64MWC function:

unsigned long long B64MWC(void)
{unsigned long long t,x; static int j=2097151;
j=(j+1)&2097151;
x=Q[j]; t=(x<<28)+carry;
carry=(x>>36)-(t<x);
return (Q[j]=t-x);
}


Arithmetically, what is happening to the array Q[] ?

David Bernier

------ results of my tests, etc. below ----------------

$ gcc -O3 -march=x86-64 test04a.c
$ time ./a.out
seeding of the array Q[] done ...

10^9 B64MWC()s done ... test of output on next line ...
Does x=13596816608992115578 ?
x=13596816608992115578

10^9 KISS values done ... test of output on next line ...
Does x=5033346742750153761 ?
x=5033346742750153761


real 0m10.632s
user 0m10.585s
sys 0m0.017s


============================================================

$ gcc -O3 -march=x86-64 test05a.c
$ time ./a.out
seeding of the array Q[] done ...

10^9 B64MWC()s done ... test of output on next line ...
Does x=13596816608992115578 ?
x=13596816608992115578

11 billion KISS values done ...
Does x=5033346742750153761 ?
x=4752557329978035295


real 1m11.451s
user 1m11.163s
sys 0m0.028s
 
D

David Bernier

David said:
geo said:
I offer here a MWC (Multiply-With-Carry) RNG whose
period I cannot determine---nor is it likely that
anyone else can---but that unknown period is almost
certainly greater than 10^40000000, i.e, 10^(40million).
Versions for either 32- and 64-bit integers are given,
as well as suggestions for similar versions with
periods as great or even greater magnitude.

MWC RNGs are ordinarily based on primes of the form
p=ab^r-1, with b=2^32 or 2^64 and a<b. They generate,
32- or 64-bits at a time, and in reverse order, the
binary expansions of rationals j/p, 0<j<p and the
period of that binary expansion is the order of 2 mod p.
The key part of the MWC process is: given 32-bit a,x,c,
extract the top and bottom 32 bits of a 64 bit a*x+c,
or, for given 64-bit a,x,c, extract the top and bottom
64 bits of a 128-bit a*x+c. [...]

---------------- 64-bit MWC version ---------------------

#include<stdio.h>
static unsigned long long Q[2097152],carry=0;

unsigned long long B64MWC(void)
{unsigned long long t,x; static int j=2097151;
j=(j+1)&2097151;
x=Q[j]; t=(x<<28)+carry;
carry=(x>>36)-(t<x);
return (Q[j]=t-x);
}

#define CNG ( cng=6906969069LL*cng+13579 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<43) )
#define KISS ( B64MWC()+CNG+XS )

int main(void)
{unsigned long long i,x,cng=123456789987654321LL,
xs=362436069362436069LL;
/* First seed Q[] with CNG+XS: */
for(i=0;i<2097152;i++) Q=CNG+XS;
/* Then generate 10^9 B64MWC()s */
for(i=0;i<1000000000;i++) x=B64MWC();
printf("Does x=13596816608992115578 ?\n x=%llu\n",x);
/* followed by 10^9 KISSes: */
for(i=0;i<1000000000;i++) x=KISS;
printf("Does x=5033346742750153761 ?\n x=%llu\n",x);
return 0;
}

---------------------------------------------------------

Note that I advocate the KISS, (Keep-It-Simple-Stupid),
principle. Even though the MWC RNGs perform very well on
tests of randomness, combining with Congruential (CNG)
and Xorshift (XS) probably provides extra insurance
at the cost of a few simple instructions, (and making
the resulting KISS even harder to crack).

Also note that for unsigned integers such as in Fortran,
the C instruction -(t<x) means: subtract 1 if t<s,
and can be implemented for signed integers as t'<s',
where the ' means: flip the sign bit.

Full random seeding of the carry and the Q[] array
calls for more than 17 megabytes of random bits.
For ordinary randomness testing, filling, as above,
the Q[] array with Congruential+Xorshift may serve, but
for stronger crypto uses, many more than the random 64-
or 128-bits that CNG and XS require are needed.
Random seeding of the carry and the Q[] array amounts to
producing, either 32- or 64-bits at a time, the reverse-
order binary expansion of j/m for some 0<=j<=m. Indeed,
for m=ab^r-1, given the carry and the Q[] array, that j is

j=carry+a*sum(Q*b^i),i=0..r-1.

There are phi(m) such j's with period order(2,m).
Since m has no prime factors less than 21000000, with
probability close to 1 a random seeding of Q[] should
produce a j that is relatively prime to m and thus
produce the full period---unknown but almost certainly
far in excess of 10^(40million). Even if random
seeding of carry and Q[] provides a j with gcd(j,m)>1,
the period is still likely to exceed 10^(40million).
There are two exceptions:
All Q=0, carry=0 yields j=0 and the binary expansion
0/m=.00000000000000000...
All Q=b-1=2^32-1 and carry=a-1=(2^28-2) yields j=m
and the binary expansion
m/m=.11111111111111111...

[...]
With the GCC compiler, adding an optimization flag
such as -O2 or -O3 brought the time down from 29 seconds
to about 11 seconds on an Intel Core 2 Quad Q6600 at 2.4 GHz.

The best compilation options for me seem to be
with
gcc -O3 -march=x86-64 , the second flag indicating
the processor architecture.

The seeding time is negligible. Both the
B64MWC() and KISS values match what it should be.

In a modified program, I computed 11 billion KISS
values. The time difference with 1 billion is
61 seconds, for 10 billion more KISS values.
That results in almost 164,000,000 KISS values
computed per second.

[...]

I'm thinking of using each of the 64 bits in one KISS
value as 64 coin tosses. Then, with 16 KISS values, we have
1024 bits, and if we count the number of '1' bits,
it should resemble a binomial distribution with
n = 1024, p = 1/2.
< http://en.wikipedia.org/wiki/Binomial_distribution > .

If y is an unsigned long long, I could do something like

unsigned long long count;
int shortcount;

count = y&1LL;
count += (y&2LL)>>1;
count += (y&4LL)>>2;
count += (y&8LL)>>3;
...
count+= (y& 9223372036854775808LL)>>63;

shortcount = (int) count;

array[shortcount]++; // array of length 1025 .

Would that be an efficient way of counting the number of
'1' bits in a 64-bit unsigned long long ?

David Bernier
 
D

David Bernier

David said:
David said:
geo said:
I offer here a MWC (Multiply-With-Carry) RNG whose
period I cannot determine---nor is it likely that
anyone else can---but that unknown period is almost
certainly greater than 10^40000000, i.e, 10^(40million).
Versions for either 32- and 64-bit integers are given,
as well as suggestions for similar versions with
periods as great or even greater magnitude.

MWC RNGs are ordinarily based on primes of the form
p=ab^r-1, with b=2^32 or 2^64 and a<b. They generate,
32- or 64-bits at a time, and in reverse order, the
binary expansions of rationals j/p, 0<j<p and the
period of that binary expansion is the order of 2 mod p.
The key part of the MWC process is: given 32-bit a,x,c,
extract the top and bottom 32 bits of a 64 bit a*x+c,
or, for given 64-bit a,x,c, extract the top and bottom
64 bits of a 128-bit a*x+c. [...]

---------------- 64-bit MWC version ---------------------

#include<stdio.h>
static unsigned long long Q[2097152],carry=0;

unsigned long long B64MWC(void)
{unsigned long long t,x; static int j=2097151;
j=(j+1)&2097151;
x=Q[j]; t=(x<<28)+carry;
carry=(x>>36)-(t<x);
return (Q[j]=t-x);
}

#define CNG ( cng=6906969069LL*cng+13579 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<43) )
#define KISS ( B64MWC()+CNG+XS )

int main(void)
{unsigned long long i,x,cng=123456789987654321LL,
xs=362436069362436069LL;
/* First seed Q[] with CNG+XS: */
for(i=0;i<2097152;i++) Q=CNG+XS;
/* Then generate 10^9 B64MWC()s */
for(i=0;i<1000000000;i++) x=B64MWC();
printf("Does x=13596816608992115578 ?\n x=%llu\n",x);
/* followed by 10^9 KISSes: */
for(i=0;i<1000000000;i++) x=KISS;
printf("Does x=5033346742750153761 ?\n x=%llu\n",x);
return 0;
}

---------------------------------------------------------

Note that I advocate the KISS, (Keep-It-Simple-Stupid),
principle. Even though the MWC RNGs perform very well on
tests of randomness, combining with Congruential (CNG)
and Xorshift (XS) probably provides extra insurance
at the cost of a few simple instructions, (and making
the resulting KISS even harder to crack).

Also note that for unsigned integers such as in Fortran,
the C instruction -(t<x) means: subtract 1 if t<s,
and can be implemented for signed integers as t'<s',
where the ' means: flip the sign bit.

Full random seeding of the carry and the Q[] array
calls for more than 17 megabytes of random bits.
For ordinary randomness testing, filling, as above,
the Q[] array with Congruential+Xorshift may serve, but
for stronger crypto uses, many more than the random 64-
or 128-bits that CNG and XS require are needed.
Random seeding of the carry and the Q[] array amounts to
producing, either 32- or 64-bits at a time, the reverse-
order binary expansion of j/m for some 0<=j<=m. Indeed,
for m=ab^r-1, given the carry and the Q[] array, that j is

j=carry+a*sum(Q*b^i),i=0..r-1.

There are phi(m) such j's with period order(2,m).
Since m has no prime factors less than 21000000, with
probability close to 1 a random seeding of Q[] should
produce a j that is relatively prime to m and thus
produce the full period---unknown but almost certainly
far in excess of 10^(40million). Even if random
seeding of carry and Q[] provides a j with gcd(j,m)>1,
the period is still likely to exceed 10^(40million).
There are two exceptions:
All Q=0, carry=0 yields j=0 and the binary expansion
0/m=.00000000000000000...
All Q=b-1=2^32-1 and carry=a-1=(2^28-2) yields j=m
and the binary expansion
m/m=.11111111111111111...

[...]
With the GCC compiler, adding an optimization flag
such as -O2 or -O3 brought the time down from 29 seconds
to about 11 seconds on an Intel Core 2 Quad Q6600 at 2.4 GHz.

The best compilation options for me seem to be
with
gcc -O3 -march=x86-64 , the second flag indicating
the processor architecture.

The seeding time is negligible. Both the
B64MWC() and KISS values match what it should be.

In a modified program, I computed 11 billion KISS
values. The time difference with 1 billion is
61 seconds, for 10 billion more KISS values.
That results in almost 164,000,000 KISS values
computed per second.

[...]

I'm thinking of using each of the 64 bits in one KISS
value as 64 coin tosses. Then, with 16 KISS values, we have
1024 bits, and if we count the number of '1' bits,
it should resemble a binomial distribution with
n = 1024, p = 1/2.
< http://en.wikipedia.org/wiki/Binomial_distribution > .

If y is an unsigned long long, I could do something like

unsigned long long count;
int shortcount;

count = y&1LL;
count += (y&2LL)>>1;
count += (y&4LL)>>2;
count += (y&8LL)>>3;
...
count+= (y& 9223372036854775808LL)>>63;

shortcount = (int) count;

array[shortcount]++; // array of length 1025 .

Would that be an efficient way of counting the number of
'1' bits in a 64-bit unsigned long long ?


Precompute_16bit seems to be recommended:

http://gurmeet.net/2008/08/05/fast-bit-counting-routines/

As it is, I don't really understand the &gt or the &amp ...

David Bernier
 
R

robin

/*** 32-bit version in PL/I ***/
(nosize):
rng: procedure options (main);

declare Q(0:4194303) unsigned fixed binary (32),
carry unsigned fixed binary (32) static initial (0);

b32MWC: procedure () returns (unsigned fixed binary (32));
declare (t,x) unsigned fixed binary (32);
declare j fixed binary (31) static initial (4194303);
j=iand(j+1, 4194303);
x=Q(j); t=isll(x, 28)+carry;
carry=isrl(x, 4)-(t<x);
Q(j)=t-x;
return (Q(j));
end b32MWC;

KISS: procedure() returns (unsigned fixed binary (32));
declare t unsigned fixed binary (32);
t = b32MWC();
cng = bin(69069)*cng+(13579);
xs = ieor(xs, isll(xs, 13));
xs = ieor(xs, isrl(xs, 17));
xs = ieor(xs, isll(xs, 5));
return (t + cng + xs);
end KISS;

declare (i,x,cng static initial (123456789),
xs static initial (362436069)) unsigned fixed binary (32);
declare (start_time, finish_time) float (18);
start_time = secs();
/* First seed Q with CNG+XS: */
do i=0 to 4194304-1;
xs = ieor(xs, isll(xs, 13));
xs = ieor(xs, isrl(xs, 17));
xs = ieor(xs, isll(xs, 5));
cng = bin(69069)*cng+bin(13579);
Q(i)=cng+xs;
end;
/* Then generate 10^9 b32MWC()s */
do i=1 to 1000000000; x=b32MWC(); end;
if decimal(x) ^= 2769813733 then
put skip list ('b32MWC: x is not the expected value 2769813733', ' x=', x);
/* followed by 10^9 KISSes: */
do i=1 to 1000000000; x=KISS(); end;
if decimal(x)^=3545999299 then
put skip list ('KISS: x is not the expected value 3545999299', ' x=', x);
Finish_time = secs();
put skip edit (Finish_time - Start_time, ' secs') (F(10,2), A);
end rng;
______________

|
| I offer here a MWC (Multiply-With-Carry) RNG whose
| period I cannot determine---nor is it likely that
| anyone else can---but that unknown period is almost
| certainly greater than 10^40000000, i.e, 10^(40million).
| Versions for either 32- and 64-bit integers are given,
| as well as suggestions for similar versions with
| periods as great or even greater magnitude.
|
| MWC RNGs are ordinarily based on primes of the form
| p=ab^r-1, with b=2^32 or 2^64 and a<b. They generate,
| 32- or 64-bits at a time, and in reverse order, the
| binary expansions of rationals j/p, 0<j<p and the
| period of that binary expansion is the order of 2 mod p.
| The key part of the MWC process is: given 32-bit a,x,c,
| extract the top and bottom 32 bits of a 64 bit a*x+c,
| or, for given 64-bit a,x,c, extract the top and bottom
| 64 bits of a 128-bit a*x+c.
|
| I have put various computers to work establishing the
| order of 2 for MWC primes of the form ab^r-1, b=2^32,
| or CMWC (Complimentary-Multiply-With-Carry), p=ab^r+1.
| For example, it took 24 days on an early laptop to
| establish that the order of 2 for p=54767*2^1337287+1
| is (p-1)/2^3, and just last week I put a Samsung 64-bit
| laptop to finding the order of 2 for the 11th largest
| known prime, p=27653*2^9167433+1; in CMWC form,
| p=14158336*b^286482+1. I expect it may take months.
|
| Such searches are motivated by more than a Mt. Everest
| syndrome, as extremely-long-period RNGs not only seem to
| perform very well on tests of randomness, but have uses
| for cryptography. For example, suppose, from a random
| set of seeds, you have observed 100000 successive 32-bit
| numbers from a CMWC RNG based on p=14158336*b^286482+1.
| You will then be somewhere in an immense loop that has
| over 10^(2million) appearances of exactly that same
| sequence of 100000, leaving you virtually no chance of
| finding your particular location and thus able to
| predict forthcoming values.
|
| Of course, if you can observe 286482 successive values,
| then, after a little modular arithmetic to determine
| the carry, you are OK. It is ensuring a large exponent
| for b that makes the RNG desirable---the larger the better.
|
| But in seeking large exponents for b and record periods,
| why bother with an Everest when there are ranges with
| peaks far beyond surveyor's skills but certain
| to be several times as tall?
|
| Such ranges come from considering, for very large r,
| composites of the form m=ab^r-1, rather than primes of
| that form. The example for this posting: the composite
| m=(2^28-1)*2^(2^27)-1=(2^28-1)*b^(2^22)-1.
| m has no prime divisors less than 21000000, and order(2,m)
| is the lcm of the orders mod the prime divisors of m.
| We cannot---and may never be able to--factor such an
| m>10^40403570, but for primes q, the average value of
| order(2,q)/q is around .572. Thus, even if m has, say,
| 40 prime factors, since (.572)^40>10^(-10), we can only
| expect to "lose" around ten 10's, and perhaps ten more
| through common factors for the lcm, providing an estimate
| around 10^40403550 for the order of 2 mod m.
|
| That the order of 2 mod m is less than 10^(40million)
| seems extremely unlikely; we would have to "lose" over
| 400thousand 10's, when something in the range
| of three to sixty 10's seems more likely.
|
| So users should feel confident that the periods of the
| following MWC RNGs far exceed 10^(40million). Based on
| m=(2^28-1)b^(2^22)-1=(2^28-1)b^4194304-1 with b=2^32,
| m=(2^28-1)B^(2^21)-1=(2^28-1)B^2091752-1 with B=2^64,
| they are simple and very fast.
| You would have to observe more than 134 million
| successive bits produced be these MWC RNGs
| in order to get close to cracking them.
|
| Note that choosing a=2^i-1 in m=ab^r-1 makes finding
| the top and bottom 32 bits of a purported 64 bit
| a*x+c feasible using only 32-bit arithmetic,
| or, within 64-bit arithmetic, finding the top
| and bottom 64 bits of a purported 128 bit a*x+c.
|
| Here are C versions using, for 32-bit integers,
| an unsigned long array Q[41943104], and for 64-bits,
| an unsigned long long array Q[2091752].
| Try them and see if you get the same results I do.
|
| --------------------32-bit MWC version-------------------
|
| #include <stdio.h>
| 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 )
|
| int main(void)
| {unsigned long int i,x,cng=123456789,xs=362436069;
| /* First seed Q[] with CNG+XS: */
| for(i=0;i<4194304;i++) Q=CNG+XS;
| /* Then generate 10^9 b32MWC()s */
| for(i=0;i<1000000000;i++) x=b32MWC();
| printf("Does x=2769813733 ?\n x=%lu\n",x);
| /* followed by 10^9 KISSes: */
| for(i=0;i<1000000000;i++) x=KISS;
| printf("Does x=3545999299 ?\n x=%lu\n",x);
| return 0;
| }
|
| ---------------- 64-bit MWC version ---------------------
|
| #include <stdio.h>
| static unsigned long long Q[2097152],carry=0;
|
| unsigned long long B64MWC(void)
| {unsigned long long t,x; static int j=2097151;
| j=(j+1)&2097151;
| x=Q[j]; t=(x<<28)+carry;
| carry=(x>>36)-(t<x);
| return (Q[j]=t-x);
| }
|
| #define CNG ( cng=6906969069LL*cng+13579 )
| #define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<43) )
| #define KISS ( B64MWC()+CNG+XS )
|
| int main(void)
| {unsigned long long i,x,cng=123456789987654321LL,
| xs=362436069362436069LL;
| /* First seed Q[] with CNG+XS: */
| for(i=0;i<2097152;i++) Q=CNG+XS;
| /* Then generate 10^9 B64MWC()s */
| for(i=0;i<1000000000;i++) x=B64MWC();
| printf("Does x=13596816608992115578 ?\n x=%llu\n",x);
| /* followed by 10^9 KISSes: */
| for(i=0;i<1000000000;i++) x=KISS;
| printf("Does x=5033346742750153761 ?\n x=%llu\n",x);
| return 0;
| }
|
| ---------------------------------------------------------
|
| Note that I advocate the KISS, (Keep-It-Simple-Stupid),
| principle. Even though the MWC RNGs perform very well on
| tests of randomness, combining with Congruential (CNG)
| and Xorshift (XS) probably provides extra insurance
| at the cost of a few simple instructions, (and making
| the resulting KISS even harder to crack).
|
| Also note that for unsigned integers such as in Fortran,
| the C instruction -(t<x) means: subtract 1 if t<s,
| and can be implemented for signed integers as t'<s',
| where the ' means: flip the sign bit.
|
| Full random seeding of the carry and the Q[] array
| calls for more than 17 megabytes of random bits.
| For ordinary randomness testing, filling, as above,
| the Q[] array with Congruential+Xorshift may serve, but
| for stronger crypto uses, many more than the random 64-
| or 128-bits that CNG and XS require are needed.
| Random seeding of the carry and the Q[] array amounts to
| producing, either 32- or 64-bits at a time, the reverse-
| order binary expansion of j/m for some 0<=j<=m. Indeed,
| for m=ab^r-1, given the carry and the Q[] array, that j is
|
| j=carry+a*sum(Q*b^i),i=0..r-1.
|
| There are phi(m) such j's with period order(2,m).
| Since m has no prime factors less than 21000000, with
| probability close to 1 a random seeding of Q[] should
| produce a j that is relatively prime to m and thus
| produce the full period---unknown but almost certainly
| far in excess of 10^(40million). Even if random
| seeding of carry and Q[] provides a j with gcd(j,m)>1,
| the period is still likely to exceed 10^(40million).
| There are two exceptions:
| All Q=0, carry=0 yields j=0 and the binary expansion
| 0/m=.00000000000000000...
| All Q=b-1=2^32-1 and carry=a-1=(2^28-2) yields j=m
| and the binary expansion
| m/m=.11111111111111111...
|
| Almost any choice of m=(2^i-1)*2^(2^27)-1 is likely
| to provide an immense order for 2 mod m.
| Choices i=16,18,22,28 resulted in m's that have no
| factors<10^7. Memory seems to be the key restriction
| for the resulting Q[] array. With enough memory,
| one might seek i's for which m=(2^i-1)*2^(2^28)-1
| has no small factors, or even m=(2^i-1)*2^(2^29)-1,
| boosting the unknown and unknowable periods of
| MWC RNGs to ranges beyond 10^(40million).
|
| George Marsaglia
 
G

Greg Rose

Note that I advocate the KISS, (Keep-It-Simple-Stupid),
principle. Even though the MWC RNGs perform very well on
tests of randomness, combining with Congruential (CNG)
and Xorshift (XS) probably provides extra insurance
at the cost of a few simple instructions, (and making
the resulting KISS even harder to crack).

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 -- that is,
there are attacks significantly better than brute
force).

I greatly admire your corpus of work, but please
don't tout these generators as being useful
for cryptography.

Greg.

--
 
R

robin

| In article <603ebe15-a32f-4fbb-ba44-6c73f7919a33@t35g2000yqj.googlegroups.com>,
| >Note that I advocate the KISS, (Keep-It-Simple-Stupid),
| >principle. Even though the MWC RNGs perform very well on
| >tests of randomness, combining with Congruential (CNG)
| >and Xorshift (XS) probably provides extra insurance
| >at the cost of a few simple instructions, (and making
| >the resulting KISS even harder to crack).
|
| 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.

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?
 
M

Maaartin

"Greg Rose" <[email protected]> wrote in messagenews:[email protected]...
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.

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?

Sorry, but for claiming that KISS is broken it's enough to break one
KISS. The existence of many equally named PRNGs is surely not Greg's
fault. I really like Marsaglia's work, but I'd strongly prefer him to
at least number his kisses.
 
R

robin

|
| I offer here a MWC (Multiply-With-Carry) RNG whose
| period I cannot determine---nor is it likely that
| anyone else can---but that unknown period is almost
| certainly greater than 10^40000000, i.e, 10^(40million).

Here is the 64-bit version using PL/I :--

/* 64-bit version in PL/I using unsigned arithmetic 18/1/2011 */
(nosize):
rng64: procedure options (main);
declare (Q(0:2097151), carry initial (0)) unsigned fixed binary (64)
static;

B64MWC: procedure () returns (unsigned fixed binary (64));
declare (t,x) unsigned fixed binary (64);
declare j fixed binary (31) static initial (2097151);
j=iand(j+1, 2097151);
x=Q(j); t=isll(x, 28)+carry;
carry=isrl(x, 36)-(t<x);
Q(j)=t-x;
return (Q(j));
end B64MWC;

KISS: procedure() returns (unsigned fixed binary (64));
declare t unsigned fixed binary (64);
t = B64MWC();
cng=unsigned(6906969069, 64)*cng+unsigned(13579);
xs = ieor(xs, isll(xs, 13));
xs = ieor(xs, isrl(xs, 17));
xs = ieor(xs, isll(xs, 43));
return (t + cng + xs);
end KISS;

declare (i,x,cng static initial (123456789987654321),
xs static initial (362436069362436069))
unsigned fixed binary (64);
declare (start_time, finish_time) float (18);
start_time = secs();

/* First seed Q with CNG+XS: */
do i=0 to 2097151;
xs = ieor(xs, isll(xs, 13));
xs = ieor(xs, isrl(xs, 17));
xs = ieor(xs, isll(xs, 43));
cng=unsigned(6906969069, 64)*cng+unsigned(13579);
Q(i)=CNG+XS;
end;

/* Then generate 10^9 B64MWC()s */
do i=1 to 1000000000; x=B64MWC(); end;
put skip list (x);
if decimal(x) ^= 13596816608992115578 then
put list ('is not the expected value 13596816608992115578');

/* followed by 10^9 KISSes: */
do i=1 to 1000000000; x=KISS(); end;
put skip list (x);
if decimal(x) ^= 5033346742750153761 then
put list ('is not the expected value 5033346742750153761');

Finish_time = secs();
put skip edit (Finish_time - Start_time, ' secs') (F(10,2), A);

end rng64;
 
T

Tom St Denis

Sorry, but for claiming that KISS is broken it's enough to break one
KISS. The existence of many equally named PRNGs is surely not Greg's
fault. I really like Marsaglia's work, but I'd strongly prefer him to
at least number his kisses.

Well that, and as Greg pointed out, stop toting them as suitable for
cryptography. Even if they were secure the large state required is
next to impossible to manage properly, so you'd need to seed the state
from a smaller seed somehow [key expansion of some sort].

Thing is George is not a cryptographer. He should stick to comp.sci
and mathematics.

Tom
 
M

Maaartin

Sorry, but for claiming that KISS is broken it's enough to break one
KISS. The existence of many equally named PRNGs is surely not Greg's
fault. I really like Marsaglia's work, but I'd strongly prefer him to
at least number his kisses.

Well that, and as Greg pointed out, stop toting them as suitable for
cryptography.  Even if they were secure the large state required is
next to impossible to manage properly, so you'd need to seed the state
from a smaller seed somehow [key expansion of some sort].

The previous versions have much smaller state, actually maybe too
small for crypto (<128 bits for the 32 bit version). I really do not
consider using it for crypto, I just like the idea. What I don't like
is the lack of seeding and the missing partitioning to setup, working
code, and test. As a simple exercise I implemented it as a subclass of
java.utilRandom, s. http://dl.dropbox.com/u/4971686/110119/Kiss1101.java
 
D

David Bernier

Noob said:
[...]

I tried that. It's probably a bit faster. However, timings vary
for blocks of the same length, from one block to the next.

I'm simulating tossing a fair coin 1024 times, over and over.
The "model" distribution is a binomial, with n = 1024, p = 1/2 .

I'm thinking of a Pearson chi-squared test for goodness of fit:
< http://en.wikipedia.org/wiki/Pearson's_chi-square_test > .

Maybe I should have "cells" for n_heads < M_0, n_heads > M_1 such that
the count for n_heads < M_0 is at least 10, and so is the count for
n_heads > M_1 ; I could require all "cells" to have counts of at least
10 sequences.

The 1024 "tosses" are generated from 16 64-bit KISS values.

I'm quite satisfied with the speed. Assembler has a reputation for
being faster, but that would take too long to do.

In a day and a bit:

After 688 billion trial 1024-bit sequences ...


2 6 6 6 9 11
25 43 44 91 115
160 218 354 516 774
1004 1498 2209 3153 4404
6220 8677 12051 16767 23355
32910 44862 61465 84042 114500
154859 208323 282213 378564 504827
672710 887162 1172437 1542000 2016182
2625848 3410628 4409349 5678094 7286055
9309772 11849071 15018493 18964434 23850479
29881319 37276043 46346250 57366390 70733488
86878861 106296411 129531866 157224264 190103929
228935360 274634376 328138070 390556751 462994047
546750599 643047284 753440174 879281478 1022090163
1183499614 1365004984 1568207777 1794511395 2045557046
2322490755 2626697375 2959148480 3320720519 3711682285
4132743882 4583290104 5063288742 5571754316 6107137837
6668098343 7252006617 7856312800 8477791876 9112934558
9757413629 10406488027 11055767102 11699222514 12332330682
12948934986 13543555420 14109864079 14642975075 15136887502
15586436970 15986946088 16333743828 16623343986 16851555328
17017024693 17116782122 [17150519987] 17116704125 17016908297
16851562445 16623139927 16333732876 15986873787 15586668293
15136798374 14643132384 14110154516 13543303338 12949086781
12332367119 11699195736 11055519863 10406500418 9757209991
9113057442 8478042642 7856436839 7252072161 6668110183
6107368395 5571720944 5063315421 4583385726 4132735113
3711777983 3320733023 2959242217 2626691521 2322624711
2045549959 1794518656 1568196749 1365042289 1183441113
1022096045 879316568 753447591 643105525 546724802
463029238 390541951 328138254 274644721 228936396
190121070 157223370 129540510 106291797 86895735
70741595 57362422 46345642 37283423 29875748
23846352 18957163 15006970 11846044 9303192
7282256 5672867 4411262 3410431 2625121
2014158 1541281 1172598 886975 672200
504195 378079 281893 209662 155295
114558 84061 61291 44746 32585
23393 17120 11992 8578 6006
4366 3058 2138 1484 1096
741 515 363 242 149
108 73 46 43 9
15 11 9 2 1
0 1 0 2 1

[17150519987] --> most likely counts of 512 "heads".

David Bernier
 
M

mike3

I wrote a paper cryptanalyzing the original KISS,
available athttp://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 -- that is,
there are attacks significantly better than brute
force).

However, is this attack so much better as to be
feasible to carry out with technology we have or
are likely to have? E.g. an attack with complexity
like 10^100 or 10^200 is pretty much worthless.
I'm curious: how then would such a huge lack of
"theoretical" security be a problem for actual
use when it's still not easily breakable? Is it
because that if an attack capable of cutting it
down that far is possible, there's almost certainly
an unknown one that cuts it down to the "feasible"
range?
 
G

Greg Rose

| 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.
--
 
G

Greg Rose

However, is this attack so much better as to be
feasible to carry out with technology we have or
are likely to have? E.g. an attack with complexity
like 10^100 or 10^200 is pretty much worthless.
I'm curious: how then would such a huge lack of
"theoretical" security be a problem for actual
use when it's still not easily breakable? Is it
because that if an attack capable of cutting it
down that far is possible, there's almost certainly
an unknown one that cuts it down to the "feasible"
range?

I've just posted an attack on this new KISS with
complexity around 2^86 "basic operations" or 2^63
"key setup operations". Even these numbers are
impractical attacks, today, but are much worse
than anything a cryptographer would consider
acceptable.

Greg.
--
 
J

jacob navia

Le 20/01/11 03:21, Greg Rose a écrit :
I've just posted an attack on this new KISS with
complexity around 2^86 "basic operations" or 2^63
"key setup operations". Even these numbers are
impractical attacks, today, but are much worse
than anything a cryptographer would consider
acceptable.

Greg.

Supposing 2^86 basic operations:
Makes 7.737125245533627e+25 operations.
Assuming a double core machine making 2 billion basic
operations per second makes
3.868562622766814e+16

Supposing you use 1000 machines, that makes it
38 685 626 227 668,135

You run your 1000 machines 365 days /year:
(365*24*3600) --> 31 536 000 seconds in a year

Result: 1 226 713,160441024067732 years,
more than a MILLION years until you crack it.

Supposing machines get 100 times as fast as today
in the next 10 years, you still would have for more
than 12 thousand years (12 267,131)
 
M

Maaartin

Le 20/01/11 03:21, Greg Rose a écrit :

Supposing machines get 100 times as fast as today
in the next 10 years, you still would have for more
than 12 thousand years (12 267,131)

That may be true, but it's irrelevant since "attacks get only better".
Greg probably didn't spend much time on it, the point is that the
existence of such an attack indicates the possibility of much better
attacks. Finding them may take a lot of work, but somebody would do it
if it was important enough. Any new crypto PRNG/cipher/hash/whatever
gets analyzed by many people for many years before it gets accepted.
Finding any attack, even one even much more impractical than above is
a definite stop sign.
 
G

Greg Rose

That may be true, but it's irrelevant since "attacks get only better".
Greg probably didn't spend much time on it, the point is that the
existence of such an attack indicates the possibility of much better
attacks. Finding them may take a lot of work, but somebody would do it
if it was important enough. Any new crypto PRNG/cipher/hash/whatever
gets analyzed by many people for many years before it gets accepted.
Finding any attack, even one even much more impractical than above is
a definite stop sign.

Yes, what Maaartin said. Even I said "impractical" above.
But the point is, we have stream ciphers and PRNGs
with far higher resistance to attack, with state sizes
of a few hundred *bits*.

KISS (any of them) is a fine PRNG for simulations,
stand-alone games, and stuff like that. But I
counsel against using them for anything where security
is important. That's all I'm saying.

Greg.
--
 

Ask a Question

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.

Ask a Question

Members online

Forum statistics

Threads
473,818
Messages
2,569,732
Members
45,691
Latest member
Dick331194

Latest Threads

Top