investigation_encoded_2 picoCTF 2019 Solution

Description

1. Step 1Analyze the differences from part 1

   Observation

   This is part 2 of the same investigation. Compare the binary and encodedData against the part 1 setup to see what layers were added, before writing 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. Run it on encodedData and you get a second layer of encoding, not plaintext. The decoding logic is not in the binary at all: reconstruct the inverse dictionary from what the encoder emits per character, then apply it 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 and some symbol names, but the secret byte array and indexTable are numeric constants in .rodata, not printable strings, so no readable key appears. Ghidra's decompiler is needed both to locate the array offsets and to find 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 2Decompile the binary

   Observation

   The binary has a login gate and an encoding function that reads internal lookup tables. Load it into Ghidra to recover the exact constants and branch logic before trying to patch or invert anything.

   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 right, but patch blindly before tracing the function signature and you may hit the wrong conditional or leave the argument setup alone. Ghidra shows the encode function reads a file path from argv[2], so the patched binary has to be called as ./mystery_patched flag.txt out.bin. Run it with no arguments and it still exits early on a missing-file check.

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

   objdump gives raw disassembly with no type recovery or variable naming, which makes the 71-byte secret array and 38-entry indexTable very hard to pick out. Ghidra lifts the loop into C-like pseudocode and labels the array accesses, which is what you need to extract both constants correctly.

   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 3Decode by brute-forcing one character at a time

   Observation

   Ghidra shows a variable-length prefix code backed by a 71-byte secret array and a 38-entry indexTable, with no arithmetic inverse. So build the decode dictionary empirically: run the patched binary on every valid character and record 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 different characters consume different numbers of bits. Assume a fixed width of 8 and every boundary after the first mismatch shifts, garbling the rest of the stream. Build the dictionary by running the patched encoder on each character and recording the exact bits 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 it ever reaches the encode function, so out.bin is never written. The script then reads a zero-byte or stale out.bin and builds an empty or wrong dictionary. Patch first, NOPing the conditional that enforces the login, then confirm a test character like 'a' 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 decoder returns a bare lowercase alphanumeric message rather than a ready-made picoCTF{...} string, and its suffix varies per instance, so wrap what you recover in the flag format before submitting. Run the prefix-code decoder against your own encodedData file to get your specific value.