writeups.noxtal.com

Write-up on CTFlearn’s challenge 856 - Rock Paper Scissors 2. Let’s break the twist ;) Challenge author: intelagent.

Challenge

Misc, 80 points

Do you think you can win 30 games of a much more twisted game or Rock Paper Scissors? I’m much less predictable now, there is no way you beat me. nc 138.197.193.132 5002

Solution

To get started with this challenge, let’s do some reconnaissance to find any vulnerability on this app.

Reconnaissance

Let’s open up netcat, enter the server’s IP address and the port and get pwning!

These are the first lines shown to us. There is an important detail we can find in this image: the word “twister”. In fact, this word refers to a Mersenne Twister, a type of PRNG (pseudo-random number generator). With that hint, we can be sure the moves will be generated randomly using this algorithm. Let’s dig further by typing one of the three choices. This image shows the behaviour of the two possible states of this system: win or loss. We can also notice that the other’s move is displayed alongside a weird number which doesn’t seem to be linked to the move chosen. Actually, it is, as you’re going to see later on.

We have now found two key details to this challenge by doing this simple reconnaissance: the allusion to a Mersenne Twister and that weird number. That’s all we are going to need to continue.

PRNGs

A pseudo-random number (PRNG) is an algorithm to generate sequences of seemingly random numbers. A PRNG can’t be random, because the outcome produced is entirely dependant on an initial value, also called “seed”. (inspired from wikipedia)

The Mersenne Twister

The Mersenne Twister is the most widely used PRNG. Let’s take a high-level overview on it. A Mersenne Twister algorithm needs to be initialized with a seed, a 32-bit value. In the initializing process, the seed is going to be converted to a state: a vector of 624 32-bit values. Every time we need a random number out of this PRNG, we convert the current state into a number using a one-way function (Temper). Then, a new state is generated by “twisting” the current one (the Twist function is also a one-way function).

The Attack

As said before, the Mersenne Twister algorithm keeps track of its state in 624 32-bit values. If we were able to collect 624 sequential values, we could reverse engineer the whole sequence and predict the next generated number. That is the flaw we are going to exploit to solve this challenge.

Remember the weird numbers from the beginning. Those are 32-bit integers, exactly the general size of random numbers generated with a Mersenne Twister. So this number is really just the PRNG output. That is exactly what we needed for this attack. Let’s write our exploit script.

The Exploit Script

Socket

The first step for this exploit script is to establish a connection between the script and the server. I’m going to use socket for that.

Let’s import the socket library and setup constants for both the IP and port of the server.

import socket

SERVER = "138.197.193.132"
PORT = 5002

Then, we need to add a function to connect the server to the script using the socket module.

def connect(server, port):
# open a connection to server
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((server, port))
return s

This function basically creates the socket from the constants declared before and return it.

Next step is to implement a function to read the socket’s response until a certain delimiter, so we can read until the “»>” which indicates we need to input our move. If the function does not find the delimiter at the end of the transmission, it will time out and end (that’s why the try/except and the settimeout are doing).

buf = b''
s.settimeout(1)
while not buf.endswith(delim):
try:
buf += s.recv(1)
except:
break

s.settimeout(None)

return buf.decode("utf8")

We are now ready to go. Let’s initialize our socket using our connect function.

# Init socket
s = connect(SERVER, PORT)

We have now got a socket connecting us (the client) to the server.

To input any move, we need to read until we have got a “»>” and then send our move to the server. Note that a socket communicates in binary, so we need to convert our strings to binary with the prefix b.

s.send(b"R")

Defeating the app

Sampling

We are now at the step to sample 624 sequent values. For this step let’s use the python module MT19937Predictor. This module will compute all the necessary in order to predict the next values given its needed 624 values. The name comes from MT for Mersenne Twister, 19937 is because of the prime used in it (2 ^ 19937 - 1) and predictor, obviously, because it is going to allow us to predict the sequence.

The first step is to install and import it at the top of our code, right under the socket import line.

from mt19937predictor import MT19937Predictor

Then, let’s create a new instance of that predictor at the end of the code.

# Collect data for prediction
predictor = MT19937Predictor()

The final step is to write a loop which collects our 624 values.

for i in range(624):
s.send(b"R")
rand = [int(i) for i in resp.split() if i.isdigit()][-1]

predictor.setrandbits(rand, 32)
print(f'Collected {i+1}/624 ({round((i+1)/624*100, 2)}%)')

The line before the loop bypasses all the information received when we connect to the server (see the first image), allowing us to write.

The first two lines after the for loop are just to read until the next input, input something just for the program to continue.

Then, we extract the random number from the response. The random number will always be the last one in the response, so we only search for all numbers in it and keep the last one.

In the next line, we feed the predictor with the random number we have extracted. The second parameter of the setrandbits function is the bit length of the value, in our case, 32.

The last line in this loop is just printing the number of samples collected alongside a simple percentage of progress.

Winning

Now, as said in the caption at the beginning of the communication (see the first image), we need to beat the game 30 times in order to get the flag. Let’s first create an object that contains every move we should make based on the other’s to win.

RPS_WIN = {
"R": "P",
"P": "S",
"S": "R"
}

With that in place, we now only need to do RPS_WIN[opp] where opp is the opponent move in order to get our move.

Let’s now do a loop of 30 iterations to get the flag.

for i in range(30):
nextrand = predictor.getrandbits(32)
opp = ["R", "P", "S"][nextrand % 3]

move = RPS_WIN[opp]
s.send(bytes(move, "utf8"))
print(move)

print(resp)

In order, this loop first predicts the next opponent’s move, then choose the right move to do against it and finally send it and read until the next possible input.

Finally, we need to close the socket and end the program.

s.close()

This is the final program:

import socket

from mt19937predictor import MT19937Predictor

SERVER = "138.197.193.132"
PORT = 5002

def connect(server, port):
# open a connection to server
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((server, port))
return s

buf = b''
s.settimeout(1)
while not buf.endswith(delim):
try:
buf += s.recv(1)
except:
break

s.settimeout(None)

return buf.decode("utf8")

# Init socket
s = connect(SERVER, PORT)

# Collect data for prediction
predictor = MT19937Predictor()

for i in range(624):
s.send(b"R")
rand = int(resp.split(" based on ").split("P"))

predictor.setrandbits(rand, 32)
print(f'Collected {i+1}/624 ({round((i+1)/624*100, 2)}%)')

# Win 30 times
RPS_WIN = {
"R": "P",
"P": "S",
"S": "R"
}

for i in range(30):
nextrand = predictor.getrandbits(32)
opp = ["R", "P", "S"][nextrand % 3]

move = RPS_WIN[opp]
s.send(bytes(move, "utf8"))
print(move)