No Spook Leaves Randomness to Chance

No Spook Leaves Randomness to Chance

Speakers: Shaanan Cohney, Academic researcher, University of Melbourne

Conference: DEF CON

YouTube: https://www.youtube.com/watch?v=OYGtNa0pJec

Overview

In "No Spook Leaves Randomness to Chance," Shaanan Cohney, an academic researcher at the University of Melbourne, delves into the elusive question of how state-level adversaries, such as the NSA, manage to decrypt encrypted traffic at scale. Moving beyond common theories like brute-forcing or widespread hardware implants, Cohney presents a compelling argument that a significant vector for mass decryption lies in the subversion of cryptographic standards and the accompanying certification processes. His research, spanning over 15 years and involving a global team, meticulously dissects instances where seemingly subtle design choices or implementation guidance within official standards have introduced systemic weaknesses, which can then be exploited by sophisticated attackers.

The talk highlights how these vulnerabilities, often exacerbated by opaque vendor implementations, create a "pre-supply chain" attack surface that compromises security long before a product even reaches deployment. Cohney illustrates this through detailed analyses of several standardized pseudo-random number generators (PRNGs), exposing critical flaws that allowed for the recovery of cryptographic keys and the decryption of live traffic. This deep dive into the practical exploitation of standards-level weaknesses offers a stark reminder that the security of our digital communications is not solely dependent on the strength of algorithms, but equally on the integrity of the design and standardization ecosystem.

Ultimately, Cohney's presentation serves as a crucial wake-up call for the cybersecurity community, urging a re-evaluation of how we perceive and trust standardized cryptography. It underscores that the battle for secure communications extends beyond mathematical proofs and into the political and procedural realms of standards bodies, where subtle influences can have profound and far-reaching security implications, often enabling mass surveillance capabilities that are otherwise considered technologically infeasible.

Background

▶ Watch: How NSA and state adversaries break crypto (0:30)

The motivating question behind Cohney's extensive research is the persistent mystery of how state-level adversaries, particularly the NSA, achieve large-scale decryption of encrypted traffic. Traditional explanations, such as brute-forcing modern ciphers like AES-128 or AES-256, are widely considered implausible due to the immense computational resources required. Similarly, while targeted hardware implants (as revealed in the Snowden slides) exist, they don't fully explain the presumed scale of mass interception and decryption. The "AI mumbo jumbo" theory is quickly dismissed as even less likely. Cohney posits that the truth is a mix, but emphasizes a less glamorous, more systemic approach: targeting the fundamental building blocks of cryptography, specifically randomness.

Cryptographic protocols rely heavily on random number generators (RNGs) for key exchange, digital signatures, and nonces. The security of these protocols is "fundamentally reliant on the unguessability of these random values." If there's a systemic flaw in how these random numbers are generated, it could open a pathway for adversaries to predict values and decrypt traffic at scale. The challenge arises because true random number generators (TRNGs), which leverage quantum mechanical fluctuations, are often expensive and not available in commodity hardware like smartphones. Consequently, most systems rely on pseudo-random number generators (PRNGs), which gather entropy from various sources (e.g., keyboard timings, boot time) and mix it using a whitening function to produce seemingly random outputs.

The critical target for subversion, Cohney argues, is standardized designs of PRNGs. Standards are attractive targets because industry adopts them widely for product design due to financial incentives and regulatory requirements. Compromising a standard can thus compromise a vast array of products. In the US, the Federal Information Processing Standards (FIPS), particularly the FIPS 140-x series (e.g., FIPS 140-2, now 140-3), are paramount. The associated Cryptographic Module Verification Program (CMVP) certifies products for procurement by the US federal government. This creates a powerful incentive for vendors like Juniper and Cisco to maintain FIPS-compliant modes in their products, even if it means supporting designs they might otherwise question. When FIPS mode is enabled, it mandates the use of FIPS-approved algorithms for all system functions, including RNGs, making these standardized components critical chokepoints for potential compromise.

Key Findings

▶ Watch: Randomness: The critical foundation of crypto security (4:20)

Shaanan Cohney's research uncovers several critical findings regarding the subversion of cryptographic standards and their implications for large-scale decryption:

1. Systemic Flaws in Standardized PRNGs: Cohney meticulously details how specific designs within FIPS-approved standards contained inherent cryptographic weaknesses.

• ANSI X9.31: This early FIPS-approved generator was found to be invertible if the internal key was known, allowing prediction of future outputs. Crucially, the standard offered "sum total of the guidance about the key" – no explicit requirement for dynamic generation, leading to widespread hardcoding.
• Counter DRBG (NIST SP800-90A): While an evolution of X9.31, it suffered from two key issues: the ability to generate arbitrary amounts of output under the same key before rotation, and the optional nature of "additional entropy," which many manufacturers simply omitted. This again led to deterministic output and vulnerability to state recovery.
• Dual EC DRBG (NIST SP800-90A): The most notorious example, known for its potential backdoor. Early distinguishing attacks and later demonstrations by Shumow and Ferguson showed how specific curve parameters could enable passive decryption. The Snowden slides later suggested NSA involvement in its standardization.

1. Prevalence of Implementation Errors and Opaque Practices: The effectiveness of standards-level flaws was amplified by poor vendor implementations.

• Hardcoded Keys: Cohney found 12 FIPS 140-2 certified devices that hardcoded the ANSI X9.31 key, often directly from test vectors. This was exemplified by FortiOS v4, which used the exact test vector key, enabling straightforward key recovery and TLS decryption.
• Optional Entropy Omission: Many Counter DRBG implementations neglected to incorporate additional entropy, rendering them deterministic and vulnerable.
• Chaining and Exposure Flaws: The Juniper ScreenOS incident revealed how an adversary (initially suspected to be NSA, later identified as a Chinese APT) subtly altered code over time. This involved first chaining Dual EC with ANSI X9.31, then removing the X9.31 chaining, and finally exposing raw Dual EC output, along with producing more bytes than necessary for nonces, making passive decryption viable.

1. The "Pre-Supply Chain Operation" (PsyCO) Model: Cohney introduces the concept of PsyCO, a broader attack vector than traditional supply chain attacks. Instead of implanting hardware or software after implementation, PsyCO targets earlier stages:

• Concept and Design: Influencing initial product design through regulatory and standardization requirements.
• Standardization: Mandating design flaws (e.g., DES key length), introducing known weaknesses through parameter choices (e.g., Dual EC curve points, Diffie-Hellman groups in RFC 5114), or introducing intentional complexity.
• Certification: Excluding critical aspects from the threat model (e.g., side channels in FIPS 140-2), making products weaker.

1. Broader Applicability Beyond RNGs: The PsyCO model extends to other cryptographic areas:

• Lightweight Ciphers (Simon and Spec): Proposed by the US, these designs lacked parameter explanations and were pushed through ISO with procedural weirdness, nearly succeeding despite academic warnings.
• Export-Grade Cryptography: Mandated weaker key lengths led to downgrade attacks like DROWN, affecting 7% of Alexa top 1 million sites.
• Diffie-Hellman Groups (RFC 5114): Standardized groups enabled precomputation attacks like Logjam on 1024-bit groups.
• TETRA Radio Encryption Standard: Critical design flaws (TEA1, TEA3) reduced key strength from 80 bits to laptop-breakable levels.

1. The "A-hole Attack" and Standardization Dynamics: Cohney observes that standardization committees, relying on good faith, can be manipulated by adversarial behavior. Intentionally disruptive or non-cooperative individuals can deter participation, influencing outcomes. The openness of processes (e.g., IETF vs. ISO) significantly impacts their susceptibility to these attacks.

1. Certification is Not an Audit, Standardization is Not Security: A crucial takeaway is that FIPS certification does not equate to a thorough security audit by crypto experts. Similarly, using a standardized algorithm does not guarantee robust security, especially if implementations are flawed. Real-world attacks often require the "tragic intersection" of both standards corruption and substantial implementation flaws.

Technical Deep Dive

▶ Watch: Systemic RNG flaws enable decryption at scale (5:00)

The core of Cohney's argument rests on a detailed examination of how specific cryptographic standards for pseudo-random number generators (PRNGs) were designed, implemented, and ultimately exploited.

ANSI X9.31 DRBG: The Hardcoded Key Vulnerability

The ANSI X9.31 generator was one of the earliest PRNGs included in FIPS standards. Its design is relatively straightforward:

1. Entropy Source: Primarily uses the system time.
2. Mixing Function: A block cipher (initially DES, later AES) is used with a secret key K.
3. State Update: The current time T is XORed with the previous state, then encrypted with the block cipher using key K to produce a new state. This new state is then XORed with the time again and encrypted to produce the random output.

The critical vulnerability arises from the invertibility of the block cipher. If an attacker knows the key K and can capture the output of the random number generator, they can effectively run the process backward. The standard's guidance on K was minimal: "for a 128-bit key, let K be a 128-bit key. This key K is reserved only for the generation of pseudo-random numbers." This lack of specification regarding dynamic key generation led many implementers to hardcode the key directly into firmware or binaries.

Cohney's team systematically reviewed CMVP certificates and reverse-engineered devices. They discovered 12 different certified products that hardcoded K. A prime example was FortiOS v4, where the hardcoded key was found to be identical to the test vector key provided in the ANSI X9.31 standard itself. This meant a publicly available key was being used in certified, deployed devices.

With the key known, the attack proceeds:

1. Capture Output: Intercept the raw output of the random number generator (e.g., the server random in a TLS handshake).
2. Invert AES: Since AES is invertible with the key K, the attacker can reverse the encryption steps to recover the state XORed with the timestamp.
3. Guess Timestamp: System timestamps, especially on older systems, have relatively low entropy (e.g., 32-bit values related to boot time). Cohney estimated this at roughly 2^28 bits of entropy, which is "crackable on a standard laptop."
4. Verify: A guessed timestamp can be verified against subsequent outputs or by attempting to derive the master secret of the TLS handshake.

This attack, requiring approximately 2^25 brute-force work under empirical observation, allowed for the recovery of private keys and decryption of TLS traffic from vulnerable FortiOS v4 devices in the wild.

Counter DRBG: Optional Entropy and Arbitrary Output

The Counter DRBG, standardized in NIST SP800-90A, was designed as a successor to X9.31, aiming to address some of its weaknesses. Key changes included:

• Using an incrementing counter instead of time as input to the block cipher.
• Adding optional support for additional entropy to be mixed into the state over time (e.g., from packet timings).

The generation process involves three steps:

1. Key and Counter Update: The existing key K, incrementing counter C, and any additional entropy E are concatenated and run through AES to produce a new K' and C'.
2. Output Generation: The new K' is used to encrypt C' (and subsequent increments) to produce the random output for the application.
3. Reseed (Optional): The key and counter can be refreshed again after a certain number of outputs or when new entropy is available.

Despite these improvements, two critical design flaws remained:

1. Arbitrary Output Length: The standard allowed an arbitrary amount of random data (e.g., 10 kilobytes) to be generated in the second step using the same key and counter value before the key was rotated.
2. Optional Additional Entropy: Many manufacturers simply did not implement the optional "additional entropy" feature.

These flaws meant that if an attacker could observe a sufficiently large block of output from an implementation lacking additional entropy, the entire sequence would be deterministic from that point. Cohney's team found that FortiOS v5 had switched to this DRBG. While a direct hardcoded key wasn't present, they demonstrated that a side-channel attack could be used to recover the AES key during the second stage of output generation. This allowed for the recovery of long-term client ECDSA secrets. While more complex than the X9.31 attack, it further illustrated how design choices and implementation omissions could create vulnerabilities.

Dual EC DRBG: The Notorious Backdoor and its Repurposing

The Dual Elliptic Curve Deterministic Random Bit Generator (Dual EC DRBG) is perhaps the most infamous example of a potentially backdoored standard. Proposed for NIST SP800-90A in 2004, it faced early scrutiny:

• 2007: Dan Shumow and Niels Ferguson demonstrated a potential backdoor, showing that if an adversary knew the relationship between two specific curve points (P and Q) used in the algorithm, they could predict future outputs.
• 2013: The Snowden slides explicitly mentioned Project Bull Run, stating the NSA's capability to "insert vulnerabilities into commercial encryption systems" and "influence policies, standards and specifications for commercial public key cryptography," strongly implying Dual EC's compromise.

Despite these warnings, Dual EC remained in the NIST standard until 2014. The real-world impact was dramatically revealed in 2015 with the Juniper ScreenOS incident. Juniper disclosed unauthorized changes to their codebase. Cohney's reverse engineering revealed a sophisticated, multi-stage attack:

1. Initial Chaining: ScreenOS was certified to use ANSI X9.31, but it was found to be chaining its output with Dual EC DRBG. Even then, Juniper was using its own curve points, not the potentially backdoored NIST ones.
2. Code Alteration: A patch revealed that someone had changed the curve points used by Dual EC DRBG within ScreenOS. This suggested a party now had knowledge of the backdoor.
3. Exposure of Raw Dual EC Output: Further analysis showed that over time, an adversary removed the ANSI X9.31 chaining, directly exposing the raw Dual EC output. Additionally, ScreenOS was producing more bytes for nonces than strictly required, providing more data for an attacker to work with.

This sequence of events indicated a long-term plan to convert a subtle cryptographic weakness into a viable passive TLS decryption attack. While Cohney's team couldn't decrypt live traffic without knowing the specific backdoor relationship for the altered points, they demonstrated the attack's viability by swapping out points on a controlled device. Critically, subsequent public reporting, corroborated by Cohney's own trusted contacts, indicated that the adversary responsible for modifying Juniper's code and exploiting this backdoor was a Chinese state-sponsored APT, not the NSA. This revealed a chilling reality: a backdoor potentially inserted by one nation-state could be discovered and repurposed by another.

These technical deep dives illustrate Cohney's central thesis: the convergence of flawed standards, lax implementation guidance, and opaque vendor code creates fertile ground for systemic cryptographic compromise, enabling mass surveillance by state-level actors.

Demo / Proof of Concept

▶ Watch: How adversaries encourage broken crypto implementations (5:45)

Shaanan Cohney's research involved several compelling demonstrations and proof-of-concept attacks that moved from theoretical weaknesses to practical decryption capabilities.

For the ANSI X9.31 generator vulnerability, the demonstration was a direct, straightforward attack:

1. Firmware Extraction: Cohney's team obtained a FortiOS v4 device, which was certified under the FIPS 140-2 program. Through reverse engineering of its firmware, they identified the hardcoded key used for the ANSI X9.31 random number generator. Alarmingly, this key was found to be identical to the test vector key published in the standard itself, indicating a lack of care or understanding during implementation.
2. Traffic Interception: The next step involved passively monitoring a TLS flow originating from a vulnerable FortiOS v4 device. In a TLS handshake, the server random value contains raw output from the random number generator.
3. Key Recovery and Decryption: With the hardcoded key in hand, the captured server random was inverted using the known AES key. This operation, combined with a brute-force guess of the timestamp (estimated at 2^25 work based on empirical observation), allowed the recovery of the internal state of the RNG. Once the state was known, all future random numbers generated by the device became predictable. This enabled the team to recover the master secret from the TLS handshake and subsequently decrypt all traffic from the vulnerable host.
4. Internet-Wide Scans: Cohney mentioned performing internet-wide scans to identify other devices in the wild that were vulnerable to this specific attack, demonstrating its broad applicability.

Regarding the Counter DRBG vulnerability, the proof of concept was more complex:

1. Side-Channel Attack: Instead of a hardcoded key, Cohney and his team utilized a side-channel attack to recover the AES key used during the second stage of the Counter DRBG's output generation process. This method, while effective, is acknowledged by Cohney as potentially more difficult to deploy at the "large scale" envisioned for mass NSA decryption.
2. ECDSA Secret Recovery: By recovering the key via the side channel, they were able to demonstrate the ability to recover long-term client ECDSA secrets that had been generated using this flawed process. This proved that even with a more robust design, implementation details and the optional nature of security features could be exploited.

For the Dual EC DRBG and the Juniper ScreenOS incident, the demonstration focused on viability rather than live exploitation:

1. Controlled Device Experiment: Since the specific backdoor relationship between the altered curve points used by the adversary in ScreenOS was unknown to the public (the "nobody but us" aspect), Cohney's team could not perform an active decryption attack in the wild.
2. Point Substitution: Instead, they purchased a target ScreenOS device and, through controlled experimentation, demonstrated the attack's viability by switching out the curve points themselves. This allowed them to simulate the adversary's knowledge and show that, under those conditions, passive decryption was indeed possible given the identified implementation flaws (exposed raw Dual EC output, excessive nonce bytes).
3. Vulnerable Device Identification: While not decrypting, they did run scans against devices in the wild to identify which ones were running the vulnerable ScreenOS versions, confirming the existence of potentially exploitable systems.

These demonstrations collectively illustrate how theoretical cryptographic weaknesses, particularly within standardized designs, can be translated into practical exploits when combined with specific implementation choices—whether those choices are accidental omissions, hardcoded values, or even malicious alterations by state-level adversaries.

Defensive Implications

▶ Watch: DES standardization and Snowden's NSA decryption slides (6:10)

Shaanan Cohney's research provides critical insights for defenders, shifting the focus from purely algorithmic strength to the broader ecosystem of cryptographic design, standardization, and implementation.

1. "Standardization is Not Security": This is a paramount takeaway. The mere fact that an algorithm or protocol is standardized (e.g., FIPS-approved) does not inherently guarantee its security. Defenders must understand that standards can be compromised, contain subtle flaws, or offer weak guidance that leads to vulnerabilities. Blindly trusting standards without scrutiny of their design and implementation is a significant risk.

1. "Certification is Not an Audit": Similarly, a product's certification under programs like the Cryptographic Module Verification Program (CMVP) for FIPS 140-2/3 does not equate to a thorough security audit by cryptographic experts. These certifications often focus on compliance with the standard's requirements rather than an exhaustive analysis of the underlying code for subtle flaws or implementation errors. Defenders should view certification as a baseline, not a complete assurance of security.

1. Rigorous Implementation Scrutiny: The attacks demonstrated often relied on the "tragic intersection" of flawed standards and "substantial implementation flaws." Defenders must prioritize rigorous code review, static analysis, and dynamic testing of cryptographic implementations, even when using standardized algorithms. This includes:

• Dynamic Key Generation: Ensure that cryptographic keys, especially for PRNGs, are generated dynamically with sufficient entropy, rather than being hardcoded or pulled from test vectors.
• Robust Entropy Sources: Verify that PRNGs are fed with high-quality, unpredictable entropy from multiple sources, and that optional entropy mechanisms are actually implemented and utilized effectively.
• Secure Chaining: If multiple cryptographic primitives or RNGs are chained, ensure the chaining is done securely, without inadvertently exposing intermediate or weaker outputs.
• Minimal Output: Ensure that applications do not expose more random bytes than strictly necessary for a protocol, as excess output can aid state recovery attacks.

1. Expand Threat Models to "Pre-Supply Chain Operations" (PsyCO): Defenders need to recognize that adversaries can target the earliest stages of product development. This means considering:

• Regulatory Influence: Be aware of how regulations and policy mandates can subtly introduce fragility or mandate support for weaker algorithms/modes (e.g., export-grade crypto, requiring many algorithms).
• Standards Body Participation: Advocate for and participate in open, inclusive standardization processes (like IETF) that allow for broad scrutiny. Be wary of closed or exclusionary processes (like some aspects of ISO) that are more susceptible to manipulation.
• Parameter Choices: Scrutinize standardized parameters (e.g., Diffie-Hellman groups, elliptic curve points) for "nothing up my sleeve" properties to prevent backdoors.

1. Awareness of Legacy Systems and Downgrade Attacks: Many of the attacks discussed, while some are older, still pose a threat due to the long tail of legacy devices and software on the internet. Defenders must maintain inventories of cryptographic assets, identify older or vulnerable implementations, and actively phase out or patch systems susceptible to downgrade attacks (like DROWN or Logjam).

1. Protecting Standardization Processes: Cohney's "A-hole attack" highlights the human element. Defenders involved in standards bodies should be vigilant against social engineering tactics and conduct that aims to disrupt or subvert the process. Promoting a culture of transparency, open debate, and constructive criticism within these committees is crucial.

1. Advocacy Against Mandated Backdoors: The ongoing attempts to mandate backdoors in cryptography (e.g., in the EU, Australia with the Access and Assistance Bill) are a direct continuation of the "PsyCO" threat model. Defenders must remain engaged in public policy debates and educate policymakers on the inherent dangers of such mandates, which weaken security for everyone and can be repurposed by foreign adversaries, as seen with Dual EC DRBG.

In essence, defending against these sophisticated threats requires a holistic approach that combines technical vigilance over implementations with an understanding of the political and procedural landscape of cryptographic standardization.

Key Takeaways

• Standardization is Not Security: Relying solely on a cryptographic standard's existence or FIPS certification is insufficient. The standard itself can contain flaws, and its guidance can be ambiguous, leading to vulnerable implementations.
• Opaque Implementations are Prime Targets: Vendor implementations, especially when proprietary or not subject to public scrutiny, frequently introduce critical flaws like hardcoded keys or the omission of optional security features, exacerbating standards-level weaknesses.
• "Pre-Supply Chain Operations" (PsyCO) are a Major Threat: Adversaries target the design, standardization, and certification phases of the product lifecycle, influencing requirements or mandating features that introduce systemic vulnerabilities before any code is even written.
• Real-World Exploits Combine Flawed Standards and Implementations: Effective large-scale decryption by state actors often requires a "tragic intersection" of a weak or backdoored standard and specific implementation errors or omissions by vendors.
• The Threat Extends Beyond Random Number Generators: The PsyCO model applies to other cryptographic areas, including lightweight ciphers, Diffie-Hellman group choices, and export-grade cryptography, demonstrating a consistent pattern of subversion.
• Vigilance Against Regulatory Backdoors is Essential: Ongoing efforts by governments to mandate cryptographic backdoors (e.g., in the EU, Australia) represent a direct continuation of this threat model, creating vulnerabilities that can be repurposed by other adversaries.
• Open and Inclusive Standardization Processes are Crucial: Openness (like IETF) allows for broader scrutiny and participation, strengthening security, while closed processes (like some ISO iterations) are more susceptible to adversarial influence.

About the Speaker(s)

Shaanan Cohney is an academic researcher at the University of Melbourne, specializing in cybersecurity. His research focuses on understanding how state-level adversaries might compromise cryptographic systems at scale, a journey he describes as spanning the last 15 years. Before his academic career, Cohney gained experience in government, working in the US Senate as a cybersecurity fellow for Senator Ron Wyden in 2018, and later at the US Federal Trade Commission. This unique blend of academic rigor and practical policy experience informs his analytical approach to cryptographic security and the political dynamics of standardization. He leads a team of researchers across various universities globally, collaborating to replicate and understand sophisticated state-sponsored cyber capabilities.