❋ ❋ ❋

A couple of months ago I came across a programming puzzle called Tom’s Data Onion.

The puzzle looked interesting because solving one layer of the puzzle lets you access further layers, for a total of 6 puzzles.

This write up will cover solving version 1.0 (released 2020-06-11) and version 1.1.3 (released 2020-08-06) of the puzzles using python.

Each puzzle shares the follow qualities:

• They all have a marked ==[ Payload ]====... section where the puzzle data is stored.

• The puzzle data is always encoded using Adobe ASCII85.

For that reason, I created common functions to extract and decode that section:

def extract_payload(data: str) -> str:
    # The payload is bound by `<~` and `~>`
    start = '<~'
    end = '~>'
    # Match all characters or linebreaks.
    match = re.search(f'{start}(.|\n)*{end}', data, re.MULTILINE)
    if match:
        found = match.group(0)
    else:
        raise Exception("No payload.")
    return found

def read_current(idx: int) -> str:
    path = pathlib.Path(__file__).parent / f'stage-{idx}.txt'
    with open(path, 'r') as f:
        data = f.read()
    encoded = extract_payload(data)
    decoded = base64.a85decode(encoded, adobe=True)
    return decoded

Layer 0

Layer 0 is the most straightforward. The payload is encoded ASCII85. Decoding it gives us the next layer without any further processing needed.

Layer 1

Layer 1 requires us to iterate over the payload byte by byte and perform the following bit operations on it:

Flip every second bit
Rotate the bits one position to the right

This function will take care of that:

def stage_1(decoded: str) -> str:
    flip_mask = 0x55
    output = ''

    for b in decoded:
        # 1. Flip every second bit (high to low).
        # 2. Rotate the bits one position to the right, fill the
        # highest with the lowest bit as a result of the rotation.
        flipped = b ^ flip_mask
        shifted = flipped >> 0x1
        # Put the lowest order bit back into the highest spot.
        shifted |= ((flipped & 0x1) << 0x8)
        # Each byte should be convertible to an ascii character.
        output += chr(shifted)
    return output

Layer 2

This layer is slightly more complicated. It requires us to once again iterate over the data and do bit operations. This time, the data contains some metadata in the form of a parity bit. We need to check the parity bit and discard any data that doesn’t pass the check. Here is how we know:

To determine if the parity bit is correct, first count how
many 1 bits exist within the seven data bits. If the count
is odd, the parity bit should be 1. If the count is even,
the parity bit should be 0.

To solve this, I iterated over all the bytes, then within each byte iterated over each bit and summed them. It was then possible to check the parity bit:

bits = []

for b in decoded:
    # Lowest order bit is a parity bit. If the count of the
    # seven highest bits is even, parity bit is 0. If the count
    # is odd, parity bit is 1. Discard bytes with an incorrect
    # parity bit.
    bit_sum = 0
    candidate_bits = []

    for bit_idx in range(0x7, 0x0, -0x1):
        # High to low bit, ignoring the parity bit.
        bit = (b & (0x1 << bit_idx)) >> bit_idx
        bit_sum += bit
        candidate_bits.append(bit)

    parity_bit = b & 0x1
    expected_parity = 0x0 if bit_sum % 2 == 0 else 0x1
    if parity_bit == expected_parity:
        bits.extend(candidate_bits)

If the check passed, I kept the non-parity bits (i.e. our data) in its own buffer (bits). This was then used to generate the next payload:

output = ''
# https://stackoverflow.com/a/32284957
for i in range(0, len(bits), 8):
    output += chr(int("".join(map(str, bits[i:i + 8])), 2))

There is probably a cleaner way to do this, but it worked just fine.

Layer 3

I thought this was the most fun puzzle, even if it wasn’t the hardest one. This stage involves XOR encryption using a cycling key:

The payload has been encrypted by XOR’ing each byte with a
secret, cycling key. The key is 32 bytes of random data,
which I’m not going to give you. You will need to use your
hacker skills to discover what the key is, in order to
decrypt the payload.

If you do some research on this form of encryption, you’ll quickly find out that it can be beat with frequency analysis. However, we can keep things even simpler because we already have a sense of what the decrypted data looks like.

For example, each puzzle so far has had a predictable header that looks like this:

==[ Layer N/5: PUZZLE_NAME ]=============================

For this exercise, we know that it’ll be named ==[ Layer 4/5: to begin with. We don’t know the name of the puzzle yet. We also know that it will end in some number of = characters and two line breaks (\n\n).

We can recover part of the key by XORing what we think the original value is with the ciphered values:

_REMAINDER = '=============================\n\n'

def _analyze_known_value(ciphered: str) -> None:
    title_end_xor = ciphered[32:64]
    partial_key = []
    for r1, r2 in zip(_REMAINDER, title_end_xor):
        k = ord(r1) ^ r2
        partial_key.append(k)

We can then apply what we’ve found to the first chunk of the title, bytes 0-32 and get a partial title:

==[ Layer 4/5: Network Traff^c}

Now that we found the unknown name of the puzzle (Network Traffic), we can recovery entire key by once again XORing what we think the original text was with the ciphered text:

_TITLE = '==[ Layer 4/5: Network Traffic ]'

def _extract_key(ciphered: str) -> list:
    key = []
    title_xor = ciphered[0:32]
    for t1, t2 in zip(_TITLE, title_xor):
        k = ord(t1) ^ t2
        key.append(k)
    return key

Layer 4

This layer’s data comes in the form of good and bad UDP packets. To get the next payload, we have to remove any UDP packets whose:

• FROM address isn’t 10.1.1.10
• TO port isn’t 42069
• TO address isn’t 10.1.1.200
• IPv4 and UDP header checksums fail

We can use the following resources to implement these checks:

• Verify the IPv4 header checksum
• Check the source and destination ports and addresses
• Verify the UDP header checksum
• Test the UDP header checksum verification

If all of the above is implemented correctly, we should get the right data. The source code to solve this isn’t included inline because it’s too long. Instead, it’s available at the end.

Layer 5

This stage’s data is encrypted using AES-256 in CBC mode. We are given the key and the initialization vector. However, the key itself is also encrypted using AES key wrap, which itself has a decryption key called a key encrypting key (KEK).

Implementing the decryption and key unwrapping manually would be too much of a pain. Thankfully, the aes-keywrap package will do that work for us. The AES decryption is then handled using AES from Crypto.Cipher. Because most of this is handled by 3rd party code, the solution is pretty short:

import struct

from Crypto.Cipher import AES
from aes_keywrap import aes_unwrap_key


def handle_encrypted_data(decoded: str) -> str:
    key_encrypting_key = decoded[0:32]
    wrapped_key_iv = struct.unpack('>Q', decoded[32:40])[0]
    wrapped_key = decoded[40:80]
    payload_iv = decoded[80:96]
    payload = decoded[96:]

    unwrapped_key = aes_unwrap_key(
        key_encrypting_key,
        wrapped_key,
        iv=wrapped_key_iv
    )

    cipher = AES.new(unwrapped_key, AES.MODE_CBC, payload_iv)
    decrypted = cipher.decrypt(payload)
    return decrypted.decode('ascii')

Version 1.1.3

There are three differences between this version and version 1.0.

First, on layer 3, our known value no longer starts like this:

==[ Layer 4/5:

Because a new layer was added we now need to update it to this:

==[ Layer 4/6:

Second, on layer 5, we need to update the encryption mode since it now uses CTR instead of CBC. Here is a contrast between the versions to show the impact on the code:

cipher = AES.new(unwrapped_key, AES.MODE_CBC, payload_iv)

counter_obj = Counter.new(
    128,
    initial_value=int.from_bytes(payload_iv, byteorder='big'),
    little_endian=False
)

# unwrapped_key and payload_iv can be used to decrypt the
# rest of the payload.
cipher = AES.new(
    unwrapped_key,
    mode=AES.MODE_CTR,
    counter=counter_obj
)

Third, a 6th layer has been added before we reach the end. The next section provides the solution.

Layer 6

This layer’s data comes in the form of custom machine code that we need to write an emulator or virtual machine to execute. If we run it correctly, then it will output the last layer (i.e. the result of the puzzle).

Like layer 4, the source code isn’t included in line because it’s too long. However, there are a few interesting qualities I want to call out.

For starters, the entire “memory” content is the code we’re executing. It is also fully readable, writable, and executable. In theory this means that the code could overwrite pieces of itself as it’s executing (i.e. it could be polymorphic). I’m not sure if this happens in practice, but it’s an interesting detail.

On top of that, the program counter register (pc) is directly mutable. There was a gotcha here because after executing an instruction, we need to increment the pc register to find the next instruction. Each opcode is 1 byte, but some are immediate mode and contain their data in line. For example, moving a value into pc looks like this:

B0 29 00 00 00  # MVI32 pc <- 0x00000029

As a result, I thought after doing this operation I would need to increment pc by 5 bytes to get to the next instruction. This was a bug, because we already overwrote pc and thus have its next value without also incrementing it.

A final detail to call out was this pseudo-register:

(ptr+c) Memory cursor – Used to access one byte of
memory. Using this pseudo-register as the
{dst} of a move instruction will write to
memory. Using this as the {src} of a move
instruction will read from memory. The memory
address of the byte to be read/written is the
sum of the ptr and c registers.

For anyone who has looked into NES emulation, I initially thought this was like a memory-mapped register. I don’t think it is because in the NES case, it uses addresses in memory rather than a register. This seems like the inverse: a register that is a passthrough to and from memory.

Conclusion

These puzzles were not only fun, but also instructive, exercising the following skills:

• bit manipulation

• packet checksum computation

• encryption

• emulation

If you haven’t already, I recommend trying them on your own.

As usual thanks for reading!

Soure Code

The solutions for all these puzzles was implemented in python, targetting python 3.8.x+.

Before providing the link, I want to clarify that I had to make modifications to the aes-keywrap package. I have included that file here, with in line comments of what I had to change to make it work.

Click here to download the source code