FENtastic chessadecimal encryPGN: Solution
This blog post shows different ways to solve the Capture the Flag (CTF) challenge posted on April 21, 2023.
First and foremost, let’s discuss the capitalized FEN and PGN in the title. Recognizing the chess-related nature of the CTF challenge allows us to understand that FEN (Forsyth–Edwards Notation) and PGN (Portable Game Notation) are chess notations. The key of the CTF
6q1/p1k5/1pb3n1/5pBP/3R4/P3P3/6P1/3QK3 b - - 0 32
is clearly a FEN string, which can be entered on most chess websites, such as our favorite Lichess. Upon entering the FEN, you will be presented with a specific position:
However, this is only half of the puzzle. What about the PGN? PGN is a notation for an entire game, not just a position. There are numerous move sequences that can lead to the same position. For instance, the last move leading to the FEN could have been any of the following 12, and there are countless more for just this single move:
This phenomenon is somewhat akin to a cryptographic hash, which can be the result of infinitely many inputs. The MD5 hash 5f4dcc3b5aa765d61d8327deb882cf99, for example, could be the result of various inputs. However, the most likely input for the hash is “password.”
In the same vein, we are searching for a sequence of chess moves that lead to the FEN and hold some special meaning. To do this, we look for games with the specific ending position. There are multiple services that allow you to search chess games based on a FEN string:
Taking Chess HQ as an example, if you enter the FEN string you get back only one game — Mihail Tal vs Mikhail Botvinnik, 1st round of the World Championship in 1960:
A simple Google search for the game leads to a Lichess study, where you can copy the PGN in the under-board panel “Share & Export”.
To extract the key from the moves, we pay attention to another hint from the CTF title: “chessadecimal”. This term resembles “hexadecimal”. In chess, the notation of the squares uses the letters “a” to “h” for the files, and the number “1” to “8” for the rows. The starting position of the white king, for example, is “e1”. We can treat these square notations as hexadecimal numbers that use an unconventional alphabet. Here is the chess board with the “chessadecimal” values of the squares:
Chess moves are typically notated in algebraic notation, where, with a few exceptions, the target square of the moved piece appears last. For example:
Finally, the key is unveiled: the target squares of the chess moves, interpreted as hexadecimal numbers with the alphabet “12345678abcdefgh”.
One challenge we faced while creating the CTF was the representation of the castling move. The PGN notation for castling uses “O-O” for Kingside castling and “O-O-O” for Queenside castling. We couldn’t find a straightforward way to translate this to ASCII which would have made the challenge harder for participants. We considered simply omitting castling moves altogether and focusing only on moves with a clear target square for the XOR operation. However, this approach could have introduced ambiguity into the challenge.
Instead, we decided to search for a game where neither player castled. Fortunately, we found a game from the 1960 Chess World Championship between Mikhail Tal and Mikhail Botvinnik where neither player castled. Tal won this game and went on to become the new Chess World Champion. Using this game as a basis for our CTF allowed us to avoid the complications associated with castling notation.
Given the key, we can finally crack the CTF challenge:
- Base64 decode the ciphertext
- XOR the ciphertext with the corresponding key byte.
In the following we present three ways to solve the CTF challenge technically in increasingly concise fashion.
Solution 1 — Python
Getting the ciphertext is just a matter of Base64-decoding the string from the challenge:
import base64
ciphertext = base64.b64decode(
"""l63B0cPnh8X2gtXJlriG5oqIgNaQwpvFo9eS4rPkl9HByZ2j0re35IHi1u6erufR1b2gmJI="""
)
# ciphertext: b'\x97\xad\xc1\xd1\xc3\xe7\x87...'
To get the key, we need to read the game from the PGN. For this we use the python-chess library, which can be installed with pip install python-chess. First, we read the game from the PGN file:
import chess.pgn
""" load the first game from a PGN file """
with open("game.pgn") as pgn:
first_game = chess.pgn.read_game(pgn)
if not first_game:
raise ValueError("No game found")
# first_game: <Game at 0x7f95d06c7d90 ('Mikhail Tal' vs. 'Mikhail Botvinnik', '1960.03.15')>
For the key, we are only interested in the target square of the move, which we can get with chess.square_name(move.to_square)
for move in first_game.mainline_moves():
print(chess.square_name(move.to_square), end=" ")
# e4 e6 d4 d5 c3 b4 e5 c5 a3 c3 c3 c7 g4 ...
Now to convert this chess squares to bytes, we can use this function:
def chessadecimal(chess_char: str) -> int:
if chess_char in "abcdefgh":
return ord(chess_char) - ord("a") + 8
elif chess_char in "12345678":
return int(chess_char) - 1
else:
raise ValueError("Invalid chess character")
def chess_move_to_byte(move: str) -> int:
""" convert a chess move to a byte """
return 16*chessadecimal(move[0]) + chessadecimal(move[1])
# hex(chess_move_to_byte("d7")) = 0xb6
Finally, we just need to XOR the key bytes from the moves with the corresponding ciphertext bytes:
plaintext = ""
moves = list(first_game.mainline_moves())
b = chess.Board()
for move, c in zip(moves, ciphertext):
k = chess_move_to_byte(chess.square_name(move.to_square))
p = c ^ k
plaintext += chr(p)
print(plaintext)
Which print the plaintext string: ThreatCat would love to be as strong as CTF{Mittens}!, so the flag is Mittens.
Solution 2 - CyberChef
After we find the PGN notation of the game we can use Cyberchef to solve the CTF. CyberChef is a web-based tool developed by GCHQ, for quickly and easily manipulating data in a variety of ways.
If you are already familiar with Subsections an Registers in Cyberchef, this is the recipe we used for the solution. For everyone else, here is a more detailed explanation of the recipe.
To get started with Cyberchef, we first need to provide it with multiple inputs, one for the key (the PGN) and one for the ciphertext. We can do this by using custom identifiers for each of the values, as shown below:
Key: {here is the key data}
Ciphertext: {here is the base64 encoded ciphertext}
The recipe starts with a Subsection plugin and a regular expression (Key: (.*)\n) to extract the key material. The next three plugins (up to the “Merge” plugin) are applied only to the data captured by the regex.
The first step for the key transformation is to extract all the target squares of the moves. We can achieve this by using the “Regular expression” plugin with the regex pattern (..)\+?\s and the output format set to “List capture groups”. This will output each capture group (or target square) on a separate line. To remove the unwanted newline characters, we use the “Find / Replace” plugin.
Next, we use the Substitute plugin to replace the characters 12345678abcdefgh with 0123456789abcdef. This will transform the target squares from a letter-number combination to a hexadecimal value (e.g. e4 becomes c3).
Then we use the “Merge” plugin to merge the inputs back together.
After transforming the key, we use the Register plugin to capture the transformed key. We can use this register as input for the XOR plugin later. You can think of it as a variable declaration where we store the key in a variable called $R0.
Then, we use another Subsection plugin and the regex pattern .*Ciphertext: (.*) to extract the base64-encoded ciphertext. The “From Base64” plugin is then used to decode the ciphertext. Finally, we use the XOR plugin to decrypt the ciphertext with the transformed key we previously stored in $R0.
Once the decryption is complete, we can view the plaintext of the ciphertext and see the flag CTF{Mittens}.
Solution 3 - Binary Refinery
“The Binary Refinery™ is a collection of Python scripts that implement transformations of binary data such as compression and encryption.”. It allows us to write a very short and concise pipeline to solve this challenge.
First, we need to extract the moves from the PGN. While you could extract the moves with a series of regular expressions, they tend to quickly become very complex and hard to read. Instead, we can use the pgn-extract tool, which is available in the Ubuntu repositories. The following command extracts the moves from the PGN file and prints them to stdout:
❯ pgn-extract -V -C -N --notags --noresults --nomovenumbers --quiet game.pgn
e4 e6 d4 d5 Nc3 Bb4 e5 c5 a3 Bxc3+ bxc3 Qc7 Qg4 f5 Qg3 Ne7 Qxg7 Rg8 Qxh7
cxd4 Kd1 Bd7 Qh5+ Ng6 Ne2 d3 cxd3 Ba4+ Ke1 Qxe5 Bg5 Nc6 d4 Qc7 h4 e5 Rh3
Qf7 dxe5 Ncxe5 Re3 Kd7 Rb1 b6 Nf4 Rae8 Rb4 Bc6 Qd1 Nxf4 Rxf4 Ng6 Rd4 Rxe3+
fxe3 Kc7 c4 dxc4 Bxc4 Qg7 Bxg8 Qxg8 h5
Next, we want just the target squares. For that we use the binary refinery unit rex. The rex unit takes a regular expression and replaces the matches with the given replacement string. In this case, we want to replace the whole line with just the target square, which is the last two characters of the line. The regular expression \w*(\w\w) matches the whole line and captures the last two characters. The replacement string {1} replaces the whole line with the first capture group, i.e., the last two characters.
❯ pgn-extract -V -C -N --notags --noresults --nomovenumbers --quiet game.pgn \
| rex "\w*(\w\w)" "{1}"
e4
e6
d4
d5
c3
b4
e5
...
Next we need to transform the chess squares to bytes. For this we use the base unit, which can convert from any base and alphabet to integers. We just need to provide the alphabet of the chess squares 12345678abcdefgh:
❯ pgn-extract -V -C -N --notags --noresults --nomovenumbers --quiet game.pgn \
| rex "\w*(\w\w)" "{1}" \
| base "12345678abcdefgh" \
| peek --bare --narrow
-----------------------------------------------------------------
C3 C5 B3 B4 A2 93 C4 A4 82 A2 A2 A6 E3 D4 E2 C6 ................
E6 E7 F6 B3 B0 B6 F4 E5 C1 B2 B2 83 C0 C4 E4 A5 ................
B3 A6 F3 C4 F2 D6 C4 C4 C2 B6 90 95 D3 C7 93 A5 ................
B0 D3 D3 E5 B3 C2 C2 A6 A3 A3 A3 E6 E7 E7 F4 ...............
-----------------------------------------------------------------
...
Finally, we need to XOR the key bytes with the ciphertext bytes, the corresponding binary refinery unit is called xor. In our case, the ciphertext is given in base64 and we need to decode it. For this purpose, we can use the multibin syntax of binary refinery, which allows us to preprocess the data with other units. In this case, we use the b64 unit to decode the base64 string.
❯ pgn-extract -V -C -N --notags --noresults --nomovenumbers --quiet game.pgn \
| rex "\w*(\w\w)" "{1}" \
| base "12345678abcdefgh" \
| xor b64:l63B0cPnh8X2gtXJlriG5oqIgNaQwpvFo9eS4rPkl9HByZ2j0re35IHi1u6erufR1b2gmJI=
ThreatCat would love to be as strong as CTF{Mittens}!Uogr`Da"v
The plaintext will show some additional characters at the end, which are the result of the key being longer than the ciphertext. We can add another rex unit to just extract the flag:
❯ pgn-extract -V -C -N --notags --noresults --nomovenumbers --quiet game.pgn \
| rex "\w*(\w\w)" "{1}" \
| base "12345678abcdefgh" \
| xor b64:l63B0cPnh8X2gtXJlriG5oqIgNaQwpvFo9eS4rPkl9HByZ2j0re35IHi1u6erufR1b2gmJI= \
| rex "CTF\{(.*?)\}" "{1}"
Mittens