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