# Challenge DescriptionWARNING: only psychics and wizards will be able complete this one
sorry :/52.59.124.14:10012# Solution
In this challenge we have a web service that runs a php script (index.php).We first this line```php	if ($_SERVER["REQUEST_METHOD"] == "POST"			&& $_SERVER["REQUEST_URI"] == "/submit") {```When we send a request that is not a post requst to the route: `/submit` (either a get request to this route or any request in another route) it execues the following:```php	{		srand(random_int(0, 4294967295));
		$t = time();		echo strval($t) . "\n";
		echo strval(rand()) . "\n";		for ($i = 0; $i < 300; $i++) {			if (($i % 60) == ($t % 60)) {				echo strval(rand()) . "\n";			} else {fit				rand();			}		}
		$_SESSION["next"] = rand();		$_SESSION["expiry"] = time() + 60;
		echo "Good luck :P";	}```The previous code ( from now on Initialization) gets a (cryptographically secure) random seed from 0 to 4294967295 and generates 301 (non cryptographically secure) integers.
From those it shows on the page only the first random number and those that their index(i) is  the same modulo 60 as the time the Initialization started like so:
```1678892907 496134670 80709468 919957814 2116517071 145427214 1291083934 Good luck :P```
	The first number represents the timestamp (t) of the time the script started and the next numbers are those with i%60 == t%60
sets to variables for the session.  One  specifies when the sessioin expires, and is initialized to 60 seconds after the script ends and one that stores the next random number (`"next"`).
When we send a post request to the `/submit` route it executes the following:```php {		if (!isset($_SESSION["expiry"])) {			echo "Invalid session!";			return;		}
		if (time() > $_SESSION["expiry"]) {			echo "You're too slow!";			return;		}
		echo $_SESSION["next"]. " " . $_POST["next"] . "\n";		if (intval($_POST["next"]) != $_SESSION["next"]) {			echo "Wrong prediction!";			return;		}
		echo "FLAG " . getenv("FLAG");```
If the session is initialized and not expired (current time < 60+ initialzation time)  it checks whether the `"next"` value of the request is the same as the `"next"` value of the session , meaning the next random number. 
This way we cannot generate enough numbers to get the state using **randcrack** like the previous challenge. We use a different method.
 We have the following script: 
 solve.py```python#!/usr/bin/env python3.7# Charles Fol# @cfreal_# 2020-01-04 (originally la long time ago ~ 2010)# Breaking mt_rand() with two output values and no bruteforce.#"""R = final rand valueS = merged state values = original state value"""
import randomimport sys
N = 624M = 397
MAX = 0xffffffffMOD = MAX + 1
# STATE_MULT * STATE_MULT_INV = 1 (mod MOD)STATE_MULT = 1812433253STATE_MULT_INV = 2520285293
MT_RAND_MT19937 = 1MT_RAND_PHP = 0
def php_mt_initialize(seed):    """Creates the initial state array from a seed.    """    state = [None] * N    state[0] = seed & 0xffffffff;    for i in range(1, N):        r = state[i-1]        state[i] = ( STATE_MULT * ( r ^ (r >> 30) ) + i ) & MAX    return state
def undo_php_mt_initialize(s, p):    """From an initial state value `s` at position `p`, find out seed.    """    # We have:    # state[i] = (1812433253U * ( state[i-1] ^ (state[i-1] >> 30) + i )) % 100000000    # and:    # (2520285293 * 1812433253) % 100000000 = 1 (Modular mult. inverse)    # => 2520285293 * (state[i] - i) = ( state[i-1] ^ (state[i-1] >> 30) ) (mod 100000000)    for i in range(p, 0, -1):        s = _undo_php_mt_initialize(s, i)    return s
def _undo_php_mt_initialize(s, i):    s = (STATE_MULT_INV * (s - i)) & MAX    return s ^ s >> 30
def php_mt_rand(s1):    """Converts a merged state value `s1` into a random value, then sent to the    user.    """    s1 ^= (s1 >> 11)    s1 ^= (s1 <<  7) & 0x9d2c5680    s1 ^= (s1 << 15) & 0xefc60000    s1 ^= (s1 >> 18)    return s1
def undo_php_mt_rand(s1):    """Retrieves the merged state value from the value sent to the user.    """    s1 ^= (s1 >> 18)    s1 ^= (s1 << 15) & 0xefc60000     s1 = undo_lshift_xor_mask(s1, 7, 0x9d2c5680)     s1 ^= s1 >> 11    s1 ^= s1 >> 22     return s1
def undo_lshift_xor_mask(v, shift, mask):    """r s.t. v = r ^ ((r << shift) & mask)    """    for i in range(shift, 32, shift):        v ^= (bits(v, i - shift, shift) & bits(mask, i, shift)) << i    return v
def bits(v, start, size):    return lobits(v >> start, size)
def lobits(v, b):    return v & ((1 << b) - 1)
def bit(v, b):    return v & (1 << b)
def bv(v, b):    return bit(v, b) >> b
def php_mt_reload(state, flavour):    s = state    for i in range(0, N - M):        s[i] = _twist_php(s[i+M], s[i], s[i+1], flavour)    for i in range(N - M, N - 1):        s[i] = _twist_php(s[i+M-N], s[i], s[i+1], flavour)
def _twist_php(m, u, v, flavour):    """Emulates the `twist` and `twist_php` #defines.    """    mask = 0x9908b0df if (u if flavour == MT_RAND_PHP else v) & 1 else 0    return m ^ (((u & 0x80000000) | (v & 0x7FFFFFFF)) >> 1) ^ mask
def undo_php_mt_reload(S000, S227, offset, flavour):    #define twist_php(m,u,v)  (m ^ (mixBits(u,v)>>1) ^ ((uint32_t)(-(int32_t)(loBit(u))) & 0x9908b0dfU))    # m S000    # u S227    # v S228    X = S000 ^ S227     # This means the mask was applied, and as such that S227's LSB is 1    s22X_0 = bv(X, 31)    # remove mask if present    if s22X_0:        X ^= 0x9908b0df
    # Another easy guess    s227_31 = bv(X, 30)    # remove bit if present    if s227_31:        X ^= 1 << 30
    # We're missing bit 0 and bit 31 here, so we have to try every possibility    s228_1_30 = (X << 1)    for s228_0 in range(2):        for s228_31 in range(2):            if flavour == MT_RAND_MT19937 and s22X_0 != s228_0:                continue            s228 = s228_0 | s228_31 << 31 | s228_1_30
            # Check if the results are consistent with the known bits of s227            s227 = _undo_php_mt_initialize(s228, 228 + offset)            if flavour == MT_RAND_PHP and bv(s227, 0) != s22X_0:                continue            if bv(s227, 31) != s227_31:                continue             # Check if the guessed seed yields S000 as its first scrambled state            rand = undo_php_mt_initialize(s228, 228 + offset)            state = php_mt_initialize(rand)            php_mt_reload(state, flavour)             if not (S000 == state[offset]):                continue             return rand    return None
def main(_R000, _R227, offset, flavour):    # Both were >> 1, so the leftmost byte is unknown    _R000 <<= 1    _R227 <<= 1     for R000_0 in range(2):        for R227_0 in range(2):            R000 = _R000 | R000_0            R227 = _R227 | R227_0            S000 = undo_php_mt_rand(R000)            S227 = undo_php_mt_rand(R227)            seed = undo_php_mt_reload(S000, S227, offset, flavour)            if seed:                return(seed)
def test_do_undo(do, undo):    for i in range(10000):        rand = random.randrange(1, MAX)        done = do(rand)        undone = undo(done)        if not rand == undone:            print(f"-- {i} ----")            print(bin(rand).rjust(34))            print(bin(undone).rjust(34))            break
def test():    test_do_undo(        php_mt_initialize,        lambda s: undo_php_mt_initialize(s[227], 227)    )    test_do_undo(        php_mt_rand,        undo_php_mt_rand    )    exit()
#test()
if len(sys.argv) < 5:    print('Finds out a PHP mt_rand() seed from two outputs of mt_rand()'          ' separated by 226 other calls.')    print('')    print('Usage:')    print(f'  {sys.argv[0]} <rand_n+0> <rand_n+227> <n> <flavour>')    print('')    print('Parameters:')    print('  rand_n+0:   First random value')    print('  rand_n+227: Second random value')    print('    The second value comes 226 mt_rand() calls after the first.')    print('  n:          Number of mt_rand() calls in between the seeding and')    print('              the first value (rand_n+0)')    print('  flavour:    0 (PHP5) or 1 (PHP7+)')else:    main(int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]), int(sys.argv[4]))
```the main function of solve.py can predict the seed of the rng used by php using the first and the 227th number generated using this seed.
All we have to do now is try and get the service to generate numbers in such a timeslot that the index of the 227th (226 for the script) number has the same %60 as the timestamp, and thus is given to us.
we wrote the following script:
```pythonfrom foresight.php import randimport requestsfrom solve import main
s = requests.Session()while(True):	l = s.post("http://52.59.124.14:10012").text#	print(1)	arr = l.split('\n')	time = int(arr[0])	print(time % 60)	inputs = []	j = 1	inputs.append(int(arr[1]))	for i in range(300):		if time % 60 == i % 60:			j += 1			if i == 226:				inputs.append(arr[j])				break	if i < 250:		print("lol")		seed = main(int(inputs[0]),int(inputs[1]),0,7)		print(seed)		break	continue
randomaki = input()
data = {"next":randomaki}
print(s.post("http://52.59.124.14:10012/submit",data=data).text)
```
this script reinitializes the state (by sending a post request to the main route instead of the / submit ) and gets the timestamp and the random generations from the response. It then runs a for loop from 0 to 300 and checks if the index that haas the same %60 as the timestamp us the desired 226. if this happened it prints the seed and sends the user input to the service.
after running this we get something like this:
```44444444444545454545454545454545454545454546lol1042126681
```
In an [onine php compiler](https://onlinephp.io/) we generate the first 302 numbers using the seed we got and put the last of them in the script we wrote.```php  ```
After that we get the flag:
```44444444444545454545454545454545454545454546lol12265348361283606073FLAG ENO{M4sT3r_0f_R4nd0n0m1c5}```