[Cryptography] An interesting little pseudorandom number generator

[Ray Dillinger]

Here's a recent discovery:  (presented without initialization code)

unsigned long A[256];
unsigned int N;
unsigned long pseudorandom(){
    N--;
    A[N%256] = A[(N+5)%256] + A[(N+17)%256];
    A[(N+17)%256] = A[(N+41)%256] + A[(N+72)%256];
    A[(N+72)%256] = A[(N+120)%256] + A[(N+161)%256];
    A[(N+161)%256] = A[(N+163)%256] + A[(N+255)%256];
    return(A[N%256] + A[(A[(N+17)%256] + (A[(N+72)%256]))%256]);
}


This is four Lagged Fibonacci Generators chasing each other
nose-to-tail, cycling around in a shared 256-word buffer.

Respectively, they are
An=A(n-5)+A(n-17), Bn=B(n-24)+B(n-55), Cn=C(n-38)+C(n-89), and
Dn=D(n-2)+D(n-93).


The generator returns the output of the first LFG added to whatever
array element is indexed by the sum of the outputs of the second and
third.  The fourth is not used directly but determines the value of over
a third of the elements returned by indexing.

The periods of these four generators is maximal for their respective
lengths, and have no
common factors except 2^wordsize.  Therefore the period of the whole
generator is expected
to be:

(2^wordsize) * (2^17 -1) * (2^55 -1) * (2^89 -1) * (2^93 -1)

There are  a factor of 2^(3*wordsize) more possible states than that. 
Most are in cycles of the same length,   but some fraction of them are
on degenerate cycles having shorter periods (as happens when one of the
LFGs has some number of low bits that are all zero, for example).  So
some care must be taken to initialize it to a non-degenerate state.

It is well known that anybody can make a cipher (or PRNG) that they
personally cannot break.  But I think this is that rarer thing; a PRNG
that nobody *else* can break.  If initialization takes care to avoid
known classes of degenerate states, I think I would trust it.  I would
happily base a cipher on it.   Or possibly on an expanded version of it
with four larger LFGs.

That may be something that someone else has better insight into, but I
don't see a way in.  I have a fairly good grasp of LFGs and their
limitations. The summation and indirect indexing in this construction
defeats all attacks on those limitations that I'm aware of.  And it
passes all the sequence pattern detectors ('randomness tests') I've
thrown at it with flying colors.

Anybody have some insights that I missed?

Bear