Very simple program in theory: it takes 4 truly random bytes from /dev/random, it checks them agains user input: if they are equal, it prints the flag. Basically we need to recover those random bytes. In the middle of this we have some calls to functions called seedRand and genRandLong, which together with the name of the challenge can give us some hints about its nature:
Most are build on algorithms involving some kind of recursive method starting from a base value that is determined by an input called the "seed".
...
The purpose of the seed is to allow the user to "lock" the pseudo-random number generator, to allow replicable analysis. Some analysts like to set the seed using a which uses hardware inputs to generate an initial seed number, and then report this as a locked number. If the seed is set and reported by the original user then an auditor can repeat the analysis and obtain the same sequence of pseudo-random numbers as the original user. If the seed is not set then the algorithm will usually use some kind of default seed (e.g., from the system clock), and it will generally not be possible to replicate the randomisation.
There are various ways to solve the challenge, from symbolic analysis (the most sophisticated), to brute forcing (the simplest method).
From the Ghidra pseudocode we can deduce that local_1408 is the internal state of the algorithm. It is a structure that holds all of its internal data.
Note: the seed is 8 bytes long.
Symbolic execution method
Basically we need to replicate the behaviour of the program using z3 to reconstruct the final output. main code:
Ok, it looks a bit scary... A quick google search of the constants brings up the algorithm that is being implemented here: Marsenne Twister 19937 generator.
A pseudo-random number generator engine that produces unsigned integer numbers in the closed interval $[0,2^{w}-1]$.
The algorithm used by this engine is optimized to compute large series of numbers (such as in Monte Carlo experiments) with an almost uniform distribution in the range.
The random numbers generated by mersenne_twister_engine have a period equivalent to the mersenne number $2^{(n-1)w}-1$.
Note about IPython
If we want to execute some code in python and then manipulate its output manually or to play with it, we can append this at the end of the script:
Wtf is mag.3808? It a global variable 16 bytes big. The first 8 are null, while the remaining 8 are a hexadecimal value. Note also that its index is & 1, which means that it is either 0 or 1 (ampersand of arity two is the bitwise AND operator). This translates in python as:
Note that we need to fix variable length: if we multiply two 32 bit numbers, the output would be 64 bits long. We need to add an ampersand 0xffffffff after the multiplication.
Bruteforce approach
Recall: this code is a random number generator with a random seed. The challenge prints out the 1001 random number and it asks for the random seed. Up until now we saw constraint programming (symbolic execution). We can also bruteforce it locally. It can be done two ways: by restarting every time the challenge binary, which can be costly, or by reimplementing the algorithm in another binary and launching this modified binary only one time.
Note: code without syscalls is faster.
Why are we able to reverse: from the same state we can always get the same output. The only random part of the algorithm is the seed.
prodkey
We have a 30 characters long key that we have to guess to get the flag, which is stored remotely. To check the correctness of our input flag the binary calls a function called verify_key, which returns 1 if its correct, 0 otherwise.
More specifically this is the check implemented by verify_key:
As we can see we have a bunch of functions that have to not return zero in order fot the check to pass. We need z3 to reverse them. They are 16 (one for each hexadecimal cypher). Or we can use angr. Using z3 can be quite time consuming, since we have to rework all the checks functions to be compatible with z3's symbolic data types. Foe example check_01 would go from:
Goal: register a user and login before that the restriction gets activated. This is the point of the race condition: we need to make the login happen before the registration is actually complete. More specifically, this is from register.php:
if($_POST['username'] === $row['username'] and $_POST['password'] === $row['password']){
?>
<h1>Logged in as <?php echo($username);?></h1>
<?php
$uid = $row['id'];
$sql = "SELECT isRestricted from privs where userid='$uid' and isRestricted=TRUE;";
$result = mysqli_query($conn, $sql);
$row = $result->fetch_assoc();
if($row['isRestricted']){
?>
<h2>This is a restricted account</h2>
<?php
}else{
?>
<h2><?php include('../key');?></h2>
<?php
}
?>
<h2>SUCCESS!</h2>
<?php
}
And we need to make registration and login happen at the same time in order to be able to login before that INSERT into privs (userid, isRestricted) values ((select users.id from users where username='$username'), TRUE); gets executed.
Toolkit
Best python library for handling HTTP requests, hands down. We'll use it for this challenge, since both the login and registration functions are POST requests. To look at requests we could use chrome developer tools or wireshark since HTTP requests are in clear.
Approach
First approach: we can try making the registration and the login happen at the same time. This will not work:
Note: we need a new username for each attempt, which means that a random string generator as username would be a good choice to make the exploitation simpler.
The engine has an internal state sequence of n integer elements, which is filled with a pseudo-random series generated on or by calling member function .
The internal state sequence becomes the source for n elements: When the state is advanced (for example, in order to produce a new random number), the engine alters the state sequence by twisting the current value using xor mask a on a mix of bits determined by parameter r that come from that value and from a value m elements away (see for details).
The random numbers produced are tempered versions of these twisted values. The tempering is a sequence of shift and xor operations defined by parameters u, d, s, b, t, c and l applied on the selected state value (see ).