From: David A Molnar Subject: Re: Weakness of MLCG style encryption Date: 8 Jul 1999 01:53:11 GMT Newsgroups: sci.crypt,sci.math Keywords: Linear Congruential Generators In sci.crypt Greg Keogh wrote: > I only follow encryption as a hobby, so without any deep maths background I' > m somewhat dumbfounded that these pseudo-random sequence generators that > seem so fantastically random are of no use for XORing streams. Can anyone > give me a potted summary of why this is so? A single LCG by itself is very predictable. This makes sense when you think of it as the equation of a line, just with a mod thrown in. There's a lot of "structure" there. It turns out that single LCGs are predictable from their output alone, even without any of the parameters known. Klaus Pommering posted a link to a program which demonstrates this using methods developed by Joan Boyar. They are even predictable if only part of the output is used - it only means a few more messages need to be examined by the adversary. I haven't looked up the references given in _Applied Cryptography_ on multiple LCGs yet, but since single generators are so easy to predict even from _partial outputs_, I imagine it's something like separating out which bits came from which generator and then cracking them all that way. Please don't take my word for it if you can help it, however. > How strong are they in practical > terms? Systems which depend on LCGs can almost always be broken with a number of messages polynomial in some reasonable measure of size. The exact number depends on the system at hand. Still, they generally aren't a good idea to use in any system which will see general use. > What techniques are used to break them? i i Every output of an LCG allows you to define an equation value_i = ax_i + c mod n where value_i is the output, which you know. x_i is the state of the generator at that point. a and c and n may or may not be known (depends on your implementation). The more outputs you get, the more equations you have. These equations can be considered as vectors, or as constraints on a linear programming problem. You use these to build a lattice with the property that knowing its shortest vector gives you the seed value x_0 , or some value which producs equivalent outputs to the LCG you have. A "lattice" can be thought of as all the _integer_ linear combinations of a particular set of vectors. So if I give you a set of k vectors [v_1 ... v_k ], then the lattice vectors are given by L := n_1 * v_1 ... n_k * v_k, n_i \in Z There's an algorithm known as LLL (after the inventors, Lenstra, Lenstra, and Lova`s) which finds shortest vectors in a lattice. It produces answers which are approximate within a ball of exponential radius. That is, if it finds a solution, you normally don't know that there isn't a better solution "nearby". For LCGs, it turns out that after "enough" equations, where "enough" depends on how you set up the lattice, you can show that the shortest vector is unique within a radius greater than the approximation error of LLL. In other words, LLL finds an answer, and you know by the way the lattice is put together that it must be the _right one_. That's a not-very-detailed explanation. There are lots of details in various papers, if you want them. That's not the only way the problem has been thought of, by the way. It's just the one I've looked at most. Nor is it necessarily what _Applied Crypto_ referred to when discussing MLCGs. It's just a fairly neat idea. >Etc. Any general information > or web references would be most welcome. Terry Ritter posted a list of papers on predicting LCGs in a thread a few months back; it should be on deja or your favorite sci.crypt archive. His page has some interesting literature overviews and archived discussions, too. Knuth vol 2 has discussions of LCGs and some exercises which may be of interest. Knuth also wrote one of the first papers on predicting LCGs. For an overview of how this lattice stuff works in practice, try " 'Pseudo-random' number generation : the DSS Case" at http://theory.lcs.mit.edu/~miccianc/papers/dss.ps I don't think any of these much address multiple LCGs, but they should prove illustrative of how unfortunate it is as a crypto primitive. -David ============================================================================== From: George Marsaglia Subject: Re: random number generator--What's available? LCG,MRG,ICG,...? Date: Wed, 24 Feb 1999 11:35:51 -0500 Newsgroups: sci.math.symbolic M. Monacelli wrote: > Two questions: > > (1) What type of RNG (random number generator) is used by Mathematica? > Is it an LCG, MRG, GFSR, ICG, etc.? I recently read the Maple's > LCG is (10^(12)-11,427419669081,0,1), but this leads me to wonder > whether this is the only RNG used by Maple or does it use an ICG, > MRG, etc. sometimes? > > I am trying to get this information not just about Maple's RNG, > but also Mathematica's, Matlab's and other popular Mathematics > software tools available today. > > (2) Does anyone know where I can find archives of the mailing lists for > Mathematica or Matlab or Maple? Do these archives exist? > For question (1): If your unknown random integers are generated as x(n+1)=a*x(n)+b mod m, then it is easy to find m, and then a,b. This has been obvious since "random numbers fall mainly in the planes" established the lattice structure of such sequences in the 1960's. It was many years later before people in Cryptography developed more complicated methods to "crack" linear congruential generators. For any i,j let d(i,j) be the absolute value of the determinant of the 2x2 matrix with rows (x(i)-x(1),x(i+1)-x(2)) (x(j)-x(1),x(j+1)-x(2)) This is the volume of a parallelepiped determined by three points in the plane with coordinates succesive integers from the generator. Because the points lie on a lattice, that volume must be a multiple of the unit-cell volume, which is m^(n-1) in n dimensions, So the modulus of the generator is the gcd of all the possible d values. In practice, one need only find the gcd of the first few: g(1)=f(2,3): g(2)=gcd(g(1),f(3,4)), g(3)=gcd(g(2),f(4,5)),... will quickly reduce to m. Example: In Maple, 4 calls to rand() provided the integers 433599229456 ,898724880795, 485531802023 ,255050614524 ,952922474293 Call them x(1),x(2),x(3),x(4),x(5) Then d(2,3),d(3,4),d(4,5) are 277931232801942756439145, 112112528252766762189206, 17680137253805518490206 and g(1)=f(2,3), g(i)=gcd(g(i-1),d(i+1,i+2), i=2,3,... becomes, from g(2) , the constant sequence ...,999999999989,999999999989,999999999989,... Solving a*x1=x2 mod 999999999989 yields a=427419669081, and sure enough, the Maple sequence produced by rand() is the sequence x(n)=427419669081*x(n-1) mod 999999999989. Example: x(n)=16807*x(n-1) mod 2^31-1, Lehmer's original suggestion for a RNG. Starting with x(1)=1234567, the first few are 1234567, 1422014746, 456328559, 849987676, 681650688, 1825340118, and d(2,3)=1000459255431253815 d(3,4)=411422373155482384 d(4,5)=1086868944357512424 With g(1)=d(1,2) and g(i)=gcd(g(i-1),d(i+1,i+2)) for i>1, the sequence g(1),g(2),g(3),... immediately converges to the the modulus m = 2^31-1. THE GENERAL PROCEDURE: Define d(i,j)=abs[(x(i)-x(1))*(x(j+1)-x(2))-(x(i+1)-x(2))*(x(j)-x(1))] and g(1)=d(2,3) and g(i)=gcd(g(i-1),d(i+1,i+2)) for i=2,3,.... Then the sequence g(1),g(2),g(3),... will quickly tail off to a constant value ...m,m,m,... , the modulus of the linear congruential generator. (For LCG's that exploit arithmetic modulo 2^32: x(n)=a*x(n-1) mod 2^32 points (x(i),x(i+1)) lie not only on a lattice with unit cell volume 2^32, they may lie on a proper sublattice with unit cell volume 2*m or 4*m. So a little extra work is required to distinguish which modulus to use: 4m,2m or m.) For background theory, see "Random numbers fall mainly in the planes," Proceedings of the National Academy of Sciences v 61, 25--28, 1968. "Regularities in congruential random number generators," Numerische Mathematik v 16, 8--10, 1970. "The structure of linear congruential sequences," in Applications of Number Theory to Numerical Analysis, Z. K. Zaremba, ed., New York: Academic Press, pp249--285, 1972. George Marsaglia