4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Please note that this is not Java's SecureRandom implementation which should always provide a cryptographically secure random number generator. This is about java.util.Random which is a small non-secure random generator. Beware that Random also acts as an interface definition for SecureRandom but the next method is overridden in (i.e. replaced for) SecureRandom - so it doesn't apply there. $\endgroup$ – Maarten Bodewes Jan 19 at 13:48
  • $\begingroup$ Note that the Java RNG is actually a well known RNG called DRAND48, which was described for the PDP11 in 1983, a rather modern computer in 1970. $\endgroup$ – Maarten Bodewes Jan 20 at 3:40
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I will test this out today or tomorrow, if it works within a reasonable time frame (like within a week max) I will mark this as an answer with the time it took me to run. $\endgroup$ – Big_Bad_E Jan 19 at 15:58
  • $\begingroup$ I've talked with some people who have a lot more experience than me in LCG, and they showed me a lot better of a method. Apparently if the output is 0, the top 2 bits are 0. Calls can also be combined into another LCG. This worked in 20 minutes. Another used said faster code can be made using lattices, but it would take a lot longer to write. $\endgroup$ – Big_Bad_E Jan 20 at 18:09
  • $\begingroup$ @Big_Bad_E: yes if the output of nextInt(4) is 0, the top 2 bits of the state after that are 0. The answer's method is based on that. I do not get "Calls can also be combined into another LCG", what calls? 20 minutes would be very hard with my method, I wish I knew more about how this was achieved: was the input only 81 bits as in the question (more inputs or choosing the indexes helps a lot)? Was the seed an arbitrary 48-bit value? $\endgroup$ – fgrieu Jan 20 at 21:10
  • $\begingroup$ It was actually less than 81 bits, and the seed was 48-bit. I will upload the cl file if it works in a bit. $\endgroup$ – Big_Bad_E Jan 20 at 22:23
  • 1
    $\begingroup$ cdn.discordapp.com/attachments/510201738003873793/… They used this to auto-generate cl files to crack the random seed. $\endgroup$ – Big_Bad_E Jan 22 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.