[write-up] hack.lu - GuessTheNumber

"Hack.lu is an open convention/conference where people can discuss about computer security, privacy, information technology and its cultural/technical implication on society"
The 2015-edition of the "hack.lu" conference took place from 20-22 October 2015 in Luxembourg. Part of the conference was a capture the flag (CTF) that could be attended both online and on-site.
I decided to participate together with the folks from the AGRS (TU-Berlin).

GuessTheNumber Challenge



This was the task description:

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


From the description we can gain some valuable information:

- we will have to write a script that guesses 100 numbers
- the numbers will be generated by an LCG with standard glibc parameters
- the LCG will be seeded with the server time in a special format
- numbers are from 0 to 99

The glibc parameters for the LCG are (taken from the link above):
m=2^31
a=1103515245
c=12345


First connection to the server


We connect to the server to get an idea about the way the service works.
We are greeted with the message:

Welcome to the awesome guess-my-number game!
It's 22.10.2015 today and we have 10:29:17 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:

We make a broad guess but no luck:

1
Wrong! You lost the game. The right answer would have been '45'. Quitting.


A first approach


We now know that for the timestamp "22.10.2015 10:29:17" the number would have been "45".
We create a python script that implements an LCG with the specified parameters and seed it with the timestamp in the format "YmdHMS".

m = 2**31
a = 1103515245
c = 12345
xn = 0

def seedMe(timeString):
  # YmdHMS
  global xn
  serverTime = time.strptime(timeString, "%d.%m.%Y %H:%M:%S")  
  seed = int(time.strftime("%Y%m%d%H%M%S", serverTime))
  xn = seed    

def rand():
  global xn
  xn = (a * xn + c) % m
  return xn  

seedMe("22.10.2015 10:29:17")
print rand()

The output however is larger than 99 and thus not the number we were looking for ("45"):
93578202
We conclude that the numbers have to be taken modulo 100 to achieve the desired range.
It could be possible that there is a fancier way to generate the desired range but we hope that this isn't the case.
"93578202 % 100 = 2" which is in the correct range but not the desired "45" either.

The solution


I then started to generate the next (1000) random numbers for several captured timestamps and compared each value with the desired one.
A common thing among all timestamps was that the 100th generated number matched the one we were looking for.
After some further try-and-error-ing I found that the 99th number matched the second called number.

I assumed that the service generates 100 random numbers once and asks for them starting from the last one.
A script that entered just these numbers into the service rewarded me with the flag:

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



Denis Werner
22.10.2015

zurück