investigation_encoded_1 picoCTF 2019 Solution

Description

1. Step 1

   Examine both files

   Observation

   I noticed the challenge provided both a mystery binary and an encodedData file, which suggested the binary is the encoder and running it against the data file would reveal what transformation it applies before attempting any manual decoding.

   Run file and strings on the binary. Run xxd on the encoded data file to understand its format. The binary likely reads and decodes the data file.

   bash

   file mystery

   Copied!

   bash

   strings mystery

   Copied!

   bash

   xxd encodedData | head -20

   Copied!

   bash

   ./mystery encodedData

   Copied!

   Expected output

   mystery: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, not stripped

   What didn't work first

   Tried: Run base64 -d on encodedData to decode it directly without touching the binary.

   base64 -d will either throw an 'invalid input' error or produce garbled binary garbage because the encoding is a custom packed bitstream, not a base64 alphabet. The binary is the only document of the encoding scheme, so skipping Ghidra analysis means you have no codebook to decode with.

   Tried: Run strings on encodedData hoping the flag is stored as a readable string inside the file.

   strings on the encoded file shows no recognizable text because the data is a packed bitstream where character codes are variable-length bit strings that cross byte boundaries. The flag only becomes readable after bitstream decoding using the codebook extracted from the binary.

   Learn more

   When a challenge provides both a binary and a data file, the binary typically demonstrates the encoding. Run it on the data file and observe the output. Then reverse the encoding using Ghidra analysis of the binary.

2. Step 2

   Reverse engineer the encoding (it is a custom prefix bit code)

   Observation

   I noticed the binary was not stripped and strings output referenced internal arrays with per-character entries, which suggested opening it in Ghidra to locate the 27-entry (bit-length, offset) matrix and secret byte pool defining a custom variable-length prefix code.

   Open the binary in Ghidra. The encoder maps each input character (the valid set is a-z plus space, input is lowercased) to a variable-length bit string. It uses a global table of 27 entries (the 'matrix') giving, per character, a (bit-length, offset) pair, and a 'secret' byte array those bits are pulled from. Each character's bits are appended to an output bitstream which is then packed into bytes. So decoding means rebuilding each character's bit string from the matrix+secret arrays, then greedily prefix-matching the output file's bitstream.

   bash

   ghidra mystery &

   Copied!

   bash

   # find the 27-entry matrix (len, offset) and the secret byte array

   Copied!

   What didn't work first

   Tried: Treat the encoding as a simple XOR cipher and brute-force a single-byte key against encodedData.

   XOR decoding produces byte-aligned output, but this encoder packs variable-length bit codes that cross byte boundaries, so XOR results are always unintelligible. The correct approach is to extract the 27-entry (bit-length, offset) matrix and the secret byte pool from Ghidra's decompiler, not to guess a key.

   Tried: Search Ghidra for a standard Huffman tree structure using node/left/right pointers.

   The codebook here is not stored as a linked tree but as two flat arrays: a matrix of (bit-length, offset) pairs and a secret byte pool. Searching for pointer-based tree nodes will find nothing. You need to look for a 27-element global array of small integers that drives a bit-extraction loop.

   Learn more

   A prefix (Huffman-style) code assigns each symbol a variable-length bit string such that no code is a prefix of another, so the stream decodes unambiguously left to right. Here the code book is not stored as a tree but reconstructed from the binary's matrix (bit lengths and offsets) and secret (the bit source). Recognizing it as a prefix code, not a byte cipher, is the whole insight.

3. Step 3

   Decode the data

   Observation

   I noticed that after extracting the 27-entry codebook from Ghidra, each character maps to a variable-length bit string that crosses byte boundaries, which required converting the entire encodedData file into a single bitstream and greedily prefix-matching against the codebook to recover the flag.

   Reconstruct each of the 27 characters' bit strings from the matrix+secret arrays, turn the encoded file into one long bitstream, then greedily match the shortest code that prefixes the remaining bits, emit that character, and repeat. The decoded lowercase message is the flag content.

   python

   python3 - <<'PY'
   # 1) read the 27-entry table (bit_len, offset) and the 'secret' byte pool from Ghidra
   # 2) build codebook[char] = the bit string of length bit_len read at offset in secret
   # 3) turn encodedData into a bitstream and greedily prefix-match codebook entries
   bits = ''.join(f'{b:08b}' for b in open('encodedData','rb').read())
   out = ''
   # while bits: find the (unique) codebook entry that is a prefix, emit its char, advance
   print(out)
   PY

   Copied!

   What didn't work first

   Tried: Read encodedData byte by byte and look up each byte directly in the codebook, treating it as a byte-aligned mapping.

   The encoder packs variable-length codes end-to-end into a bitstream, so a single byte in the output file typically contains the tail bits of one character and the leading bits of the next. Byte-aligned lookup always produces garbage. The correct approach converts the whole file to a single bit string and then greedy-matches from the left.

   Tried: Use Python's huffman or dahuffman library with a frequency-derived tree instead of the binary's own codebook.

   A frequency-derived Huffman tree will assign different code lengths than the binary's hardcoded matrix, so decoded output will be wrong or crash at the first mismatched prefix. The codebook is fixed in the binary's global arrays and must be read directly from Ghidra, not re-derived from the file's symbol frequencies.

   Learn more

   The decoded message is instance-specific and is NOT necessarily in picoCTF{...} form (some instances decode to a bare lowercase string that you submit wrapped in the flag format). Verify by checking the output is all lowercase letters and spaces, matching the encoder's valid alphabet.

Flag

Not a simple XOR/base64: the binary uses a custom variable-length prefix (Huffman-style) code defined by a 27-entry matrix of (bit-length, offset) pairs plus a 'secret' byte pool. Rebuild each character's bit string, then greedily prefix-match the encoded file's bitstream to decode. The decoded message is instance-specific.