mardi 5 janvier 2021

Finding Java.util.Random seed from bounded nextInt(int bound) results

Background

I've been reading and trying to wrap my head around various questions/answers that relate to finding the seed from Java.util.Random given its output from nextInt().

The implementation of nextInt(int bound) is:

public int nextInt(int bound) {
   if (bound <= 0)
     throw new IllegalArgumentException("bound must be positive");

   if ((bound & -bound) == bound)  // i.e., bound is a power of 2
     return (int)((bound * (long)next(31)) >> 31);

   int bits, val;
   do {
       bits = next(31);
       val = bits % bound;
   } while (bits - val + (bound-1) < 0);
   return val;
 }

The implementation of next(int bits) is:

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
        oldseed = seed.get();
        nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

where the multiplier is 0x5DEECE66DL, the addend is 0xBL, and the mask is (1L << 48) - 1. These are hexadecimal values where the L is Java convention for long conversion.

By calling nextInt() without a bound, the full 32-bits are returned from next(32) instead of dropping bits with bits % bound.

Questions

  1. Without completely bruteforcing the full $2^{48}$ possibilities, how would I go about finding the current seed after $x$ amount of calls to nextInt(n) (assuming the bound is never a power of 2)? For example, let's assume I want to find the seed given 10 calls to nextInt(344) [251, 331, 306, 322, 333, 283, 187, 54, 170, 331].

  2. How can I determine the amount of data I'd need to find the correct seed, not just another one that produces the same starting data?

  3. Does this change given bounds that are either odd/even?




Aucun commentaire:

Enregistrer un commentaire