Anyone interested in helping with a new random number generator?

[Thaddy]

One of the questions I have is... how does one break a LGC generator?
I would like to see some code (preferrably Pascal rather than the dreaded C), which demonstrates how it can be done.

From the descriptions I've seen online, the method seems to be just a brute-force trial of each unknown variable, then comparing each calculated result, with the observed results.

However, even with only 4 variables, and assuming 32bit integers, that is 2^128 possibilities, which is a big number to brute-force.

Basically, this is done by reversing the output of tests for randomness. It is not just brute force, although it can be computationally expensive.
For example, based on statistical analyses, one can often reduce the power (you gave 128) by some margin and so reduce the numbers you have to probe.

Here's some code that proves that Delphi's random is weak. The same technique can be applied to other lcg prng's.
First a Delphi style (compatible) random I wrote a couple of years ago:
https://wiki.freepascal.org/Delphi_compatible_LCG_Random

Code: Pascal  [Select][+][-]

1. unit lcg_random;
2. // Delphi compatible LCG random number generator routines for Free Pascal.
3. // (c)2017, Thaddy de Koning. Use as you like
4. // Algorithm, Delphi multiplier and increment taken from:
5. // https://en.wikipedia.org/wiki/Linear_congruential_generator
6. // The default Delphi RandomSeed is determined as zero.
7. {$ifdef fpc}{$mode objfpc}{$endif}
8.  
9. interface
10.  
11. function LCGRandom: extended; overload;inline;
12. function LCGRandom(const range:longint):longint;overload;inline;
13.  
14. implementation
15.  
16. function IM:cardinal;inline;
17. begin
18.   RandSeed := RandSeed * 134775813  + 1;
19.   Result := RandSeed;
20. end;
21.  
22. function LCGRandom: extended; overload;inline;
23. begin
24.   Result := IM * 2.32830643653870e-10;
25. end;
26.  
27. function LCGRandom(const range:longint):longint;overload;inline;
28. begin
29.   Result := IM * range shr 32;
30. end;
31.  
32. end.

And a program that shows it is weak, i.e. we can predict the next value for all seeds:

Code: Pascal  [Select][+][-]

1. program ProveWeakness;
2.  
3. {$apptype console}
4.  
5. uses
6.   lcg_random;
7.  
8. const
9.   Two32: extended = 4294967296.0;  // 2^32
10.  
11. var
12.   x1, x2: extended;
13.   s1, s2: cardinal;
14.   i: integer;
15.  
16. begin
17.   for i := 0 to 100 do
18.   begin
19.     // Set a seed
20.     RandSeed := i * 1000;
21.  
22.     // Generate two consecutive extended random numbers
23.     x1 := LCGRandom;
24.     x2 := LCGRandom;
25.  
26.     // Recover the state from the first output
27.     s1 := round(x1 * Two32);
28.  
29.     // Compute the next state using the LCG formula
30.     s2 := s1 * 134775813 + 1;  // Cardinal arithmetic automatically mod 2^32
31.  
32.     // Compare the predicted value with the actual second output
33.     if abs(x2 - s2 / Two32) > 1e-10 then
34.       writeln('Failure at seed: ', i * 1000)
35.     else
36.       writeln('Success at seed: ', i * 1000);
37.   end;
38.   writeln('Test completed. Press Enter.');
39.   readln;
40. end.

Explanation:
1. Initialization: The program tests multiple seeds (0 to 100000 in steps of 1000).
2. Generate Outputs: For each seed, it generates two consecutive extended random numbers (x1 and x2).
3. Recover State: The first output x1 is multiplied by 2^32 and rounded to recover the internal state s1
4. Predict Next State: The next state s2 is computed using the LCG formula: s2 := (s1 * 134775813  + 1) mod 2^32;
5. Compare Values: The predicted value s2 / Two32 is compared to the actual second output x2. If they match closely, the prediction is successful.

This program consistently predicts the next output correctly across all tested seeds, proving that the LCG is weak because its internal state can be exposed by a single output, leading to trivial prediction of future values. This vulnerability arises because the output directly reveals the state, and the LCG's linearity allows easy forward computation. This goes for any LCG with not enough state.
(Proof of weakness helped and verified by DeepSeek)

[Nitorami]

A few general words from rather an amateur on the matter.

Cryptography is not for amateurs. You have been told that already, read it again. No problem for toy purposes but please don't think you can easily create a secure PRNG. I agree this is an interesting and seducing task, and consequently many amateurs crafted complicated algorithms, and defended them vigorously against criticism. But it's probably fair to claim that none of these would resist a professional attack. The fact that many of these attempts are afloat without having been broken does not mean they are good; it probably just means that no experts have bothered to attack the algorithm, because it has no relevance anyway. It is absolutely not adequate to just have other amateurs look at it and saying "I can't break it, it looks secure" !

There is some interesting reading from Bob Jenkins (burtleburtle.net), the author of the ISAAC cipher. His approach was to first study how to break a cipher before designing one, and I think that's generally a very good advice.

On the LGC as such: This has been studied thoroughly, and tables of good multipliers and moduli are available on the Internet. Sebastian Vigna has published a free python script to search for good combinations.

However, the lower bits of an LGS are always weak, regardless which multiplier, and combining umpteen LGCs does not change this at all ! Any such combination will fail even the simplest randomness tests within milliseconds, without need to run big crush or PractRand on it. Read some LGC theory first.

This has given the LGC a bad reputation, but it does not mean the LGC concept is bad. When only using the upper bits, a LGC can have very good statistical properties. AFAIK a 128bit LGC, when using only the upper 32 bit, passes big crush. However, statistical quality is not equivalent to cryptographic security ! As Thaddy said, it will be important to hide a part of the state, i.e. output only a small part of the internal state, such as the mentioned 32 of 128 bit. Hiding information makes it more difficult to an attacker to calculate the state by Gaussian elimination or such. But that alone will not make the generator secure.
 
I recommend Melissa O'Neill's very accessible paper on her PCG, a modified LGC. Melissa does not call it cryptographically secure, but "challenging" to break. That reading should give you a little bit of insight how to make a generator secure so that it cannot be broken by clever statistical or mathematical tricks, only by brute force. The 32-bit PCG due to its small state can be brute forced in a few seconds, on the 64bit version I once read a university study which concludes that it can be brute forced in "no more than 50.000 CPU hours". That may duly be considered "challenging", but the essential fact is that brute force is the ONLY viable approach to break it.

Oh, and on the period of PRNGs: I don't understand how you intend to achieve "infinite" period, but there is no such thing. The period is at maximum 2 to the number of bits in use. No way around that.

[ad1mt]

Here is some example pseudo-code to illustrate the algorithm. It might not compile or run.
An important thing to note is that the multiplier, modulus and seeds used would not be fixed, they would change every time the RNG was run, and can vary between 131072 and 4294967295. So it is not just one RNG, it is a set of (4294836223 ^ 18) different RNGs.
When I use this in a cryptograhy algorithm, the 18 variables are generated by interpreting the password as a big integer, then multiplying it by the date/time in microseconds. The date/time is stored alongside the encrypted text, and the decryption can only be done with the password that was used originally. Every time encryption is done, even if the password is the same, the product of password multiplied by date/time, gives a different set of variables. This is in effect, a one-time pad.

Code: Pascal  [Select][+][-]

1. program example;
2. var
3. multiplier1:= 131072001; modulus1:= 131073003; seed1:= 131074005; constant1:= 1;
4. multiplier2:= 131075007; modulus2:= 131076009; seed2:= 131077011; constant2:= 1;
5. multiplier3:= 131078013; modulus3:= 131079015; seed3:= 131080017; constant3:= 1;
6. multiplier4:= 131081019; modulus4:= 131082021; seed4:= 131083023; constant4:= 1;
7. multiplier5:= 131084025; modulus5:= 131085027; seed5:= 131086029; constant5:= 1;
8. multiplier6:= 131087031; modulus6:= 131088033; seed6:= 131089035; constant6:= 1;
9.  
10. function random:integer;
11. begin
12. seed1:= (((seed1 * multiplier1) + constant1) MOD modulus1);
13. seed2:= (((seed2 * multiplier2) + constant2) MOD modulus2);
14. seed3:= (((seed3 * multiplier3) + constant3) MOD modulus3);
15. seed4:= (((seed4 * multiplier4) + constant4) MOD modulus4);
16. seed5:= (((seed5 * multiplier5) + constant5) MOD modulus5);
17. seed6:= (((seed6 * multiplier6) + constant6) MOD modulus6);
18.  
19. Random:= (seed1 XOR seed2 XOR seed3 XOR seed4 XOR seed5 XOR seed6) MOD 65536;
20. end;

[ad1mt]

I agree this is an interesting and seducing task, and consequently many amateurs crafted complicated algorithms, and defended them vigorously against criticism.

I'm not defending my algorithm, I'm inviting people to criticise it.

There is some interesting reading from Bob Jenkins (burtleburtle.net), the author of the ISAAC cipher. His approach was to first study how to break a cipher before designing one, and I think that's generally a very good advice.

I agree, but my maths is not good enough to make me a professional cryptographer. I stumbled across this algorithm by accident over a number of years of experimenting, and I found it interesting & fun as a hobby. I'm very interested in maths, but have always struggled with the theory. What I think is interesting about computers, is that you can test ideas by writing programs to do the work.

On the LGC as such: This has been studied thoroughly

Yes. After a few years of working on my algorithm, I discovered that the idea was not new. The Wichmann-Hill algorithm does exactly the same thing but uses three LCGs with a fixed set of primes. My idea simply extends this idea, to six LCGs. The interesting thing is this enables any odd numbers to be used, rather than "special" numbers, and this opens up very interesting possibilities.

However, the lower bits of an LGS are always weak, regardless which multiplier, and combining umpteen LGCs does not change this at all ! Any such combination will fail even the simplest randomness tests within milliseconds, without need to run big crush or PractRand on it.

You are not correct. I've tested thoroughly with Practrand, and it passes all tests easily. I've tested both keeping & removing the lower bits, and removing them was not necessary.

Oh, and on the period of PRNGs: I don't understand how you intend to achieve "infinite" period, but there is no such thing. The period is at maximum 2 to the number of bits in use.

Please my later post exlaining the algorithm in more detail. That explains why I make my claim that the period is "virtually" infinite. With a slight tweak to the algorithm, the period can be made truly infinite, by adding an extra LCG if/when repetition is detected.

[Thaddy]

Code: Pascal  [Select][+][-]

1. {$if fpc_fullversion < 30301}{$error minimum supported version is fpc 331.}{$ifend}
2. {$apptype console}
3. {$mode delphi}{$h+}
4. program example_working;
5. uses
6.   {$ifdef unix}cthreads,{$endif}sysutils,classes;
7.   const
8.   multiplier1 = 131072001; modulus1 = 131073003; seed1 = 131074005; constant1 = 1;
9.   multiplier2 = 131075007; modulus2 = 131076009; seed2 = 131077011; constant2 = 1;
10.   multiplier3 = 131078013; modulus3 = 131079015; seed3 = 131080017; constant3 = 1;
11.   multiplier4 = 131081019; modulus4 = 131082021; seed4 = 131083023; constant4 = 1;
12.   multiplier5 = 131084025; modulus5 = 131085027; seed5 = 131086029; constant5 = 1;
13.   multiplier6 = 131087031; modulus6 = 131088033; seed6 = 131089035; constant6 = 1;
14.  
15. var
16.   a,b,c,d,e,f,g:TThread;
17.   seeds:array[1..6] of cardinal = (1,2,3,4,5,6);
18.   Value:Cardinal = 0;
19. begin
20.   a := TThread.ExecuteInThread(procedure
21.                                begin
22.                                  seeds[1]:= (((seeds[1] * multiplier1) + constant1) MOD modulus1);
23.                                end);
24.   b := TThread.ExecuteInThread(procedure
25.                                begin
26.                                  seeds[2]:= (((seeds[2] * multiplier2) + constant2) MOD modulus2);
27.                                end);
28.   c := TThread.ExecuteInThread(procedure
29.                                begin
30.                                  seeds[3]:= (((seeds[3] * multiplier3) + constant3) MOD modulus3);
31.                                end);
32.   d := TThread.ExecuteInThread(procedure
33.                                begin
34.                                  seeds[4]:= (((seeds[4] * multiplier4) + constant1) MOD modulus4);
35.                                end);
36.   e := TThread.ExecuteInThread(procedure
37.                                begin
38.                                  seeds[5]:= (((seeds[5] * multiplier5) + constant5) MOD modulus5);
39.                                end);
40.   f := TThread.ExecuteInThread(procedure
41.                                begin
42.                                  seeds[6]:= (((seeds[6] * multiplier6) + constant6) MOD modulus6);
43.                                end);
44.   g := TThread.ExecuteInThread(procedure begin writeln('Wait tests:');
45.                                            a.waitfor;                                        
46.                                            b.waitfor;                                          
47.                                            c.Waitfor;                                          
48.                                            d.waitfor;                                          
49.                                            e.waitfor;                                          
50.                                            f.waitfor;
51.                                            writeln('finished');
52.                                            Value := (seeds[1] XOR seeds[2] XOR seeds[3] XOR seeds[4] XOR seeds[5] XOR seeds[6]) MOD 65536;
53.                                         end);
54.   { performs final calulation }
55.   g.waitfor;
56.   writeln(Value);
57. end.

It doesn't look very strong to me because all are multiply/add/mod.
Much better would be to use xorshift or six different prng's as I suggested.
Anyway this is definitely NOT cryptographically secure, I am afraid.
It would fail in the same way as Delphi failed, simply by measuring the gap returned from thread g.
Also remind yourself that multiply and modulo are relatively expensive compared to shift and xor.
Over the six threads, because it is the same algorithm, the output is deterministic. The threads only make the code a bit faster.
This has the same proof as what I showed for Delphi.

[ad1mt]

I'm trying to write a program to "break" an LCG.
The algorithm I'm trying to implement comes from this link...   https://security.stackexchange.com/questions/4268/cracking-a-linear-congruential-generator
One of the replies describes the follwing method...

A linear congruential generator is defined by S[n+1] = (((A * S[n]) + B) mod M).
If none of A, B, M are known, one can still break a linear congruential generator, by first recovering M.
To recover M, define T[n] = S[n+1] - S[n]. Then calculate U[n] = (((T[n+2] * T[n]) - (T[n+1] ^ 2)). Then with high probability you will have M = GCD(U[1], U[2], ...).

I've tried to implement this method using output from a LCG with multiplier=1664525, modulus=65536, constant=1 and seed=1; which produces 1, 26126, 49847, 52556, 46301, 15674, 14323, 43352, 43385, 53542, etc.
The problem I'm getting is that when I calculate the GCD of u1 & u2 (etc), I'm often getting 1 as the result. I'm also sometimes getting u1, u2 (etc) as negative numbers, which seems to break the GCD algorithm.
Any help with this most welcome! Thanks.

[ad1mt]

One of the questions I have is... how does one break a LGC generator?

Basically, this is done by reversing the output of tests for randomness. It is not just brute force, although it can be computationally expensive.
For example, based on statistical analyses, one can often reduce the power (you gave 128) by some margin and so reduce the numbers you have to probe.

Here's some code that proves that Delphi's random is weak.

Thanks for that code... I'll study it closely.

[ad1mt]

Just so everyone knows...
I'm only using my encryption algorithm in my own personal password manager/database, so that if my computer gets stolen, the thief cannot see my passwords.
I think that it is safe to assume that a typical thief will not be able to break my encryption!

[Thaddy]

Try to test my threaded example against the delphi test: it fails, because the output is still deterministic.
You need to rewrite the test a bit, but you will always come up with the same difference.
If your pseudocode is serious, it isn't any good as my example demonstrates.

[Thaddy]

I think that it is safe to assume that a typical thief will not be able to break my encryption!

Well, I am not a thief, but I would break it in seconds....
That is because the combined state of the six threads is the sum of the individuals, so the - global -state is known with one run.
BTW. Your algorithm is known as "multiply with carry", see Marsaglia.

[Nitorami]

You are not correct. I've tested thoroughly with Practrand, and it passes all tests easily. I've tested both keeping & removing the lower bits, and removing them was not necessary.

Ok, I see that you are using only the lower 16bit of the xored LGCs, and these are indees statistically good. Must have to do with the prime moduli you are using. But that does not mean that the paralleled LGCs are good per se; the full 32bit output fails all tests miserably. So you are forced to discard bits in any case.

On your GCD issue and the negative values - cannot really help with this but it seems you are using signed integers. Why ? Wouldn't it be more adequate to use unsigned ints for these sorts of algorithms ?

[ad1mt]

the full 32bit output fails all tests miserably. So you are forced to discard bits in any case.

To generate 32 bit random numbers, I do:

Code: Pascal  [Select][+][-]

1. Random32bit:= 16bit_rand(); Random32bit:= (Random32bit << 16); Random32bit:= (Random32bit + 16bit_rand());

This passes the tests.

[Nitorami]

Yes, I inferred that from your code fragment.

[ad1mt]

This looks like what I'm doing...  https://en.wikipedia.org/wiki/Combined_linear_congruential_generator
But I don't understand the equations, so I'm not sure.

[Thaddy]

"The results of multiple LCG algorithms are combined through the CLCG algorithm" Quote from that wiki entry.
They must be different. An example is - again from Marsaglia: KISS.
You use the same algorithm, just with different parameters. That is conceptually wrong.
When at least one of the threads uses a different algorithm then your code may even pass dieharder.
Also MOD 65536 is wrong of course, should be 2^32 for a 32 bit prng.

Changing parameters does not make a different algorithm, it just means different output.