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 ]=--------------------=]
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 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
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.
--[ 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
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 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:
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
00001571,4D98EE96,AF25F095,AFD9BA96,6FCBD068,2CD06A72,384F0100,85B46507
295E8801,0D1B316E,7B305E70,BDB6BBA0,1CEFB8F6,8B499F1B,3FDF25EB,CBC1B8C6
38B252C9,DC273A5E,AE40CBC3,6AE1AC38,B1C27391,5E964414,744B195F,6BC6502D
67592D74,19B58C42,FA7DA824,1FA1367E,6635EDD2,B451BF5C,C73BCE34,7374CAD2
9D63F05F,629A99D2,DC159B61,FC5BBFCD,D079EA6A,336AAC92,AF6E37C0,90A0D1B1
5F9086C7,438F2247,B8B9FBC8,83A570DD,A3C5DF27,377ED6C6,2D64B24C,BC39042B
2ED7955D,2B87B2E2,0772855C,AF10D97F,C474B385,66C78A13,B41B1B50,E78EA991
EF0608D2,F1D053AE,29B3987B,9FD1FBC2,4FD212FC,2AF5E30E,A6E712C4,8DA05E5D
5B5F12BB,E89DEDA3,49D96062,DE0D0252,CD964339,D4D89027,FF90227A,F39F5B04
D6C6A90B,0C0DF871,B28E7DDF,609DED7C,DCD1979D,16265FA3,A7C6F69D,7DD3640A
253D5BA7,7CD28834,FF671A3B,483D506B,3B1F7426,5D9B2953,B0922FB0,4B111391
0A24C828,08B86021,A916965F,24EC180C,A257E918,7023E19F,453791B4,63D959C8
F64BFDAD,2E7F3407,CB384625,3DC80361,6D5F3EA9,B5B3A0AD,09A50C71,24DD61FC
02AB84D4,E98CDC0D,72B84FF0,C1168380,16D7FE1B,F0F0B414,7FF85C81,EDFCFEEF
D1B0DF8C,D354BADC,E888116D,7104BED9,78E8E3AC,8B7468B6,1DE1A37A,7AD7C999
952CE170,2178F473,22AEFCD9,CA48E318,6A080D23,D82260E7,81A63E72,131092AF
3AD2868B,30DC7858,ADCA933A,A03D0D9B,CF8C3EE1,0029C1AF,88E91191,3D609A86
AB78AD66,2922ECFD,2285E55B,F00E3072,4C9C9621,A0FE5B2D,F56F2119,2D44F9D1
C69E6905,89DDA5EF,87B94C13,F6471C48,A23F4D2B,4B6362C2,E5655285,83CD4575
F46A178B,392B1141,7F00983F,BE673F11,1D020E1B,52190444,010A9CD7,14FFF072
EBC4DF9A,098418FE,496FCAD8,E4982940,02F22313,B7D20224,000B2FA4,7E64905B
99631E2A,42564E71,C116E2DA,2D5CA148,40D32A14,9767D7F6,2635C7F2,6AD66529
86D05178,5E206FD3,2561808C,8116A3EF,83238235,8132CF68,8DF18F88,6AE47C29
B7AE6480,63253A03,77C8F584,A0500B34,2C0E530A,895D1DAF,D2594AFF,233F722B
1F4E0EB7,BAACBDF4,118998D0,7BC09AD3,B995779E,4A3EAD51,52AA3156,BEEE071A
075CA540,00BC7309,15283457,FF40361E,C815DF3D,E7CB4243,0965640E,9BEDF855
5D2A8A23,A4A2B23B,F11FD24F,F92CA4CF,C4623150,6467E194,3BC7BD9F,BDA0E792
01576CA8,293BC721,A00D39DF,0A3A1A0C,E730B398,9391D004,7904493C,C68D8AF0
65D8DDBF,756C2AD7,AA736D50,9A49043D,A3CD64BF,081CE476,B0E34974,36362275
A8FF3611,BF258168,BDF3C9BC,145746E1,978460B1,C7DEF28C,20AD3A59,BD00A70C
640A6776,11BA81E4,8B5443E6,1BCFCDE7,437DDC17,48099BA3,298219E0,354D1657
98BF604B,1C070EC6,C51ACB18,0C0095A2,7BBCBBE6,6955C220,AEA04103,DB0A2F64
9E33D3A3,DC1AA886,D256AA7B,A6B37A5B,B5B7E721,3234ECD4,0B6AE4AA,AE313219
CFF638AF,ED2C68E5,3CF279C8,834E14F3,D59A3D21,D47F5177,22FE37D2,F8E968E9
B3A19F62,38AE41F1,17A0FE27,E1982576,CF45653D,D641208B,A5D29EBE,CA2F3D43
B92A6B58,A8A5859B,50FB9777,838AE8A9,BCFE4F93,01E0FE52,B21C3978,6A3AF841
41DE3260,3246CA66,49087160,5AA8A568,D6ED7491,A70F20BF,A2A810B7,EE327590
35D90F27,45CFDA8C,3CD1AFCB,A85AFF42,193FF56C,7686A0C9,94A07816,3C1E1513
68AA7CAF,58BE4FD7,52A906A0,2BA2C7B8,6A2244CC,93F1DB16,3A35241A,5BFF2979
9B249590,787825D3,74624F14,8CAE7184,7E3D811A,A41863E4,8E5F80FC,F6A7D375
B09A94CE,8831E1BD,2DB6489D,CE11AC34,ABA361F7,3094C3EE,8B0DAC2C,4ACB8D6D
DEF198E4,E275F36C,F3D87315,77962EF9,762B4124,28F081E6,71B1570C,9FE84E70
A5BFF64A,3B80B3B9,5003EA4F,FA113019,243BE596,E898DB83,92461AD6,65D00AFB
45CA1FFA,77B8F260,C2548A9F,83CC2CE7,19D744B5,A2A5F9C6,82816FB2,0FA641CF
4678BF0B,DD25BA53,48C752F2,2AACC642,90118B6E,9A7CCF01,AB1B4895,CBBD73FA
FC9E03A5,5BD547E7,5DE97528,7CED2B98,F31615C9,89E5B41F,7DCE95DF,F1C6F005
F219E9CE,42F2F452,20DFD131,2397C2C8,F594E25C,D57B27F0,BD9CCF55,19345DCA
C0601C2A,661C0EA6,277A285D,4956B32C,3752C73D,4EF3418E,72F765E9,6A7C5E07
AB8C4FDE,C41C3F4D,2027B948,62CBA2EB,20EC81D6,63A4C0F3,D9DFA300,5C8CECB6
9B4854BB,55EF6F86,0AD740CD,BA35476C,56410DF2,BDC68D6C,6707ABF4,D0BFF638
B61EB9D7,3C654F9A,30C7D354,663A55B7,ACDC3862,17AD9F75,FA0887BF,3C252AC3
0DE13B87,9768BCDC,9B775330,8FF79655,1C83E0EF,CDF0A6E8,BDB29F55,7E1F6DF2
19E26D7F,F5672BBC,CE567AFD,34E275D9,D358A141,1111F2AF,CDBD67B1,76162CE1
2EE39608,C54C7AD1,B8A4D884,84932489,B068CF83,C8ECE892,95E45BE3,C76AAA74
9F8FF1A3,83807F36,10310536,8B9AF601,FFDFABE3,D959B115,DFC1A564,E2BB625A
F7FE6FD5,5815A727,F10849B8,6FD72B82,BAC2476B,E6BC5F2A,BD5D7DEB,7BA35FAC
CF635601,2D46028B,09C86599,6D9DF820,7E038FC9,EDD1C3AD,D73C536C,4F7C5392
31CBA5C7,1D80E84C,0A4053C6,4AA004E9,161A1954,D125F3F1,9723C248,4C1B4301
729C70D0,31CF5D46,B4A44470,248E04CD,0A349BB5,CC084D3E,C9471FE7,885C9ACB
62DDA425,4B45080D,EBDE9A96,459FBBA4,B0F356F5,9E4C8050,7F188438,ECFDAD5C
13763F5B,150BB3C8,DB4BF7CA,BF125530,9E31609E,4A729B71,34764516,293C0995
84E386B1,63BEF188,F0569DF7,6E5FE72F,98CFD512,1674A13D,6AF843FF,1447C325
59C1CC89,17A27B99,346EA64F,C6D0E61E,C25B5065,C6D75033,1E2C54E6,FB3696B5
3A2ADDC6,7C027717,C84DC3A8,2211B772,084763F6,FC63180B,A32CC526,EA260D33
5A61E5F0,0244B316,D68B6FB0,D5AEDEA2,E5890089,1C1D1277,5B9AF9F9,89B258DF
6EF65639,96DBFE21,F6C100D9,A190020D,3153D8F7,77F1CA80,AD4AEFF3,B48FA524
A817800E,751FF2CD,021DF88E,93B91019,265ECFBB,72B009DC,F5C62B47,E33277EB
CC6C78A0,C3CFD568,74227851,4E2C49AB,468B0C2E,67A9F7A8,ED3728CB,990E2107
F561B619,0CB6C463,F5E97831,57CD2FDD,91949FF0,70D99E9F,FA10247C,DF5F5F42
31615FCD,B24A830A,2CBCFC52,47D57085,54080A40,286FD6D2,45D42508,E3C36FBC
15214F8B,FA82C708,E76A6C89,70D8AEA5,716EACE8,0191EB22,7B54F8A0,D9FB42BC
DE128E93,318D5109,305DCBC7,CD7FE6BE,911C2FCD,F85DA5E8,C82A3AF5,F6F0EB4D
B21B9606,D24655D5,3A8965B0,A77050B3,0B559119,C717A222,8CFDA24B,97E91A14
AC8712F6,CF1B108D,8D6B8850,A99EACA5,02907F2F,A55B56D8,7679F050,BDEE2B44
1B098AEE,FA9F3037,5305DAD6,934D6826,93415C88,D3155EC7,FE8149AA,E90C8304
2D3F731B,585EDF00,27CC86BF,6B0662B6,8B59E38F,CA183DFE,22A7DC2F,5A5807EA
1C64E517,2A08B374,15A3E326,7C41F661,8F7F9644,88ABC203,909D15CB,83212BB4
7674A736,F0036A1C,7FFC77A5,101DFA1F,518747A7,8D411CEB,A9881B5B,04C46D8C
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
It's been generated using the following C program:
<++>mtgen.c
#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;
init_genrand(5489UL);
for(; i < 624; i++)
printf("%8lX\n", mt[i]);
}
<-->mtgen.c
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
cracking.
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:
<++>usr.h
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;
}
<-->usr.h
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.
<++>usl.h
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;
}
<-->usl.h
Now, to untemper the value, just apply these functions in reverse order:
<++>untemper.h
#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;
}
<-->untemper.h
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]:
<++>generate.py
import random
program="983247832"
length=780
random.seed(int(program[1]))
chars="".join(map(chr,range(32,127)))+'\n'
prog="".join([chars[int(random.random()*96)] for i in range(length)])
print(prog)
<-->generate.py
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
<++>hqb.py
import random
endprog='hi'
seed=0
chars=''.join(map(chr,range(32,127)))+'\n'
length=len(endprog)
prog,n='',0
while prog != endprog:
n+=1
random.seed(seed)
prog = ''
for t in range(1,length+1):
prog += chars[int(random.random()*96)]
if endprog[:t] != prog:
seed += 1
break
print('"{0}" => {1} {2}'.format(prog,length,seed))
<-->hqb.py
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 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.
--[ 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:
<++>crack.asm
; ----------------------------------------------------------------------------
; 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).
genrand_int32:
; 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 < N-M;kk++)
xor eax, eax
.genrand_loop1:
; standard mask application in the first subloop, nothing fancy to see
mov esi, DWORD [rdi + mt19937.tsv + rax * 4]
inc rax
mov edx, DWORD [rdi + mt19937.tsv + rax * 4]
and esi, 0x80000000
and edx, 0x7FFFFFFF
or edx, esi
; second part of the twist.
mov esi, edx
and edx, 1
shr esi, 1
xor esi, DWORD [rdi + M * 4 + rax * 4]
xor esi, DWORD [mag01 + rdx * 4]
mov DWORD [rdi + rax * 4], esi
; Do we satisfy the condition yet?
cmp rax, NSUBM
jne .genrand_loop1
.genrand_loop2:
mov esi, DWORD [rdi + mt19937.tsv + rax * 4]
inc rax
mov edx, DWORD [rdi + mt19937.tsv + rax * 4]
and esi, 0x80000000
and edx, 0x7FFFFFFF
or edx, esi
mov esi, edx
and edx, 1
shr esi, 1
xor esi, DWORD [rdi - 4 * NSUBM + rax * 4]
xor esi, DWORD [mag01 + rdx * 4]
cmp rax, N - 1
mov DWORD [rdi + mt19937.tsv - 4 + rax * 4], esi
jne .genrand_loop2
mov eax, DWORD [rdi + 4 * N]
mov DWORD [rdi], 0
mov edx, DWORD [rdi + mt19937.tsv]
and eax, 0x80000000
and edx, 0x7FFFFFFF
or eax, edx
mov edx, eax
and eax, 1
shr edx, 1
xor edx, DWORD [rdi + M * 4]
xor edx, DWORD [mag01 + rax * 4]
mov DWORD [rdi + M * 4], edx
.genrand_skip_twist:
; standard tempering code. bump up the mti.
movsxd rax, DWORD [rdi + mt19937.mti]
lea edx, [rax + 1]
mov DWORD [rdi + mt19937.mti], edx
; bit trickery follows.
mov eax, DWORD [rcx + rax * 4]
mov edx, eax
shr edx, 11
xor edx, eax
mov eax, edx
sal eax, 7
and eax, 0x9D2C5680
xor edx, eax
mov eax, edx
sal eax, 15
and eax, 0xEFC60000
xor eax, edx
mov edx, eax
shr edx, 18
xor eax, edx
ret
; ----------------------------------------------------------------------------
; init_by_array copied over from Mersenne Twister source code. No significant
; changes have been made. Because seeding the Mersenne Twister and forcing it
; to generate the TSV all the times with multiple seeds would take a lot of
; excess time. The routime has been optimized to copy over data from the
; initial MT19937 init_by_array state.
init_by_array:
mov DWORD [rdi + mt19937.mti], N
mov eax, DWORD [initial_state + mt19937.tsv]
lea r8, [rdi + mt19937.tsv]
xor r9d, r9d
push rbx
mov DWORD [rdi + mt19937.tsv], eax
; note: eax maps to i in the original MT19937 code.
mov eax, 1
.mtinit_loop1:
; all the time we refer to i-1, therefore no need to add
; the +mt19937.tsv-4 idempotency. this part is an optimized 1:1
; of the original code.
mov r10d, DWORD [rdi + rax * 4]
mov ecx, r10d
shr ecx, 30
xor ecx, r10d
mov r10d, DWORD [rsi + r9 * 4]
imul ecx, ecx, mtinit_magic1
xor ecx, DWORD [initial_state + mt19937.tsv + rax * 4]
add r10d, r9d
add ecx, r10d
mov DWORD [rdi + mt19937.tsv + rax * 4], ecx
; bump up the counters: rax => i, r9 => j
inc rax
inc r9
cmp rdx, r9
; j >= key length condition
ja .mtinit_keep_j
xor r9d, r9d
.mtinit_keep_j:
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]
.mtinit_loop2:
; 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
.mtinit_blk1:
; j >= key?
cmp rdx, r9
ja .mtinit_blk2
xor r9d, r9d
.mtinit_blk2:
dec rcx
jne .mtinit_loop2
mov edx, N - 1
.mtinit_loop3:
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
.mtinit_blk3:
dec rdx
jne .mtinit_loop3
pop rbx
mov DWORD [rdi + mt19937.tsv], 0x80000000
ret
; ----------------------------------------------------------------------------
; 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.
generic_get_seed:
; 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
.seedrev_deinit_last:
; 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
.seedrev_fixup_skip:
; 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
.crack_loop:
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]
cdqe
; 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
.seedrev_size_miss:
; 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
.seedrev_do_iterator:
movsxd rax, r12d
; set [iterator #2]
mov DWORD [r8 + mt19937.tsv + rax * 4], r10d
.crack_fixup:
; 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
.reset_j:
test r12d, r12d
jns .loop_again
lea r12d, [rbx - 1]
.loop_again:
; adjust the pointer to the next location and jump again.
inc rbp
jmp .crack_loop
.revseed_halt:
; stack cleanup, mostly.
; and return value in rax, obviously.
add rsp, 9C0h + 8
mov rax, r8
pop rbx
pop rbp
pop r12
pop r13
ret
; ----------------------------------------------------------------------------
; 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.
main:
; 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.
.generate_state:
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
.main_error:
; 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
.input_ok:
; 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 generic_get_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
.seedgen_im_loop:
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
.seedgen_im_done:
; done. now, generate seed from r2 state.
mov rsi, rbx
mov QWORD [rbp - temp_keylen], r8
lea rdi, [rbp - zerogen_temp + 4]
call generic_get_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
.rafinate:
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 - ' ']
.skip_nolf:
; 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
.untemper:
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
.generator_step2:
; make a mersenne twister state out of 2nd buffer.
xor eax, eax
.state_filler:
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 generic_get_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]
.verify_loop:
; 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 - ' ']
.wrongspot:
movsx eax, al
cmp ecx, eax
je .main_loop_again
.verify_quit:
cmp QWORD [rbp - target_length], r9
je .display_result
mov edi, stopmsg_internal_err
jmp .main_error
.main_loop_again:
inc r9
jmp .verify_loop
.display_result:
mov rsp, QWORD [rbp - gen_temp]
mov rsi, rbx
mov edi, format_leading
xor eax, eax
call printf
.display_seed:
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
.display_finished:
lea rsp, [rbp - 40]
xor eax, eax
pop rbx
pop r12
pop r13
pop r14
pop r15
pop rbp
ret
<-->crack.asm
--[ Appendix A - Sources
[1] - https://github.com/lattera/glibc/blob/master/stdlib/random_r.c#L364
[2] - http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm
?csnumber=50372
[3] - http://developer.classpath.org/doc/java/util/Random-source.html
[4] - https://crypto.stackexchange.com/questions/20495/how-brittle-
are-lcg-cracking-techniques
[5] - http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/
mt19937ar.c
[6] - https://esolangs.org/wiki/Seed
--[ Appendix B - Paleologoi method 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: http://kspalaiologos.now.im/doc/projects/mtcracker
Linux/WSL, 64-bit.