# Wang123 Write-up for T0113

> From: HKCERT23 CTF
> Tags: Reverse, ★★★☆☆
> Problem statement:
> fake flag is faker than real flag, so what is the real flag?
> Attachment: wang123_507d11104d387d2c886dc8300a8bfceb.png (This image)
>
> Solved by: Jackylkk2003

## Foreword

If you already know about the Turing machine, Tiling Problem using Wang Tiles and simulating Turing machine using Wang Tiles, you can directly skip to the solution since the things in the middle are trivial for you (this is my case). Well, you should be able to solve this problem easily without this write-up anyway.

Otherwise, you can follow the following observations and insights. Be prepared for an unnecessarily lengthy write-up.

## Observations (Part 1)

0. Tuning step: The problem name is Wang123, and the problem is about tiles
- With some "simple" tuning skills, you should go and search about Wang Tiles and you will see something interesting.
- > The basic question about a set of Wang tiles is whether it can tile the plane or not, i.e., whether an entire infinite plane can be filled this way.
- The above quote is quoted from Wikipedia
2. There are some important words at the top of the image:
- Machine
- Alphabet
- States
- Transitions
3. The words on the tiles are highly related to the alphabet and states above
- The words on the tiles are either states, characters from the alphabet, or a combination of both.

## Insights

Talking about tiles and machines, we can think/search of a classic undecidable problem -- given a set of Wang tiles (problem name!), is it possible to tile the plane? For simplicity, we will call it the "Tiling Problem".

We can verify our ideas by looking at the words stated in Observation 1. These words are commonly used in describing Turing machines and automata.

We will outline a proof here, and it will not be a very rigid one. Feel free to search about the rigid proof online.

> We can simulate a Turing machine using the Wang tiles. The configuration at row $r$ is the configuration of the Turing machine after $r$ steps of computation and column $c$ stores the character at position $c$ of the tape of Turing machine.
> A Turing machine will run forever if and only if there is way to tile the infinite plane given row 0, the initial configuration.
> If the Tiling Problem is solvable, then we can transform a Turing machine into tiles and solve the Tiling Problem and see if it can tile completely. That is, this would be a solution to the well-known unsolvable Halting Problem. A contradiction occurs.
> So, the Tiling Problem is not solvable.

However, the undecidability of Tiling Problem is not our concern here. The most important part is that we can simulate a Turing machine using Wang tiles.

We can apply the same technique and transform the tiles into a Turing machine and run the Turing machine and get the flag. But first, we need some more observations.

## Observations (Part 2)

3. There are action tiles for all states except H.
- It is a reasonable guess that H represents the halting state of the Turing machine
4. The tiling at the right shows a demonstration of the Turing machine using "fake" as the input
- Well, it is stated at the top too
5. The problem description is "fake flag is faker than real flag, so what is the real flag?"
- By Observation 4, which shows that the example input is "fake", it is again a reasonable guess that the actual input would be "real" or something similar.
6. The major problem is that there are too many tiles
- Keep in mind that we are simulating the Turing machine, which is deterministic in nature. So, look for the current state and the character at the current position when feeling confused about the choice of the tiles.
- For the tiles adjacent to the current position of the Turing machine, look for the moving tiles to see which suits the current tile.
- For the tiles not adjacent or the pointer head is not moving to this position, simply use the alphabet tiles.
- In most cases, there should be only 1 possible match.
7. A tile has 2 characters on its top side if and only if it is an action tile.
- It is now convenient to find them.
- They are also unique, because of the deterministic properties of Turing machine.
8. For moving tiles, it is sufficient to determine which tile fits the position given the top character and the character on its side.
- So it is again convenient to find the appropriate one to fill in the grid.

## Mini Conclusion
1. A Turing machine has to handle empty characters
- There is a character '#' in the alphabet, and other characters are obviously not denoting the empty character. So '#' is the empty character in this case.
2. The current state also has to be encoded in the tiles
- We can see that in Observation 2, there are some words on the tiles that are composed of both states and characters from the alphabet.
- The tiles encodes the current state using this method, since this stores both what the current state is, and what the character in this position is.
- That is, the words with 2 characters are the current position and current state of the Turing machine.
3. The states on the left and on the right of the tiles shows the moving of the Turing machine pointer.
- Turing machines allow moving left and right on the input tape, and we need the left and right edges to simulate the movement of the pointer head.

## Meanings and Example of the Tiles

Alphabet tile:
Alphabet tile encodes a character in that position. There are 2 usages: to indicate the initial character in that position (if appears in row 0), or the character has not been changed and is not pointed by the pointer head of the Turing machine (if not in row 0).

This tile will not appear the row 0 column 0.

If this tile is in row 0, it means that the character in this position (column) is 't' initially.

If this tile is not in row 0, it means that the character in this position is 't' since the previous row and has not been changed. It also indicates that it is not pointed by the pointer head of the Turing machine at the start nor the end of this step of computation.

Action tile:
Action tile encodes an action. For this tile, "1a" on top means that the original state is '1', and the original character in this position (represented by column) is 'a'. 'f' on bottom means that the character in this position is updated to 'f'. The '4' on right means that the state now changes to '4' and the pointer of the Turing machine moves 1 character to the right.

Head tile:
Head tile only appears at row 0 column 0. Indicating the starting character and state of the computation.

This tile means that the first character in the input is 'f', and the starting state is '0'. The pointer head is now pointing at this character.

Moving tile [L]:
![Moving tile [L]](https://hackmd.io/_uploads/Hk_L-qCQa.png)
Moving tile indicates that the pointer head of the Turing machine has changed.

'r' on top means that the character in this position is 'r'. '1' on the right means that the state of the Turing machine is now '1', and the pointer head has moved from the right character to the current character. The "1r" at the bottom means the current character is 'r' and the current state is '1', and is now pointed by the pointer head.

~~Sadly, the Moving tile (L) is not used in this problem at all.~~

Moving tile [R]:
![Moving tile [R]](https://hackmd.io/_uploads/H1rVzq0Q6.png)

Moving tile indicates that the pointer head of the Turing machine has changed.

'r' on top means that the character in this position is 'r'. '1' on the left means that the state of the Turing machine is now '1', and the pointer head has moved from the left character to the current character. The "1r" at the bottom means the current character is 'r' and the current state is '1', and is now pointed by the pointer head.

Different from its [L] counterpart, Moving tile [R] is used in this problem.

## Solution

It would be a great advantage if you have learnt about the Tiling Problem and Turing machines, since the solution is to run the Turing machine simulated by the given tiles, or to do the tiling and see the final results.

By Observation 5, we use "real" as the input, so we construct the machine as follows (recall that '#' means empty):


This is constructed by looking at the example given, the first tile is a head tile and the followings are alphabet tiles. The tiles following "real" are all alphabet tiles of '#', since they represent empty space and does not affect the results anyway.

For the next steps, we focus on the tile with 2 characters (the tile encoding the current position and state). By default, other tiles will use alphabet tiles that match the position.

Here is row 0 and row 1:

Continue to fill in the tiles, we would have a final board like this:


Since there are no tiles with "H#" on the top and 'H' is the halting state, the string on the bottom is the flag. Remember that 'H' is the state and '#' is empty space, and they should not appear in the flag.

Of course, it does not make sense to keep track of such a large grid of tiles when working on the problem. You can use any kind of expression you like to represent the grid. You only have to keep the last working row since the rows above it does not matter anymore. For example, you can store the final configuration like hkcert23{3hakkc3er}***#***, state H, and the initial configuration like ***r***eal###, state 0.

## Flag

The flag obtained, as shown above, is: `hkcert23{3hakkc3er}`.

## Comments

I learnt about Tiling Problem and undecidability just around 2 weeks before the CTF challenge, so I can easily know how to solve this problem. So it basically took me no time to figure out how to solve this problem. It is very lucky for me :P