Lion Cipher Lab
Build Huffman coding from scratch, and measure it against the entropy bound
- Foundations
- Intermediate
- ~75 min
- Free · no account required
Why it matters
Entropy shows up all over security tooling. Ransomware detectors flag files that 'look encrypted'. Exfiltration hunts flag payloads that 'look random'. Malware triage flags sections that 'look packed'. Most of that tooling uses one number, and most people who read it could not say what the number measures or when it lies. This lab fixes that by building the thing the number describes. Shannon's entropy is a floor: the fewest bits per byte any coder could reach if all it knows is how often each byte appears. Huffman coding is the classic way to get close to that floor. Your coder will land…
What you'll learn
- computing byte-level Shannon entropy and reading it as a floor: app.log scored 4.9689 bits/byte, so no coder that only counts bytes can shrink it below about 155,436 of its 250,254 bytes
- building a Huffman coder from scratch with Python's heapq: merge the two rarest subtrees until one is left, and every merge adds one bit to the codes beneath it
- turning code lengths into canonical codes exactly as DEFLATE does (RFC 1951 section 3.2.2), so a 264-byte header of lengths is enough for the decoder, and proving all 9 inputs round-trip byte for byte
- measuring the theory: Huffman landed 0.022 bits/byte above the entropy floor on app.log and 0.046 on data.csv, always inside the 1-bit guarantee
- showing why order-0 entropy is not the limit for real compressors: zlib took app.log to 1.013 bits/byte and lzma to 0.855, against an order-0 floor of 4.969
- proving Huffman cannot help random data: random.bin grew from 100,000 to 100,264 bytes because every code was exactly 8 bits and the header still costs 264 bytes
- testing an 'entropy means encrypted' rule and finding its failures: it flagged all 5 compressed files as encrypted; adding magic bytes and a chi-square test fixed most of that but still missed Base64-wrapped ciphertext (entropy 5.9998) and the body of an xz file (chi-square 264.0)
- measuring why you compress BEFORE you encrypt: compress-then-encrypt gave 12.67% of the original size, encrypt-then-compress gave 100.03%
Steps in this lab
- What you are building, and what a bit of information is
- Set up: Python, a terminal, and a lab folder
- Make the test inputs (all local, mostly seeded)
- Measure entropy, and read it as a floor
- Build the Huffman tree with a heap
- Canonical codes, a 264-byte header, bit packing, and a decoder
- Huffman vs the entropy floor vs real compressors
- Honest negatives: random data, small files, and a biased H1
- 'High entropy' is a weak signal for 'encrypted' -- measured
- Compress BEFORE you encrypt, never after (and the one exception to know)
- Do it better: how to use entropy like a pro, then clean up