Дневник игрока в самую "эзотерическую" игру... Рулетку.

Взлом ГПСЧ Вихрь Мерсенна в PHP
Рассмотрим ещё один не криптостойкий алгоритм генерации псевдослучайных чисел Mersenne Twister. На этот раз будем анализировать реализацию алгоритма в исходном коде php версии 5.4.6.
Содержимое файла /ext/standard/basic_functions.h
#define MT_N (624)
/* rand.c */
php_uint32 state[MT_N+1]; /* state vector + 1 extra to not violate ANSI C */
php_uint32 *next; /* next random value is computed from here */
int left; /* can *next++ this many times before reloading */
unsigned int rand_seed; /* Seed for rand(), in ts version */
zend_bool rand_is_seeded; /* Whether rand() has been seeded */
zend_bool mt_rand_is_seeded; /* Whether mt_rand() has been seeded */

Содержимое файла /ext/standard/rand.c
#define N MT_N /* length of state vector */
#define M (397) /* a period parameter */
#define hiBit(u) ((u) & 0x80000000U) /* mask all but highest bit of u */
#define loBit(u) ((u) & 0x00000001U) /* mask all but lowest bit of u */
#define loBits(u) ((u) & 0x7FFFFFFFU) /* mask the highest bit of u */
#define mixBits(u, v) (hiBit(u)|loBits(v)) /* move hi bit of u to hi bit of v */
#define twist(m,u,v) (m ^ (mixBits(u,v)>>1) ^ ((php_uint32)(-(php_int32)(loBit(u))) & 0x9908b0dfU))

/* {{{ php_mt_reload
*/
static inline void php_mt_reload(TSRMLS_D)
{
/* Generate N new values in state
Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */

register php_uint32 *state = BG(state);
register php_uint32 *p = state;
register int i;

for (i = N - M; i--; ++p)
*p = twist(p[M], p[0], p[1]);
for (i = M; --i; ++p)
*p = twist(p[M-N], p[0], p[1]);
*p = twist(p[M-N], p[0], state[0]);
BG(left) = N;
BG(next) = state;
}
/* }}} */

/* {{{ php_mt_initialize
*/
static inline void php_mt_initialize(php_uint32 seed, php_uint32 *state)
{
/* Initialize generator state with seed
See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier.
In previous versions, most significant bits (MSBs) of the seed affect
only MSBs of the state array. Modified 9 Jan 2002 by Makoto Matsumoto. */

register php_uint32 *s = state;
register php_uint32 *r = state;
register int i = 1;

*s++ = seed & 0xffffffffU;
for( ; i < N; ++i ) {
*s++ = ( 1812433253U * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffU;
r++;
}
}
/* }}} */

/* {{{ php_mt_srand
*/
PHPAPI void php_mt_srand(php_uint32 seed TSRMLS_DC)
{
/* Seed the generator with a simple uint32 */
php_mt_initialize(seed, BG(state));
php_mt_reload(TSRMLS_C);

/* Seed only once */
BG(mt_rand_is_seeded) = 1;
}
/* }}} */

/* {{{ php_mt_rand
*/
PHPAPI php_uint32 php_mt_rand(TSRMLS_D)
{
/* Pull a 32-bit integer from the generator state
Every other access function simply transforms the numbers extracted here */

register php_uint32 s1;

if (BG(left) == 0) {
php_mt_reload(TSRMLS_C);
}
--BG(left);

s1 = *BG(next)++;
s1 ^= (s1 >> 11);
s1 ^= (s1 << 7) & 0x9d2c5680U;
s1 ^= (s1 << 15) & 0xefc60000U;
return ( s1 ^ (s1 >> 18) );
}

Можно заменить, что php_mt_reload вызывается при инициализации и после вызова php_mt_rand 624 раза. Начнем взлом с конца, обратим трансформации в конце функции php_mt_rand(). Рассмотрим (s1 ^ (s1 >> 18)) в бинарном представление операция выглядит так
10110111010111100111111001110010 s1
00000000000000000010110111010111100111111001110010 s1 >> 18
10110111010111100101001110100101 s1 ^ (s1 >> 18)
Видно, что первые 18 бит (выделены жирным) остались без изменений.
Напишем две функции для инвертирования битового сдвига и xor

public static long unBitshiftRightXor(long value, long shift) {
// we part of the value we are up to (with a width of shift bits)
long i = 0;
// we accumulate the result here
long result = 0;
// iterate until we've done the full 32 bits
while (i * shift < 32) {
// create a mask for this part
long partMask = (-1 << (32 - shift)) >>> (shift * i);
// obtain the part
long part = value & partMask;
// unapply the xor from the next part of the integer
value ^= part >>> shift;
// add the part to the result
result |= part;
i++;
}
return result;
}

public static long unBitshiftLeftXor(long value, long shift, long mask) {
// we part of the value we are up to (with a width of shift bits)
long i = 0;
// we accumulate the result here
long result = 0;
// iterate until we've done the full 32 bits
while (i * shift < 32) {
// create a mask for this part
long partMask = (-1 >>> (32 - shift)) << (shift * i);
// obtain the part
long part = value & partMask;
// unapply the xor from the next part of the integer
value ^= (part << shift) & mask;
// add the part to the result
result |= part;
i++;
}
return result;
}

Тогда код для инвертирования последних строк функции php_mt_rand() будет выглядеть так
long value = output;
value = unBitshiftRightXor(value, 18);
value = unBitshiftLeftXor(value, 15, 0xefc60000);
value = unBitshiftLeftXor(value, 7, 0x9d2c5680);
value = unBitshiftRightXor(value, 11);

Если у нас есть 624 последовательных числа сгенерированных Mersenne Twister , то применив этот алгоритм для этих последовательных чисел, мы получим полное состояние Mersenne Twister, и сможем легко определить каждое последующее значение, запустив php_mt_reload для известного набора значений.