A Security Evaluation of Whitenoise

David A. Wagner

TL;DR

In this 2003 report, renowned cryptographer David Wagner evaluates the "Whitenoise" stream cipher and finds it remarkably resilient against standard cryptanalytic attacks. By combining multiple secret-length subkeys with a nonlinear substitution step, the cipher maintains a massive internal state and a high margin of safety, making it a serious candidate for both cryptographic and high-performance statistical applications.

What Problem Does This Paper Address?

The paper provides an independent security audit of a then-new stream cipher called Whitenoise (specifically the "Tinnitus" instantiation), developed by BSB Utilities Inc.

In the world of cryptography, the "canon" dictates that no algorithm should be trusted until it has been poked, prodded, and analyzed by the community. Wagner’s goal was to determine if Whitenoise could provide confidentiality protection against the "big three" attack models:

  1. Ciphertext-only: The attacker only sees the encrypted data.
  2. Known-plaintext: The attacker has pairs of original and encrypted data.
  3. Chosen-plaintext: The attacker can choose what data gets encrypted.

The challenge was to see if this specific design—which relies on XORing multiple subkeys of varying lengths—could stand up to modern mathematical "shortcut" attacks that often break simpler stream ciphers.

Methods

Wagner performed a "limited time analysis" using several standard and advanced cryptanalytic techniques:

  • Linear Complexity Analysis: Using the Berlekamp-Massey algorithm to see if the keystream could be reconstructed via linear feedback shift registers (LFSRs).
  • Correlation Attacks: Checking for statistical leaks between the inputs and outputs of the cipher's nonlinear components.
  • Linearization: Attempting to turn the cipher's logic into a system of linear equations (inspired by Coppersmith’s work) to solve for the secret key.
  • Statistical Bias Analysis: Examining the key setup procedure for inherent biases that might give an attacker a foothold.

Datasets

Not discussed in the paper. As this is a theoretical security evaluation of a cryptographic primitive, it does not use external datasets. The "data" consists of the mathematical specifications of the Whitenoise algorithm itself.

Key Insights and Ideas

  • The Power of the "SuperKey": Whitenoise generates a "SuperKey" by XORing together between 50 and 99 subkeys ($s^{(i)}$). Because each subkey has a different, secret prime length, the resulting period of the keystream is astronomical (at least $2^{303}$).
  • Nonlinearity is the Shield: The cipher applies a nonlinear substitution box ($S[]$) to the SuperKey before XORing it with the plaintext. Wagner notes that without this S-box, the system would be trivial to break using Berlekamp-Massey. The S-box effectively "hides" the linear structure of the subkeys.
  • Secret Lengths as a Defense: A key finding is that many attacks (like linearization) fail because the lengths of the subkeys are themselves secret and key-dependent. An attacker would have to guess from roughly $2^{150}$ possible length combinations to even begin certain attacks.
  • Massive Internal State: The system boasts an internal state of approximately 320,000 bits. For context, most modern ciphers like AES-128 use only 128 bits of state. This makes "divide-and-conquer" attacks—where an attacker guesses part of the state—completely infeasible.

Key Results

  • Exhaustive Search Resistance: With a 1600-bit minimum key size, the probability of a brute-force attack succeeding is roughly $1/2^{1340}$, which Wagner describes as "unimaginably small."
  • Linear Complexity: Wagner estimates the linear complexity of the keystream to be at least $2^{100}$, meaning an attacker would need an astronomical amount of known plaintext to reconstruct the cipher.
  • Performance Potential: While not a formal benchmark, Wagner estimates the cipher could run at 5–10 clock cycles per byte on 32-bit processors. This puts it in the same performance ballpark as RC4 and faster than block ciphers like 3DES.
  • Security Verdict: The cipher resisted every attack method Wagner could conceive, suggesting a very large "margin of safety."

Limitations and Future Work

  • Key Setup Bias: Wagner identified a slight statistical bias in how the S-box is generated (specifically when handling duplicate values). While he couldn't exploit it, he recommended switching to a "fair shuffling" algorithm (like the Fisher-Yates shuffle) to eliminate the bias.
  • Implementation Blindspot: The report only evaluates the mathematical algorithm. It does not cover "side-channel attacks" (like measuring power consumption or timing) that might occur in a real-world hardware or software implementation.
  • Call for Vetting: Wagner emphasizes that this is a "first step." He concludes that while Whitenoise is a "serious candidate," it requires further scrutiny from the broader security community before it should be deployed in critical systems.

Summary updated

Abstract

This report studies the security of Whitenoise, a stream cipher invented by BSB Utilities Inc. http://bsbutil.com "Even if we hypothesized the existence of some magic computer that could test a trillion trillion key trials per second (very unlikely!), and even if we could place a trillion trillion such computers somewhere throughout the universe (even more unlikely!), and even if we were willing to wait a trillion trillion years (not a chance!), then the probability that we would discover the correct key would be negligible (about (1/2)^1340, which is unimaginably small)."
BibTeX
@article{wagner2003security,
  author = {David A. Wagner},
  title = {{A Security Evaluation of Whitenoise}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2003},
  url = {https://openreview.net/forum?id=rB127AGmjb},
}
Figure