Achilles: A Formal Framework of Leaking Secrets from Signature Schemes via Rowhammer

Achilles: A Formal Framework of Leaking Secrets from Signature Schemes via Rowhammer

Speakers: Junkai Liang

Conference: USENIX Security

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

Overview

In the realm of digital security, signature schemes serve as fundamental cryptographic building blocks, underpinning the integrity and authenticity of virtually every networked interaction. From securing network protocols and blockchain transactions to validating software updates and facilitating secret message transfers, their reliability is paramount. However, these critical schemes have repeatedly demonstrated vulnerabilities to fault injection attacks, a class of physical attacks that manipulate the operational environment of a computing system to induce errors in cryptographic computations, often leading to the leakage of secret keys. This talk, presented by Junkai Liang, introduces "Achilles," a novel, formal framework designed to systematically analyze and exploit signature schemes for secret leakage through Rowhammer attacks.

Existing fault injection attacks have successfully targeted prominent schemes like ECDSA and RSA, and even some post-quantum candidates, leading to real-world security incidents documented by CVEs. Yet, a significant gap remains: many widely used signature schemes, such as BLS and MLS, have not been thoroughly analyzed for their susceptibility to such attacks, and a generalized methodology for identifying vulnerabilities across diverse schemes has been lacking. Achilles addresses this challenge by proposing a common framework that formalizes the characteristics of signature schemes and the mechanics of Rowhammer, enabling the identification of new exploitable vulnerabilities and providing a scalable approach to assess the security of cryptographic implementations against physical memory attacks.

The significance of Achilles lies in its ability to bridge the gap between theoretical cryptographic security and practical hardware-level vulnerabilities. By providing a formal model and automated tools, the framework not only uncovers specific weaknesses in signature schemes but also offers a systematic methodology for security researchers and practitioners. It underscores the persistent threat posed by Rowhammer, a physical phenomenon that can be leveraged to compromise even robust cryptographic primitives, thereby necessitating a re-evaluation of current security practices and the adoption of more resilient implementations to safeguard against sophisticated memory-based attacks.

Background

▶ Watch: Introduction to Achilles and problem statement (0:00)

The security of modern digital infrastructure heavily relies on the robustness of signature schemes. These cryptographic primitives are essential for verifying the identity of a sender and ensuring the integrity of data across a myriad of applications, including secure boot processes, blockchain wallets, software update mechanisms, and encrypted communication channels. Despite their critical role, many signature schemes have been shown to be susceptible to various forms of fault injection attacks. These attacks, which include differential fault analysis, leverage induced errors in computations to derive secret information. Historical examples include successful attacks on ECDSA (Elliptic Curve Digital Signature Algorithm), RSA, and even some candidates for post-quantum cryptography, often resulting in real-world security vulnerabilities and associated CVEs. The core principle behind these attacks is that cryptographic parameters, typically loaded into memory, can be subtly altered, leading to predictable errors that, when analyzed, reveal secret keys.

One potent physical fault injection technique is Rowhammer. This phenomenon exploits a physical property of modern DRAM chips, where repeatedly accessing a row of memory (the "aggressor row") can cause bit flips in physically adjacent rows (the "victim rows"). This occurs due to electrical interference, leading to data corruption without direct write access to the victim rows. In the context of cryptographic attacks, Rowhammer can be used to inject faults by manipulating the memory cells where critical parameters of a signature scheme are stored. By carefully orchestrating memory accesses, an attacker can induce bit flips in specific memory locations, thereby altering a secret key, public parameter, or intermediate computation result, and ultimately influencing the output of the signing process in a way that facilitates secret recovery.

A key problem identified by the researchers is the lack of a generalized approach to analyze the vulnerability of diverse signature schemes to Rowhammer-induced fault injection. While specific attacks have been demonstrated for certain schemes, others, such as BLS (Boneh-Lynn-Shacham) and MLS (Messaging Layer Security), remain largely unanalyzed in this context. Furthermore, existing attack methodologies often lack a formal framework that can be broadly applied to different cryptographic constructions. This makes it challenging to systematically identify potential weaknesses across a wide range of signature schemes and to develop comprehensive countermeasures.

To address these limitations, the research proposes Achilles, a common framework designed for generalizing the analysis of signature schemes against Rowhammer attacks. Achilles specifically targets signature schemes with scalable parameters and aims to identify new exploitable vulnerabilities by providing a formal treatment of signature schemes and the Rowhammer attack model. This framework offers a structured methodology to analyze how faults, whether injected into public or secret parameters, can be leveraged to leak sensitive information, thereby enhancing our understanding of the practical security of cryptographic implementations in the face of advanced physical attacks.

Key Findings

▶ Watch: Formal framework design of Achilles (2:43)

The Achilles framework presents several significant contributions and key findings that advance the understanding and exploitation of Rowhammer vulnerabilities in signature schemes.

Firstly, the framework introduces a formal treatment of signature schemes, defining their core functionalities (key generation, signing, verification) and crucial parameters such as randomness, message hash value, public key, and secret key. This formalization allows for a systematic analysis of how each of these parameters, when subjected to fault injection, can be exploited.

Secondly, Achilles categorizes attacker capabilities based on the location of the induced fault, distinguishing between faults occurring on public parameters and those on secret parameters. This distinction is critical because it dictates the observable behavior and the appropriate attack strategy.

• If a fault occurs on a public parameter, the attacker can output a valid signature on a new message, implying they have learned the secret key.
• If a fault occurs on a secret parameter, the attacker can output valid fault information and a signature on an existing message, which was previously queried.

To exploit these distinct scenarios, the framework develops two primary algorithms:

• Differential Fault Analysis (DFA): Designed for scenarios where faults occur on public parameters. DFA leverages the comparison between a faulty signature and a valid one to derive the secret key.
• Secret Collection Attack (SCA): Tailored for situations where faults occur on secret parameters. SCA focuses on correcting the faulty signature to its valid form, with the correction term revealing parts of the secret.

A crucial finding is the development of AutoWAR, an automated program that significantly streamlines the process of identifying potentially vulnerable parameters. By inputting symbolic descriptions of schemes and their underlying equations, AutoWAR can automatically output vulnerable attack paths, greatly enhancing the scalability and efficiency of vulnerability discovery.

Furthermore, the research demonstrates the practical feasibility of these attacks through online injection techniques. This includes methods for precisely triggering Rowhammer within a limited time window during parameter initialization and subsequent computations, a significant challenge for real-world exploitation. The demonstration also highlights the number of faulty signatures required for recovery, for instance, 40 faulty signatures for DFA on schemes like GAS and Mystic, and hundreds for SCA.

Finally, the work reveals that even quantum countermeasures can be bypassed. By faulting the off code (likely referring to opcode or specific instruction sequences), the researchers demonstrated a way to circumvent protections designed to secure cryptographic operations against quantum attacks, further emphasizing the pervasive nature of Rowhammer as a threat vector. The comparison with other physical fault injection types (radiation, water clock, pneumatic, temperature) also highlights Rowhammer's unique advantages in terms of remote applicability and precise temporal/spatial control, making it a particularly potent attack vector.

Technical Deep Dive

▶ Watch: DFA and SCA algorithms for secret key recovery (4:55)

The Achilles framework establishes a rigorous, formal treatment of signature schemes to systematically analyze their susceptibility to Rowhammer-induced fault injection. This formalization begins by defining the core components of any signature scheme: the key generation process, the signing algorithm, and the verification algorithm. Crucially, it identifies and models the key parameters involved in these processes, including the randomness used during signing, the message hash value being signed, the public key, and the highly sensitive secret key. The framework posits that an attacker can induce faults in any of these parameters.

At the heart of Achilles is a game-based model that delineates two distinct attacker capabilities, each corresponding to a specific fault location and exploitation strategy. This model dictates how an attacker interacts with a faulty signature scheme to deduce secret information.

1. Fault on Public Parameter: In this scenario, the attacker's objective is to obtain the secret key. The model states that if a fault occurs on a public parameter, the attacker can successfully output a valid signature on a new message. The ability to generate a valid signature for a previously unseen message implies that the attacker has successfully learned the secret key. This type of fault is particularly dangerous as it directly compromises the confidentiality of the signing key.

1. Fault on Secret Parameter: Conversely, if the fault occurs on a secret parameter, the attacker aims to extract specific fault information or parts of the secret key. In this case, the attacker's success is measured by their ability to output valid fault information and a signature on an existing message that was previously queried. Unlike public parameter faults, directly generating a new valid signature might not be possible, but the controlled corruption of secret parameters allows for differential analysis that reveals the secret.

To operationalize these attack scenarios, Achilles introduces two primary algorithms: Differential Fault Analysis (DFA) and Secret Collection Attack (SCA).

The Differential Fault Analysis (DFA) algorithm is designed to exploit faults in public parameters. The process involves:

• Symbolic Representation: The signature scheme's mathematical operations and parameters are first translated into a symbolic representation. This allows for a generalized analysis independent of specific cryptographic implementations.
• Parameter Enumeration and Tracking: The algorithm then systematically enumerates all possible parameters that could be affected by a fault. These parameters are tracked, for instance, using concepts like the Jacobian matrix, to understand their influence on the signature output.
• Comparison and Subtraction: The core of DFA involves comparing a faulty signature (generated after a Rowhammer-induced fault) with a valid signature (generated without a fault). By performing a "simple subtraction" or other differential operations between these two signatures, the attacker can isolate the effect of the fault and, in many cases, directly derive the secret key. The talk mentions that in DFA, a minimal number of 40 faulty signatures were sufficient for recovery in schemes like GAS and Mystic.

The Secret Collection Attack (SCA) algorithm is tailored for scenarios where faults are induced in secret parameters. Its methodology includes:

• Parameter Emulation: Similar to DFA, SCA involves emulating all possible secret parameters that could be targeted by a fault.
• Faulty Signature Representation: The algorithm captures the representation of the faulty signature, understanding how the corrupted secret parameter affects the final output.
• Correction Term Derivation: The key step in SCA is to "correct" the faulty signature back to what it should have been had no fault occurred. If this correction is successful, the difference or the "correction term" itself reveals information about the corrupted secret. This correction term can then be used to reconstruct the ignored or leaked secret components. SCA often requires a larger number of faulty signatures, with the talk indicating "hundreds" for successful recovery.

A significant technical advancement presented is AutoWAR, an automated program that facilitates the discovery of vulnerable parameters. AutoWAR takes as input:

• A description of the symbols representing the scheme's parameters.
• A description of the equations governing the scheme's operations.

The program then automatically analyzes these inputs to identify potentially vulnerable parameters and attack paths, presenting them, for example, in a format similar to Table 3 mentioned in the talk. This automation drastically reduces the manual effort required for analyzing new schemes or variations.

The research also delves into methods for finding remaining bits of a secret when only partial information is leaked, developing a new, more efficient algorithm compared to existing scalar algorithms. Furthermore, specific adaptations for various cryptographic features were discussed, including indent cryptography schemes, verifying after signing, and redundancy checks (e.g., those found in SHA and DSA implementations), demonstrating the framework's versatility. Notably, the talk highlights that even quantum countermeasures can be bypassed by faulting specific off code (likely referring to critical instruction sequences or opcodes), thereby undermining protective mechanisms designed for future cryptographic security.

Demo / Proof of Concept

▶ Watch: Practical attack methodology and requirements (7:40)

The practical demonstration of Achilles involved a sophisticated setup to perform online Rowhammer injection and subsequent secret recovery. The researchers tackled the inherent challenges of Rowhammer attacks, particularly the need for precise temporal and spatial control over fault injection.

The initial phase involved offline memory profiling. This crucial step utilized a tool called drum day to map physical memory addresses to their corresponding DRAM banks. This mapping is essential for identifying which memory rows are adjacent and thus susceptible to Rowhammer-induced bit flips. By pulling out 12 GB of memory, the researchers could accurately characterize the DRAM layout and identify optimal aggressor-victim row pairs. This foundational work ensures that when an online attack is launched, the attacker knows precisely which memory regions to target to affect cryptographic parameters.

The more challenging aspect was the online injection of faults. This required a method to trigger Rowhammer while the victim process was actively using the memory for cryptographic operations. The researchers utilized a technique leveraging "PC of SP" (likely referring to specific page cache manipulation or memory management primitives like madvise(MADV_DONTNEED) combined with pagemap analysis), which allowed them to perform memory messages by releasing pages. The primary challenge here was the limited time window – faults must occur precisely during the parameter initialization or subsequent computation phases of the signature scheme, which are often very brief.

To overcome this temporal constraint, the solution involved an intricate inter-process communication mechanism. The attacker process was designed to signal the victim process using a registered signal. This signal was used to track specific write operations, allowing the attacker to precisely time the Rowhammer attack to coincide with the victim process writing critical parameters to memory. By switching the victim process's code or memory access patterns, the attacker could create the necessary conditions for Rowhammer to occur effectively within the narrow time window.

Once Rowhammer was successfully induced and faulty signatures were obtained, the previously described algorithms, DFA and SCA, were employed for secret recovery. For DFA, the demonstration showed that as few as 40 faulty signatures were sufficient to recover secrets from schemes like GAS and Mystic. For SCA, which targets secret parameters, a larger dataset of hundreds of faulty signatures was required. The researchers also developed a new, more efficient algorithm for finding remaining bits of a secret when only partial information was leaked, showcasing an improvement over existing scalar algorithms.

The demonstration extended to specific adaptations for various cryptographic features. This included handling indent cryptography schemes, where cryptographic operations might be deeply nested or protected, and schemes employing verifying after signing or redundancy checks (e.g., in SHA or DSA). The paper also explicitly showed that quantum countermeasures could be bypassed by targeting and faulting the off code (opcode or critical execution paths) of the cryptographic implementation.

Finally, the talk briefly contrasted Achilles with other physical fault injection techniques, such as radiation, water clock, pneumatic, and temperature attacks. The key distinction highlighted was that these alternative methods often lack the temporal and spatial precision required for Rowhammer-like attacks and generally do not allow for the remote exploitation that Rowhammer can facilitate, making Achilles' approach particularly potent and relevant in modern computing environments.

Defensive Implications

▶ Watch: Bypassing countermeasures and comparison to other attacks (10:00)

The Achilles framework and its demonstrated capabilities underscore the critical need for robust defensive strategies against Rowhammer-induced fault injection attacks on cryptographic signature schemes. The ability to remotely induce bit flips and subsequently leak secret keys from fundamental security primitives demands a multi-layered defense approach, encompassing hardware, software, and architectural considerations.

Firstly, memory isolation and protection mechanisms are paramount. Technologies like Intel SGX, AMD SEV, and other Trusted Execution Environments (TEEs) aim to encrypt memory regions and isolate critical computations from the host operating system, potentially mitigating the impact of Rowhammer. However, even TEEs have faced their own set of vulnerabilities, so their efficacy against sophisticated Rowhammer attacks needs continuous re-evaluation. Hardware-level memory encryption, such as that provided by modern CPUs, can also help protect data at rest and in transit within the memory hierarchy, making it harder for an attacker to reliably induce specific bit flips on unencrypted cryptographic parameters.

Secondly, redundant computations and error detection codes are essential. For critical cryptographic operations, performing computations multiple times and comparing the results can detect inconsistencies caused by Rowhammer-induced faults. If a discrepancy is found, the operation can be aborted, preventing the generation of a faulty signature that could be exploited. ECC (Error-Correcting Code) memory is a hardware-based solution that can detect and correct single-bit errors and detect some multi-bit errors. While ECC memory is common in servers, its widespread adoption in client devices, where many signature operations occur, is less prevalent. Even with ECC, certain Rowhammer patterns can overwhelm its correction capabilities, so it's not a complete panacea.

Thirdly, memory allocation randomization and page coloring can make Rowhammer attacks harder to execute reliably. By randomizing the physical memory addresses where cryptographic parameters are stored, or by employing page coloring techniques to ensure that sensitive data is not placed in physically adjacent rows, attackers face a greater challenge in identifying and targeting the correct victim rows. This increases the attacker's guesswork and reduces the probability of successful fault injection.

Fourthly, continuous monitoring for Rowhammer-like access patterns can serve as an early warning system. Hardware performance counters or software agents could detect anomalous memory access patterns indicative of a Rowhammer attack. While challenging to implement without significant overhead, such monitoring could trigger alerts or defensive actions, such as isolating the affected memory region or restarting the cryptographic service.

Fifthly, secure software development practices are crucial. Cryptographic libraries and applications should be designed with fault tolerance in mind. This includes carefully validating all inputs and outputs, implementing sanity checks on cryptographic parameters, and avoiding predictable memory layouts for sensitive data. Regular security audits and penetration testing specifically targeting fault injection scenarios are also vital. The bypass of "quantum countermeasures" highlighted in the talk further emphasizes that even forward-looking security mechanisms need to consider physical attack vectors.

Finally, the talk's findings necessitate a re-evaluation of the security assurances given to even well-established signature schemes. The fact that Rowhammer can compromise schemes like GAS and Mystic, and potentially others like BLS and MLS, means that developers and security architects must not assume the absence of physical attacks. Instead, cryptographic implementations should be designed with an inherent resilience to memory-level faults, perhaps by incorporating explicit fault-detection and mitigation logic directly into the cryptographic algorithms themselves, or by strictly enforcing memory protection at the hardware level.

Key Takeaways

• Achilles is a novel, formal framework for systematically analyzing and exploiting signature schemes for secret leakage via Rowhammer attacks.
• The framework categorizes Rowhammer attacks into two types: Differential Fault Analysis (DFA) for faults on public parameters (requiring ~40 faulty signatures for schemes like GAS and Mystic) and Secret Collection Attack (SCA) for faults on secret parameters (requiring hundreds of faulty signatures).
• AutoWAR is an automated tool developed within Achilles that can identify potentially vulnerable parameters and attack paths in signature schemes by analyzing symbolic descriptions and equations.
• The research demonstrated practical online Rowhammer injection techniques, including precise timing mechanisms to trigger faults within narrow time windows during cryptographic parameter initialization and computation.
• Achilles showed that even quantum countermeasures can be bypassed by faulting critical off code (opcode or instruction sequences), highlighting the pervasive threat of physical memory attacks.
• The work underscores the continued threat posed by Rowhammer, necessitating robust defensive measures such as enhanced memory isolation, redundant computations, ECC memory, and careful software design in cryptographic implementations.

About the Speaker(s)

Junkai Liang presented the research on "Achilles: A Formal Framework of Leaking Secrets from Signature Schemes via Rowhammer" at the USENIX Security conference. The talk highlighted their work in developing a systematic approach to analyze and exploit cryptographic signature schemes using Rowhammer-induced fault injection.