Huffpuff

Platform: spbctf | Category: Reversing | Type: Challenge | Difficulty: Medium | OS: Linux | Author: XESXOR | Date: 2026-03-31 | Status: Solved Techniques: huffman_tree_reconstruction, known_plaintext_recovery, prefix_code_decoding, reverse_engineering

Summary

Task: 64-bit ELF that computes custom Huffman codes for a fixed internal string and prints only code integers plus the encoded bitstream. Solution: reverse the exact heap tie-breaking and bit-building logic, reconstruct a consistent prefix code table, then decode the stream into the final sentence.

Huffpuff — spbctf

Description

A 64-bit non-stripped Linux ELF implements its own Huffman encoder. Instead of printing the original string, it prints a table of character = integer values and then emits the encoded bitstream.

The goal is to recover the hidden plaintext. A known hint was that the output starts with I_Like_.

Analysis

What the program does

The binary uses a fixed global string named test, counts byte frequencies, builds a Huffman tree, prints one integer per used symbol, and finally prints the encoded stream. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The important detail is that the printed integer is not the code length. It is the integer value of the code bits accumulated while walking from leaf to root.

The provided output was:

 text read-only • copy allowed Copy
C=34, I=0, L=35, P=32, R=33, S=38, T=1, _=1, a=7, c=30, d=1, e=1, f=39, g=8, h=36, i=5, k=37, m=31, n=6, o=6, p=58, r=10, s=11, t=9, u=59, y=28

0000000011000110101100101000100100000111000110011001001111011000011110000110001011011111111010101000011011101101011100110001000001100100000111010101110000110011111010100010000101110100101110011000001010110111100001101110110101011001000001011101100000100100000011111011101000000100110000100011111011001000011001010100101011100110

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Exact Huffman behavior

The reconstruction depended on matching the binary's exact implementation details:

1. The heap array is kept sorted in descending frequency order.
2. _heap_remove() pops from the end, so it returns the minimum-weight node.
3. Equal weights are stable under insertion, so later inserted equal-weight nodes are popped first.
4. Initial leaves are inserted in ascending byte order.
5. Internal nodes are inserted later and therefore win ties against older equal-weight leaves.
6. During merge:
   • first popped node gets parent[a] = +next, meaning bit 1
   • second popped node gets parent[b] = -next, meaning bit 0
7. Code bits are accumulated LSB-first while walking from leaf to root.
8. inttobits() prints those bits MSB-first, producing the normal root-to-leaf Huffman code. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

This means the displayed integers alone are ambiguous unless the code length is also recovered.

Reconstructing the code table

Using the known prefix I_Like_, the output constraints, and the exact merge/tie-breaking rules, the consistent code table is:

 text read-only • copy allowed Copy
C=100010
I=000000
L=100011
P=100000
R=100001
S=100110
T=000001
_=001
a=0111
c=11110
d=00001
e=0001
f=100111
g=01000
h=100100
i=0101
k=100101
m=11111
n=0110
o=110
p=111010
r=1010
s=1011
t=01001
u=111011
y=11100

There is one formal ambiguity in the printed mapping: both n and o have integer value 6. After decoding, the meaningful English sentence makes the intended choice obvious, and rebuilding the Huffman codes from that plaintext reproduces the printed values exactly. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

1. Reverse create_huffman_codes() and the heap helper functions.
2. Notice that the program prints integer-valued codes, not lengths.
3. Use the hint I_Like_ to constrain the prefix-free code assignment.
4. Rebuild the exact Huffman tree behavior, including tie-breaking and bit orientation.
5. Decode the full bitstream with the recovered table.
6. Verify by re-encoding the decoded plaintext and checking that all printed integers match.

The decoded plaintext is:

 text read-only • copy allowed Copy
REDACTED

Solver script

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
#!/usr/bin/env python3

codes = {
    'C': '100010', 'I': '000000', 'L': '100011', 'P': '100000', 'R': '100001',
    'S': '100110', 'T': '000001', '_': '001', 'a': '0111', 'c': '11110',
    'd': '00001', 'e': '0001', 'f': '100111', 'g': '01000', 'h': '100100',
    'i': '0101', 'k': '100101', 'm': '11111', 'n': '0110', 'o': '110',
    'p': '111010', 'r': '1010', 's': '1011', 't': '01001', 'u': '111011',
    'y': '11100',
}

bitstream = (
    '0000000011000110101100101000100100000111000110011001001'
    '1110110000111100001100010110111111110101010000110111011'
    '0101110011000100000110010000011101010111000011001111101'
    '0100010000101110100101110011000001010110111100001101110'
    '1101010110010000010111011000001001000000111110111010000'
    '00100110000100011111011001000011001010100101011100110'
)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

trie = {}
for ch, code in codes.items():
    node = trie
    for bit in code:
        node = node.setdefault(bit, {})
    node['ch'] = ch

out = []
node = trie
for bit in bitstream:
    node = node[bit]
    if 'ch' in node:
        out.append(node['ch'])
        node = trie

plaintext = ''.join(out)
print(plaintext)

Running it prints:

 text read-only • copy allowed Copy
REDACTED

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍