investigation_encoded_2 picoCTF 2019 Solution

Description

1. Step 1

   Analyze the differences from part 1

   Observation

   I noticed the challenge is labeled 'part 2' of the same investigation, which suggested comparing the binary and encodedData against the part 1 setup to identify what new layers were added before attempting to write any decoder.

   This challenge adds two obstacles not present in part 1: (1) a login gate in the binary that blocks the encode function from running - patch the binary in a hex editor or with pwntools to NOP the conditional branch, and (2) a per-character transformation (modulo/XOR arithmetic) applied before the same prefix-code encoding from part 1, which also extends the valid alphabet to include digits 0-9. Identify both in Ghidra before writing your decoder.

   bash

   ./mystery encodedData

   Copied!

   bash

   strings mystery

   Copied!

   bash

   ghidra mystery &

   Copied!

   What didn't work first

   Tried: Running ./mystery encodedData and reading the output directly as ASCII, assuming the binary decodes rather than encodes.

   The binary is the encoder, not the decoder. Running it on encodedData produces a second layer of encoding, not plaintext. The decoding logic does not exist in the binary at all - you must reconstruct the inverse dictionary by studying what the encoder emits for each character, then apply that dictionary to encodedData yourself.

   Tried: Using 'strings mystery' output to find the flag or a hardcoded key and skipping Ghidra entirely.

   strings may surface the login prompt text and some symbol names, but the secret byte array and indexTable are numeric constants embedded in .rodata, not printable strings. They will not appear as a readable key. Ghidra's decompiler is needed to identify both the byte array offsets and the login branch that must be patched before the encode path is reachable.

   Learn more

   More complex encodings may apply multiple transformations in sequence: first XOR, then shift, then substitute - or the encoding may be position-dependent (the key changes based on the current position in the file). Identifying the sequence of operations is the key challenge.

2. Step 2

   Decompile the binary

   Observation

   I noticed the binary contains a login gate and an encoding function that references internal lookup tables, which suggested loading it into Ghidra to recover the exact constants and branch logic before attempting to patch or reconstruct the inverse.

   Use Ghidra to fully decompile the encoding function. Trace through each operation on the data bytes. Pay attention to any loop variables or counters that modify the transformation.

   bash

   ghidra mystery &

   Copied!

   What didn't work first

   Tried: Patching the binary by flipping the login branch before understanding what argument the encode function expects.

   Patching the branch is correct, but if you patch blindly before tracing the function signature you may patch the wrong conditional or leave the argument setup untouched. Ghidra shows that the encode function reads from a file path passed as argv[2], so the patched binary must be called as ./mystery_patched flag.txt out.bin - running it with no arguments after patching will still exit early from a missing-file check.

   Tried: Using 'objdump -d mystery' instead of Ghidra to understand the encoding loop.

   objdump produces raw disassembly without type recovery or variable naming, making it very difficult to identify the 71-byte secret array and the 38-entry indexTable by inspection. Ghidra's decompiler lifts the loop into C-like pseudocode and labels array accesses, which is essential for correctly extracting the two constants needed to reconstruct the code book.

   Learn more

   In Ghidra, the Data Type Manager lets you define structures that match how the program interprets its data. This can make the decompilation output much more readable when the code processes structured binary data.

3. Step 3

   Decode by brute-forcing one character at a time

   Observation

   I noticed Ghidra revealed a variable-length prefix code backed by a 71-byte secret array and a 38-entry indexTable with no arithmetic inverse, which suggested building the decode dictionary empirically by running the patched binary on every valid character and recording the bit pattern each one produces.

   Because the encoding is a Huffman-style prefix code, you cannot "invert" it with arithmetic. The standard approach is: for every valid character (a-z and 0-9), write that single character to flag.txt, run the patched binary, and record the resulting bit pattern. This builds a dictionary mapping bit strings to characters. Then read the encoded output file as a bit stream and greedily consume bits, emitting a character each time a known prefix matches.

   python

   python3 << 'EOF'
   import subprocess
   
   CHARS = 'abcdefghijklmnopqrstuvwxyz0123456789'
   
   # Build encoding dictionary by running the patched binary on each character
   char_to_bits = {}
   for c in CHARS:
       with open('flag.txt', 'w') as f:
           f.write(c)
       result = subprocess.run(['./mystery_patched', 'flag.txt', 'out.bin'],
                               capture_output=True)
       with open('out.bin', 'rb') as f:
           raw = f.read()
       # Convert raw bytes to a bit string
       bits = ''.join(f'{b:08b}' for b in raw)
       char_to_bits[c] = bits.rstrip('0') or '0'
   
   # Invert the dictionary: bit string -> character
   bits_to_char = {v: k for k, v in char_to_bits.items()}
   
   # Read the encoded output and decode greedily
   with open('encodedData', 'rb') as f:
       raw = f.read()
   bitstream = ''.join(f'{b:08b}' for b in raw)
   
   flag = ''
   buf = ''
   for bit in bitstream:
       buf += bit
       if buf in bits_to_char:
           flag += bits_to_char[buf]
           buf = ''
   
   print('Flag:', flag)
   EOF

   Copied!

   Expected output

   picoCTF{...}

   What didn't work first

   Tried: Treating the encoded bit stream as a fixed-width code (e.g., 8 bits per character) and decoding directly without building the dictionary from the binary.

   The prefix code uses variable-length codewords, so characters consume different numbers of bits. Assuming a fixed width of 8 shifts every boundary after the first mismatch, producing garbled output for the rest of the stream. The dictionary must be built by running the patched encoder on each character individually and recording the exact bit string it emits.

   Tried: Running the decode script against the original unpatched mystery binary and getting no output or a login error.

   The unpatched binary exits at the login check before ever reaching the encode function, so out.bin is never written. The script then opens a zero-byte or stale out.bin and builds an empty or incorrect dictionary. Patch the binary first (NOP the conditional branch that enforces the login) and verify a test character like 'a' actually produces a non-empty out.bin before running the full loop.

   Learn more

   The encoding uses a variable-length prefix code backed by two constants baked into the binary: a 71-byte secret array and a 38-entry indexTable. Each character maps to a unique range of bits within secret. Because the code words have different lengths and no code word is a prefix of another, decoding is unambiguous - but only via lookup, not arithmetic inversion.

   An alternative to the brute-force runner above is to extract the secret and indexTable values directly from the binary with radare2 or Ghidra, reconstruct the bit strings in Python, and build the dictionary statically. Both routes produce the same dictionary.

Flag

The flag is not in the standard picoCTF{} format - it is a hex string such as t1m3f1i35... whose suffix varies per instance. Run the prefix-code decoder against your encodedData file to recover your specific flag.