Tags: game algorithm

Rating:

**Description**

> Guess Guess Guess
>
> nc 149.28.139.172 10002

**Solution**

Upon connecting, we get a standard PoW prompt:

sha256(****+UJBS55MXKhMOcSQO) == 4e3cefcf649092ef546aaabfcfa628e63377ce08bf17012f628ac48fbba2307d
Give me XXXX:

([simple PoW solver](https://github.com/Aurel300/empirectf/blob/master/writeups/2018-05-19-RCTF/scripts/pow.py))

After solving the PoW:

o__ __o o__ __o ____o__ __o____ o__ __o__/_
<| v\ /v v\ / \ / \ <| v
/ \ <\ /> <\ \o/ < >
\o/ o/ o/ | |
|__ _<| <| < > o__/_
| \ \ | |
<o> \o \ / o <o>
| v\ o o <| |
/ \ <\ <\__ __/> / \ / \

In every round of the game, I'll choose some different numbers from the figure interval. You are required to guess those numbers,ofc so does the order of them.
On each surmise of yours, 2 numbers will be told as a hint for you, but you need to speculate the fuctions of these 2 figures. (XD
GLHF

================== round 1 ==================
Give me 4 numbers, in[0, 10), You can only try 6 times

Some string format vulns and overflows were tried, but no luck, we actually have to solve the game properly. Providing 4 numbers returns e.g.:

Nope. 1, 0

Should be familiar, it's the [Mastermind game](https://en.wikipedia.org/wiki/Mastermind_(board_game)), apparently also known as "cows and bulls". In each round, there is a hidden sequence of four numbers, 0 through 9. We get 6 attempts to guess the correct sequence. With each incorrect attempt, we get two pieces of feedback:

- "blacks" - how many of our numbers are in the hidden sequence AND in the same position
- "whites" - how many of our numbers are in the hidden sequence but NOT in the same position

So I ~~stole~~ adapted a Mastermind solver from [here](https://github.com/Michael0x2a/mastermind-solver/blob/master/python/solve_mastermind.py) (thanks @Michael0x2a!). The principle is simple:

1. generate a pool of all possible guesses, for 10 different numbers and a sequence of 4 numbers, there are 10000 possible sequences
2. pick a guess and get feedback for it
3. if incorrect, eliminate all guesses from the pool that are inconsistent with the feedback and go back to step 2

The first guess is always [0, 0, 1, 1] for the 10 number 4-sequence (as it turns out all rounds are actually like this). There is an additional heuristic in picking a good guess, namely, a guess which may reduce the pool to the fewest remaining sequences.

I added socket interaction and the PoW solver to make it automated. After letting it run for a bit, I was disappointed to see that it rarely got past 4 rounds, and at this point I found out on the IRC that there are 8 rounds before you get the flag.

Mostly hopeless, I looked at the correct solutions it got to the few rounds it managed. Interestingly enough, among all the correct solutions, there was never a sequence with duplicate numbers! So, I removed these sequences from the initial pool and made the initial guess to always be [0, 1, 2, 3].

With this modification the results were immediately better and in just a couple of attempts the flag was obtained!

RCTF{0lD_GaM3_nAmed_Bu11s_4nd_C0ws}