Applying Linear Algebra to Solve For Fixed Seeds in Pokémon Sword and Shield

...

import numpy as np

class Xoroshiro128PlusGF:
	"""Xoroshiro128+ Generator used in GameFreak games"""

	XOROSHIRO_CONST = np.uint64(0x82A2B175229D6A5B)

	def __init__(
		self,
		seed_0: np.uint64,
		seed_1: np.uint64 = XOROSHIRO_CONST
	) -> None:
		self.state = np.empty(2, np.uint64)
		self.state[:] = seed_0, seed_1

	@staticmethod
	def rotl(integer: np.uint64, shift: np.uint64) -> np.uint64:
		"""Rotate the bits of a 64-bit unsigned integer left by
		a specified shift"""
		return (
			(np.uint64(integer) << np.uint64(shift))
			| (np.uint64(integer) >> np.uint64(64 - shift))
		)

	@staticmethod
	def bit_mask(integer: np.uint32) -> np.uint32:
		"""Generate a bitmask for a 32-bit integer"""
		return np.uint32((1 << (int(integer).bit_length())) - 1)

	def next_full(self) -> np.uint64:
		"""Generate the next 64-bit random number"""
		seed_0, seed_1 = self.state
		result = seed_0 + seed_1
		seed_1 ^= seed_0
		self.state[:] = (
			self.rotl(seed_0, 24)
			^ seed_1
			^ (seed_1 << np.uint64(16)),
			self.rotl(seed_1, 37)
		)

		return result

	def next(self) -> np.uint32:
		"""Generate the next 32-bit random number"""
		return np.uint32(self.next_full())

	def rand_max(self, maximum: np.uint32) -> np.uint32:
		"""Generate the next random number < maximum"""
		maximum = np.uint32(maximum)
		mask = self.bit_mask(maximum - 1)
		result = self.next() & mask

		while result >= maximum:
			result = self.next() & mask

		return result
 
Copy

The Xoroshiro128+ state transition function is -linear, this means it can be represented as multiplying the state's bit vector representation by some matrix . The bit-wise algorithm for the state transition function can be boiled down to the following operations:

# 1.
seed_1 ^= seed_0
# 2.
seed_0 = rotl(seed_0, 24)
# 3.
seed_0 ^= seed_1
# 4.
seed_0 ^= seed_1 << 16
# 5.
seed_1 = rotl(seed_1, 37)
 
Copy

where seed_0 and seed_1 are the two 64-bit halves of the internal state. Due to the relations between the two halves of the state, it is useful to refer to them each as 64-bit bit vectors . Due to the properties of addition and subtraction in , addition between bit vectors is equivalent to the exclusive-or operation on binary integers. Because of this and the properties of the shifted and rotated matrices defined earlier, we can represent the state transition function as follows:

By looking at each half of the state individually, we can build two matrices which when we multiply the entire state by result in and respectively. The matrices can be built by applying each step as follows:

0. seed_0 = ...; seed_1 = ...
1. seed_1 ^= seed_0
2. seed_0 = rotl(seed_0, 24)
3. seed_0 ^= seed_1
4. seed_0 ^= seed_1 << 16
5. seed_1 = rotl(seed_1, 37)
   Since maps the current state to the next seed_0, and maps the current state to the next seed_1, horizontally concatenating the matrices gives our final target matrix
   that describes the full state transition function.

Consider a modified form of the Xoroshiro128+ output function that when returning a random number in the interval would simply return the value of the first bit of the state. That function would look like this:

def rand2(self):
	result = self.seed0 & 1
	self.next_full()
	return result
 
Copy

This is evidently not how rand_max(2) would be handled in the actual implementation, but it is useful to consider for solving the problem of calculating the initial state of the PRNG from only its outputs. If we look at the first column for any given power of the state transition matrix , we can get a column vector that maps the initial state vector to the value of its first entry after multiplications of the state transition matrix, i.e.

What this means then, is if we construct an augmented square matrix made up of these column vectors for consecutive values of , i.e.

This matrix would map the initial state vector to some vector made up of the first bit of consecutive states

This vector , then is trivially able to be constructed by recording the outputs of the rand2 function described earlier:

prng = ... # prng with an unknown initial state
a = [prng.rand2() for _ in range(128)]
 
Copy

As we have now found a linear mapping from the initial state to this trivially observable vector , if this mapping can be shown to be invertible, the matrix inverse could be used to directly map from back to the initial state , and thereby expose the full initial state based only on the observable outputs. In the case of this implementation of Xoroshiro128+, this matrix can be shown to be invertible.

The game generates the fixed attributes via the following algorithm:

fixed_seed = ... # 32-bit value randomly decided
guaranteed_ivs = ... # a number [0,6] that determines how many IVs are guaranteed to be "perfect"
rng = Xoroshiro128PlusGF(fixed_seed)

ec = rng.rand_max(0xFFFFFFFF)
pid = rng.rand_max(0xFFFFFFFF)

# default values
ivs = [None, None, None, None, None, None]

for _ in range(guaranteed_ivs):
	# choose a random iv to set to "perfect" (31)
	random_iv_index = rng.rand_max(6)
	# if the iv has already been set to 31, choose a new iv until one is found that is not already perfect
	while ivs[random_iv_index] is not None:
		random_iv index = rng.rand_max(6)
	ivs[random_iv_index] = 31

# check each iv
for iv_index in range(6):
	# if the iv has not yet been set, set it to a random value [0,31]
	if ivs[iv_index] is None:
		ivs[iv_index] = rng.rand_max(32)
 
Copy

The thing that really complicates this algorithm and the progression of the PRNG is the guaranteed_ivs variable. This variable is only set to a non-0 value in the following specific cases:

1. The pokémon is a "brilliant aura pokémon"
   • up to a 3% chance of occurring
   • sets the value to either 2 or 3 with a 50% chance of each
2. The pokémon is a specific one-time "legendary pokémon encounter"
   • only happens with a specific set of pokémon
   • sets the value to 3

guaranteed_ivs being set can massively change the outcome of the generation algorithm, but due to it only happening in these two cases, for simplicity's sake we will only consider the case when it is set to 0. With guaranteed_ivs set to 0, the algorithm condenses to the following:

fixed_seed = ... # 32-bit value randomly decided
rng = Xoroshiro128PlusGF(fixed_seed)

ec = rng.rand_max(0xFFFFFFFF)
pid = rng.rand_max(0xFFFFFFFF)

ivs = [rng.rand_max(32) for _ in range(6)]
 
Copy

The input value for the rand_max that returns the EC and PID stands out as it is 1 less than , meaning the possible values for each includes every possible 32-bit value except . This is done by the game because it uses 0xFFFFFFFF which is -1 when interpreted as a signed 32-bit integer to denote when a value has not yet been set. If we replace rand_max with its definition we can more clearly see what this means for the relation between the seed and these results

fixed_seed = ... # 32-bit value randomly decided
rng = Xoroshiro128PlusGF(fixed_seed)

mask_0xFFFFFFFF = rng.bit_mask(0xFFFFFFFF - 1)
mask_32 = rng.bit_mask(32 - 1)

ec = rng.next() & mask_0xFFFFFFFF
while ec >= 0xFFFFFFFF:
	ec = rng.next() & mask_0xFFFFFFFF

pid = rng.next() & mask_0xFFFFFFFF
while pid >= 0xFFFFFFFF:
	pid = rng.next() & mask_0xFFFFFFFF

# default values
ivs = [None, None, None, None, None, None]
for iv_index in range(6):
	iv = rng.next() & mask_32
	while iv >= 32:
		iv = rng.next() & mask_32
	ivs[iv_index] = iv
 
Copy

mask_0xFFFFFFFF and mask_32 are constants which can be computed ahead of time

mask_0xFFFFFFFF = Xoroshiro128PlusGF.bit_mask(0xFFFFFFFF - 1)
mask_32 = Xoroshiro128PlusGF.bit_mask(32 - 1)
print(f"{hex(mask_0xFFFFFFFF)=} {mask_32=}")
 
Copy

fixed_seed = ... # 32-bit value randomly decided
rng = Xoroshiro128PlusGF(fixed_seed)

ec = rng.next() & 0xFFFFFFFF
while ec >= 0xFFFFFFFF:
	ec = rng.next() & 0xFFFFFFFF

pid = rng.next() & 0xFFFFFFFF
while pid >= 0xFFFFFFFF:
	pid = rng.next() & 0xFFFFFFFF

# default values
ivs = [None, None, None, None, None, None]
for iv_index in range(6):
	iv = rng.next() & 31
	while iv >= 32:
		iv = rng.next() & 31
	ivs[iv_index] = iv
 
Copy

You'll then notice that the loop that checks if iv >= 32 is redundant, as a bit-wise AND operation by 31 will never return a value greater than 31.

fixed_seed = ... # 32-bit value randomly decided
rng = Xoroshiro128PlusGF(fixed_seed)

ec = rng.next() & 0xFFFFFFFF
while ec >= 0xFFFFFFFF:
	ec = rng.next() & 0xFFFFFFFF

pid = rng.next() & 0xFFFFFFFF
while pid >= 0xFFFFFFFF:
	pid = rng.next() & 0xFFFFFFFF

ivs = [rng.next() & 31 for _ in range(6)]
 
Copy

The loops for EC and PID, however, are not full redundant as a bit-wise AND operation by 0xFFFFFFFF can produce a number 0xFFFFFFFF solely in the case where the value is already 0xFFFFFFFF. This means that if rng.next() returns 0xFFFFFFFF for either the EC or the PID it will cause an extra call to be needed to avoid it. This case, however, is 1 out of possible values that rng.next() can return, making it a very unlikely edge-case which can be accounted for easily down the line. For the sake of simplicity, we will be treating it as redundant.

fixed_seed = ... # 32-bit value randomly decided
rng = Xoroshiro128PlusGF(fixed_seed)

ec = rng.next() & 0xFFFFFFFF
pid = rng.next() & 0xFFFFFFFF
ivs = [rng.next() & 31 for _ in range(6)]
 
Copy

What we can now see is that under these conditions the IVs are generated using bits directly from the result of rng.next() consistently 2-8 "advances" away from the original fixed_seed. Let's now discard EC and PID completely and expand the rng.next() call used for generating the IVs

fixed_seed = ... # 32-bit value randomly decided
rng = Xoroshiro128PlusGF(fixed_seed)

rng.next_full()
rng.next_full()

# default values
ivs = [None, None, None, None, None, None]
for iv_index in range(6):
	seed_0, seed_1 = rng.state
	iv = (seed_0 + seed_1) & 31
	seed_1 ^= seed_0
	rng.state[:] = (
		rng.rotl(seed_0, 24)
		^ seed_1
		^ (seed_1 << np.uint64(16)),
		rng.rotl(seed_1, 37)
	)
	ivs[iv_index] = iv
 
Copy

As 31 in binary is 0b11111, when applying the bit-wise AND operation between it and another number, you simply mask the 5 least significant bits of that number. This means that each IV is simply the 5 least significant bits of the addition between the two halves of the internal state. Additionally, the operations done on the state afterwards are just the state transition algorithm so they will be abbreviated as rng.next_state()

fixed_seed = ... # 32-bit value randomly decided
rng = Xoroshiro128PlusGF(fixed_seed)

rng.next_full()
rng.next_full()

# default values
ivs = [None, None, None, None, None, None]
for iv_index in range(6):
	seed_0, seed_1 = rng.state
	iv = ((seed_0 & 31) + (seed_1 & 31)) & 31
	rng.next_state()
	ivs[iv_index] = iv
 
Copy

Thinking back to the example of initial state reconstruction, we now almost have an observable sequence of outputs that we can build a matrix to map the fixed_seed to. The one glaring issue here is that instead of directly having part of the state as output like we did in the example, we are adding two different portions of the state together as output. If we could somehow determine seed_0 & 31 and seed_1 & 31 from the IV, we would have our target observable sequence.

Unfortunately, addition with carry is a lossy non-linear operation and thus we cannot directly map from the initial state to the IVs. The solution to this problem is to introduce the element of brute-force. We know the value of iv, and if we could know the value of seed_1 & 31, we could simply subtract it from the value of iv to determine seed_0 & 31. We would then have our full observable sequence.

The idea then is to brute-force all 32 possible values of seed_1 & 31 for each IV, thereby giving us the value of both seed_0 & 31 and seed_1 & 31 for each IV. If we were to brute-force this for all 6 IVs, that would be a brute-force of or total values. This already is only 2 times more efficient than if we simply brute-forced all possible seeds, but the key here is that we are getting in return bits of information over the 6 states we are measuring. is way more information than we theoretically need, if everything worked out perfectly, we could build a 32-by-32 matrix to map the fixed_seed directly to 32 bits of observed information, and then invert that to map only 32 bits of information back to the fixed_seed.

If we then only focus on 3 of the IVs rather than all 6, we only need to brute-force possible values for theoretically up to 30 bits of the fixed_seed. We are then left with the task of finding the last bits, which we will later find is fairly easy.

The 5 least significant bits of seed_0 are represented by the 1st to 5th entries in the state bit vector, and the 5 least significant bits of seed_1 are represented by the 65th to 69th entries. We can map from the initial state to these bits with the following matrix:

where is an augmented vector containing the observable bits of interest after multiplications by the state transition matrix. We can then concatenate these matrices again to map from an initial state to the bits of interest from all 3 measured IVs

We start from here because of the two state transitions from generating the EC and then the PID prior to the generation of the first 3 IVs. now is 128-by-30 matrix mapping the full initial state to the 30 bits that make up the first 3 IVs. Looking at the initial state, the first 32 bits are made up of the fixed_seed, the next 32 bits are 0, and the last 64 bits are made up of the "Xoroshiro constant" 0x82A2B175229D6A5B. The Xoroshiro constant introduces a constant vector that is added to the result and the zero bits have no effect on the result so we can truncate from the 33rd row onward and handle the constant factor later.

As is a 32-by-30 matrix, it is not square and therefore is not directly invertible. In this case, we can use the Moore-Penrose inverse to compute a particular solution. Once we have a particular solution, we can combine it with any linear combination of the vectors that form the basis of the cokernel of to find all possible solutions. This works because the cokernel of consists of all vectors such that , this means that for any particular solution where , , and therefore also constitutes a solution.

If we find that the cokernel of has a nullity of , that is, the number of linearly independent vectors in the cokernel, we can determine that the entire cokernel is made up of vectors, as under there are only two possible scalars each vector could be multiplied by. This means there are unique solutions to the equation .

We have now detailed the process for finding all solutions to the equation , where is the bit vector representation of a "fixed seed", and is a augmented vector of "observable" bits based on the IVs of the pokémon we want to find the possible fixed seeds for:

1. Build the matrix based on concatenating the columns of powers of the state transition matrix which correspond to the observable bits we are measuring, and truncating it to only include the rows that correspond to the bits of the fixed seed
2. Calculate the Moore-Penrose inverse of , and multiply it our observable bits by it to get a particular solution
3. Compute the cokernel of and combine each vector with our particular solution to find all unique solutions where is the nullity of the cokernel

What we will then find is that for the problem we have detailed, the nullity of is equal to 4, just greater than the minimum of 2 bits predicted earlier. The linearly independent vectors themselves are the bit vectors representing the integers 0x97a11084, 0x7addf188, 0x852536b0, and 0x2e4b6840 respectively.

We should now build a target vector based on the IVs we want to test our solution. What we need to recall is that half of the target vector is entirely free and each possible value needs to be brute-forced to get all possible solutions. As there are 15 free bits, there are more possible solutions, and therefore fixed seeds that will potentially produce the first three IVs we are using to calculate with.

These seeds can then be manually filtered for the ones that also have the target value for the last 3 IVs. For our example vector, we will use a trivial case where the first 10 free bits are unset, the last 5 bits are set, and our target first 3 IVs will be "perfect", each being 31. This example is chosen because it is known to produce a valid particular solution when multiplying it by , something easy to test when brute-forcing.

import sys
from itertools import product

# pyodide support
if sys.platform == "emscripten":
    import micropip
    await micropip.install("numpy")

import numpy as np

class Xoroshiro128PlusGF:
    """Xoroshiro128+ Generator used in GameFreak games"""

    XOROSHIRO_CONST = np.uint64(0x82A2B175229D6A5B)

    def __init__(
        self,
        seed_0: np.uint64,
        seed_1: np.uint64 = XOROSHIRO_CONST
    ) -> None:
        self.state = np.empty(2, np.uint64)
        self.state[:] = seed_0, seed_1

    @staticmethod
    def rotl(integer: np.uint64, shift: np.uint64) -> np.uint64:
        """Rotate the bits of a 64-bit unsigned integer left by
        a specified shift"""
        return (
            (np.uint64(integer) << np.uint64(shift))
            | (np.uint64(integer) >> np.uint64(64 - shift))
        )

    @staticmethod
    def bit_mask(integer: np.uint32) -> np.uint32:
        """Generate a bitmask for a 32-bit integer"""
        return np.uint32((1 << (int(integer).bit_length())) - 1)

    def next_full(self) -> np.uint64:
        """Generate the next 64-bit random number"""
        seed_0, seed_1 = self.state
        result = seed_0 + seed_1
        seed_1 ^= seed_0
        self.state[:] = (
            self.rotl(seed_0, 24)
            ^ seed_1
            ^ (seed_1 << np.uint64(16)),
            self.rotl(seed_1, 37)
        )

        return result

    def next(self) -> np.uint32:
        """Generate the next 32-bit random number"""
        return np.uint32(self.next_full())

    def rand_max(self, maximum: np.uint32) -> np.uint32:
        """Generate the next random number < maximum"""
        maximum = np.uint32(maximum)
        mask = self.bit_mask(maximum - 1)
        result = self.next() & mask

        while result >= maximum:
            result = self.next() & mask

        return result


def generate_ivs(fixed_seed: int) -> list[int]:
    """Generate ivs from a fixed seed"""

    rng = Xoroshiro128PlusGF(fixed_seed)
    rng.next_full()
    rng.next_full()

    return [rng.rand_max(32) for _ in range(6)]

def matmul(vector: int, matrix: list[int]) -> int:
    """Multiply vector by matrix"""
    result = 0
    for i, row_vector in enumerate(matrix):
        if (vector >> i) & 1:
            result ^= row_vector

    return result

# precomputed matrices
L = [
    1049601,
    35653634,
    71307268,
    176169000,
    352338000,
    671088768,
    301990144,
    603980288,
    134218752,
    268437504,
    536875008,
    34612256,
    69224512,
    138416256,
    311435520,
    622871040,
    138413057,
    311461890,
    622923780,
    172105736,
    344211472,
    688390144,
    268435456,
    536870912,
    1025,
    2050,
    4100,
    34644009,
    69288018,
    138543236,
    277119240,
    554238480,
]

L_plus = [
    75040,
    37749248,
    75498496,
    16779529,
    155325210,
    172190824,
    71349924,
    25240576,
    184680776,
    75506852,
    16852256,
    4194816,
    8389632,
    16793665,
    155353482,
    134217993,
    163980590,
    172705856,
    72398516,
    27337760,
    16777217,
    155320586,
    9248,
    776693824,
    310650420,
    188875016,
    67118116,
    16852000,
    4194304,
    8388608,
]

L_co_kernel = [
    0,
    2543915140,
    2061365640,
    3984384268,
    2233808560,
    310650420,
    4294494008,
    1750718396,
    776693824,
    3119151300,
    1419155912,
    3275196748,
    2876137200,
    1020218996,
    3518214008,
    1175633916
]

c = 0x2c10b46c

TARGET_IVS = [0, 0, 0, 0, 0, 0]
fixed_seeds = []

for seed_1_values in product(range(32), range(32), range(32)):
    observable_bits = 0
    for iv_index, seed_1_value in enumerate(seed_1_values):
        seed_0_value = (TARGET_IVS[iv_index] - seed_1_value) & 31
        observable_bits |= (seed_0_value | (seed_1_value << 5)) << (iv_index * 10)

    # account for the xoroshiro constant
    observable_bits ^= c

    # if the vector does not produce a valid solution, skip it
    if matmul(matmul(observable_bits, L_plus), L) != observable_bits:
        continue

    principal_solution = matmul(observable_bits, L_plus)
    for co_kernel_vector in L_co_kernel:
        solution = principal_solution ^ co_kernel_vector

        solution_ivs = generate_ivs(solution)
        if solution_ivs == TARGET_IVS:
            fixed_seeds.append(solution)

for fixed_seed in fixed_seeds:
    print(f"Valid Fixed Seed: {fixed_seed:08X}")

 
Copy