The teacher of your programming class gave you a tiny little task: just write a guess-my-number script that beats his script. He also gave you some hard facts:

  • he uses some LCG with standard glibc LCG parameters
  • the LCG is seeded with server time using number format YmdHMS (python strftime syntax)
  • numbers are from 0 up to (including) 99
  • numbers should be sent as ascii string

You can find the service on school.fluxfingers.net:1523

Challenge Overview

The service is a text socket application with a self-explaining banner on connection:

$ nc school.fluxfingers.net 1523
Welcome to the awesome guess-my-number game!
It's 23.10.2015 today and we have 15:24:47 on the server right now. Today's goal is easy:
just guess my 100 numbers on the first try within at least 30 seconds from now on.
Ain't difficult, right?
Now, try the first one:
22
Wrong! You lost the game. The right answer would have been '55'. Quitting.

Straight approach

As shown in other teams’ write-ups on CTFtime, the intended way to solve this challenge is to use the LCG random number generator in glibc with standard parameters and the seed given by the application itself. The only caveat is that the server generates 100 numbers, takes modulo 100 and checks in reverse order.

Using the server as an oracle

An alternative approach is to use the server as an oracle in order to obtain the correct sequence. As shown before in the example, in case of error, the server returns the correct answer. On every connection the server seeds the LCG with its actual timestamp so the leakage is limited to the first number of the sequence.

Nevertheless, as shown in the description, the LCG is seeded with server time using number format YmdHMS, so the seed gets updated once per second. Well, in a whole second we can make a lot of connections to the server right? ;) The trick is to create 101 connections to the server within one second: we need 100 connections to leak the 100 right answers and one more to get the flag!

We coded a simple script which spawn 101 processes communicating with the main thread through pipes.

import os, re
from multiprocessing import Process, Pipe
from pwn import remote, context

def worker(pipe):
    s = remote('school.fluxfingers.net', 1523)
    s.recv(267, timeout=.5)
    while True:
        s.send('{}\n'.format(pipe.recv()))
        response = s.recv(timeout=.5)
        # check if we have found a new correct guess
        new_correct_guess = re.findall("The right answer would have been " + 
            "'([\d]+)'. Quitting.", response)
        # if we have found it, then return it to the main thread
        if new_correct_guess:
            pipe.send(new_correct_guess[0])
            break
        # We have (probably) found the flag!
        elif 'Correct! Guess the next one!' not in response:
            print(response)
            break

# disable pwntools standard logging
context.log_level = 'error' 

pipes = [Pipe() for i in range(101)]
procs = [Process(target=worker, args=(child_p,)) for child_p,parent_p in pipes]

# connect 101 times within 1 second.
for proc in procs:
    proc.start()

for n, (child_p,parent_p) in enumerate(pipes):
    os.system('clear')
    print('{:d} %'.format(n))
    # send a wrong answer to the nth process but the last
    parent_p.send(last_num if n is 100 else 1337)
    # read back the last correct guess
    last_num = parent_p.recv()
    # send the last correct guess to all the remaining processes
    for child_p,parent_p in pipes[n + 1:]:
        parent_p.send(last_num)

Once we have established 101 connections to the server within the very same second we are done. Now we just need to retrieve the correct sequence, send it back with the 101th process and read the flag!

The first process is fed with number 1337 which, being greater than 99, is clearly wrong. So the server answers back with the first correct guess which, in turn, is sent to all the remaining processes to be transmitted. By feeding the second process with the same wrong value, we can now get the second correct guess in the sequence. Instead, the last process is fed with the last correct guess, finishing the challenge.

Eventually, the flag is printed as expected:

100 %
Congrats! You won the game! Here's your present:
flag{don't_use_LCGs_for_any_guessing_competition}