<- MISC

Deterministic

4 minutes to read

We are given a large text file called deterministic.txt:

$ head -30 deterministic.txt
The states are correct but just for security reasons,
each character of the password is XORed with a very super secret key.
100 H 110
110 T 111
111 B 112
112 { 113
113 l 114
114 0 115
115 l 116
116 _ 117
117 n 118
118 0 119
119 p 120
120 e 121
121 } 122
9 18 69
3 61 5
69 93 22
1 36 10
9 18 69
3 61 5
69 93 22
1 36 10
17 27 20
22 28 18
12 89 1
22 28 18
12 89 1
10 93 13
4 93 1

$ tail deterministic.txt
57 5 6969
101 88 121
91 15 99
55 60 57
9999 20 999
6969 29 39
121 10 55
39 72 46
9 18 69
3 61 5

$ wc -l deterministic.txt
   15589 deterministic.txt

Moreover, this is the description for the challenge:

There is a locked door in front of us that can only be opened with the secret passphrase. There are no keys anywhere in the room, only this .txt. There is also a writing on the wall.. “State 0: 69420, State N: 999, flag ends at state N, key length: one”.. Can you figure it out and open the door?

Intuition

The data given is a list of numbers distributed three per row. There is a short example, and numbers seem to match (100 -> 110; 110 -> 111; 111 -> 112; 112 -> … -> 121; 121 -> 122).

So it seems that we must find the row that starts with number 69420 (“State 0”), take the middle number as a character and find another row that starts with the last number of the current row. This process repeats until we reach number 999 (“State N”).

The list is extremely long because there are repeated rows. This can be solved using sort -u:

$ cat deterministic.txt | sort -u | wc -l
     410

Nevertheless, we need to program a bit to find the flag.

Programming strategy

First of all, we will need to read the file and remove all duplicated rows. Furthermore, it will be helpful to have a sorted list:

def main():
    with open('deterministic.txt') as f:
        unique_lines = sorted(set(f.read().splitlines()))

Then we will create a dictionary called states to have a mapping between the first number of each row and the tuple made of the value (second number) and the next state (third number):

    states = {}

    for line in unique_lines:
        if re.match(r'\d+ \d+ \d+', line):
            state, value, next_state = map(int, line.split())
            states[state] = (value, next_state)

Notice that we use re to omit rows that do not match pattern <number> <number> <number>.

After that, we define the initial and final states, then we can append values in the list named values traversing through the dictionary:

    values = []

    initial_state, final_state = 69420, 999
    current_state = initial_state

    while current_state != final_state:
        value, next_state = states[current_state]
        values.append(value)
        current_state = next_state

This way, we have an efficient use of data structures.

At this point, we can print out the values as bytes:

    print(bytes(values))

We have this result:

$ python3 solve.py
b"0\x06\x1cI\x04\x08\x07\x08\x0e\x0c\rI\x1d\x06I\x19\x08\x1a\x1aI\x1d\x01\x1b\x06\x1c\x0e\x01I\x08\x05\x05I\x1d\x01\x0cI\n\x06\x1b\x1b\x0c\n\x1dI\x1a\x1d\x08\x1d\x0c\x1aI\x06\x0fI\x1d\x01\x0cI\x08\x1c\x1d\x06\x04\x08\x1d\x08I\x08\x07\rI\x1b\x0c\x08\n\x01I\x1d\x01\x0cI\x0f\x00\x07\x08\x05I\x1a\x1d\x08\x1d\x0cGI$\x08\x07\x10I\x19\x0c\x06\x19\x05\x0cI\x1d\x1b\x00\x0c\rI\x1d\x06I\r\x06I\x1d\x01\x00\x1aI\x0b\x10I\x01\x08\x07\rI\x08\x07\rI\x0f\x08\x00\x05\x0c\rGGI&\x07\x05\x10I\x1d\x01\x0cI\x1b\x0c\x08\x05I\x06\x07\x0c\x1aI\x04\x08\x07\x08\x0e\x0c\rI\x1d\x06I\x1b\x0c\x08\n\x01I\x1d\x01\x0cI\x0f\x00\x07\x08\x05I\x1a\x1d\x08\x1d\x0cGI0\x06\x1cI\x08\x05\x1a\x06I\x0f\x06\x1c\x07\rI\x1d\x01\x0cI\x1a\x0c\n\x1b\x0c\x1dI\x02\x0c\x10I\x1d\x06I\r\x0c\n\x1b\x10\x19\x1dI\x1d\x01\x0cI\x04\x0c\x1a\x1a\x08\x0e\x0cGI0\x06\x1cI\x08\x1b\x0cI\x1d\x1b\x1c\x05\x10I\x1e\x06\x1b\x1d\x01\x10HHI0\x06\x1cI\x1a\x01\x06\x1c\x05\rI\x0b\x0cI\x1b\x0c\x1e\x08\x1b\r\x0c\rI\x1e\x00\x1d\x01I\x1d\x01\x00\x1aI\x0e\x00\x0f\x1dHI=\x01\x0cI\x19\x08\x1a\x1a\x19\x01\x1b\x08\x1a\x0cI\x1d\x06I\x1c\x07\x05\x06\n\x02I\x1d\x01\x0cI\r\x06\x06\x1bI\x00\x1aSI!=+\x12]\x1c\x1dY$]\x1d]6]\x1bZ6/\x1c<\x1c'6]\x07-6'Y\x1d6-X\x0f/X\n<\x05\x1dHH\x14"

Obviously, this is not what we expected. But remember that the descryption said that the result is encrypted with XOR, and the key is just one byte (“key length: one”). Hence, let’s apply brute force until we find HTB in the decrypted string:

    for n in range(256):
        result = xor(bytes(values), bytes([n]))

        if b'HTB' in result:
            print(result.decode())
            break

And here we have the decrypted message:

$ python3 solve.py
You managed to pass through all the correct states of the automata and reach the final state. Many people tried to do this by hand and failed.. Only the real ones managed to reach the final state. You also found the secret key to decrypt the message. You are truly worthy!! You should be rewarded with this gift! The passphrase to unlock the door is: HTB{4ut0M4t4_4r3_FuUuN_4nD_N0t_D1fF1cUlt!!}

Flag

The flag is at the end:

$ python3 solve.py | grep -oE 'HTB{.*?}'
HTB{4ut0M4t4_4r3_FuUuN_4nD_N0t_D1fF1cUlt!!}

The full script can be found in here: solve.py.