[Halloween crypto puzzles] Jed

Description

I solved a wonderful crypto puzzle by jed#6113 on the crypto_puzzles site, and won 5mBTC along with a cryptokitty and a Neon District trophy for it. Let’s look at how it was solved.

Solution

Stage 1

For stage 1, we got a P6 format PPM image, containing a reference to the OEIS prime numbers sequence attached to a sieve where colours where going in. After a bit of trying to filter colors by prime numbers, bit indices by prime numbers and other weird stuff, the solutions came to me after the hint jed gave: HINT: byte offsets, not pixel values.

It was only a matter of taking all bytes in prime numbered positions (+ 0 and 1) and making a new image out of that.

Stage 2

Connecting to 81.187.244.47:1900 with netcat, we got to some kind of dungeon puzzle:

Stage 2 of 3: Tower of Terror

You're about to enter a fiendish tower built into some mountains, created by notorious supervillian jed.
The tower contains exactly 4,531,985,219,092 rooms, although not all rooms are reachable.
Each room has trapdoors in the floor which you can jump down, but you can never travel back up.
You'll enter on the 20th floor.
Try to find your way out, but be careful! From the 16th floor onwards, some of the rooms are deadly snake pits.

Good luck.

At first, after a couple attempts to brute-force this with breadth-first or depth-first search and mapping where every trapdoor leads, we realized that this would take a long time to finish.

Some easy research in the number of rooms (because why would such a weird number be included?), we came to the conclusion that we were playing connect 4 to an opponent who’s moves were either invisible, or encoded in the descriptions of the rooms we got.

Trying to find logic in the description turned out to be impossible (as confirmed by the creator), so we had to make some assumptions about the AI.

It’s clear that the AI will play optimally, and thus if we want any possibility o win, we get the first move. The ambiguity arises when the AI has multiple valid moves. Trying out in a game where we forced a draw, we could eventually confirm that it always chose the leftmost optimal choice. Plugging that strategy in on http://connect4.gamesolver.org/, we managed to first get a draw (where we ended up in the basement, without any next possible move) and after that also a win.

This led us to stage 3.

Stage 3

This was probably the easiest part of the puzzle:

We had gotten

Stage 3 of 3: International Smorgasbord

Spain Lisbon 2 Uganda 7 ukraine Fiji Gabon ghana iceland Hungary reykjavik 2 qatar Rwanda Samoa mexico
xaixai Taiwan jamaica 6 Uzbekistan swaziland Haiti qingyang quilmes Gambia Macedonia 9 micronesia

from the victory in our game of connect 4, so we now had to make sense of this.

Taking the first letter of each word – including numbers and taking caps into account – resulted simply in the private key. Though I have to admit that I was almost looking for the next puzzle in that string, interpreting it as base64 encoded.

Wrap-up

A lot of thanks for this very fun puzzle go out to jed and Cr0wn_Gh0ul from the crypto_puzzles community and of course the associated prizes (for which I’d like to thank JTobcat and Neon District). On to the next halloween puzzle.

Also a word of thanks for LeFevre#5755 for some valuable input and forming a solving team with me on this one.