TL;DR
This paper presents a novel differential fault attack on the Grain-128a stream cipher's authentication mechanism. By injecting carefully timed faults and analyzing the resulting faulty MACs, the authors can recover the secret key with significantly fewer fault injections and MAC computations than previously thought possible.
What Problem Does This Paper Address?
Stream ciphers are essential for secure communication, but they are often vulnerable to fault attacks. These attacks involve introducing errors into the cipher's internal state during operation, which can then be exploited to reveal the secret key. The Grain family of stream ciphers, known for its efficiency and low hardware complexity, has been a target for such attacks. While previous attacks focused on recovering the keystream directly, the Grain-128a variant incorporates an authentication mechanism (MAC) that limits direct access to the keystream. This paper addresses the challenge of mounting a fault attack on Grain-128a when only the MAC is observable, aiming to recover the secret key by analyzing the differences between correct and faulty MACs.
Methods
The core of the attack relies on a differential fault analysis approach. The authors assume an attacker can:
- Reset the cipher with the same key and IV.
- Inject a single bit flip fault at a random location within the LFSR (Linear Feedback Shift Register) or NFSR (Non-linear Feedback Shift Register).
- Obtain the MAC of any chosen message, including the empty message.
The attack proceeds in several stages:
- Fault Location Identification: The crucial first step is to pinpoint where the fault occurred in the LFSR. This is achieved by comparing the MACs of the empty and zero messages generated with a fault-free and a faulty run. By analyzing specific differences in these MACs, the attacker can deduce a "Signature Vector" that is unique to each potential fault location. This process involves comparing these signature vectors to narrow down the possible fault locations.
- LFSR State Recovery: Once the fault location is identified, the attacker can use the differences in the faulty and fault-free MACs to recover specific bits of the LFSR's internal state. This is done by analyzing how the fault propagates through the cipher and affects the output keystream bits that contribute to the MAC.
- NFSR State Recovery: With the LFSR state known, the attacker then proceeds to recover the NFSR's internal state. This involves a similar process of analyzing the differences in MACs, but leveraging the specific structure of the Boolean function used in Grain-128a.
- Secret Key Recovery: Finally, once the entire initial state of the cipher (LFSR and NFSR) is recovered, the secret key can be efficiently derived by reversing the key scheduling algorithm (KSA).
Datasets
Not discussed in the paper. The attack is theoretical and relies on the internal state of the cipher, not external datasets.
Key Insights and Ideas
- MAC as an Oracle: The paper demonstrates that the MAC, even with limited keystream visibility, can serve as a powerful oracle for fault attacks. The differences in MACs reveal crucial information about the internal state.
- Signature Vectors for Fault Localization: The introduction of "Signature Vectors" is a key innovation, providing a systematic way to identify the exact location of a fault within the LFSR by analyzing the resulting MAC differences.
- Efficiency through Differential Analysis: The attack achieves high efficiency by exploiting the linear properties of the LFSR and the specific structure of the Boolean functions, requiring a surprisingly small number of fault injections and MAC computations.
- Unified Attack Strategy: The paper presents a coherent strategy that first identifies the fault location, then recovers the LFSR state, and subsequently the NFSR state, leading to the full secret key.
Key Results
The paper claims a successful differential fault attack on Grain-128a with the following performance:
- Fault Injections: Less than $2^{11}$ fault injections are required.
- MAC Generations: Less than $2^{12}$ MAC generation routines are invoked.
- State Recovery: The attack can recover a significant portion of the LFSR and NFSR states, enabling the full recovery of the 128-bit secret key.
Limitations and Future Work
- Random Fault Assumption: The attack assumes a single bit flip fault at a random location. The effectiveness against multiple faults or faults at specific non-random locations is not discussed.
- LFSR vs. NFSR Faults: While the paper mentions that NFSR fault injection has been studied, their primary attack focuses on LFSR faults for location identification. The efficiency of NFSR fault injection for this specific attack scenario might differ.
- Practicality: The paper focuses on the theoretical feasibility and complexity. The practical implementation of such fault injections (e.g., using laser or clock glitches) and the precise timing required are not detailed.
Future work could explore attacks with different fault models, investigate the impact of multiple faults, and analyze the practical feasibility of the proposed attack on actual hardware implementations of Grain-128a.
Summary updated