Some implementations of Pseudo Random Number Generation (PRNG) mechanisms suffer from several known issues.
A particular implementation of PNRG is Linear Congruent Generator (LCG). A famous example is java’s Random() class. The basic principle is that a new Random() object is initiated with a seed dependent on the current time and then, at every call to Random.nextInt() the seed is updated according to this formula:
$$ S_{n+1} = (A*S_n + B) mod 2^{42} $$ Where A and B are known coefficients, which can be found in the references. Every time that nextInt() is called, the seed is updated according to the above formula and the output of the function nextInt() is:
This means that only the upper 32 bits of S affect the output of the nextInt() function (Notice that S is at most 48 bits). In this case, having two subsequent observations of X can lead to the discovery of S with a reduced bruteforce attack. In fact, reversing the above equation yields:
Where $$ g < 2^{16} $$ One can enumerate all the possible g and then verify which one of these yields the next observation X. A simple proof-of-concept can be found later in the references.
In some cases, the function nextInt() is called with a parameter R that is the maximum range of the output. In this case let’s call Z the output of nextInt(R). Then:
That is, X is given by the upper 31 bits of S, differently from the former case, and then the output observed (Z) is given by something dependent on the lower bits of X. The point here is that we aren’t leaked directly the upper bits of S, instead we’re leaked some information on the lower bits of the 31 upper bits of S, depending on the range used.
In this case the operation Z=X mod R gives directly the lowest p bits of X. In fact, reasoning in base 2, the modulo operation consists in taking the remainder of X / 2^p, i.e. the lowest p bits of X.
Example:
X = 38 = 32 + 4 = 100100
R = 8 = 2^3
X / R = 32/8 + 4/8 = (X >> 3) + Z/8
Where Z is the remainder, i.e. the last 3 bits that are lost in the shift operation.
So, we know that the output of Random.nextInt(R) must be the lowest p bits of X, i.e. the lowest p bits of the upper 31 bits of the seed. Equivalently, they are the upper p bits of the lowest 17+p = 20 (in this example) bits of the seed. We can use this to brute separately the two parts of the seed. Notice that, at every update of the seed, the leaked p bits can be influenced only by the lower ones:
At every multiplication and addition, the operations performed on the lower 17+p bits are independent on what happens to the upper 31-p bits (i.e. we could split the seed in two parts, upper and lower, and perform the operations only on the lower part and the result would be the same, exploiting the associative property). If we have a set of subsequent observations, we actually have a set of leaked bits from the seed sequence. It means that is sufficient to guess a (17+p)-bits initial seed such that the produced Sn sequence has the observed p-bits. This can be done in seconds. After determining the lower 17+p bits, one can brute the upper ones by simply guessing which seed will give the observed sequence.
Note In the end, what we said here means that the output of Random.nextInt(R) with R = 2^p depends only on the lower 17+p bits of the seed. This implies that we don’t even need to know the full seed in order to predict future observations, instead we can just brute the lower 17+p bits in some seconds and then we can predict every observation.
To avoid this issue, the actual implementation of java’s Random.nextInt(R) differs from the one described here for R=2^p. Instead the actual computation is: $$ Z = (R*X) >> 31 $$
That is, we take the upper 31 bits of the seed (i.e. the number X), we multiply it by R and then divide by 2^31 and take the integer part. This operation yields a number Z < R. (Z = R only if X = 2^31). We still haven’t thought of any attack against this implementation.
If R is even, then the output of Z=(X mod R) will have the same parity of X. In fact
Being R even and n an integer number, n*R is even and thus Z and X must be either both even or both odd. This case then is analogous to the previous one with p = 1, i.e. from a sequence of observations we’re only leaked the 18th bit (starting from low), that is the parity bit of X and Z, and we must brute the lowest 17 and the upper 30 using the same technique. A simple PoC for this case is provided in this repository (file: predictJavaRandom.java).
We still don’t know how to attack this case.
- [1] [Java Random Source Code] (http://developer.classpath.org/doc/java/util/Random-source.html)
- [2] Cracking Java’s Random without RANGE
- [3] Hints on how to crack LCG with fixed RANGE