mersenne twister - secret revealed

Note: I plan on publishing this article in Phrack. I already mailed my article and chances are, it'll get published in the next release, that is, P71. I'm really happy because of that, as it's the first time I'm writing for such a big player in the cracking scene. Anyways, I hope the lecture will be pleasing for you, dear reader.

[=--------------=[ Cracking a pseudorandom number generator ]=--------------=]
[=--------------------=[ By Palaiologos @ MENACE /29A ]=--------------------=]

     * 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 set 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 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

     * 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.

--[ 1 - Classification of pseudorandom number generators.

      Multiple algorithms have been discovered. Some variations of a general
idea still fall to a given category. Some of the PRNG's are considered
CSPRNG, that is, cryptographically secure pseudorandom number generators
that are well suited for, well, cryptographical needs.

--[ 1. 1 - 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_(i-1) + 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 32-bit 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 [4].

--[ 2 - Mersenne Twister

      Mersenne Twister is a very popular PRNG, for a couple of reasons, listed

     * 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 spin-up
buffer (the internal state, generated based on the seed; in code called
the state vector).

MT19937 can also run without a seed. In this case, 5489UL is the seed for
filling the state vector. The state vector looks like this:


It's been generated using the following C program:

#define N 624

static unsigned long mt[N];
static int mti = N + 1;

void init_genrand(unsigned long s) {
      mt[0] = s & 0xffffffffUL;
      for (mti = 1; mti < N; mti++) {
          mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
          mt[mti] &= 0xffffffffUL;

int main(void) {
      int i = 0;
      for(; i < 624; i++)
          printf("%8lX\n", mt[i]);

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|
               +------------+         +------------+         +---+

Depending on the goal, you can
     a) perform PRS -> TSV crack
     b) 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 coefficient-based, pruning bruteforce approach to efficient EQS

Before we start, I'd like to note that Mersenne Twister isn't one of these
cryptographically secure pseudorandom number generators, but I've seen it
being used by inexperienced persons; heck, 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.

--[ 2. 1 - 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 32-bit
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 inter-twist data, the solution will not work.
Reverse-tampering 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:

      y ^= (y >> 11);
      y ^= (y << 7) & 0x9d2c5680UL;
      y ^= (y << 15) & 0xefc60000UL;
      y ^= (y >> 18);

Assume a = x at the beginning of the untempering algorithm (x=number, y=shift)
Then, right-shift a by y, and xor it over with x, for each bit of uint32_t.
Let's assume:

y = 0x12345678;
y ^= (y >> 18); // y = 0x123452F5
z = y           // z = 0x123452F5
z = y ^ z >> 18 // z = 0x123452F5 ^ 0x48D = 0x12345678

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:

y = 0x12345678;
y ^= (y >> 11); // y = 0x123610F2
z = y           // z = 0x123610F2
z = y ^ z >> 11 // z = 0x123610F2 ^ 0x246C2 = 0x12345630
z = y ^ z >> 11 // z = 0x123610F2 ^ 0x2468A = 0x12345678

A very important observation has been made - 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:

uint32_t usr(uint32_t x, uint32_t y) {
      uint32_t tmp = x;
      uint8_t counter;
      for(counter = 0; counter < 8; counter++) {
          tmp = x ^ tmp >> y;
          tmp = x ^ tmp >> y;
          tmp = x ^ tmp >> y;
          tmp = x ^ tmp >> y;
      return tmp;

The leftshift is a bit more complex - one needs to get rid of the mask applied
(0x9d2c5680UL, 0xefc60000UL), but this is doable aswell using the same method.

uint32_t usl(uint32_t x, uint32_t y, uint32_t m) {
      uint32_t tmp = x;
      uint8_t counter;
      for(counter = 0; counter < 8; counter++) {
          tmp = x ^ (tmp << y & m);
          tmp = x ^ (tmp << y & m);
          tmp = x ^ (tmp << y & m);
          tmp = x ^ (tmp << y & m);
      return tmp;

Now, to untemper the value, just apply these functions in reverse order:

#include "usl.h"
#include "usr.h"

uint32_t untemper(uint32_t y) {
      y = usr(y, 18);
      y = usl(y, 15, 0xefc60000UL);
      y = usl(y,  7, 0x9d2c5680UL);
      y = usr(y, 11);
      return y;

Running untemper() over the output will recover the internal state of MT19937.
Note: You may fall to a pitfall trying to perform PRS2TSV crack. Remember,
that the recent MT19937 performs a twist straight at the beginning.

--[ 2. 2 - A "deep" crack.

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[6]:

import random

prog="".join([chars[int(random.random()*96)] for i in range(length)])


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 Funge-98 compatible interpreter
and execute it. It motivated me to devise a set of algorithms:

      +  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 |    +-+---------+   +---->+Well-suited for medium-length 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 |    |Paleologoi 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 method||characters, 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 (B-F) 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 expression easier.

--[ 3 - 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 completness though, here it is, implemented in Python

import random


while prog != endprog:
      prog = ''
      for t in range(1,length+1):
          prog += chars[int(random.random()*96)]
          if endprog[:t] != prog:
              seed += 1
print('"{0}" => {1} {2}'.format(prog,length,seed))

It's better though to use `BX=n` algorithm for PRS of length `n` - it will
produce simillar or exact same result more efficiently.

--[ 4 - 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.
I've invented the BXn algorithm after tinkering with the Paleologi Algorithm.
The general idea looks like this:

+-------------+       +----------------+
|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)*2|397+<----+
    ++----------------------+    +-----------------+
     |for each 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.

--[ 5 - Paleologoi Algorithm

The most efficient, instant algorithm I invented publicly known (as of 2020).
Paleologoi Algorithm is discarding the last part from BXn algorithm, that is,
producing one-deep xorred state. I've implemented this algorithm in Assembly.
The code follows:

; ----------------------------------------------------------------------------
; Paleologoi Algorithm implementation in x86-64 assembly.
; assemble and run (skid tutorial):
; ---- skids cut here ----
;  > yasm -f elf64 crack.asm
;  > gcc crack.o -o crack
;  > crack "Hello"
; ---- skids cut here ----

; We're operating in 64-bit mode.
[BITS 64]

; Import some required libc procedures.
extern malloc
extern free
extern printf
extern strlen
extern puts
extern exit

; Export main. I could aswell export _start, but
; I'd rather stick to these (at least mildly) portable
; arguments passed via rsi / rdi.
global main

; Some constants ripped directly from the MT19937 source.
N              equ 624
M              equ 397
NSUBM          equ 227
MATRIX_A       equ 9908B0DFh

; Two magic numbers from the init_by_array method from MT19937 source code.
mtinit_magic1  equ 1664525
mtinit_magic2  equ 1566083941

; Initial array import seed for Mersenne Twister.
initial_mtseed equ 19650218

; INS to TSV conversion constant.
ins_tsv        equ 1812433253

section .bss

; initial_state is essentially a TSV and index snapshot of a Mersenne Twister
; instance, with the default array import seed (19650218U).

;      mersenne twister instance in rsi   
;   +-------------------------------------+
;   +                                     +
;     RSI   RSI+4               RSI+0x9C4   
;     +---------------------------------+   
;     |mti||mt / tsv (624 * 4 = 9C0)    |   
;     +---------------------------------+   
initial_state resd 4 * N + 4

mt19937.mti equ 0
mt19937.tsv equ 4

section .data
; First one of these is taken from the init_by_array() procedure.
; Overall, they're magic numbers. Avada Kedavra!
mag01:         dd 00000000h, MATRIX_A
rev_magic_1:   dd 00000000h, 40580000h
rev_magic_2:   dd 00000000h, 43400000h
rev_magic_3:   dd 00000000h, 3E500000h
rev_magic_4:   dd 00000000h, 41900000h
rev_magic_5:   dd 00000000h, 3CA00000h

; Stop messages used by the cracker. Nothing fancy.
; "*** STOP" is here to draw the attention.
stopmsg_internal_err:  db "*** STOP: Internal error", 0
stopmsg_no_data:       db "*** STOP: No data", 0
stopmsg_short_in:      db "*** STOP: Short input, try bruteforce", 0
stopmsg_input_long:    db "*** STOP: Input too long", 0

; Formats used for displaying the seed. First one of them will start
; the output, displaying length of the seed. The second one will display
; all the DWORD's of the seed.
format_leading:  db "%lX ", 0
format_interfix: db "%08X", 0

section .code
; ----------------------------------------------------------------------------
; This function has essentially been copied from Mersenne Twister source code.
; I added a few comments regarding assembly itself (because it may be hard to
; read).
; First, check if mti of current MT19973 instance is greater or equal than N
; A twist will happen periodically, after 624 byte-long PRS has been generated
; for the current TSV.
    cmp DWORD [rdi + mt19937.mti], N - 1
    lea rcx, [rdi + mt19937.tsv]
    jle .genrand_skip_twist
; eax is the first iterator of the for loop with signature (kk=0;kk i, r9 => j
		inc rax
		inc r9
		cmp rdx, r9
	; j >= key length condition
		ja .mtinit_keep_j
		xor r9d, r9d
		cmp rax, N
		jne .mtinit_loop1
	; tsv[0] = tsv[n-1]
		mov ecx, DWORD [rdi + N * 4]
		cmp rdx, N
	; i = 1
		mov r10d, 1
		cmovnb rax, rdx
		mov DWORD [rdi + mt19937.tsv], ecx
	; A lovely piece of code regarding loading the key length.
	; Imagine I want to load [rax - 623] effective adress into rcx.
	; Use [rax - N - 1]? Wrong! YASM will merge the constants for you
	; to create a valid x86 instruction. Therefore, there's an invisible
	; parenthesis around (N+1).
		lea rcx, [rax - N + 1]
	; formula's exactly the same like it used to be in the original
	; MT19937 code.
		lea rax, [r10 * 4]
		mov ebx, DWORD [r8 - mt19937.tsv + rax]
		lea r11, [r8 + rax]
		mov eax, ebx
		shr eax, 30
		xor eax, ebx
		mov ebx, DWORD [rsi + r9 * 4]
		imul eax, eax, mtinit_magic1
		xor eax, DWORD [r11]
		add ebx, r9d
	; increment counters.
		inc r9
		inc r10
		add eax, ebx
	; i >= N?
		cmp r10, N - 1
		mov DWORD [r11], eax
		jbe .mtinit_blk1
		mov eax, DWORD [rdi + N * 4]
		mov r10d, 1
		mov DWORD [rdi + 4], eax
	; j >= key?
		cmp rdx, r9
		ja .mtinit_blk2
		xor r9d, r9d
		dec rcx
		jne .mtinit_loop2
		mov edx, N - 1
		lea rax, [r10 * 4]
		mov esi, DWORD [r8 - 4 + rax]
		lea rcx, [r8 + rax]
		mov eax, esi
		shr eax, 30
		xor eax, esi
		imul eax, eax, mtinit_magic2
		xor eax, DWORD [rcx]
		sub eax, r10d
		inc r10
	; i >= N
		cmp r10, N - 1
		mov DWORD [rcx], eax
		jbe .mtinit_blk3
		mov eax, DWORD [rdi + N * 4]
		mov r10d, 1
		mov DWORD [rdi + mt19937.tsv], eax
		dec rdx
		jne .mtinit_loop3
		pop rbx
		mov DWORD [rdi + mt19937.tsv], 0x80000000

; ----------------------------------------------------------------------------
; State to seed conversion. It's gotten a bit hairy, but works just fine. Note
; the unconventional use of ebp (the base pointer) - It won't be used for
; stack adressing.
; Preserve registers. Make a copy of the first parameter.
    push r13
    push r12
    push rbp
    push rbx
    mov rax, rdi
; Reserve 9C0h bytes for the TSV copy, 8 more for other interesting stuff.
    sub rsp, 9C0h + 8
; eax: iterator #1, starts at one. Binary size trick: xor eax, eax, inc eax
; is actually smaller than mov eax, 1 due to instruction size padding!
; For sure the opcode size is larger (B801000000h for mov eax, 1 - padding
; kills), while xor eax, eax & inc eax is just 3 bytes big! (31C040h; it may
; refer to ecx, though, but it doesn't make real difference). The processor
; pipeline will probably do a good job and these two instructions being split
; will make no negative performance impact.
    xor eax, eax
    inc eax
; need to copy memory from the state over to the stack.
; set up the pointers then and perform rep movsd to copy the memory
; in larger chunks (dword vs byte).
    mov ecx, N
    mov ebp, N - 1
    mov rbx, rsi
    mov rsi, rdi
    mov rdi, rsp
    rep movsd
	; An algorithm has been squashed here to reverse the last step
	; of the array_init procedure. This is actually being executed in a loop.
	; if iterator #1 == 1, then tsv[0] = tsv[n-1].
		cmp rax, 1
		jne .seedrev_fixup_skip
	; Effective adress wololo.
		mov edx, DWORD [rsp + (N - 1) * 4]
		mov DWORD [rsp], edx
	; for each element of TSV, xor value of it's value and position by
	; xor of last element and it's rightshifted value by 30, mutliplied
	; by the magic constant #2.
	; It may not sound welcoming.
	; But that's what needs to be done in correspondence with the
	; original algorithm; pay close attention to this snippet from the
	; original MT19937 code, located in the second loop of the init_by_array:
	; mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * mtinit_magic2)) - i;
		lea rdx, [rax * 4]
		mov esi, DWORD [rsp - 4 + rdx]
		lea rcx, [rsp + rdx]
		mov edx, esi
		shr edx, 30
		xor edx, esi
		mov esi, DWORD [rcx]
		imul edx, edx, mtinit_magic2
		add esi, eax
		xor edx, esi
		mov DWORD [rcx], edx
	; decrement `i`
		dec rax
	; wrap rax around to N-1.
		mov edx, N - 1
		cmove rax, rdx
	; next element ...
		dec rbp
		jne .seedrev_deinit_last
	; last step has been reversed, now its time to find the maximum
	; key length.
		mov eax, DWORD [rsp + (N - 1) * 4]
	; has been done before, refer to the original above.
		cmp rbx, N
		mov r13d, N
		cmovnb r13, rbx
	; clear iterator (#2) - pay close attention to the iterators,
	; because their naming might get hairy.
		xor edx, edx
	; load the expected key array length, it has to be done now,
	; because later on rbx is trashed.
		lea rdi, [rbx * 4]
		mov DWORD [rsp], eax
	; trust me, I hate this zwischenzug comming from nowhere, but there's
	; nothing to be done if I want to keep the code tight.
		mov eax, N - 1
		div rbx
		mov r12d, edx
		call malloc
		mov edi, DWORD [initial_state + mt19937.tsv]
	; counter #1 is now ecx.
		mov ecx, 1
		lea r9d, [r13 - 1]
		mov r8, rax
		cmp r13d, ebp
		mov eax, ebp
	; don't exceed kmax.
		jle .revseed_halt
	; very important check for the sake of 2nd array_init block.
	; for k in Z+ and k < N - 1 /k ey length - 1 which one's larger,
	; make a fixup.
		cmp ebp, 1
		movsxd rsi, ecx
		jle .crack_fixup
		cmp r9d, eax
		jle .crack_fixup
	; standard xor mask
		mov edx, DWORD [rsp + rsi * 4]
		mov eax, edx
		shr eax, 30
		xor eax, edx
		imul eax, eax, mtinit_magic1
	; apply the mask to create a seed.
		lea edx, [rcx + 1]
		movsxd rdx, edx
		mov r10d, DWORD [rsp + rdx * 4]
		xor r10d, eax
		xor eax, DWORD [initial_state + mt19937.tsv + rdx * 4]
		sub r10d, eax
	; k - 2 == length?
		lea rdx, [rbp - 2]
		cmp rbx, rdx
	; precalculate iterator #2 + 1
		lea eax, [r12 + 1]
	; miss :/
		jnb .seedrev_size_miss
	; does expected key state at iterator #2 capped at key length
	; equal to seed?
		xor edx, edx
		div rbx
		cmp DWORD [r8 + rdx * 4], r10d
		je .crack_fixup
	; Something bad happened nad they're not equal. Dump out an
	; internal error. If you do something wrong with your implementation,
	; for sure you'll see it a lot.
		mov edi, stopmsg_internal_err
		call puts
	; exit with code 1
		mov edi, 1
		call exit
	; in this case, we set the expected key state at calculated index
	; to the seed. This depends on the value of iterator #2 compared
	; to the maximum key length.
		cmp rbx, rax
		ja .seedrev_do_iterator
	; set [0]
		mov DWORD [r8], r10d
		jmp .crack_fixup
		movsxd rax, r12d
	; set [iterator #2]
		mov DWORD [r8 + mt19937.tsv + rax * 4], r10d
	; as above, simple state reversal, nearly ctrl+c & ctrl+v of above.
		dec ecx
		movsxd rax, ecx
		mov edx, DWORD [rsp + rax * 4]
		mov eax, edx
		shr eax, 30
		xor eax, edx
		mov edx, DWORD [rsp + rsi * 4]
		imul eax, eax, mtinit_magic1
		sub edx, r12d
		xor eax, edx
		mov DWORD [rsp + rsi * 4], eax
	; iterator decreasing is a bit scattered around, but the goal is to
	; keep the code relatively dense.
		dec r12d
	; for iterator #2 == 0, reset iterator #1, and pass around seed uint32
	; to the final array.
		test ecx, ecx
		jne .reset_j
		mov DWORD [rsp], edi
		mov ecx, N - 1
		test r12d, r12d
		jns .loop_again
		lea r12d, [rbx - 1]
	; adjust the pointer to the next location and jump again.
		inc rbp
		jmp .crack_loop
	; stack cleanup, mostly.
	; and return value in rax, obviously.
		add rsp, 9C0h + 8
		mov rax, r8
		pop rbx
		pop rbp
		pop r12
		pop r13

; ----------------------------------------------------------------------------
; The constants below apply ONLY to the main function.
; seed buffer's stack offset.
seed_buf    equ 0x3100

; temporary (work) mersenne twister instance stack offset.
mersenne_bp  equ 0x2740

; the "target" size - main reversal array.
target_length equ 12552

; internal seed generator's temporary states.
zerogen_temp  equ 7548
zerogen_temp2 equ 5048
zerogen_temp3 equ 2548

; An interesting variable - it's used for various calculations.
; for example, it stores seed length, but is used inside many more
; computations regardin seed regarding later on, so I'll treat this
; like an "additonal", slow and temporary register.
gen_temp equ 12560
temp_keylen equ 12568

; Final key storage for init_by_array.
final_key equ 0x3318

; ----------------------------------------------------------------------------
; Entry point for the cracker.
; TODO, directed mainly to the reader: You may want to make a library or
; something out of this program. This function is probably the most complex,
; taking out around 1/2 of the code' volume. There are at least two algorithms
; squashed into this one. First of all, the stack allocation amount is
; enormous.
; This prologue to a function might seem odd. As mentioned before, a lot of
; operations are done in parallel, therefore it may look hairy.
	push rbp
	mov rbp, rsp
	push r15
	push r14
; clear eax and set up ecx - we're setting up a buffer on the stack.
; as edi is the destination index, we'll save it so it's not wrecked
; by rep stosd.
	mov r8d, edi
	xor eax, eax
	mov ecx, N
; load the seed buffer, as we will rep stosd it with zeros.
	lea rdi, [rbp - seed_buf]
	push r13
	push r12
	push rbx
	sub rsp, 12536
; argc == 2?
	cmp r8d, 2
	rep stosd
; preload the no_data message
	mov edi, stopmsg_no_data
	jne .main_error
	lea r14, [rbp - seed_buf]
; first, we need to initialize the initial MT19937 state
; with the default values.
	mov edx, 1
; first byte of pre-twist TSV is always the seed.
	mov DWORD [initial_state + mt19937.tsv], initial_mtseed
; it's nearly the exact same procedure we discussed above.
; so simply the code will follow.
		mov ecx, DWORD [initial_state + rdx * 4]
		mov eax, ecx
		shr eax, 30
		xor eax, ecx
		imul eax, eax, ins_tsv
		add eax, edx
		mov DWORD [initial_state + mt19937.tsv + rdx * 4], eax
	; we want to fill the entire TSV, therefore loop N times.
		inc rdx
		cmp rdx, N
		jne .generate_state
	; r15 = ptr argv[1], ptr is 2B long, so we get 2nd element.
		mov r15, QWORD [rsi + 8]
		mov QWORD [rbp - gen_temp], rsp
		mov DWORD [initial_state + mt19937.mti], N
	; load the argument, check the length of input string.
		mov rdi, r15
		call strlen
	; less than 4 bytes long?
		cmp rax, 3
		ja .input_ok
	; nope, better load the error message.
		mov edi, stopmsg_short_in
	; and that's where the execution falls into, when an error occurs.
	; write out the error message in edi and exit outta here.
		call puts
		mov edi, 1
		call exit
	; seed length = M + input_length * 2. It's a fantastic property
	; of this generator.
		lea r13, [rax + rax]
		lea rbx, [r13 + M]
	; first, let's check may it be the case that input is too long
		mov edi, stopmsg_input_long
		cmp rbx, N - 3
		ja .main_error
	; with couple of input sanity checks over, we're heating up the cracker.
	; first, let's load up the current seed to a mersenne twister instance.
		lea r12, [rbp - mersenne_bp]
		mov rdx, rbx
		mov rsi, r14
		mov QWORD [rbp - target_length], rax
		mov rdi, r12
		call init_by_array
	; seed generation stub, to be polished up by the mt_reverse_seed
	; procedure first, make two copies of the state.
		add r13, M - 1
		lea rdi, [rbp - zerogen_temp]
		mov ecx, N + 1
		mov rsi, r12
		rep movsd
		lea rdi, [rbp - zerogen_temp2]
		mov ecx, N + 1
		lea rsi, [rbp - zerogen_temp]
		rep movsd
	; generate a random number fron the first state.
		lea rdi, [rbp - zerogen_temp2]
		call genrand_int32
		mov r8, QWORD [rbp - target_length]
	; xor one state and another with M offset on the 2nd.
		mov eax, M
		cmp rax, r13
		jnb .seedgen_im_done
	; Halloween's effective adresses incoming. The same problem arises
	; here as the one with effective adresses mentioned above, so you possibly
	; need to wrap your head around signs.
		mov edx, DWORD [rbp - zerogen_temp + 4 + rax * 4]
		xor edx, DWORD [rbp - zerogen_temp2 - 4 * M + 4 + rax * 4]
		mov DWORD [rbp - zerogen_temp + 4 + rax * 4], edx
	; pass around
		inc rax
		jmp .seedgen_im_loop
	; done. now, generate seed from r2 state.
		mov rsi, rbx
		mov QWORD [rbp - temp_keylen], r8
		lea rdi, [rbp - zerogen_temp + 4]
		call mt_reverse_seed
	; now, let's initialize state 3 with the key supplied.
		lea r13, [rbp - zerogen_temp3]
		mov rdx, rbx
		mov rsi, rax
		mov rdi, r13
		mov QWORD [rbp - target_length], rax
		call init_by_array
	; we don't need 3rd key anymore, free the memory for it.
		mov r9, QWORD [rbp - target_length]
		mov rdi, r9
		call free
	; copy the 3rd instance into the current, shared MT state.
		mov ecx, N + 1
		mov rdi, r12
		mov rsi, r13
		rep movsd
	; Floating-point trickery will emerge soon.
		movsd xmm1, QWORD [rev_magic_2]
		movsd xmm2, QWORD [rev_magic_3]
		mov r8, QWORD [rbp - temp_keylen]
		xor edx, edx
	; allocate enough stack space for the target buffer.
		lea rax, [r8 + 15]
		and rax, -16
		sub rsp, rax
	; allocate target2 buffer, twice as big.
		lea rax, [15 + r8 * 8]
		mov rdi, rsp
		shr rax, 4
		sal rax, 4
		sub rsp, rax
		mov rsi, rsp
	; finally, allocate rand3 buffer, twice as big aswell.
		sub rsp, rax
		mov rcx, rsp
		mov r9b, BYTE [r15 + rdx]
	; map an ASCII character to it's corresponding printable
	; character vector equivalent. For normal characters, it's
	; usually the value minus 32 (ascii space, ' '). For newline
	; though, code 95, therefore there are exactly 96 distinct
	; values that can be held inside of a printable vector.
		mov al, 95
	; 10 -> ascii code for the newline.
		cmp r9b, 10
		je .skip_nolf
		lea eax, [r9 - ' ']
	; reversal step two: reverse the floating point trickery.
	; the values have been loaded before, so it shouldn't be a problem.
		mov BYTE [rdi + rdx], al
	; x + 1 / 96, why 96? see above.
		movsx eax, al
		mov r11d, 127
		inc eax
	; multiply by 2^53 - 1 (the mantissa size), multiply by 2^-26 (double
	; extended precision).
		cvtsi2sd xmm0, eax
		divsd xmm0, QWORD [rev_magic_1]
		mulsd xmm0, xmm1
		mulsd xmm0, xmm2
		cvttsd2si rax, xmm0
	; subtract 0x20, shift the result five and apply FE000000h mask
		sub eax, 32
		sal eax, 5
		and eax, 0xfe000000
		mov r9d, eax
	; remember: 2 * i (as a single dword maps to two dwords in side buffers).
		mov DWORD [rsi + rdx * 8], eax
	; standard untempering code we discussed above.
		shr r9d, 18
		xor eax, r9d
		sal r9d, 15
		and r9d, 0x2FC60000
		xor eax, r9d
		mov r9d, 4
		mov r10d, eax
		and r10d, r11d
		sal r11d, 7
		sal r10d, 7
		and r10d, 0x9D2C5680
		xor eax, r10d
		dec r9
		jne .untemper
		mov r10d, eax
		shr r10d, 11
		and r10d, 2096128
		xor eax, r10d
		mov r10d, eax
		shr r10d, 11
		and r10d, 1023
		xor eax, r10d
	; fill in the second buffer.
		mov DWORD [rcx + rdx * 8], eax
	; clear next two cells.
		mov DWORD [rsi + 4 + rdx * 8], 0
		mov DWORD [rcx + 4 + rdx * 8], 0
	; Manage the loop.
		lea rax, [rdx + 1]
		cmp r8, rax
		mov QWORD [rbp - target_length], rax
		je .generator_step2
		mov rdx, QWORD [rbp - target_length]
		jmp .rafinate
	; make a mersenne twister state out of 2nd buffer.
		xor eax, eax
		mov esi, DWORD [r12 + 4 * M + 4 + rax * 8]
		xor esi, DWORD [rcx + rax * 8]
		mov DWORD [r12 + 4 * M + 4 + rax * 8], esi
		mov rsi, rax
		inc rax
		cmp rdx, rsi
		jne .state_filler
	; done filling the state 0, now as we regain the key
	; from it, it is actually our final, final seed!
	; load the #1 => state, #2 => length.
		mov rsi, rbx
		mov QWORD [rbp - temp_keylen], r9
		lea rdi, [rbp - mersenne_bp + mt19937.tsv]
		call mt_reverse_seed
	; copy the key over to the seed buffer.
		lea rcx, [rbx * 4]
		mov rdi, r14
		mov rsi, rax
		mov ecx, ecx
		rep movsb
	; free the old buffer.
		mov rdi, rax
		call free
	; last, final bit of the code: verify the seed.
	; first, create the state.
		mov rdx, rbx
		mov rsi, r14
		mov rdi, r13
		call init_by_array
		mov r9, QWORD [rbp - temp_keylen]
		movsd xmm1, QWORD [rev_magic_4]
	; loop until we hit NUL in the input string (the end).
		cmp BYTE [r15 + r9], 0
		je .verify_quit
	; randomize two numbers.
		mov rdi, r13
		call genrand_int32
		mov r8d, eax
		call genrand_int32
	; shift first right by 5, second right by 6.
		shr r8d, 5
		shr eax, 6
	; store, calculate, load back.
		cvtsi2sd xmm0, r8d
		cvtsi2sd xmm2, eax
		mulsd xmm0, xmm1
		addsd xmm0, xmm2
		mulsd xmm0, QWORD [rev_magic_5]
		mulsd xmm0, QWORD [rev_magic_1]
		cvttsd2si ecx, xmm0
	; printable vector conversions.
		mov dl, BYTE [r15 + r9]
		mov al, 95
		cmp dl, 10
		je .wrongspot
		lea eax, [rdx - ' ']
		movsx eax, al
		cmp ecx, eax
		je .main_loop_again
		cmp QWORD [rbp - target_length], r9
		je .display_result
		mov edi, stopmsg_internal_err
		jmp .main_error
		inc r9
		jmp .verify_loop
		mov rsp, QWORD [rbp - gen_temp]
		mov rsi, rbx
		mov edi, format_leading
		xor eax, eax
		call printf
		test rbx, rbx
		je .display_finished
		dec rbx
		mov edi, format_interfix
		xor eax, eax
		mov esi, DWORD [r14 + mt19937.tsv + rbx * 4]
		call printf
		jmp .display_seed
		lea rsp, [rbp - 40]
		xor eax, eax
		pop rbx
		pop r12
		pop r13
		pop r14
		pop r15
		pop rbp


--[ Appendix A - Sources

[1] -
[2] -
[3] -
[4] -
[5] -
[6] -

--[ Appendix B - Paleologoi method test cases
Test case A: "HelloWorld"
Test case B: "!@#$%^&*()"
Test case C: "VeryLongTextBewareVeryVeryLong"

A ----------------------------------------------------------------------------
1A1 00000000F7E71E877991EAC19B1633118E3EB38705206F3F037C9078CA5C5FC2574CD6D776
8EBE0CB2C0502CF89265D6CF [pad out with zeros to 1A1h]

B ----------------------------------------------------------------------------
1A1 000000003B451CAEC15B4A1F7AEC61A2FDB04511A609F6A6BA24BB12BD71E82FA7D8EC015E

C ----------------------------------------------------------------------------
1C9 000000007EBA24439AC90F8B94D96D1C71378E90157DD5FA367EB2D1BF8ED3BF1CBC555176