Unsettled Huffman
Unsettled Huffman
Platform: volgactf | Category: Steganography | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-03-28 | Status: Solved Techniques: bait_decoy_identification, deflate_block_type_steganography, raw_bitstream_parsing, zip_internal_structure_analysis
Summary
Task: ZIP archive with deflate-compressed PNG that is larger after compression; challenge hints at Huffman/deflate. Solution: parse raw deflate bitstream, extract block type (stored=1, fixed Huffman=0) from each of 435 blocks, decode bits as ASCII to recover the flag.
Unsettled Huffman — VolgaCTF 2026
Description
What a strange archive! Why would anyone want to deflate the contents, it makes no sense at all!..
Given a unsettled_huffman.zip archive containing a single file not_flag.png (~16MB). The ZIP uses deflate compression (method=8), but the compressed stream (16,252,680 bytes) is actually larger than the uncompressed file (15,903,404 bytes). The challenge title "Unsettled Huffman" and the description's emphasis on "deflate" hint that the steganography is embedded in the compression layer itself.
Analysis
Initial Triage
The extracted not_flag.png is a legitimate 2310×2310 RGB PNG image. Standard stego checks (exiftool, strings, binwalk, zsteg) reveal nothing hidden in the image data itself. However, the image visually contains the text:
VolgaCTF{TH1S_I$_NOT_THE_FL4G_I_PROMIS3}
This is a bait/decoy flag — a red herring designed to waste time.
Compression Anomaly
The key anomaly is that the ZIP's deflate compression expanded the file rather than compressing it:
- Compressed: 16,252,680 bytes
- Uncompressed: 15,903,404 bytes
- Ratio: ~102% (negative compression)
PNG files are already compressed internally, so deflating them typically yields no benefit. But a legitimate compressor would simply use stored blocks (btype=0) for the entire file. The fact that the compressor alternates between block types suggests intentional manipulation.
Deflate Stream Structure
A custom deflate parser was written to analyze the raw compressed bitstream extracted from the ZIP local file header. The parser revealed:
- 435 total deflate blocks (extremely unusual for a single file)
- Only two block types used:
btype=0— stored blocks (raw data, no compression)btype=1— fixed Huffman blocks (standard static Huffman trees)btype=2— never used (no dynamic Huffman trees at all)
A normal deflate compressor would not alternate between stored and fixed Huffman blocks hundreds of times. The block type choices are the steganographic channel.
Encoding Scheme
The encoding maps each block's type to a single bit:
btype=0(stored block) → bit 1btype=1(fixed Huffman block) → bit 0
Reading the 435 block-type bits in order and grouping them MSB-first into 8-bit bytes produces printable ASCII text. The decoded message is the flag, followed by 0xff padding bytes to fill the remaining blocks.
Solution
Step 1: Extract the Raw Deflate Stream
Locate the compressed data in the ZIP file by parsing the local file header:
python read-only • copy allowedimport struct with open("unsettled_huffman.zip", "rb") as f: blob = f.read() # Parse ZIP local file header name_len, extra_len = struct.unpack_from("<HH", blob, 26) comp_size = struct.unpack_from("<I", blob, 18)[0] start = 30 + name_len + extra_len data = blob[start : start + comp_size]
Step 2: Parse Deflate Blocks and Extract Block Types
Use a custom bitstream reader to parse each deflate block header and record the btype field:
python read-only • copy allowedclass BitReader: def __init__(self, data): self.data = data self.pos = 0 self.bitbuf = 0 self.bitcnt = 0 def readbits(self, n): while self.bitcnt < n: if self.pos >= len(self.data): raise EOFError("unexpected end of deflate stream") self.bitbuf |= self.data[self.pos] << self.bitcnt self.pos += 1 self.bitcnt += 8 out = self.bitbuf & ((1 << n) - 1) self.bitbuf >>= n self.bitcnt -= n return out def align_byte(self): self.bitbuf = 0 self.bitcnt = 0
Step 3: Walk All Blocks and Collect Block Types
python read-only • copy allowedbr = BitReader(data) btypes = [] while True: bfinal = br.readbits(1) btype = br.readbits(2) btypes.append(btype) if btype == 0: # Stored block: align to byte boundary, read length, skip data br.align_byte() ln = br.readbits(16) nln = br.readbits(16) for _ in range(ln): br.readbits(8) elif btype == 1: # Fixed Huffman block: decode using standard tables until end-of-block (256) # ... (full Huffman decoding logic) pass elif btype == 2: # Dynamic Huffman block: parse custom trees, then decode # ... (full dynamic tree parsing + decoding) pass if bfinal: break
Step 4: Decode Block Types to ASCII
python read-only • copy allowed# Map: stored (btype=0) -> bit 1, fixed Huffman (btype=1) -> bit 0 bits = [1 if bt == 0 else 0 for bt in btypes] # Group into bytes (MSB first) and decode message = [] for i in range(0, len(bits) - 7, 8): byte_val = 0 for j in range(8): byte_val = (byte_val << 1) | bits[i + j] if byte_val == 0xff: break # padding reached message.append(chr(byte_val)) flag = "".join(message) print(flag) # VolgaCTF{REDACTED}
Full Solver Script
python read-only • copy allowed#!/usr/bin/env python3 """ Unsettled Huffman — VolgaCTF 2026 Extracts flag hidden in deflate block type choices within a ZIP file. """ import struct from collections import Counter class BitReader: def __init__(self, data): self.data = data self.pos = 0 self.bitbuf = 0 self.bitcnt = 0 def readbits(self, n): while self.bitcnt < n: if self.pos >= len(self.data): raise EOFError("unexpected end of deflate stream") self.bitbuf |= self.data[self.pos] << self.bitcnt self.pos += 1 self.bitcnt += 8 out = self.bitbuf & ((1 << n) - 1) self.bitbuf >>= n self.bitcnt -= n return out def align_byte(self): self.bitbuf = 0 self.bitcnt = 0 def revbits(code, n): out = 0 for _ in range(n): out = (out << 1) | (code & 1) code >>= 1 return out def build_huffman(lengths): maxbits = max(lengths) if lengths else 0 bl_count = [0] * (maxbits + 1) for ln in lengths: if ln: bl_count[ln] += 1 next_code = [0] * (maxbits + 1) code = 0 for bits in range(1, maxbits + 1): code = (code + bl_count[bits - 1]) << 1 next_code[bits] = code table = {} for symbol, ln in enumerate(lengths): if not ln: continue code = next_code[ln] next_code[ln] += 1 table[(revbits(code, ln), ln)] = symbol return table, maxbits def decode_symbol(br, table, maxbits): code = 0 for n in range(1, maxbits + 1): code |= br.readbits(1) << (n - 1) key = (code, n) if key in table: return table[key] raise ValueError("invalid huffman code") def fixed_trees(): litlen = [] for i in range(288): if i <= 143: litlen.append(8) elif i <= 255: litlen.append(9) elif i <= 279: litlen.append(7) else: litlen.append(8) dist = [5] * 32 return build_huffman(litlen), build_huffman(dist) LEN_BASE = [3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43,51,59,67,83,99,115,131,163,195,227,258] LEN_EXTRA = [0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0] DIST_BASE = [1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577] DIST_EXTRA = [0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13] def main(): with open("unsettled_huffman.zip", "rb") as f: blob = f.read() name_len, extra_len = struct.unpack_from("<HH", blob, 26) comp_size = struct.unpack_from("<I", blob, 18)[0] start = 30 + name_len + extra_len data = blob[start : start + comp_size] br = BitReader(data) btypes = [] while True: bfinal = br.readbits(1) btype = br.readbits(2) btypes.append(btype) if btype == 0: br.align_byte() ln = br.readbits(16) nln = br.readbits(16) for _ in range(ln): br.readbits(8) elif btype in (1, 2): if btype == 1: (ltable, lmax), (dtable, dmax) = fixed_trees() else: # Dynamic trees (not used in this challenge but included for completeness) raise NotImplementedError("dynamic trees not expected") while True: sym = decode_symbol(br, ltable, lmax) if sym < 256: pass elif sym == 256: break else: idx = sym - 257 length = LEN_BASE[idx] + br.readbits(LEN_EXTRA[idx]) dsym = decode_symbol(br, dtable, dmax) dist = DIST_BASE[dsym] + br.readbits(DIST_EXTRA[dsym]) if bfinal: break # Decode: stored (btype=0) -> 1, fixed Huffman (btype=1) -> 0 bits = [1 if bt == 0 else 0 for bt in btypes] message = [] for i in range(0, len(bits) - 7, 8): byte_val = 0 for j in range(8): byte_val = (byte_val << 1) | bits[i + j] if byte_val == 0xFF: break message.append(chr(byte_val)) print(f"Blocks: {len(btypes)}") print(f"Block type distribution: {Counter(btypes)}") print(f"Flag: {''.join(message)}") if __name__ == "__main__": main()