# What stops the Multiply-With-Carry RNG from being a Cryptographically Secure PRNG?

Despite the fact that Marsaglia's MWC PRNG (multiply-with-carry random number generator) is considered to be "the mother of all RNGs", it does not seem to be considered to be a CSPRNG (cryptographically secure pseudo-random number generator) even though it passes several statistical randomness tests, including ENT and Die-Hard.

Considering it's possible to define a seed etc., what is the MWC RNG missing that a CSPRNG has? Simpler asked: "What stops the MWC PRNG from being a CSPRNG?"

CSPRNGs have to pass statistical randomness tests, which MWC RNG seems to satisfy. Also, MWC PRNG allows you to choose random initial as long as c < 809430660, which seems big enough to make it hard for people to analyse which of the 809430659 options you chose to seed the MWC PRNG. And last but not least people call it the "mother of all RNGs" — see George Marsaglia's "Mother of all RNGs" (C code with comments) (via archive.org) — which implies it's about the best (P)RNG out there.

Comparing MWC PRNG with cryptographically secure PRNGs, it shows both are pseudo-random, both produce comparable randomness, and both pass the same statistical tests. Some even claim it has cryptographic quality. Yet, I can not find a single indication that it is cryptographically secure.

Therefore I am wondering and asking: "What stops the MWC PRNG from being a CSPRNG?"

Or, asking in other words:

• What is the MWC PRNG missing a CSPRNG should have to be cryptographically secure, and/or
• What does the MWC PRNG have that a CSPRNG should not have to be cryptographically secure?

Currently, I am suspecting I am missing some security definition related to cryptographically secure pseudo-random number generators, or maybe I'm not seeing the obvious security issue which makes the MWC PRNG cryptographically insecure. Therefore, every explanation which could help me understand why the MWC PRNG fails to be classified as a cryptographically secure PRNG is highly appreciated.

In case someone needs some references related to MWC PRNG…

Since Berkeley obviously removed all of George Marsaglia's work during a server cleanup, which is why I’m posting a copy of stat.berkeley.edu/classes/s243/mother.c here for reference purposes:

/*

Article: 16024 of sci.math.num-analysis
Xref: taurus.cs.nps.navy.mil sci.stat.consult:7790 sci.math.num-analysis:16024
Path: taurus.cs.nps.navy.mil!lll-winken.llnl.gov!uwm.edu!news.alpha.net!news.mathworks.com!udel!ssnet.com!usenet
From: Bob Wheeler <bwheeler@ssnet.com>
Newsgroups: sci.stat.consult,sci.math.num-analysis
Subject: Marsaglia's Mother of all RNG's (Long?)
Date: Fri, 28 Oct 94 19:32:08 EDT
Organization: SSNet -- Public Internet Access in Delaware!
Lines: 285
Distribution: inet
Message-ID: <38s2p1$qaf@marlin.ssnet.com> NNTP-Posting-Host: echip.com Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Newsreader: NEWTNews & Chameleon -- TCP/IP for MS Windows from NetManage Several people have asked me to post this: First the C program, then George Marsaliga's post with details about the RNG. He claims a period of about 2^250 for this and that it passes all of the usual tests. I've tried it enough to be sure his claim is reasonable. The program: */ #include <string.h> static short mother1[10]; static short mother2[10]; static short mStart=1; #define m16Long 65536L /* 2^16 */ #define m16Mask 0xFFFF /* mask for lower 16 bits */ #define m15Mask 0x7FFF /* mask for lower 15 bits */ #define m31Mask 0x7FFFFFFF /* mask for 31 bits */ #define m32Double 4294967295.0 /* 2^32-1 */ /* Mother ************************************************************** | George Marsaglia's The mother of all random number generators | producing uniformly distributed pseudo random 32 bit values with | period about 2^250. | The text of Marsaglia's posting is appended at the end of the function. | | The arrays mother1 and mother2 store carry values in their | first element, and random 16 bit numbers in elements 1 to 8. | These random numbers are moved to elements 2 to 9 and a new | carry and number are generated and placed in elements 0 and 1. | The arrays mother1 and mother2 are filled with random 16 bit values | on first call of Mother by another generator. mStart is the switch. | | Returns: | A 32 bit random number is obtained by combining the output of the | two generators and returned in *pSeed. It is also scaled by | 2^32-1 and returned as a double between 0 and 1 | | SEED: | The inital value of *pSeed may be any long value | | Bob Wheeler 8/8/94 */ double Mother(unsigned long *pSeed) { unsigned long number, number1, number2; short n, *p; unsigned short sNumber; /* Initialize motheri with 9 random values the first time */ if (mStart) { sNumber= *pSeed&m16Mask; /* The low 16 bits */ number= *pSeed&m31Mask; /* Only want 31 bits */ p=mother1; for (n=18;n--;) { number=30903*sNumber+(number>>16); /* One line multiply-with-cary */ *p++=sNumber=number&m16Mask; if (n==9) p=mother2; } /* make cary 15 bits */ mother1[0]&=m15Mask; mother2[0]&=m15Mask; mStart=0; } /* Move elements 1 to 8 to 2 to 9 */ memmove(mother1+2,mother1+1,8*sizeof(short)); memmove(mother2+2,mother2+1,8*sizeof(short)); /* Put the carry values in numberi */ number1=mother1[0]; number2=mother2[0]; /* Form the linear combinations */ number1+=1941*mother1[2]+1860*mother1[3]+1812*mother1[4]+1776*mother1[5]+ 1492*mother1[6]+1215*mother1[7]+1066*mother1[8]+12013*mother1[9]; number2+=1111*mother2[2]+2222*mother2[3]+3333*mother2[4]+4444*mother2[5]+ 5555*mother2[6]+6666*mother2[7]+7777*mother2[8]+9272*mother2[9]; /* Save the high bits of numberi as the new carry */ mother1[0]=number1/m16Long; mother2[0]=number2/m16Long; /* Put the low bits of numberi into motheri[1] */ mother1[1]=m16Mask&number1; mother2[1]=m16Mask&number2; /* Combine the two 16 bit random numbers into one 32 bit */ *pSeed=(((long)mother1[1])<<16)+(long)mother2[1]; /* Return a double value between 0 and 1 */ return ((double)*pSeed)/m32Double; } /* ********************* Marsaglia's comments Yet another RNG Random number generators are frequently posted on the network; my colleagues and I posted ULTRA in 1992 and, from the number of requests for releases to use it in software packages, it seems to be widely used. I have long been interested in RNG's and several of my early ones are used as system generators or in statistical packages. So why another one? And why here? Because I want to describe a generator, or rather, a class of generators, so promising I am inclined to call it The Mother of All Random Number Generators and because the generator seems promising enough to justify shortcutting the many months, even years, before new developments are widely known through publication in a journal. This new class leads to simple, fast programs that produce sequences with very long periods. They use multiplication, which experience has shown does a better job of mixing bits than do +,- or exclusive-or, and they do it with easily- implemented arithmetic modulo a power of 2, unlike arithmetic modulo a prime. The latter, while satisfactory, is difficult to implement. But the arithmetic here modulo 2^16 or 2^32 does not suffer the flaws of ordinary congruential generators for those moduli: trailing bits too regular. On the contrary, all bits of the integers produced by this new method, whether leading or trailing, have passed extensive tests of randomness. Here is an idea of how it works, using, say, integers of six decimal digits from which we return random 3- digit integers. Start with n=123456, the seed. Then form a new n=672*456+123=306555 and return 555. Then form a new n=672*555+306=373266 and return 266. Then form a new n=672*266+373=179125 and return 125, and so on. Got it? This is a multiply-with-carry sequence x(n)=672*x(n-1)+ carry mod b=1000, where the carry is the number of b's dropped in the modular reduction. The resulting sequence of 3- digit x's has period 335,999. Try it. No big deal, but that's just an example to give the idea. Now consider the sequence of 16-bit integers produced by the two C statements: k=30903*(k&65535)+(k>>16); return(k&65535); Notice that it is doing just what we did in the example: multiply the bottom half (by 30903, carefully chosen), add the top half and return the new bottom. That will produce a sequence of 16-bit integers with period > 2^29, and if we concatenate two such: k=30903*(k&65535)+(k>>16); j=18000*(j&65535)+(j>>16); return((k<<16)+j); we get a sequence of more than 2^59 32-bit integers before cycling. The following segment in a (properly initialized) C procedure will generate more than 2^118 32-bit random integers from six random seed values i,j,k,l,m,n: k=30903*(k&65535)+(k>>16); j=18000*(j&65535)+(j>>16); i=29013*(i&65535)+(i>>16); l=30345*(l&65535)+(l>>16); m=30903*(m&65535)+(m>>16); n=31083*(n&65535)+(n>>16); return((k+i+m)>>16)+j+l+n); And it will do it much faster than any of several widely used generators designed to use 16-bit integer arithmetic, such as that of Wichman-Hill that combines congruential sequences for three 15-bit primes (Applied Statistics, v31, p188-190, 1982), period about 2^42. I call these multiply-with-carry generators. Here is an extravagant 16-bit example that is easily implemented in C or Fortran. It does such a thorough job of mixing the bits of the previous eight values that it is difficult to imagine a test of randomness it could not pass: x[n]=12013x[n-8]+1066x[n-7]+1215x[n-6]+1492x[n-5]+1776x[n-4] +1812x[n-3]+1860x[n-2]+1941x[n-1]+carry mod 2^16. The linear combination occupies at most 31 bits of a 32-bit integer. The bottom 16 is the output, the top 15 the next carry. It is probably best to implement with 8 case segments. It takes 8 microseconds on my PC. Of course it just provides 16-bit random integers, but awfully good ones. For 32 bits you would have to combine it with another, such as x[n]=9272x[n-8]+7777x[n-7]+6666x[n-6]+5555x[n-5]+4444x[n-4] +3333x[n-3]+2222x[n-2]+1111x[n-1]+carry mod 2^16. Concatenating those two gives a sequence of 32-bit random integers (from 16 random 16-bit seeds), period about 2^250. It is so awesome it may merit the Mother of All RNG's title. The coefficients in those two linear combinations suggest that it is easy to get long-period sequences, and that is true. The result is due to Cemal Kac, who extended the theory we gave for add-with-carry sequences: Choose a base b and give r seed values x[1],...,x[r] and an initial 'carry' c. Then the multiply-with-carry sequence x[n]=a1*x[n-1]+a2*x[n-2]+...+ar*x[n-r]+carry mod b, where the new carry is the number of b's dropped in the modular reduction, will have period the order of b in the group of residues relatively prime to m=ar*b^r+...+a1b^1-1. Furthermore, the x's are, in reverse order, the digits in the expansion of k/m to the base b, for some 0<k<m. In practice b=2^16 or b=2^32 allows the new integer and the new carry to be the bottom and top half of a 32- or 64-bit linear combination of 16- or 32-bit integers. And it is easy to find suitable m's if you have a primality test: just search through candidate coefficients until you get an m that is a safeprime---both m and (m-1)/2 are prime. Then the period of the multiply-with- carry sequence will be the prime (m-1)/2. (It can't be m-1 because b=2^16 or 2^32 is a square.) Here is an interesting simple MWC generator with period> 2^92, for 32-bit arithmetic: x[n]=1111111464*(x[n-1]+x[n-2]) + carry mod 2^32. Suppose you have functions, say top() and bot(), that give the top and bottom halves of a 64-bit result. Then, with initial 32-bit x, y and carry c, simple statements such as y=bot(1111111464*(x+y)+c) x=y c=top(y) will, repeated, give over 2^92 random 32-bit y's. Not many machines have 64 bit integers yet. But most assemblers for modern CPU's permit access to the top and bottom halves of a 64-bit product. I don't know how to readily access the top half of a 64-bit product in C. Can anyone suggest how it might be done? (in integer arithmetic) George Marsaglia geo@stat.fsu.edu */  And here's a copy of Marsaglia's original publication, which was first published at sci.stat.math… good C random number generator From: George Marsaglia (geo@stat.fsu.edu) Subject: Re: good C random number generator Newsgroups: comp.lang.c Date: 2003-05-13 08:55:05 PST Organization: Florida State University Lines: 89 Most RNGs work by keeping a certain number, say k, of the most recently generated integers, then return the next integer as a function of those k. The initial k integers, the seeds, are assumed to be randomly chosen, usually 32-bits. The period of the RNG is related to the number of choices for seeds, usually 2^(32k), so to get longer periods you need to increase k. Probably the most common type has k=1, and needs a single seed, with each new integer a function of the previous one. An example is this congruential RNG, a form of which was the system RNG in VAXs for many years:  /* a random initial x to be assigned by the calling program */ static unsigned long x=123456789; unsigned long cong(void ) { return (x=69069*x+362437); }  Simple, k=1, RNGs can perform fairly well in tests of randomness such as those in the new version of Diehard,  csis.hku.hk/~diehard  but experience has shown that better performances come from RNGs with k's ranging from 4 or 5 to as much as 4097. Here is an example with k=5, period about 2^160, one of the fastest long period RNGs, returns more than 120 million random 32-bit integers/second (1.8MHz CPU), seems to pass all tests:  /* replace defaults with five random seed values in calling program */ static unsigned long x=123456789,y=362436069,z=521288629,w=88675123,v=886756453; unsigned long xorshift(void) { unsigned long t; t=(x^(x>>7)); x=y; y=z; z=w; w=v; v=(v^(v<<6))^(t^(t<<13)); return (y+y+1)*v; }  Another example has k=257, period about 2^8222. Uses a static array Q[256] and an initial carry 'c', the Q array filled with 256 random 32-bit integers in the calling program and an initial carry c<809430660 for the multiply-with-carry operation. It is very fast and seems to pass all tests.  /* choose random initial c<809430660 and 256 random 32-bit integers for Q[] */ static unsigned long Q[256],c=362436; unsigned long MWC256(void) { unsigned long long t,a=809430660LL; static unsigned char i=255; t=a*Q[++i]+c; c=(t>>32); return(Q[i]=t); }  The Mersenne Twister (check Google) is an excellent RNG, with k=624. But it requires an elaborate C program and is slower than many RNGs that do as well in tests, have comparable or longer periods and require only a few lines of code. Here is a complimentary-multiply-with-carry RNG with k=4097 and a near-record period, more than 10^33000 times as long as that of the Twister. (2^131104 vs. 2^19937)  /* choose random initial c<809430660 and 4096 random 32-bit integers for Q[] */ static unsigned long Q[4096],c=362436; unsigned long CMWC4096(void) { unsigned long long t, a=18782LL; static unsigned long i=4095; unsigned long x,r=0xfffffffe; i=(i+1)&4095; t=a*Q[i]+c; c=(t>>32); x=t+c; if(x<c) { x++; c++; } return(Q[i]=r-x); }  You will find several more CMWC RNGs and comments on choice of seeds in the May 2003 Communications of the ACM. George Marsaglia • This article may be helpful: eprint.iacr.org/2011/007 The short story is that given MWC output, it's fairly easy to recover internal state and do all kinds of bad things from there. – Samuel Neves Sep 15 '13 at 18:29 • I suppose the "mother of all RNGs" is mostly a historic description, not a quality one: many other RNGs came later and borrowed from its design. – Paŭlo Ebermann Mar 1 '14 at 11:53 ## 2 Answers It fails to be a cryptographically-strong PRNG because it is predictable: given some outputs, you can predict the next outputs. For instance, if you observe the outputs at offsets 0, 1, and 4096, you can predict what the output will be at offset 4097. What it's missing: it's not that it's missing some little tweak (just change line 7 to use addition instead of xor, something like that). What it's missing is that it fundamentally wasn't designed to be cryptographically-strong. A cryptographically-strong PRNG needs to be designed in a very different way from a non-crypto PRNG. This was designed to be a non-crypto PRNG, and that's what it is. In particular, it sounds like MWC was designed to have a long period. But having a long period does not guarantee that a PRNG will be crypto-strength; not anywhere near it. Crypto-strength PRNGs have much stronger requirements, so there is no reason to expect that a statistical non-crypto PRNG will be cryptographically strong (it almost certainly won't be, if it wasn't designed to be). If you want a crypto-strength PRNG, you need to pick one that was designed to be that way from the start; you're not likely to fare well by picking a non-crypto PRNG and then trying to tweak it. Anyway, I'm not sure why this question comes up. We have crypto-strength PRNGs that are secure, fast, and well-vetted. I don't know why one would mess around with trying to design your own based upon a non-crypto PRNG; that way leads to insecurity. If you think you can do better than the entire field at designing fast crypto-strength PRNGs... well, maybe you can, but I doubt the odds are on your side. Instead, I recommend you use a standard crypto-strength PRNG, if you need crypto-quality pseudorandom numbers. • Wikipedia has a reasonable explanation of what "security" means. Note that no RNG that "work[s] by keeping a certain number, say k, of the most recently generated integers, then return[ing] the next integer as a function of those k" can possibly satisfy the next-bit test, because anyone who's seen its k most recently generated integers can predict its entire future output. – Gordon Davisson Sep 15 '13 at 18:25 Even though it passes some statistical tests, it fails hardly the spectral test with 3 dimensions. You can reproduce that with R: RNGkind("Marsaglia-Multicarry") RNG <- runif(10000000) RNG.data <- data.frame(RNG.R) RNG.data$id <- as.numeric(row.names(RNG.data))
library("rgl")
plot3d (RNG.data[1:9998,1],
RNG.data[2:9999,1],
RNG.data[3:10000,1])