Reverse Java random seed using 81 calls to nextInt with a bound of 4?

Question

I'm trying to reverse the Java random seed using 81 calls to nextInt(bound) with a bound of 4. I am wondering if it is at all possible to reverse the random seed.

In this situation Java's random number generator is called 81 times, and for each call I know if the returned value is either 0 or not 0. Looking at the int nextInt(int bound) method, here is the relevant code:

int r = next(31);
if ((bound & (bound-1)) == 0)  // i.e., bound is a power of 2
    r = (int)((bound * (long)r) >> 31);

where r is the returned value, and next(31) is the next pseudo-random value using 31 bits. Here is that next method:

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

where the multiplier is a constant 0x5DEECE66DL, addend is 0xBL, mask is (1L << 48) - 1. Here, 0x indicates a hexadecimal value, and the L is there to make the literal value a Java long (64-bit).

---

In Java, int is always 32 bits in size. Furthermore AtomicLong is a multi-threading related construct that simply represents a 64 bit long in this code. The mask makes sure that the value never exceeds 48 bits. The loop construct and !compareAndSet can be entirely replaced by a simple seed = nextSeed.

Basically then, the seed $s$ is updated using:

$$s \gets (\mathtt{5DEECE66D}_{16} \cdot s + \mathtt{B}_{16}) \bmod {2^{48}}$$

after which the two most significant bits of the 48 bit value $s$ are returned.

---

I don't know if this is possible, since so many bits are dropped, but I have seen this done with calls to nextInt(10).

Sorry if there is anything I left out or if this is too vague, this is my first cryptography post.

Answer 1

The $48$-bit state $s_i$ evolves per a Linear Congruential Random Number Generator, with modulus $n=2^{48}$, multiplier $a=\mathtt{5DEECE66D}_{16}$, and additive constant $b=\mathtt B_{16}$; that is $s_i=(a\cdot s_{i-1}+b)\bmod2^{48}$. We are given the OR $r_i$ of its two upper bits for $i\in[1,81]$, or equivalently the $81$ booleans $s_i\ge2^{46}$. Our goal is to find $s_0$: if the Java default generator was explicitly seeded, $s_0\oplus a$ is the low-order 48 bits of the given long seed.

The $81$ givens yield about $-81\left(\frac14\log_2(\frac14)+\frac34\log_2(\frac34)\right)\approx65.7$ bit of information, which should be typically ample to pinpoint a single $48$-bit seed.

A most brute force solution to the problem enumerates all the $s_0$ in $[0,2^{48})$, and for increasing $i$ computes the $s_i$ and eliminates a candidate $s_0$ as soon as there's a mismatch between a bit $r_i$ and the condition $s_i\ge2^{46}$. That's feasible, and particularly easy to distribute on multiple threads/CPUs/GPUs/FPGAs. The rest of this answer illustrates the NSA saying (popularized by Bruce Schneier): Attacks always get better; they never get worse.

---

Notice that we can compute for $z\in[-81,81]$ the $48$-bit constants $a_z$ and $b_z$ such that $s_{i+z}=(a_z\cdot s_i+b_z)\bmod2^{48}$. We have $$\begin {align} a_0&=1&b_0&=0\\ a_{z+1}&=a\cdot a_z\bmod2^{48}&b_{z+1}&=(a\cdot b_z+b)\bmod2^{48}\\ a_{-1}&=a^{-1}\bmod2^{48}=\mathtt{DFE05BCB1365}_{16}&b_{-1}&=a_{-1}\cdot (-b)\bmod2^{48}\\ a_{z-1}&=a_{-1}\cdot a_z\bmod2^{48}&b_{z-1}&=a_{-1}\cdot (b_z-b)\bmod2^{48} \end{align}$$ This allows computing directly any $s_j$ from any $s_i$, by taking $z=j-i$. That's put to use in the following optimizations:

• Pick an $i$ with $r_i=0$ and reorganize the search by walking $s_i$ in the interval to $[0,2^{46})$, then compute $s_0$ from $s_i$. That's a welcome gain by a factor of $4$.
• We most likely¹ can pick the above $i$ such that $r_i=r_{i+1}=0$. The condition $s_{i+1}<2^{46}$ (which must hold) changes rarely when incrementing $s_i$: it holds true for about $2^{46}/a\approx2791$ consecutive values, then is false for an interval about three times longer, that we can skip, giving a speedup by a factor next to $4$.

At that stage of optimization, we explore $2^{44}$ values of $s_i$. I guesstimate² we can run faster than $2^6$ cycles/value tested on a core of a modern x64 desktop CPU. With a single $2^2$-core CPU at $2^{31}$ Hz, that would be $2^{17}$ seconds (1.5 day for the full exploration), and half that on average.

We can do better, but be warned that premature optimization is the root of all evils (Donald Knuth). We most often are able to make good use of the fact that $a_{-67}$ is small: when we can find $i,z$ with $r_i=r_{i+1}+r_{i-67}=0$, that allows getting down to $2^{42}$ values searched at cost of a further sub-division of the search sub-intervals for $s_i$ into sub-sub-intervals of width $2^{46}/a_{-67}\approx394$.

We often are able to further subdivide at least once or even twice, each time gaining another reduction by a factor of $4$ of the number of $a_i$ to test. We want to explore the usefulness of such subdivision for each $s_{i+z}$ with $r_{i+z}=0$. The better choices have the highest width $\approx2^{46}/\min(a_z,2^{48}-a_z)$ for the interval of $a_i$ with $s_{i+z}<2^{46}$. In particular, we might be able to use that $2^{46}/a_{19}\approx60$ or $2^{46}/(2^{48}-a_{-12})\approx60$. But we'll quickly get hit by the law of diminishing returns.

---

Update: There must be better methods. Something at least quite close was studied by Alan M. Frieze, Johan Hastad, Ravi Kannan, Jeffrey C. Lagarias, and Adi Shamir, Reconstructing Truncated Integer Variables Satisfying Linear Congruences, in SIAM Journal on Computing, 1988.

---

¹ In the very unlikely case (I'm not even sure it is possible) that there's no $i$ with $r_i=r_{i+1}=0$, the simplest of several possible fallbacks is to pick $i$ and $z$ with $r_i=r_{i+z}=0$ and the smallest $a_z$ possible; that will often be $z=-67$ or $z=19$. The reduction in number of $s_i$ scanned is the same, but we'll more often change sub-intervals.

² When $s_i$ increases in a sub-interval, we want to quickly update at least one $s_j$ that we'll always test. An update of $s_j$ cost one addition of $a_{j-i}$ and a mask³. We'll pick $j$ with $r_j=0$, which will leave only one out of $4$ values of $s_i$ needing more scrutiny. For these, we sequentially compute and test the many other $s_{i+z}$ that we could still have wrong, of course stopping at the first mismatch and first testing $z$ with $r_{i+z}=0$. Each additional $z$ requires a multiplication by $a_z$. If that's too costly, we'll want to maintain one or a few more $s_k$ by addition.

³ A simple micro-optimization maintains $2^{16}s_i$ over a $64$-bit variable, saving the masking. The comparison becomes against $2^{62}$, also implementable as a $62$-bit right shift and a test for zero.