23. Information Theory

Level: Expert You'll use this for: password/key entropy, compression limits, ML loss functions, and network channel capacity.

Shannon entropy — quantifying uncertainty/information

H(X) = -Σ p(x) · log2(p(x))

Entropy measures, in bits, the average "surprise" of a random variable. A fair coin has H = 1 bit (maximally uncertain). A coin that always lands heads has H = 0 bits (no uncertainty, no information gained by observing it).

import numpy as np

def entropy(probs):
    probs = np.array(probs)
    probs = probs[probs > 0]   # avoid log(0)
    return -np.sum(probs * np.log2(probs))

entropy([0.5, 0.5])          # 1.0 bit  -- fair coin
entropy([0.99, 0.01])        # 0.08 bits -- barely any uncertainty
entropy([0.25]*4)            # 2.0 bits  -- uniform over 4 outcomes

Computing entropy([0.25]*4) by hand — a fair 4-sided die, each face equally likely:

H = -Σ p(x)·log2(p(x))

  = -(0.25·log2(0.25)) × 4 terms, since all 4 probabilities are equal

  log2(0.25) = log2(1/4) = -2      (2^-2 = 0.25)

  each term: -(0.25 × -2) = 0.5
  sum over 4 outcomes: 0.5 × 4 = 2.0 bits

Sanity check against Ch. 5: a uniform choice among 4 outcomes needs exactly log2(4) = 2 bits to identify which one occurred — entropy for a uniform distribution always equals log2(number of outcomes), which is why the fair-coin case above gives exactly log2(2) = 1 bit.

Password entropy — the direct security application

If a password is drawn uniformly at random from a keyspace of size N, its entropy is log2(N) bits. This is the correct, rigorous way to quantify password strength — not "has a symbol and a number."

import math
def password_entropy_bits(alphabet_size, length):
    return length * math.log2(alphabet_size)

print(password_entropy_bits(26, 8))    # lowercase, 8 chars: 37.6 bits
print(password_entropy_bits(95, 16))   # full ASCII printable, 16 chars: 105.2 bits
print(password_entropy_bits(2048, 6))  # 6-word Diceware passphrase (2048-word list): 66 bits

Why a 6-word Diceware passphrase (66 bits) can beat an 8-character "complex" password (~38–52 bits depending on charset assumptions): entropy is about the size of the space an attacker must search, not surface complexity — length from a large-but-memorable word list often wins.

Cross-entropy and KL divergence, formally

Cross-entropy: H(p, q) = -Σ p(x)·log2(q(x))
KL divergence: D_KL(p || q) = H(p, q) - H(p) = Σ p(x)·log2(p(x)/q(x))

KL divergence measures how different distribution q is from p — it's not symmetric (D_KL(p||q) ≠ D_KL(q||p)), which matters: it means "how surprised is a model expecting q, when reality is p" is a directional question. This exact quantity is the loss function minimized during classifier training (Ch. 22) and is used in diffusion models, variational autoencoders (VAEs), and reinforcement learning (e.g., PPO's KL penalty term that keeps policy updates from moving too far in one step).

Mutual information — for feature selection

I(X;Y) = H(X) - H(X|Y)

"How many bits of uncertainty about X are removed once you know Y." Used directly in ML feature selection: pick the features with the highest mutual information with the target label — i.e., the features that are actually informative, beyond simple correlation (mutual information captures non-linear relationships that correlation coefficients miss).

Shannon-Hartley theorem — the hard limit on channel capacity

C = B · log2(1 + S/N)

C = maximum error-free channel capacity (bits/sec), B = bandwidth (Hz), S/N = signal-to-noise ratio. This is a hard physical limit — no amount of clever engineering can transmit faster than this over a given channel with a given noise level. It's why increasing Wi-Fi throughput requires either more bandwidth (wider channels, Ch. 27) or better SNR (closer to the router, less interference), and it directly explains why "5G is faster" partly comes down to using wider channels and better modulation to approach this Shannon limit more closely.

import math
def shannon_capacity(bandwidth_hz, snr_db):
    snr_linear = 10 ** (snr_db / 10)
    return bandwidth_hz * math.log2(1 + snr_linear)

print(shannon_capacity(20_000_000, 30))  # 20 MHz channel, 30dB SNR -> bits/sec

So 20 MHz × 9.97 ≈ 199 Mbit/s is the ceiling for that channel. Ch. 27 shows how Wi-Fi 6 gets close to it.

Entropy, symbol by symbol, and why the log

H(X) = -Σₓ p(x) · log₂ p(x)  =  Σₓ p(x) · log₂(1 / p(x))

Why a logarithm? We want the information from two independent events to add. Their probabilities multiply, p(x,y) = p(x)·p(y), and only the log turns products into sums (Ch. 5). Shannon proved that, up to the choice of base, -log p is the only function with that property and a few other natural ones.

Min-entropy: the entropy that matters for keys

Shannon entropy is an average. An attacker doesn't care about averages. They try the most likely value first. The right measure for guessing attacks is min-entropy:

H∞(X) = -log₂( maxₓ p(x) )

The two can be wildly different. Take a password generator that outputs "password1" half the time and otherwise picks uniformly from 2²⁰ random strings:

Shannon:      H  = 0.5·log₂(2) + 0.5·log₂(2·2²⁰) = 0.5·1 + 0.5·21 = 11 bits
Min-entropy:  H∞ = -log₂(0.5)                                     =  1 bit

"11 bits" sounds respectable, but an attacker wins half the time on the first guess. Real data: if 1% of users pick 123456, a breached password database has at most -log₂(0.01) ≈ 6.6 bits of min-entropy for the most exposed accounts, whatever its average entropy is. That's why NIST's randomness-source standard (SP 800-90B) and key-derivation proofs are stated in min-entropy, and why credential-stuffing attackers use breach-frequency lists instead of brute force.

Source coding: entropy is the compression limit

Theorem (Shannon's source coding theorem, 1948). No lossless code can use fewer than H(X) bits per symbol on average, and a code exists that uses fewer than H(X) + 1.

Huffman coding by hand. Symbols with probabilities A: 0.5, B: 0.25, C: 0.125, D: 0.125. Repeatedly merge the two least likely nodes:

merge C(0.125) + D(0.125) -> CD(0.25)
merge B(0.25)  + CD(0.25) -> BCD(0.5)
merge A(0.5)   + BCD(0.5) -> root(1.0)

Read the codes off the tree (left = 0, right = 1):
A = 0     B = 10     C = 110     D = 111

average length = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 bits
entropy H      = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 bits   <- optimal, exactly at the limit

A naive fixed-width code needs 2 bits per symbol, so Huffman saves 12.5% here by giving short codes to common symbols. No code is a prefix of another, so the bitstream decodes unambiguously. The Kraft inequality, Σ 2^(-ℓᵢ) ≤ 1, is the condition for code lengths ℓᵢ to allow such a prefix code: 2⁻¹ + 2⁻² + 2⁻³ + 2⁻³ = 1 ✓. DEFLATE (gzip, PNG, HTTP compression) uses Huffman, and zstd and Brotli use the closely related arithmetic/ANS coders, which can get even closer to H.

Security in the wild: compression is a side channel

Compression works by finding repeats (low entropy). So the compressed length leaks how much of the data repeats. If a response contains both a secret (a session cookie or CSRF token) and text the attacker controls, the attacker can guess the secret one character at a time:

secret in the page:   token=7f3a...
attacker injects:     token=7     -> repeats the secret's first char  -> compresses SMALLER
attacker injects:     token=8     -> no repeat                         -> compresses larger

Each length difference confirms one character, so a 32-character token falls in a few thousand requests. This is CRIME (2012, TLS compression, which is why TLS compression was disabled everywhere) and BREACH (2013, HTTP-level gzip). Encryption hides content but not length, and the length here carries information. Mitigations reduce the mutual information (Ch. 23 above) between the secret and the observable length: never compress secrets alongside attacker input, mask tokens with a fresh random value each response, or pad lengths.

Real-life engineering ties

• Security: rigorous password/key entropy calculation (above); also the theoretical basis for evaluating whether a random number generator is producing enough real entropy (/dev/random blocking behavior on Linux exists precisely because of this concern).
• AI: cross-entropy loss (classification), KL divergence (VAEs/diffusion/RLHF), mutual information (feature selection, information bottleneck theory of deep learning).
• Network: Shannon-Hartley is the fundamental ceiling for every wireless and wired link capacity planning exercise (Ch. 25, 27).
• SWE: compression algorithms (gzip, Huffman coding) are literally bounded by the source's entropy — you cannot losslessly compress random (maximum-entropy) data, which is why compressing already-compressed or already-encrypted data does nothing.

More real-life examples:

• The Electronic Frontier Foundation publishes a curated 7,776-word Diceware wordlist specifically so people can generate the kind of high-entropy, memorable passphrases calculated in this chapter using physical dice rolls.
• Linux's /dev/random and /dev/urandom are built around entropy estimation — the kernel tracks how many bits of real-world unpredictability (keyboard timing, disk timing, interrupts) have accumulated, directly applying Shannon entropy to decide whether output is safe for cryptographic keys.
• "Zip bomb" files (a small compressed file that expands to petabytes) exploit extremely low-entropy, highly repetitive data — since compression is bounded by source entropy, and repetitive data has almost none, it compresses (and decompresses) at an extreme ratio, which attackers weaponize as a denial-of-service payload.
• Shannon's 1948 source coding theorem set the theoretical best-possible compression ratio for a given data source decades before formats like gzip, Zstandard, or Brotli were built to approach that limit.

Common mistake

Treating password "complexity rules" (must have 1 uppercase, 1 digit, 1 symbol) as equivalent to high entropy — such rules often reduce the effective keyspace (everyone puts the digit at the end, the symbol is almost always !), producing lower real entropy than the naive log2(N^L) calculation suggests. Real-world password entropy is lower than theoretical entropy because human choices aren't uniformly random.