Hack.lu 2010 CTF Challenge #5 Writeup

Captain Redbeard’s Battleships (500)
While pirating-out a bit, you run into Captain Redbeard and his armada of ghost ships.
source1, source2
pirates.fluxfingers.net 2204 /tcp.

It is a Battleships game. We have to win Cpt. Redbeard 3 times in a row, to get the flag. First time he shots every 3 ships from 5, than 4 from 5, and in the final battle he doesn’t give us a chance for mistake at all.

Quick look through the source don’t show any vulneravilities. So, probably, we have to ‘guess’ ships placement. Let’s look at random functions used:

def __init__(self, name):
    self.name = name

    #init Wichmann-Hill prng with 256 bits (32*8) seed
    self.rand = random.WichmannHill(os.urandom(32))

def randInt(self, low, high):
    r = self.rand.randint(low,high)
    return r

After Player instance is initialized, all its methods use self.randInt() to get random numbers. CaptainRedbeard class uses randInt() in three places:
1. in _createBoardRandom(), inherited from Player class
2. in his messages (random from msgSuccess and msgFail)
3. when he wants to miss (each 4th and 5th shot in first game)

os.urandom(32) has 256 bits,we cant’ guess that. But does Wichmann-Hill PRNG use it properly?
Let’s look:

>>> import random
>>> import os
>>> rand = random.WichmannHill(os.urandom(32))
>>> for i in range(15):
...     rand = random.WichmannHill(os.urandom(32))
...     print rand.getstate()
... 
(1, (24488, 25495, 30321), None)
(1, (16665, 26259, 30322), None)
(1, (17370, 9334, 30321), None)
(1, (23963, 22211, 30321), None)
(1, (27292, 15574, 2), None)
(1, (23350, 8484, 1), None)
(1, (1257, 29985, 30321), None)
(1, (27580, 14174, 2), None)
(1, (21443, 4841, 30321), None)
(1, (13463, 21032, 2), None)
(1, (16971, 8873, 30321), None)
(1, (4171, 2111, 30322), None)
(1, (12437, 2108, 3), None)
(1, (11168, 24161, 30320), None)
(1, (20273, 11633, 30322), None)

Isn’t it strange about the fourth number? It has only 5 different values. Two other numbers are probably in range [0, 32000]. So there are 5×32000×32000=5120000000 different states. It’s rather bruteforceable ;)

So, we have to receive some random numbers from Captain Redbeard, then bruteforce the initial state and compute ships’ positions.

I wrote a C implementation of WichmanHill’s PRNG, using the jython’s code.
(later I found similar code in /usr/lib/python2.6/random.py).
The resulting bruteforcer is here. Random numbers sequence is to be inserted directly in source, I know it’s rude, but it’s fast and saves much time.

My bot uses classes from game sources. Creating a Redbeard class needs a socketserver. I simply commented 48 line in redbeard.py (it is self.printMsgLine(“blablabla”)). This prevents using the socketserver’s methods.

Finally, the bot source is here. Let’s try it:

$ py bot.py 
Collected 18 randoms.
Source generated, run ./brute 4
Waiting for seed:

Now bot asks the seed. This allows you to run bruteforcer at another PC or server and then simply enter seed numbers here. So, after ~15 minutes:

Waiting for seed: 14781 13592 2
...

Won first battle.
...

Won second battle.
...

GOT FLAG:
    Here are your 500P: 2bf847b8efa3997550020f

The flag is: 2bf847b8efa3997550020f