Cult of the RNG, bad news: your deity is pseudo.

While the titles are similar, I have 2 train puzzles rolling now. http://www.steamgifts.com/discussion/u1kMH/ is the other one

Have you ever wanted to predict the future? Now here is the opportunity. Many computing environments use a linear congruential generator (Wikipedia) for creating a pseudo-random sequence of numbers. Now the thing is that this beast is predictable, back and forth.
Java is such an environment (as mentioned in the Wikipedia article, and also described in its own documentation, Random).
Here is an example code:

    public static void main(String[] args) {
        java.util.Random r=new java.util.Random(88572484529474l);
        System.out.println(r.nextInt());
        System.out.println(r.nextInt());
        byte b[]=new byte[5];
        r.nextBytes(b);
        System.out.println(new String(b));
    }

It will display 2 numbers and a five-letter character sequence (hint: there are online environments for Java on Tutorialspoint, repl.it and perhaps at other locations).

What the puzzle is here is that knowing the 2 numbers is enough for predicting what kind of character sequence (or anything else) the generator will produce next. The numbers are 9258196 and 1399737795.

Hint -2: while it is possible to do, there is no need for finding out a counterpart for 88572484529474
Hint -1: whatever you try, make sure to have the necessary 48-bit precision (typically 'long' and 'int64' types)
Hint 0: Java itself is not an absolute must...
Hint 1: ... but (re)implementing its random number generator will be necessary. The java.util.Random docs page contains the related expressions
Hint 2: and try ("brute force") some 65536 possibilities
Some hints from the other train may be useful here.


Solution

The documentation and the hints describe the task pretty well. The internal state variable seed is a 48-bit number, as the documentation says it at the very beginning and also repeatedly shows the & ((1L << 48) - 1) step used for ensuring it.
nextInt() simply calls next(32), and next(bits) does 2 things:

  • updates the seed to (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1), which is really a simple multiplication and addition, just the result is truncated to 48 bits at the end
  • and returns (seed >>> (48 - bits)), so seed >>> 16 in our case. It is simply about dropping the lowest 16 bits of the number, and returning the rest as a 32-bit integer

Here comes the puzzle part: as we know the numbers returned now and in the next step, we know 32 bits of the current seed and the next seed. What we do not know is just a 16-bit number (the bits which are dropped), so something between 0 and 65535. And trying the simple calculation above 65536 times is not really a challenge to any computer manufactured in the last 30-40 years.
So here is the simple brute-forcing code:

    public static void main(String[] args) {
        long currknown=9258196L << 16; // known part of the current seed
        long nextknown=1399737795L << 16; // known part of the next seed
        long nextmask=0xFFFFFFFF0000L; // mask for testing the known part of the number only

        long mul = 0x5DEECE66DL; // from Java documentation
        long add = 0xBL; // from Java documentation

        for (int i = 0; i < 65536; i++)
        {
            long currtest=currknown+i;
            if( ((currtest*mul+add) & nextmask) == nextknown ) // do an actual generation step and test the result
            {
                java.util.Random r=new java.util.Random(currtest^mul); // Random xor-s the seed
                System.out.println(r.nextInt()); // should be 1399737795
                byte b[]=new byte[5];
                r.nextBytes(b);
                System.out.println(new String(b));
            }
        }
    }

And then there was a train starting from http://www.steamgifts.com/giveaway/z7wL2/
The example leads to a Thief Gold and a Papo & Yo.

9 years ago*

Comment has been collapsed.

Now what?

View Results
Choo-choo
FUUUU....-FUUUU...
My name is Griffin. Draco "Nope, nope, nope" Griffin
Ok, this is nice. But I would rather solve congruences
I really wait for some puzzle about the anatomy of the rat brain
At last, I found this answer mentioning potatoes

But where are the vouchers? :)

9 years ago
Permalink

Comment has been collapsed.

Do I need to add something to this code to make it work ? I'm trying it on repl.it but I get errors

9 years ago
Permalink

Comment has been collapsed.

I tried it on repl.it. Remember to overwrite the main() method only.
Did not want to add the actual class something{} wrapper, because the class name has to match with the filename in Java, and it is different for the two sites already

9 years ago
Permalink

Comment has been collapsed.

Ho ok, I had overwritten everything. I managed to make the example work but I have no idea how to do the next part ^^

9 years ago
Permalink

Comment has been collapsed.

I had the same problem at repl.it. I successfully used a different (but similar) site but I'm not sure if the creator is OK with me giving out the URL.

9 years ago
Permalink

Comment has been collapsed.

Feel free. I found Tutorialspoint for the steganography stuff (just it has no support for the bitmap classes), then a couple weeks ago someone did a random draw in a discussion and showed the related Python code mentioning repl.it.
If you know more environments, that is good to share

9 years ago
Permalink

Comment has been collapsed.

Bump for solved (I think). I found the GAs from the example and the train from predicting the next sequence after 9258196 and 1399737795. But there are more GAs listed in your user profile?

9 years ago
Permalink

Comment has been collapsed.

I was already sitting on it too long, the second part of the puzzle comes tomorrow

9 years ago
Permalink

Comment has been collapsed.

Cool, I'll check back tomorrow, then. :)

9 years ago
Permalink

Comment has been collapsed.

This will keep my busy for a while!

9 years ago
Permalink

Comment has been collapsed.

Well I have just given up with the online sites, installing JDK now :)

9 years ago
Permalink

Comment has been collapsed.

I think I underestimated the maths involved in this

9 years ago
Permalink

Comment has been collapsed.

Well, the 2nd hint is two days ahead, but in short: it can be solved without fancy math

9 years ago
Permalink

Comment has been collapsed.

Bump for great puzzle and waiting for the second part!

9 years ago*
Permalink

Comment has been collapsed.

Ok, let's try this :D
*a drop of sweat washes off runs down his forehead*
EDIT: Google translate sucks >_<

9 years ago*
Permalink

Comment has been collapsed.

Back to the top this goes.

9 years ago
Permalink

Comment has been collapsed.

Friendly bump

View attached image.
9 years ago
Permalink

Comment has been collapsed.

I thought I found the code, but it failed...

9 years ago
Permalink

Comment has been collapsed.

I think you found it a couple minutes later. Perhaps it was just a missing / for the link.

9 years ago
Permalink

Comment has been collapsed.

May you please give some better wording?
What is "counterpart", I have never heard anyone using this word in context of RNGs?
The 2 numbers you gave, what do they represent? Just giving numbers without context where they belong is kinda annoying? Also, it they are new seeds, are they sequential or not, or it they are part of same equation, etc...

9 years ago
Permalink

Comment has been collapsed.

If you run the example, it displays 2 random integers and a string of 5 random characters. What is said that knowing the 2 numbers is enough to find the internal state (seed) of the random number generator and thus know what 5 characters it will generate next.
That is the puzzle here, finding the 5 characters the Java RNG generates after generating the integers 9258196 and 1399737795.

However what happened for creating this puzzle is that I constructed a "seed" for generating 5 specific characters, and then constructed the previous 3 seeds. (In the example "seed-3" is 88572484529474, "seed-2" has something to do with the first random number displayed, "seed-1" has something to do with the second random number displayed, and "seed" has something to do with the 5 characters displayed). These steps are not necessary for solving this puzzle, but necessary for solving the other one (where it comes from).
For comparison: this puzzle had a solver in some 20 minutes after posting, the other one has one right now, 17 hours after posting.

9 years ago
Permalink

Comment has been collapsed.

Thank you for fast response. I just saw your puzzles few minutes ago, while at work.
I know how does RNGs work, it was part of my course, just way you worded it, and I translate it to my native language ended you bit confusing.

I'll try to get in to it more during the break, if i manage to get it before boss sees me. XD

9 years ago
Permalink

Comment has been collapsed.

DracoGriffin impostors everywhere :o

9 years ago
Permalink

Comment has been collapsed.

Bump for almost a week is left

9 years ago
Permalink

Comment has been collapsed.

Bump for late-coming solver :)

9 years ago
Permalink

Comment has been collapsed.

Bump for still a lot of time left

By the way, has anyone considered combining some of the poll options with the fact that there are congruences to solve in the other puzzle? (There is nothing to worry about right now, as I have no available GA slots at the moment)

9 years ago
Permalink

Comment has been collapsed.

Bump for also bumped the other one

9 years ago
Permalink

Comment has been collapsed.

Bump

9 years ago
Permalink

Comment has been collapsed.

Last bump from my side

9 years ago
Permalink

Comment has been collapsed.

I found the seed, however converting the next random number to 5 bytes leads to meaningless result :(

9 years ago
Permalink

Comment has been collapsed.

If you try to feed the seed to "new Random", or setSeed, note that the number is immediately xor-ed with 0x5DEECE66DL. So you need to use something like new Random(calculatedseed^0x5DEECE66DL)
(This hint appears in the other thread)

9 years ago
Permalink

Comment has been collapsed.

Thanks for the reply :)
Actually, I did exactly this thing and had one question mark sign in the result. That is what I called meaningless.

9 years ago
Permalink

Comment has been collapsed.

And just solved the other train puzzle and did not had such a problem there. Strange indeed!

9 years ago
Permalink

Comment has been collapsed.

Hmm, if you solve the puzzle and get the seed, it will generate the second number first, and then the letters.

9 years ago
Permalink

Comment has been collapsed.

Omg, stupid me! I definitely need more sleep! Thanks again man :)

9 years ago
Permalink

Comment has been collapsed.

Bump for solved

9 years ago
Permalink

Comment has been collapsed.

Sign in through Steam to add a comment.