Understanding Random Bitstreams: IID vs. Non-IID Analysis & Entropy Loss

How do we know that the AES key we are generating actually has 256 bits of true randomness?

These past weeks I have been diving deeper into the underlying mathematics to answer this fundamental question about physical entropy sources. One of the central aspects of entropy validation is determining whether the digitized bitstream is truly Independent and Identically Distributed (IID). If an engineer incorrectly estimates this characteristic, the security repercussions can be catastrophic.

1. Hardware Transduction Deviations & Non-IID Behavior

In physical random number generators, the digitized output is frequently influenced by environmental characteristics—such as ambient temperature drift, diurnal fluctuations, or power supply ripple. If a physical sensor exhibits positive autocorrelation, consecutive digitized readings become temporally coupled.

Examining empirical metrics captured from 1,000,000 physical samples partitioned into 64 discrete bins demonstrates how non-IID properties manifest:

• Autocorrelation (Temporal Memory): Lag-1 correlation ${\rho }_1=+0.6012$ and Lag-2 correlation ${\rho }_2=+0.4185$. Consecutive symbols carry strong statistical memory of previous states.
• Sample Variance Over-Dispersion: Observed variance ${\sigma }^2=68.42$ versus an ideal baseline of $42.50$, showing significant over-dispersion relative to an ideal Poisson process.
• Power Spectral Density (PSD): A distinct 24-hour diurnal peak, proving environmental modulation of the physical entropy harvester.

2. The Flawed Independent (IID) Assumption

When developers assume a bitstream is IID without verifying temporal independence, they evaluate min-entropy using the unconditional Most Common Value (MCV) estimator defined in NIST SP 800-90B:

Under this naive IID model:

1. Peak Probability: Measured peak probability across 64 bins is $P_{\text{max}}=0.0800$.
2. Unconditional Min-Entropy:
   H_{∞, IID} = −log₂(P_max) = −log₂(0.0800) ≈ 3.6438 bits / sample
3. Claimed Total Entropy: To extract 256 bits of security, the system samples 71 values:
   71 samples × 3.6438 bits/sample = 258.71 total bits
4. The False Conclusion: The engineering team assumes the resulting AES key requires a brute-force search space of $2^{256}$ operations, completely ignoring temporal persistence.

3. Markov Chain Modeling & Search Space Collapse

An attacker inspecting the physical data source will test for correlation. By modeling the bitstream as a first-order Markov chain, the attacker conditions their estimation on the preceding symbol:

Because consecutive states are coupled, knowledge of symbol $C_{t-1}$ drastically concentrates the probability distribution of symbol $C_t$:

The true conditional min-entropy collapses from 3.6438 bits down to:

Across the 71 collected samples, the real accumulated min-entropy is not 258.71 bits, but:

The Real Problem: The adversary does not need to search $2^{256}$ states. By exploiting the Markov transition matrix of the hardware sensor, the effective search space collapses to $2^{93.8}$ operations—bringing key recovery well within the threshold of specialized distributed compute or FPGA clusters.

Original discussion and slides published on LinkedIn.