Python-random-module-cracker icon indicating copy to clipboard operation
Python-random-module-cracker copied to clipboard

Implement offsetting to previous internal states

Open JorianWoltjer opened this issue 2 years ago • 1 comments

While reading into some PRNG cracking, I learned that it is possible to recover any previous states of the Mersenne Twister after it has been cracked. See this post for the algorithm used:
https://jazzy.id.au/2010/09/25/cracking_random_number_generators_part_4.html

The main change is the addition of the untwist() method, which is the Java algorithm from the article above translated to Python:

def untwist(self):
    w, n, m = 32, 624, 397
    a = 0x9908B0DF

    # I like bitshifting more than these custom functions...
    MT = [self._to_int(x) for x in self.mt]

    for i in range(n-1, -1, -1):
        result = 0
        tmp = MT[i]
        tmp ^= MT[(i + m) % n]
        if tmp & (1 << w-1):
            tmp ^= a
        result = (tmp << 1) & (1 << w-1)
        tmp = MT[(i - 1 + n) % n]
        tmp ^= MT[(i + m-1) % n]
        if tmp & (1 << w-1):
            tmp ^= a
            result |= 1
        result |= (tmp << 1) & ((1 << w-1) - 1)
        MT[i] = result

    self.mt = [self._to_bitarray(x) for x in MT]

In the implementation, I found it easier to work with bit-shifting and XORing directly, but I noticed most of the code uses custom functions for that. You may want to clean up the implementation to use those custom functions, but this simply translates the self.mt into integers for the algorithm and then translates them back to bit arrays in the end.

To ease in using this untwist() method, an offset(n) method was made that works for positive and negative numbers, to set the state back to a previous one by untwisting.

def offset(self, n):
    if n >= 0:
        [self._predict_32() for _ in range(n)]
    else:
        [self.untwist() for _ in range(-n // 624 + 1)]
        [self._predict_32() for _ in range(624 - (-n % 624))]

There are some details like the randbelow() function possibly advancing the state multiple times, and a note about this is added to the README.

I have also written a couple of tests to make sure this all works as expected.

JorianWoltjer avatar May 05 '23 08:05 JorianWoltjer

@tna0y I see the repository is a bit inactive, but any chance can this be merged?

JorianWoltjer avatar May 24 '23 13:05 JorianWoltjer