If we're talking about the Oracle (née Sun) implementation of java.util.Random, then yes, it is possible once you know enough bits.
Random uses a 48-bit seed and a linear congruential generator. These are not cryptographically safe generators, because of the tiny state size (bruteforceable!) and the fact that the output just isn't that random (many generators will exhibit small cycle length in certain bits, meaning that those bits can be easily predicted even if the other bits seem random).
Random's seed update is as follows:
nextseed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)
This is a very simple function, and it can be inverted if you know all the bits of the seed by calculating
seed = ((nextseed - 0xBL) * 0xdfe05bcb1365L) & ((1L << 48) - 1)
since 0x5DEECE66DL * 0xdfe05bcb1365L = 1 mod 248. With this, a single seed value at any point in time suffices to recover all past and future seeds.
Random has no functions that reveal the whole seed, though, so we'll have to be a bit clever.
Now, obviously, with a 48-bit seed, you have to observe at least 48 bits of output or you clearly don't have an injective (and thus invertible) function to work with. We're in luck: nextLong returns ((long)(next(32)) << 32) + next(32);, so it produces 64 bits of output (more than we need). Indeed, we could probably make do with nextDouble (which produces 53 bits), or just repeated calls of any other function. Note that these functions cannot output more than 248 unique values because of the seed's limited size (hence, for example, there are 264-248 longs that nextLong will never produce).
Let's specifically look at nextLong. It returns a number (a << 32) + b where a and b are both 32-bit quantities. Let s be the seed before nextLong is called. Then, let t = s * 0x5DEECE66DL + 0xBL, so that a is the high 32 bits of t, and let u = t * 0x5DEECE66DL + 0xBL so that b is the high 32 bits of u. Let c and d be the low 16 bits of t and u respectively.
Note that since c and d are 16-bit quantities, we can just bruteforce them (since we only need one) and be done with it. That's pretty cheap, since 216 is only 65536 -- tiny for a computer. But let's be a bit more clever and see if there's a faster way.
We have (b << 16) + d = ((a << 16) + c) * 0x5DEECE66DL + 11. Thus, doing some algebra, we obtain (b << 16) - 11 - (a << 16)*0x5DEECE66DL = c*0x5DEECE66DL - d, mod 248. Since c and d are both 16-bit quantities, c*0x5DEECE66DL has at most 51 bits. This usefully means that
(b << 16) - 11 - (a << 16)*0x5DEECE66DL + (k<<48)
is equal to c*0x5DEECE66DL - d for some k at most 6. (There are more sophisticated ways to compute c and d, but because the bound on k is so tiny, it's easier to just bruteforce).
We can just test all the possible values for k until we get a value whos negated remainder mod 0x5DEECE66DL is 16 bits (mod 248 again), so that we recover the lower 16 bits of both t and u. At that point, we have a full seed, so we can either find future seeds using the first equation, or past seeds using the second equation.
Code demonstrating the approach:
import java.util.Random;
public class randhack {
public static long calcSeed(long nextLong) {
final long x = 0x5DEECE66DL;
final long xinv = 0xdfe05bcb1365L;
final long y = 0xBL;
final long mask = ((1L << 48)-1);
long a = nextLong >>> 32;
long b = nextLong & ((1L<<32)-1);
if((b & 0x80000000) != 0)
a++; // b had a sign bit, so we need to restore a
long q = ((b << 16) - y - (a << 16)*x) & mask;
for(long k=0; k<=5; k++) {
long rem = (x - (q + (k<<48))) % x;
long d = (rem + x)%x; // force positive
if(d < 65536) {
long c = ((q + d) * xinv) & mask;
if(c < 65536) {
return ((((a << 16) + c) - y) * xinv) & mask;
}
}
}
throw new RuntimeException("Failed!!");
}
public static void main(String[] args) {
Random r = new Random();
long next = r.nextLong();
System.out.println("Next long value: " + next);
long seed = calcSeed(next);
System.out.println("Seed " + seed);
// setSeed mangles the input, so demangle it here to get the right output
Random r2 = new Random((seed ^ 0x5DEECE66DL) & ((1L << 48)-1));
System.out.println("Next long value from seed: " + r2.nextLong());
}
}
