5
$\begingroup$

I understand a little how Java's Random class works.

I have two random numbers output from calls to nextInt() from a java.util.Random object in Java. I want to determine the next number output after a third call.

The first two numbers are: $-1952542633$ and $-284611532$, how can I determine the next number given only this information?

$\endgroup$

closed as off-topic by e-sushi Apr 9 '18 at 15:07

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Programming questions are off-topic even if you are writing or debugging cryptographic code. Unless your question is specifically about how the cryptographic algorithm, protocol or side-channel (mitigation) works, you should look into asking on Stack Overflow instead." – e-sushi
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ If you could determine the next number without knowing the seed, then that random generator would be totally broken. So I think you will need much more than those two numbers. $\endgroup$ – Hilder Vítor Lima Pereira Sep 21 '17 at 12:58
  • $\begingroup$ if you'd know that these two numbers are 'first two numbers generated' or 'first generated' numbers and you'd know the seed is based on timestamp, then you'd be lucky as you could just iterate over a few thousand posible timestamps (that's why it is not cryptographically secure to use timestamp as the Random seed ).. However - even the Java Random algorithm is well know, it's not easy to compute the seed based only on two (even not necesarily subsequent) integers. $\endgroup$ – gusto2 Sep 21 '17 at 13:12
  • 1
    $\begingroup$ @gusto2: actually, the Java random object uses a LCRNG, which makes it easy to compute the seed with not that much output. The seed is 48 bits; two consecutive 32 bit outputs are quite sufficient. If you need something which is cryptographically secure, use the SecureRandom object... $\endgroup$ – poncho Sep 21 '17 at 13:17
  • $\begingroup$ @poncho what I once did - when I know the seed was the timestamp and the random value was generated as a first output, just iterating through half-a-day timestamps did the job.. but - good to know, thanks :) $\endgroup$ – gusto2 Sep 21 '17 at 13:21
  • $\begingroup$ @HilderVitorLimaPereira Actually this is not the case with the plain Random class. $\endgroup$ – Lery Sep 21 '17 at 14:33
10
$\begingroup$

In Java, if you do not seed the Random object, then it will seed itself. According to that same documentation, it uses a "linear congruential PRNG"...

This means it will easily be cracked if you have two values.

Such a PRNG will have an "internal state", which will change after each generation of a "random" number by applying the following linear process:

$$X_{n+1} = \left( a X_n + c \right)~~\bmod~~m$$ where we call $X_n$ the state at the step $n$, $a$ is the "multiplier", $c$ is the "increment" and $m$ is the "modulus".

Now, Wikipedia tells us that Java is using 25214903917 as multiplier and 11 as an increment and has a modulus equal to $2^{48}$.

Finally you need to know that java.util.Random won't spit all of its internal state into your random numbers: 32 bits only of the internal state are revealed by a call to nextInt().

So, we just one value, it would be hard, but since you have 2 different values, you can easily bruteforce the seed used and thus find the next value by calling nextInt with that seed.

Here is a snippet of code, which produces the correct result (I believe... This is only my fourth time trying out Java), I didn't felt like bruteforcing the bitwise AND operation to reverse it to the actual initial state, I let this as an exercise to a motivated fellow:

import java.util.Random;

public class lol {
    // implemented after https://docs.oracle.com/javase/7/docs/api/java/util/Random.html
    public static int next(long seed) {
        int bits=32;
        long seed2 = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
        return (int)(seed2 >>> (48 - bits));
    }

    public static void main(String[] args) {
        System.out.println("Starting");
        long i1 = -1952542633L;
        long i2 = -284611532L;
        long seed =0;
        for (int i = 0; i < 65536; i++) {
            seed = i1 *65536 + i;
            if (next(seed) == i2) {
                System.out.println("Seed found: " + seed);
               break;
            }
        }
        Random random = new Random((seed ^ 0x5DEECE66DL) & ((1L << 48) - 1));
        int o1 = random.nextInt();
        int o2 = random.nextInt();
        System.out.println("So we have that nextInt is: "+o1+" and the third one is: "+o2+" with seed: "+seed);

    }
}

Which produces the following output:

Starting
Seed found: -127961833934689
So we have that nextInt is: -284611532 and the third one is: -1527300283 with seed: -127961833934689

And so I think your third integer would be $-1527300283$.

$\endgroup$
  • $\begingroup$ Also when m is small, another solution described here is possible. $\endgroup$ – rustyx Oct 25 '18 at 7:38

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