MiscellaneousEncodingScriptingWeb +296 points

1 month ago - 91 views

Malfunctioning Beads

This was a Steganography challenge that was not solved until a hint was given by the organizers. I had one idea with the hint given, and it turned out to be the correct one. This challenge seems hard to create and it was super cool to see a hidden message encoded in a chess game.

The Challenge

The challenge description goes as follows:

There might have been some interference in the chess hall. Maybe someone sent a hidden message?
Hint: Quite interesting how a chessboard has 64 spaces

It also had a link to https://lichess.org/KLkVd333 where a chess game can be seen:

A screenshot of the game on lichess.org, showing a chess board

I have no experience in playing chess myself, but I noticed in the top left it said "Imported by ...", so this might be some sort of file loaded in the lichess.org website. Scrolling down on the page shows a link to "Download PGN", which stands for Portable Game Notation, a file format for storing chess games. You can download it and view the raw text the moves are made of:

PGN

[Event "?"]
[Site "?"]
[Date "????.??.??"]
[Round "?"]
[White "?"]
[Black "?"]
[Result "*"]
[FEN "rnbqkbnr/8/8/8/8/8/8/RNBQKBNR w KQkq - 0 1"]
[SetUp "1"]

1. Bf4 Bg7 2. Ra5 Ne7 3. Qf3 Rxh1 4. Qb7 Rxg1 5. Bd2 Rg5 6. Rb5 Ra1 7. Bd3 Rh5 8. Qa6 Bf6 9. Qa3 Bg7 10. Ra5 Kd7 11. Kf2 Rh1 12. Qb3 Nf5 13. Qb4 Rc1 14. Qxb8 Rc5 15. Qg3 Rc3 16. Qb8 Rc1 17. Be4 Qg5 18. Rxf5 Qg6 19. Qb3 Qh7 20. Bb7 Qg6 21. Bb4 Kc7 22. Be7 Bxb7 23. Qd3 Rc5 24. Rf7 Qf5+ 25. Kg3 Bh1 26. Qb3 Bc3 27. Qa3 Qf1 28. Rf8 Rd5 29. Qa2 Bg7 30. Rf3 Kd7 31. Kg4 Rc5 32. Qf7 Ra3 33. Qa2 Rd3 34. Rf2 Rcd5 35. Bb4 Rf3 36. Qa6 Bf6 37. Qa2 Re3 38. Qa8 Ra5 39. Bc3 Qc1 40. Be1 Be5 41. Nd2 Rh3 42. Nb1 Bh2 43. Na3 Ke7 44. Rf6 Rf5 45. Bf2 Kd7 46. Be3 Ra5 47. Rf2 Bg1 48. Qb8 Qe1 49. Ra2 Qf1 50. Qb1 Ke8 51. Bf2 Qe1 52. Re2+ Kd7 53. Qb3 Qf1 54. Re8 Rh7 55. Nc4 Qe1 56. Qf3 Bxf2 57. Nd2 Rd5 58. Nb1 Bg2 59. Nd2 Rf5 60. Qa3 Rd5 61. Re2 Kc7 62. Nb1 Qc1 63. Qd3 Kd7 64. Qb3 Kc7 65. Qb4 Bf1 66. Qf8 Rh3 67. Nc3 Bg1 68. Qf3 Bg2 69. Ra2 Qe1 70. Ra8 Ba7 71. Qe2 Bg1 72. Rb8 Rf5 73. Qd2 Rfh5 74. Kf4 Qa1 75. Qf2 Bf3 76. Rf8 Be2 77. Qxe2 Qd1 78. Nb1 Kd6 79. Qa2 Rg3 80. Ra8 Rg7 81. Qh2 Rgh7 82. Ra7 Rb7 *

A file like this is much easier to work with if we want to find something hidden in the chess game. When I first saw the challenge I thought the hidden message might be encoded in the time it took to make a move, like seconds being converted to ASCII numbers. But I could not find any data relating to the time it took to make the move, so it probably just isn't stored.

The PGN notation stores the piece, and where it is moved to. This location on the board is written as a letter and a number, as you can see on the edges of the board as well. There are quite a few moves in this game, so there might be data encoded into these locations.

Extracting the Hidden Message

The hint also tells us about a chessboard having 64 spaces, being 8x8. The emphasis on 64 made me think of Base64, maybe that is somehow encoded in the moves being played? This was my first guess after the hint, so let's try it out.

Real Base64 works by taking a message in bytes, splitting it into chunks of 6 bits, and then mapping each 6-bit number to the Base64 alphabet:

A table of the Base64 alphabet, showing the decimal, binary, and character representation

The last step is taking a number from 0-63 and mapping it to a character. With our 64 spaces on the board, it could be a good candidate. We can guess that the numbers 1-64 on the chess board would be sequential from the bottom left to the right going up each row because the rows on the board go from low to high. So A1 is the first square. This would then mean that the 10th space on the board for example, C2, would be the 10th character in the Base64 alphabet, J. To implement this, we need to understand the PGN notation from before.

The moves are prefixed with a number and a dot. Then the move consists of first the name of the piece, possibly an x character if the move captured a piece, the location of the move as [letter][number], and finally a + sign only if the move puts the opponent in check. I found the simplest way to be just looking at the last 2 characters, but if the last character is a +, we need to look at the 2 characters before it:

Python

def number_from_move(move):
    if move[-1] == "+":  # + is added when move creates a check, ignore it when that happens
        move = move[:-1]

    row = int(move[-1]) - 1  # 0-indexed
    column = ord(move[-2]) - ord('a') # a-h -> 0-7
    return row*8 + column  # Rows skip 8 numbers

Here we just convert some strings like Rxg2 into the numbers as column 2 and row 6, becoming the number 1*6 + 1 = 7. Now that we have numbers from 0-63, we can just map them to the Base64 alphabet from earlier:

Python

>>> BASE64_ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
>>> BASE64_ALPHABET[number_from_move("Rxg2")]
'O'

So in this case the Rxg2 move would turn into the O character in Base64. We can keep doing this for all the moves in the game, and finally decode it from Base64:

Python

from base64 import b64decode

...

with open("lichess_raw.pgn") as f:
    game = f.readlines()[-1]

result = ""

# Parse the game into moves, and convert them to the Base64 characters
for turn in game.split(".")[1:]:  # Example: " Qb3 Kc7 65"
    parts = turn.split(" ")  # Example: ['', 'Qb3', 'Kc7', '65']
    white_move, black_move = number_from_move(parts[1]), number_from_move(parts[2])

    # Add both moves decoded to result
    result += BASE64_ALPHABET[white_move] + BASE64_ALPHABET[black_move]

print(b64decode(result))

This reads all the moves from the .pgn file from the site, and maps them to the Base64 alphabet, eventually creating the full Base64 string. Decoding this string results in the big flag!
wh4T|[email protected]|[email protected]_c#esz-P!3ceZ-!N H!$-pOCKe75 4nD P|4C3D_7hEM.0N.T#3 BO4rd_WHeN [email protected]_L00k!n6?|1

Note: This flag is not in the standard format for the event of TUDCTF{...}, probably because it's limiting having to make a valid chess game and Base64 characters at the same time. Not all moves you want to make will be valid. But the organizers found a way to still encode this big message in the game!