Mersenne Twister
Cracking a pseudorandom number generator⌗
Abbreviations⌗
 The State Vector > TSV
 INitial Seed > INS
 EQuivalent Seed > EQS
 PseudoRandom number generator > PRNG
 PseudoRandom Sequence > PRS
Pseudorandom number generator is, simply put, an algorithm used to generate a sequence of numbers (PRS). These numbers are somehow related to the random seed, supplied to the generator. Applications of PRNG’s include (but aren’t limited to!) mathematics (for instance, the Monte Carlo method), cryptography (for generating asymetrical keypairs or keys in general) and many others.
Pseudorandom number generators have a few fundamental properties describing them:

seed sensitivity  PRNG’s may or may not be sensitive to seed, that is, the real period and randomness may or may not be observed with certain seeds. This is a property of an algorithm. Sometimes, seeds producing “less random” data are called weak seeds.

period  very important property classifying pseudorandom number generators. A PRS relies on finite precision arithmetic, therefore it has to repeat at certain point with a finite period. The bigger period a PRNG has, the more “random” output may be considered.

randomness  a PRNG is meant to produce independent, uniformly distributed random values that pass most statistical tests measuring randomness.

predictability  a property I’ll base my paper on. It’s usually said, that for given seed or internal state, the output should be constant.

portability  most PRNG’s fullfill this criterion. A PRNG should produce the same result on different computers and platforms.

efficiency  a PRNG that is efficient doesn’t perform a whole lot of operations, and consumes fairly manageable amount of memory.
Classification of pseudorandom number generators⌗
Multiplicative and mixed linear congruential generators⌗
Simple, widely used and fast PRNG family producing PRS of questionable quality The generator can be represented in form of a mathematical formula.
S_0  the initial PRNG seed.
S_i = (A * s_(i1) + C) mod M
For real numbers <0, 1), one can use simply:
r_i = S_i / M for a fairly large M (around 2 << 32 for 32bit numbers).
While implementing a MLCG, the initial choice of A, C and M constants is very important, because it affects period of the generator. Let’s look at this set of example parameters:
M = 9, A = 2, C = 0
For S_0
, the generator will output reccuring sequence of 3, 6, 3, 6, ...
That being said, there have been attempts to derive optimal constants. The
example above is not only a MLCG, but MCG (a mixed congruential generator).
Let’s look at some common values for A, C and M.
+++++
 Source  M  A  C 
+++++
 GNU C library [1]  2 << 31  1103515245  12345 
 C++11 minstd_rand [2]  2 << 31  1  48271  0 
 java.util.Random [3]  2 << 48  25214903917  11 
+++++
LCG cracking has been done before, even without knowing neither M, A or C. It’s been done even assuming, that some modifications have been made to the algorithm (source).
Mersenne Twister⌗
Mersenne Twister is a very popular PRNG, for a couple of reasons listed below:
 It’s very fast and can be eaisly vectorized.
 Has a large period (2^19937  1).
 Produces good quality PRS’s.
It’s worth noting, that MT19937[5] uses an abnormally big, 624 cell spinup buffer (the internal state, generated based on the seed; in code called the state vector). This can be considered a flaw (because, for instance, xorshift generators require only a few bytes of state to function). MT19937 can also run without a seed. In this case, 5489UL is the seed for filling the state vector. It can be generated using the following program:
The internal state of Mersenne Twister is interesting, because it provides a simpler way of cracking MT19937  you no longer need to trace back to the original seed. Let’s look at it.
++ ++ ++
Initial Seed+>+State vector+>+PRS
++ ++ ++
NB: after the initial seed is used, the state vector is perpetually refilled. Depending on the goal, you can
 perform PRS > TSV crack
 perform PRS > EQS crack
Note: You can’t perform PRS2INS crack in every case. Assuming finite integers, you may need to bruteforce the seed. The amount of possible seeds is obviously increasing the bigger numbers get, so you may hit an edge case when two seeds produce the same output to certain extent (e.g. up until 624th character), but you’re out of data, so you can’t verify whether the first or second one is the one you may be looking for.
In this paper, I’ll describe a way to perform PRS2TSV crack that has been known before. I’ll describe a way of performing PRS2EQS crack aswell, but this one doesn’t seem to be publicly discussed, so here it is. Also, I’ll describe my coefficientbased, pruning bruteforce approach to efficient EQS cracking.
Before we start, I’d like to note that Mersenne Twister isn’t one of the cryptographically secure pseudorandom number generators, but I’ve seen it being used by inexperienced persons; I’ve even seen LCG’s being used for (mainly) cryptographical applications.
Also, it’s worth mentioning that cracking a PRNG may be extremally useful in tight spaces. That’s what Notch did with java.util.Random()
LCG in his Minecraft2k game  he cracked java.util.Random()
so it gives a sequence of bytes that makes up a texture set! Thanks to this, he may have saved 8x8x16 (8x8 textures, assume 16 textures overall), whooping 1024 bytes (assuming 1bpc)  that’s half of the game size.
Other applications of PRNG cracking include… programming, but I’ll get to that later.
Performing a PRS2TSV crack.⌗
Before we start, I’ll be targeting specifically the Python’ random module Mersenne Twister implementation (it’s using array seeding, contradictionairly to most implementations that just rely on a 32bit input seed). The difference arises, because Python by default operates on large numbers. It doesn’t mean, though, that the article doesn’t apply to other implementations or platforms.
To perform a PRS2TSV crack, we need at least 624 characters of input  that’s the length of TSV. After 624 characters, a twist occurs (hence the name, Mersenne Twister).
Ruling out game plan, one should start by gathering the data straight after a twist  if one supplies intertwist data, the solution will not work. Reversetampering the input for each character will return the internal Mersenne Twister state.
Please note, that cracking the twists isn’t an easy task, and I won’t cover it in this paper (it’s not probably worth mentioning, and the method isn’t refined enough).
The tempering method has been invented to (hopefully) stop crackers from recovering the internal state, OR spice up the output a bit. Either reason it’s been added, to recover the internal state one has to untemper the output. The following tempering code is used by MT19937:
Assume a = x
at the beginning of the untempering algorithm (x=number, y=shift). Then, rightshift a by y, and xor it over with x, for each bit of a uint32_t
. Let’s assume:
A very important observation has to be made  for some cases, one doesn’t need to perform exactly 32 passes  sometimes, only one is sufficient. Let’s review another example:
One can slowly recover the value of the (y >> 11
). Because x ^ y ^ y
is idempotent, getting rid of the mask is trivial and the algorithm is doing exactly that in the meantime.
Let’s write some helper procedures for unshifting then:
The leftshift is a bit more complex  one needs to get rid of the mask applied (0x9d2c5680UL
, 0xefc60000UL
), but this is doable as well using the same method.
Now, to untemper the value, just apply these functions in reverse order:
Running untemper() over the output will recover the internal state of MT19937. Note: There’s a pitfall you might stumble upon while trying to perform PRS2TSV crack  the recent MT19937 performs a twist straight at the beginning.
How to recover an equivalent seed?⌗
In this chapter, I’ll try to describe a way of cracking Mersenne Twister in such a way, that you can generate a seed, that Mersenne Twister will accept and output a PRS of your choice, no longer than around 100 bytes.
To test the deep crack, I’ll use this program (source):
Seed goes into the program
variable, and length of the data goes into length
variable. Note, how the output is limited to printable character range  I’ll explain that in a second.
I got interested in Mersenne Twister cracking due to existence of Seed esoteric programming language  put the length and random seed in Mersenne Twister, generate printable PRS, dump it in a Funge98 compatible interpreter and execute it. It motivated me to devise a set of algorithms (original diagram):
+ Lower speed


v Higher speed
Z P ++
E R  ++ ++
R U  HQB method+>+Very efficient seed generation. (A) 
O N  +++ Very slow runtime, calculating a long
E ++  PRS may take a very long time. 
++ v ++
 +++ ++
 BX=6 method+>+Very efficient seed generation. (B) 
 +++ A bit faster than HQB, calculating 6 
  element long PRS may take more than 
 v 50'000 minutes. 
 +++ ++
 BX=5 method++ ++
B  +++ +>+Wellsuited for mediumlength PRS (C)
X   Still a bit slow. Very decent output.
 v ++
F  +++ ++
A  BX=4 method+>+Seed generation equilibrium (D). 
M  +++ Quite small output, pretty fast (less
I   than half an hour for quite long PRS)
L  v ++
Y  +++ ++
 BX=3 method+>+Fast, well suited for long strings, 
 +++ best speed to seed score. (E) 
  ++
 v ++
 +++ Quite fast, questionable quality of 
 BX=2, BX=1 methods+>+output (F). Not recommended under 
 +++ any circumstances. 
++  ++
++ v ++
 +++ Instant. Decent quality output (given
I  This method +>+that the algorithm is instant), but 
N  +++ still worse than BX=3 (G) 
S   ++
T  v ++
A  +++Instant. Can predict a long PRS (600 
N  Approximating methodcharacters, compared to mere 100). 
T  ++Terrible quality seed (>4000 digits).
++ The output may not be correct in all 
cases. (H) 
++
Seed size
AB C D E F G H
+>
Tiny Huge
Note: Seed size and efficency
for the BX family (BF) depends
on the PRS and can't be estimated
reliably, therefore this chart
assumes BX_n with n in <4,6>.
The terminology, constructs and method names have been devised by me beforehand to make the idea expressing easier.
The HQB algorithm⌗
The HQB algorithm has been made by the Esolangs Wiki contributors (I didn’t invent it). It’s very slow, though, and there is no good reasoning why would one use it. For completeness though, here it is, implemented in Python:
It’s better though to use BX=n
algorithm for PRS of length n
 it will produce simillar or the exact same result more efficiently.
BX algorithm family⌗
BX family is arguably the best way to create short seeds for an arbitrary PRS, up to 100 characters. The implementation hasn’t been published yet, but a flowchart of the algorithm is quite simple to comprehend and implement. The general idea looks like this (original diagram):
++ ++
BXn algorithm+>+length(PRS) le n
++++ ++++
^ ^  
  1 0
  v v
+++ +++ +++ +++
n PRS HQB(PRS)  // Seed length is known 
++ ++ ++  // before computation! 
+++
++ ++ 
if ans>621, can't crack+<+length(PRS)*2397+<+
+++ ++

for each c1..cm in PRS
 ++ ++
+>+convert ASCII to printable index+>+calculate such a 
++ where random(a,b)*96 
++ ++ is equal to the input
clear +<+untemper A,  +++
n*2+1  place values  ++ 
for named except target +<+random(a,b)=float(a<>5,b<>6)+<+
targets  on n*2 position ++
+++ ++

 ++
 instantize MT with zeros up to M, 
+>+spin up the MT and {artificially 
alter the internal TSV using a 
xormask} until found a correct seed.
++
The BXn algorithm obviously is utilizing the advantage given by the TSV.
The public algorithm⌗
Appendix  test cases⌗
Test case A: "HelloWorld"
Test case B: "!@#$%^&*()"
Test case C: "VeryLongTextBewareVeryVeryLong"
A 
1A1 00000000F7E71E877991EAC19B1633118E3EB38705206F3F037C9078CA5C5FC2574CD6D776
BA10664FA5B1D20481CE7A9B63F5758E55C724F4914DD9768D8CC58DE5E554180A5219F19F01A5
8EBE0CB2C0502CF89265D6CF [pad out with zeros to 1A1h]
B 
1A1 000000003B451CAEC15B4A1F7AEC61A2FDB04511A609F6A6BA24BB12BD71E82FA7D8EC015E
C088B3FEEE670294B91EA2086970AFF928591088E6A7791535635A8FF5BB3EFAB01C7DF23BE107
7EA03CCC2BE8C0AA7375AEF2
C 
1C9 000000007EBA24439AC90F8B94D96D1C71378E90157DD5FA367EB2D1BF8ED3BF1CBC555176
F40920463B09C33230559BB27F39067B7223171A708EBCF4EEB4DE0CC10D02449C876F575C1FA1
D0EA8194D6A1196958EA059876AC236B6DD6E23CAA37BD4E8A2FE5ED35D34438DD3086E53D6BED
C3A61FEDD5DD35D2B9DAC2A26C885117AA7D353EA5DB0635A20516EDD7CDA124BD29863C3F8E17
3C7E231DB7515E466A0135537FD7B099CAE21AC1A3C03C270A34BEA0F33B87B60331C1D9484EB9
E149BD70CF9D9D545C5C64D28DD54E75557A60CCB85E0A34F291E1E7461FCDF509C6BB7DAABC0E
B9E48872C0636D76DADECF4891ACCC08
You can download the cracker binary if you don’t want to build it. Linux/WSL, 64bit.