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.