3
$\begingroup$

Given a set of numbers within the range of 1-6:

[3,4,3,4,5,6,2,3,1,5,2,3,6,2,2,3,3,6,6,4,5,2,5,3,5,2,4,4,2,6,3,6,1,5,1,3,6,1,1,2,2,4,5,3,1,2,3,4,4,6]

generated using Java's nextInt(6)+1, is it possible to reverse engineer this to find the seed?

Upon investigating Java's source-code I understand this is how the nextInt() method works:

public static int nextInt(int n){
        if (n <= 0)
            throw new IllegalArgumentException("n must be positive");
        if ((n & -n) == n) // i.e., n is a power of 2
            return (int) ((n * (long) next(31)) >> 31);
        int bits, val;
        do
            {
                bits = next(31);
                val = bits % n;
            }
        while (bits - val + (n - 1) < 0); //do, until its a positive number
        return val;
    }

Since n in this case is 6, it is not a power of 2 so it carries out this part of the code:

do
  {
    bits = next(31);
    val = bits % n;
  }
  while (bits - val + (n - 1) < 0); //do, until its a positive number
  return val;

it now calls next(31) and this is the code where it essentially runs through a linear-congruential generator

public static int next(int bits){
  seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
  return (int) (seed >>> (48 - bits));
}

this 31bit number is returned as an int and assigned into bits

Finally we do bits % 6 and this gives the final value.

I have a few questions:

(1) what is the purpose of this line of code?

while (bits - val + (n - 1) < 0);

(2) How does one reverse engineer and find the seed from a set of numbers generated from this procedure?

$\endgroup$
0
5
$\begingroup$

what is the purpose of this line of code?
while (bits - val + (n - 1) < 0);

From a syntactic perspective, it ends the do opened above. From a functional perspective, it makes the pseudo-random number generated uniform on the specified interval. I'll focus on the later aspect.

Assume n was $3\cdot2^{29}\,$ (that is 3<<29) rather than $6$. After the statement bits = next(31); this quantity is uniformly random in $[0,2^{31})$. Therefore val = bits % n; is

  • bits with probability 75%; and then uniform on $[0,3\cdot2^{29})$
  • or bits-(3<<29) with probability 25%; and then uniform on $[0,2^{29})$

It follows that before the while, val is in $[0,2^{29})$ with probability 50%, in $[2^{29},3\cdot2^{29})$ with probability 50%. The second interval is twice as large as the first, and we see that val is very far from uniform on the whole interval $[0,3\cdot2^{29})\ $!

The while repeats the loop when in the problematic second bullet, and thus makes the outcome uniform on the full interval $[0,3\cdot2^{29})$.


Alternate explanation with small numbers

Imagine that, starting from $b=0$, four times: we double $b$, then add $1$ to $b$ if we get a tail from a fair coin throw. The outcome is $b$ a nonnegative integer less than $2^4=16$, and each of these $16$ integers is equally likely. That is, the outcome is a discrete uniform random number $b$ in $[0,16)$.

From this we want a uniform random number $v$ in $[0,6)\,$ just like nextInt(6) is tasked to do. Problem is, if we use a fixed assignment of values of $b$ from $[0,16)$ to values of $v$ in $[0,6)$, the outcome can't be uniform. The most even we can get is that $4$ values of $v$ have probability $3/16$, and the $2$ other $2/16$. Think of separating $16$ mints (the $b$) into $6$ persons (the $v$).

A simple solution to that is: when $b$ is in $[0,6)$, that's our $v$. When $b$ is in $[6,12)\,$, our $v$ is $b-6$. Otherwise, we try again, generating another $b$ using coin throws. That's what the code does in it's do … while loop, only with $2^{31}$ using next(31) where our analogy uses $2^4$ and coin throws; using bits for $b$, and val for $v$.


Off-topic: what's up with bits - val + (n - 1) < 0 ?

One wonders how while (bits - val + (n - 1) < 0); manages to do what's described above. bits is in range [0, 0x7FFFFFFF], n is 6, val is bits % n, thus val < bits holds and bits - val is non-negative. But it does not follow that bits - val + (n - 1) is non-negative, because the operations are carried per two's-complement arithmetic over 32-bit.

That's how int works in Java, many other computer languages, and most modern computer hardware when manipulating signed integers as a 32-bit quantities. If the int quantities u and v represent the integers $u$ and $v$, these integers are both in range $[-2^{31},2^{31}-1]$, then u + v is an int quantity representing an integer $w$ in range $[-2^{31},2^{31}-1]$ with $u+v\equiv w\bmod2^{32}$, that is by definition $u+v-w$ a multiple of $2^{32}$, and depending on values of $(u,v)$ that multiple can be $0$, $2^{32}$, or $-2^{32}$. In the end, $w$ is the integer $((u+v+2^{31})\bmod2^{32})-2^{31}$. That arithmetic is commutative, associative, has neutral zero, and every element has an opposite. A caveat: $-2^{31}$, that is -0x80000000, shares with zero the property of being it's own opposite.

So for example if bits was $2^{31}-2$, val is $0$, bits - val is $2^{31}-2$, bits - val + (n - 1) is $((2^{31}-2+(6-1)+2^{31})\bmod2^{32})-2^{31}$, that is $((2^{32}+3)\bmod2^{32})-2^{31}=3-2^{31}$, and that's negative.

For those that just want to move along: the condition bits - val + (n - 1) < 0 is logically equivalent to bits - val >= ((long)1<<31) + 1 - n (with no overflow and only non-negative quantities, thanks long being 64-bit).

It should now be apparent that bits - val + (n - 1) < 0 holds when bit is at the top of its interval [0, 0x7FFFFFFF]. It is left as an exercise to the reader to show that the rest of the interval contains a multiple of n integers, thus all the n values of val on exit of the loop are exactly as likely, under the assumption that all values of bits are.


How does one reverse engineer

That's already done. The question has reverse-engineered the algorithm, and even more than this: simplified the code from what it is in a recent Java environment by removing the thread-safety stuff (or traveling back in time to get the source before that was added); and thought about removing the part of the code that is demonstrably unreachable in the circumstance.

and find the seed from a set of numbers generated from this procedure?

Next step towards that goes: compute the probability that the condition in the while statement is true when n is $6$, and decide what can be done about this case.

Then proceed. There's several paths to resolution:

  • Brute force, trying all $2^{48}$ initial state values. This is feasible, but inelegant and resource-hungry.
  • Reducing the above search space by a factor of $6$ by exploiting the first result available.
  • Using that $6$ is even to get 18 bits of the seed out of 48 (with fair probability), then brute force the rest. That's relatively simple and educative. It's outlined in this answer of mine. Some combinations with the above tweaks work.
  • A that-could-well-work-but-I-didn't-bother-to-try approach using SAT solvers (in same answer).

Likely there are other approaches, but if there's anything readily applicable here or here, I missed it.

If stuck, state at what point at the bottom of the present question.

$\endgroup$
6
  • $\begingroup$ 1) For the bit about probability distributions being uniform or not, would I need to understand a fair bit of statistics particularly on probability distributions? 2) Would this mathematical knowledge be necessary to compute the probability that the condition in the while statement is true when n is 6? $\endgroup$ – javaproblem201 Nov 19 '20 at 9:46
  • $\begingroup$ @javaproblem201 : A working intuitive notion of (discrete) probability will do, without the notion of probability distribution. To visualize the problem with small numbers, try turning an hex dice throw into a random integer in $[0,6)$. Just examine all the 16 cases, what's the corresponding outcome, deduce the probability of each outcome. Uniform means equal probabilities. $\endgroup$ – fgrieu Nov 19 '20 at 10:10
  • 1
    $\begingroup$ I fail to see how the condition (bits - val + (n - 1) < 0) would achieve proper uniform sampling. Assuming bits, val and n are positive, $\mathrm{val} \leq \mathrm{bits}$ always holds, since val is bits modulo n. Therefore bits - val is always non-negative. Therefore, unless $n$ is 0, (bits - val + (n - 1) is also non-negative. I've tried it out, and when I invert the loop condition, the program does not halt. I don't know what this code is trying to achieve, but I'm fairly certain it's not achieving rejection sampling. $\endgroup$ – cisnjxqu Nov 21 '20 at 8:30
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – fgrieu Nov 26 '20 at 11:21
  • 1
    $\begingroup$ @fgrieu Many thanks for your help and sorry I forgot to press accept answer even yes it solved my original question. For your referral to my ultimate one ((int)Math.random()*6+1) it involved mathematics that I lack which after some effort I decide its not possible for me at this point, would it be possible to ask you to write a working program that could crack that, and perhaps someday when i know lattice theory I could figure out how it works? $\endgroup$ – javaproblem201 Dec 18 '20 at 17:44

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.