### Analysis of the Java RNG

Posted:

**Sat Apr 21, 2018 11:39 am UTC**Given a seed, the java code for setSeed is:

The code to get the next n bits is

And finally the code to get the nextLong (which is 64 bits) is

(it may be useful to know that java evaluates the next(32) on the left before the next(32) on the right)

Suppose I pick an arbitrary starting seed m, then call setSeed and call nextLong. Call the returned value x. Given the lower 48 bits of x, I want to recover the upper 16 bits of x. Is it possible?

Hopefully, this should be relatively easy since setSeed already throws away 16 bits of m away, leaving 48 bits of uncertainty. In order to accomplish this task, it would be sufficient to figure out the lower 48 bits of m.

Another question: What can we say about the lower 48 bits of x? Are all possible values covered, just most of them, or almost none of them?

I don't have much ideas on what to try other than throwing everything into a SAT solver. Is there a smarter way?

Some motivating background: It's relatively easy to recover the lower 48 bits of a minecraft world's seed. However, the upper 16 bits are more difficult. The full 64 bit seed is generated by the procedure described in this problem. In addition, can we rule out parts of the lower-48-bits-space to make the search easier?

Code: Select all

`seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) - 1)`

The code to get the next n bits is

Code: Select all

`seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)`

result = (int)(seed >>> (48 - n))

And finally the code to get the nextLong (which is 64 bits) is

Code: Select all

`result = ((long)next(32) << 32) + next(32)`

(it may be useful to know that java evaluates the next(32) on the left before the next(32) on the right)

Suppose I pick an arbitrary starting seed m, then call setSeed and call nextLong. Call the returned value x. Given the lower 48 bits of x, I want to recover the upper 16 bits of x. Is it possible?

Hopefully, this should be relatively easy since setSeed already throws away 16 bits of m away, leaving 48 bits of uncertainty. In order to accomplish this task, it would be sufficient to figure out the lower 48 bits of m.

Another question: What can we say about the lower 48 bits of x? Are all possible values covered, just most of them, or almost none of them?

I don't have much ideas on what to try other than throwing everything into a SAT solver. Is there a smarter way?

Some motivating background: It's relatively easy to recover the lower 48 bits of a minecraft world's seed. However, the upper 16 bits are more difficult. The full 64 bit seed is generated by the procedure described in this problem. In addition, can we rule out parts of the lower-48-bits-space to make the search easier?