Mersenne Twister

Introduction

The Mersenne Twister is a general-purpose pseudorandom number generator (PRNG) developed in 1997 by Makoto Matsumoto and Takuji Nishimura. Its name derives from the fact that its period length is chosen to be a Mersenne prime.

The Mersenne prime is the prime number that is one less than a power of two.
That is, it a prime number of the form $M_n = 2^n -1$ for some integer $n$.
The expoenents $n$ which give Mersenne primes are $2,3,5,6,13,17,19,31, ...$
and the resulting Mersenne primes are $3,7,31,127,8191,131071,524287,2147483647,...$
(https://en.m.wikipedia.org/wiki/Mersenne_prime)

The most commonly used version of the Mersenne Twister algorithm is based on the Mersenne prime $M_{19937}=2^{19937}-1$. The standard implementation of that, MT19937, uses a 32-bit word length. There is another implementation that uses a 64-bit word length, MT19937-64; it generates a different sequence.

Algorithmic detail

For a w-bit word length, the Mersenne Twister generates integers in the range $[0,2^w -1]$.
The Mersenne Twister algorithm is based on a matrix linear recurrence over a finite binary field $\textbf {F}_{2}$.

In mathematics, a recurrence relation is an equation according to which the $n$th term of a sequence of numbers is equal to some combination of the previous terms.
In linear recurrences, the $n$th term is equated to a linear function of the $k$ previous terms. A famous example is the recurrence for the Fibonacci numbers,

$\space F_n = F_{n-1} + F_{n-2}$
(https://en.m.wikipedia.org/wiki/Recurrence_relation)

The algorithm is a twisted generalised feedback shift register (twisted GFSR, or TGFSR).
The general algorithm is characterized by the following quantities:

• $w$: word size (in number of bits)
• $n$: degree of recurrence
• $m$: middle word, an offset used in the recurrence relation defining the series $x$,
  ($1\leq m<n$),
• $r$: seperation point of one word, or the number of bits of the lower bitmask,
  ($0\leq r \leq w-1$)
• $a$: coefficients of the rational normal form twist matrix
• $b, c$: TGFSR(R) tempering bitmasks
• $s, t$: TGFSR(R) tempering bit shifts
• $u,d,l$: additional Mersenne Twister tempering bit shifts/masks

with the restriction that $2^{nw-r}-1$ is a Mersenne prime.

For example, $(w,n,m,r)=(32,624,397,31)$, $nw-r = 624\times 32 - 31 = 19937$,
The $2^{19937}-1$ is Mersenne prime. This is the case of the coefficients for MT19937. You may make sense after reading the rest of the algorithmic details.

The series $x$ is defined as a series of w-bit quantities with the recurrence relation:

${x_k^u}$ : the upper $w-r$ bits of $x_k$
${x_{k+1}^l}$ : the lower $r$ bits of $x_{k+1}$
$A$ : the twist transformation A, defined in rational normal form.

$A$ defined in rational normal form as:

${\displaystyle A={\begin{pmatrix}0&I_{w-1}\\a_{w-1}&(a_{w-2},\ldots ,a_{0})\end{pmatrix}}}$

With $I_{w-1}$ as the $(w-1)(w-1)$ identity matrix. The rational normal form has the benefit that multiplication by $A$ can be efficiently expressed as: (remember that here matrix multiplication is being done in ${\displaystyle {\textbf {F}}_{2}}$, and therefore bitwise XOR takes the place of addition)

${\displaystyle {\boldsymbol {x}}A={\begin{cases}{\boldsymbol {x}}\gg 1&x_{0}=0\\({\boldsymbol {x}}\gg 1)\oplus {\boldsymbol {a}}&x_{0}=1\end{cases}}}$

Where $x_0$ is the lowest order bit of $x$.

As with A, we choose a tempering transform to be easily computable, and so do not actually construct $T$ itself. The tempering is defined in the case of Mersenne Twister as (We can call it as Temper Function):

Where $x$ is the next value from the series, $y$ is a temporary intermediate value, and $z$ is the value returned from the algorithm, with << and >> as the bitwise left and right shifts, and & as the bitwise AND. The first and last transforms are added in order to improve lower-bit equidistribution. From the property of TGFSR, ${\displaystyle s+t\geq \left\lfloor {\frac {w}{2}}\right\rfloor -1}$ is required to reach the upper bound of equidistribution for the upper bits.

The coefficients for MT19937 are:

${\displaystyle {\begin{aligned}(w,n,m,r)&=(32,624,397,31)\\a&={\textrm {9908B0DF}}_{16}\\(u,d)&=(11,{\textrm {FFFFFFFF}}_{16})\\(s,b)&=(7,{\textrm {9D2C5680}}_{16})\\(t,c)&=(15,{\textrm {EFC60000}}_{16})\\l&=18\\\end{aligned}}}$

Note that 32-bit implementations of the Mersenne Twister generally have $d$= FFFFFFFF$_{16}$. As a result, the $d$ is occasionally omitted from the algorithm description, since the bitwise and with $d$ in that case has no effect.

Initialization

The state needed for a Mersenne Twister implementation is an array of $n$ values of $w$ bits each. To initialize the array, a $w$-bit seed value is used to supply $x_0$ through $x_{n-1}$ by setting $x_0$ to the seed value and thereafter setting

from $i$ from $1$ to $n-1$.

• The first value the algorithm then generates is based on $x_n$, not on $x_0$.
• The constant $f$ forms another parameter to the generator, though not part of the algorithm proper.
• The value for $f$ for MT19937 is 1812433253.

Pseudocode

The following pseudocode implements the general Mersenne Twister algorithm. The constants $w,n,m,r,a,u,d,s,b,t,c,l,$ and $f$ are as in the algorithm description above. It is assumed that int represents a type sufficient to hold values with $w$ bits:

 // Create a length n array to store the state of the generator
 int[0..n-1] MT
 int index := n+1
 const int lower_mask = (1 << r) - 1 // That is, the binary number of r 1's
 const int upper_mask = lowest w bits of (not lower_mask)
 
 // Initialize the generator from a seed
 function seed_mt(int seed) {
     index := n
     MT[0] := seed
     for i from 1 to (n - 1) { // loop over each element
         MT[i] := lowest w bits of (f * (MT[i-1] xor (MT[i-1] >> (w-2))) + i)
     }
 }
 
 // Extract a tempered value based on MT[index]
 // calling twist() every n numbers
 function extract_number() {
     if index >= n {
         if index > n {
           error "Generator was never seeded"
           // Alternatively, seed with constant value; 5489 is used in reference C code[54]
         }
         twist()
     }
 
     int y := MT[index]
     y := y xor ((y >> u) and d)
     y := y xor ((y << s) and b)
     y := y xor ((y << t) and c)
     y := y xor (y >> l)
 
     index := index + 1
     return lowest w bits of (y)
 }
 
 // Generate the next n values from the series x_i 
 function twist() {
     for i from 0 to (n-1) {
         int x := (MT[i] and upper_mask)
                   | (MT[(i+1) mod n] and lower_mask)
         int xA := x >> 1
         if (x mod 2) != 0 { // lowest bit of x is 1
             xA := xA xor a
         }
         MT[i] := MT[(i + m) mod n] xor xA
     }
     index := 0
 }

random module (Python)

/* Period parameters -- These are all magic.  Don't change. */
#define N 624
#define M 397
#define MATRIX_A 0x9908b0dfU    /* constant vector a */
#define UPPER_MASK 0x80000000U  /* most significant w-r bits */
#define LOWER_MASK 0x7fffffffU  /* least significant r bits */

static uint32_t
genrand_uint32(RandomObject *self)
{
    uint32_t y;
    static const uint32_t mag01[2] = {0x0U, MATRIX_A};
    /* mag01[x] = x * MATRIX_A  for x=0,1 */
    uint32_t *mt;

    mt = self->state;
    if (self->index >= N) { /* generate N words at one time */
        int kk;

        for (kk=0;kk<N-M;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1U];
        }
        for (;kk<N-1;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1U];
        }
        y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1U];

        self->index = 0;
    }

    y = mt[self->index++];
    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680U;
    y ^= (y << 15) & 0xefc60000U;
    y ^= (y >> 18);
    return y;
}

(Reference: https://rbtree.blog/posts/2021-05-18-breaking-python-random-module/)

Predicting the random number (Python random.getrandbits(32n))

Idea

After observing $n$ numbers, it is possible to predict all future iterations by reconstructing the internal state of the RNG, since the tempering funciton used to produce outputs is bijective and invertible (bijective means One-to-One Correspondence).
Inverting the temper transform involves applyting the inverse of each opration of the tempering function in reverse order. Examine the code segment from the tempering function:

y = y ^ ((y >> MT19937.u) & MT19937.d)
y = y ^ ((y << MT19937.s) & MT19937.b)
y = y ^ ((y << MT19937.t) & MT19937.c)
y = y ^ (y >> MT19937.l)

Note that there are essentially two types of operations:

• Shift left + bitwise and
• Shift right + bitwise and

How to "Untemper" the "Tempering Function"?

We can untemper the tempering function with the following python code:

TemperingMaskB = 0x9d2c5680
TemperingMaskC = 0xefc60000

def untemper(y):
    y = undoTemperShiftL(y)
    y = undoTemperShiftT(y)
    y = undoTemperShiftS(y)
    y = undoTemperShiftU(y)
    return y

def undoTemperShiftL(y):
    last14 = y >> 18
    final = y ^ last14
    return final

def undoTemperShiftT(y):
    first17 = y << 15
    final = y ^ (first17 & TemperingMaskC)
    return final

def undoTemperShiftS(y):
    a = y << 7
    b = y ^ (a & TemperingMaskB)
    c = b << 7
    d = y ^ (c & TemperingMaskB)
    e = d << 7
    f = y ^ (e & TemperingMaskB)
    g = f << 7
    h = y ^ (g & TemperingMaskB)
    i = h << 7
    final = y ^ (i & TemperingMaskB)
    return final

def undoTemperShiftU(y):
    a = y >> 11
    b = y ^ a
    c = b >> 11
    final = y ^ c
    return final

We can untemper the tempering function, so we can recover the MT19937's state with 624 * 32-bit outputs.

MAPNA CTF Write-up : What next II?

chall.py

#!/usr/bin/env python3

from random import *
from Crypto.Util.number import *
from flag import flag

def encrypt(msg, KEY):
	m = bytes_to_long(msg)
	c = KEY ^ m
	return c

n = 80
TMP = [getrandbits(256) * _ ** 2 for _ in range(n)]
KEY = sum([getrandbits(256 >> _) for _ in range(8)]) 

enc = encrypt(flag, KEY)

print(f'TMP = {TMP}')
print(f'KEY = {KEY}')
print(f'enc = {enc}')

#TMP = [0, 60532113298156934035006892408508955361282411773999112364347341111075018147927, 389708033651020865401865717693397865196213972164600460902422823183461779915980, 405918065202512971659130608346843374237984902589139232574420604120059844720341, 1221288278415504784467034784431436409217396366988324269872668238978249045586368, 227272449199630828507165833400505281743840056074337728659380026370174597983400, 3253503829229933909142928710502222745989372185283055446591180092486412602783216, 5285988746830110954075248573612981420829816533804399404046882938020472042330356, 1595336926944568705525401229738700126737605961193041889427425025694023495226176, 7954983836536199412561303342870946300319308569704526681942922892057412417369996, 9131160911707622814886835054526857850430982962993746463098999466544684215014000, 7533615981375704965377803926757920571133747559444638616597692539324665788824241, 9066823514420452679519089047747738557989264923523328666138044339979172532091952, 11067455968068371535244972547693443476921719558645991175617294899803940399861323, 14537042287558789972327728985738890609505033466725608088977070967810362118279248, 4572250646126446008858673089127752592787335839144590539404665629413086318239650, 6294362797378922374391238457327978545276595686984712745478781562202157935775488, 22747367842710135893711619452307079245750111941624369856170309106764880998100552, 6004893915710283480070189414407284168050988366555745204074130859740178577433240, 14420752900418475271133573248938786225809597358248108049760284685159047602036537, 43733009974069364671572839996339051940609184658654624940598489171524524051944400, 35346194693613025068395009821809884943769752588359988505793537720962714260019869, 42204169462513802238599356946318680734527685184414356760365290489529820960713072, 34277378263896547381266820799512178423239236243790865361707633583497481357796407, 65716310119362366398237218525711748744052085839683547702975404773566674635748352, 46557817276176359993118228055060795747091243514590105677103910660112788974583750, 77490786359937960192983922284789298329689351038928181926278354279011358030727124, 80111990003818834469282875276984278230143118837645016537448310618261479083651342, 20554557048628019672240583641369145446540900712224309311213526066135949044952288, 62735818615066536453205944582471026825278180907531123883210362947117955616343781, 86042719783890082289653687251665836736491344225760521302063306208331002685576500, 25965698487671814117818570753889366721907386924362900403011501627358460499758383, 29616377817002001833630895361629451907964508596441826676791174072122929285049344, 15021399892362753107059884462124333866295538287397369553705410328403621774185468, 38002604304046319679742306015002655608233191413179528560874731009946042988120788, 93295366307461634335632781504982997626366942447637302439067556300965151557831725, 13540230203788528048897000123546822994874145971630139618336417120723676174022384, 154432198666672358575141914680506005090971687803151597762263520020713308780579072, 72136447292935153078321891268785033320056922245403740454889157780753773717242568, 25501852421215926138677841658578129717118066368151623403551273037829983575243468, 126735578787059666358271681647457626985119387894943043206239792071598867033556800, 135202944925842633454294137881609034393280829104975826296437659832444402212706990, 195878634803984461306574869979621981219794907747012161075921193902109987239350696, 70016262426074427215170249788098050659024805306136436354383469618536112786361350, 35956258331474238072248600117735641962702369830606009799455005594969570110652976, 22225110718496125427125444008161845696087660990666988086936919846739655848747525, 27548874118316168690466237353230253832267098824834641381166573208182433313572936, 217350749041695488338708373584952864553819378993764330831653495907756867001916100, 257655749972831097290040240403045642767794308639832322802465135822003512301701120, 170931799252374463455850569878339599585582089254513276315581340035784063404547904, 260648666226967018693658250893274370482164362954223893135614467834502818278817500, 69425639907308137984060966310312800675576800616943121851698019398372874074587564, 38272797691322675978111710027833013466477209475584360707344650868692232767605712, 159989233909295381868776328891896676159494718709642790902586750185703386017519100, 239424076217975267533547688379482794244638593887104216992730670874367591889686424, 235805166260230600224517436738096467578276265139558424271706458619605152151155650, 312887850933221623827051251636459958804378796969233372438708909260471396708839360, 226254410804533566347737443581029620895018482953889083109343308899334155214465084, 75663356945666060728297569858199894519238029780108571803169998187745851675033696, 379521198853533961681034095706543224338730654829393858931702778389925326037905581, 146969137746310211928872994682693200202368153046275429574482720738790962130698000, 294260825765970965744028560390675570627618373545459966200549616640279283196332026, 319516693693602451939925738770832547195167488538421484010981799971938667101170272, 235996689233669489969452603688581556879686306558426802897567227857894956933720385, 129860515531400644974201481565448922647210002409167735625695108262182647544782848, 434775250558913676954052533315009488640533958618010407554959841056206485055286800, 22149580084411886515787074680813749427656731151235741580693077660337965563693340, 250909616829332329061530688103059354065323867429954924090541815760594873142372389, 190341994069073757182537956898692121864681766192223013320579410693514741018663328, 498585070302128781878557564834342148816012866139626477296471773760922822044892275, 263835635996152386059834449296099627577713122650362830498873071118489986876211700, 225673582284037816919955555063840997388361787112308169031986640074367056949780747, 361331112554037421979550439774599874333938415297694314983681794489970792139813248, 254546085100670719262378937737022676839283545191763458089424319101240909887973785, 253610597769560898884657084492335380622121458721155827380866680741694312733007816, 457274233985553849774588573500169926255994068617887370590713102886816853234873125, 449778455880514807591245873496025212715825137347886177910517238904962733456694256, 401484248501670039446475341305100595322092268787582033086127175618422362454931911, 22016053572627515851711195096973390151818785168234961407013202935121714403513020, 199223592692197859565380631569896354958045929491349287395617253114895842147327801]
#KEY = 23226475334448992634882677537728533150528705952262010830460862502359965393545
#enc = 2290064970177041546889165766737348623235283630135906565145883208626788551598431732

solve
The Python's "random.getrandbits" uses the Mersenne Twister algorithm. So if we know the MT algorithm's output greater than 32 * 624 bits, We can calculate the MT19937's state.

In this problem, since $32\times624=19968$ is less than $80\times256=20480$, we can calculate the MT19937's state with "untempering" the "tempering function". After replacing the recovered MT19937's state with the current random module's state, we can easily predict(or make) the next sequences.

If we use the "untempering function", we can untemper the tempering function. Then we can get the recovered state. But instead of coding the untempering function, we can use the extend_mt19937_predictor module.

Following code is the exploit code using the extend_mt19937_predictor module :

import random
from extend_mt19937_predictor import ExtendMT19937Predictor
from random import *
from Crypto.Util.number import *

predictor = ExtendMT19937Predictor()

TMP = [0, 60532113298156934035006892408508955361282411773999112364347341111075018147927, 389708033651020865401865717693397865196213972164600460902422823183461779915980, 405918065202512971659130608346843374237984902589139232574420604120059844720341, 1221288278415504784467034784431436409217396366988324269872668238978249045586368, 227272449199630828507165833400505281743840056074337728659380026370174597983400, 3253503829229933909142928710502222745989372185283055446591180092486412602783216, 5285988746830110954075248573612981420829816533804399404046882938020472042330356, 1595336926944568705525401229738700126737605961193041889427425025694023495226176, 7954983836536199412561303342870946300319308569704526681942922892057412417369996, 9131160911707622814886835054526857850430982962993746463098999466544684215014000, 7533615981375704965377803926757920571133747559444638616597692539324665788824241, 9066823514420452679519089047747738557989264923523328666138044339979172532091952, 11067455968068371535244972547693443476921719558645991175617294899803940399861323, 14537042287558789972327728985738890609505033466725608088977070967810362118279248, 4572250646126446008858673089127752592787335839144590539404665629413086318239650, 6294362797378922374391238457327978545276595686984712745478781562202157935775488, 22747367842710135893711619452307079245750111941624369856170309106764880998100552, 6004893915710283480070189414407284168050988366555745204074130859740178577433240, 14420752900418475271133573248938786225809597358248108049760284685159047602036537, 43733009974069364671572839996339051940609184658654624940598489171524524051944400, 35346194693613025068395009821809884943769752588359988505793537720962714260019869, 42204169462513802238599356946318680734527685184414356760365290489529820960713072, 34277378263896547381266820799512178423239236243790865361707633583497481357796407, 65716310119362366398237218525711748744052085839683547702975404773566674635748352, 46557817276176359993118228055060795747091243514590105677103910660112788974583750, 77490786359937960192983922284789298329689351038928181926278354279011358030727124, 80111990003818834469282875276984278230143118837645016537448310618261479083651342, 20554557048628019672240583641369145446540900712224309311213526066135949044952288, 62735818615066536453205944582471026825278180907531123883210362947117955616343781, 86042719783890082289653687251665836736491344225760521302063306208331002685576500, 25965698487671814117818570753889366721907386924362900403011501627358460499758383, 29616377817002001833630895361629451907964508596441826676791174072122929285049344, 15021399892362753107059884462124333866295538287397369553705410328403621774185468, 38002604304046319679742306015002655608233191413179528560874731009946042988120788, 93295366307461634335632781504982997626366942447637302439067556300965151557831725, 13540230203788528048897000123546822994874145971630139618336417120723676174022384, 154432198666672358575141914680506005090971687803151597762263520020713308780579072, 72136447292935153078321891268785033320056922245403740454889157780753773717242568, 25501852421215926138677841658578129717118066368151623403551273037829983575243468, 126735578787059666358271681647457626985119387894943043206239792071598867033556800, 135202944925842633454294137881609034393280829104975826296437659832444402212706990, 195878634803984461306574869979621981219794907747012161075921193902109987239350696, 70016262426074427215170249788098050659024805306136436354383469618536112786361350, 35956258331474238072248600117735641962702369830606009799455005594969570110652976, 22225110718496125427125444008161845696087660990666988086936919846739655848747525, 27548874118316168690466237353230253832267098824834641381166573208182433313572936, 217350749041695488338708373584952864553819378993764330831653495907756867001916100, 257655749972831097290040240403045642767794308639832322802465135822003512301701120, 170931799252374463455850569878339599585582089254513276315581340035784063404547904, 260648666226967018693658250893274370482164362954223893135614467834502818278817500, 69425639907308137984060966310312800675576800616943121851698019398372874074587564, 38272797691322675978111710027833013466477209475584360707344650868692232767605712, 159989233909295381868776328891896676159494718709642790902586750185703386017519100, 239424076217975267533547688379482794244638593887104216992730670874367591889686424, 235805166260230600224517436738096467578276265139558424271706458619605152151155650, 312887850933221623827051251636459958804378796969233372438708909260471396708839360, 226254410804533566347737443581029620895018482953889083109343308899334155214465084, 75663356945666060728297569858199894519238029780108571803169998187745851675033696, 379521198853533961681034095706543224338730654829393858931702778389925326037905581, 146969137746310211928872994682693200202368153046275429574482720738790962130698000, 294260825765970965744028560390675570627618373545459966200549616640279283196332026, 319516693693602451939925738770832547195167488538421484010981799971938667101170272, 235996689233669489969452603688581556879686306558426802897567227857894956933720385, 129860515531400644974201481565448922647210002409167735625695108262182647544782848, 434775250558913676954052533315009488640533958618010407554959841056206485055286800, 22149580084411886515787074680813749427656731151235741580693077660337965563693340, 250909616829332329061530688103059354065323867429954924090541815760594873142372389, 190341994069073757182537956898692121864681766192223013320579410693514741018663328, 498585070302128781878557564834342148816012866139626477296471773760922822044892275, 263835635996152386059834449296099627577713122650362830498873071118489986876211700, 225673582284037816919955555063840997388361787112308169031986640074367056949780747, 361331112554037421979550439774599874333938415297694314983681794489970792139813248, 254546085100670719262378937737022676839283545191763458089424319101240909887973785, 253610597769560898884657084492335380622121458721155827380866680741694312733007816, 457274233985553849774588573500169926255994068617887370590713102886816853234873125, 449778455880514807591245873496025212715825137347886177910517238904962733456694256, 401484248501670039446475341305100595322092268787582033086127175618422362454931911, 22016053572627515851711195096973390151818785168234961407013202935121714403513020, 199223592692197859565380631569896354958045929491349287395617253114895842147327801]
KEY = 23226475334448992634882677537728533150528705952262010830460862502359965393545
enc = 2290064970177041546889165766737348623235283630135906565145883208626788551598431732

TMP = [ t//((i+1)**2) for i, t in enumerate(TMP[1:])]
print(TMP)
for T in TMP:
    predictor.setrandbits(T, 256)
    
    
KEY = sum([predictor.predict_getrandbits(256 >> _) for _ in range(8)]) 

def encrypt(msg, KEY):
	m = msg
	c = KEY ^ m
	return c

print(long_to_bytes(encrypt(enc,KEY)))
b'MAPNA{R_U_MT19937_PRNG_Predictor?}'

참고: https://rbtree.blog/posts/2021-05-18-breaking-python-random-module/
https://en.wikipedia.org/wiki/Mersenne_Twister
https://github.com/NonupleBroken/ExtendMT19937Predictor
https://kanzya.github.io/posts/MAPNACTF/
https://github.com/anneouyang/MT19937