investigation_encoded_1 picoCTF 2019 Solution

Description

1. Step 1Examine both files

   Observation

   The challenge ships a mystery binary alongside an encodedData file. The binary is the encoder, so running it against the data first shows what transformation it applies, before 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 either errors on invalid input or spits out binary garbage, because this is a custom packed bitstream, not a base64 alphabet. The binary is the only record of the scheme, so skipping Ghidra leaves you with no codebook at all.

   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 2Reverse engineer the encoding (it is a custom prefix bit code)

   Observation

   The binary is not stripped, and strings shows internal arrays with per-character entries. Opening it in Ghidra should turn up the 27-entry (bit-length, offset) matrix and secret byte pool that define the custom 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 codes that cross byte boundaries, so the result is always unintelligible. Pull the 27-entry (bit-length, offset) matrix and the secret byte pool out of Ghidra instead of guessing a key.

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

   The codebook is not a linked tree but two flat arrays: a matrix of (bit-length, offset) pairs and a secret byte pool. Searching for pointer-based tree nodes finds nothing. Look for a 27-element global array of small integers driving 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 3Decode the data

   Observation

   With the 27-entry codebook extracted, each character maps to a variable-length bit string that crosses byte boundaries. So convert the whole encodedData file into one bitstream and greedily prefix-match against the codebook.

   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, so one output byte usually holds the tail bits of one character and the leading bits of the next. Byte-aligned lookup always gives garbage. Convert the whole file to a single bit string, then greedy-match 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 assigns different code lengths than the binary's hardcoded matrix, so decoding goes wrong or crashes at the first mismatched prefix. The codebook is fixed in the binary's global arrays and has to be read from Ghidra, not re-derived from 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.