Free Fault Leakages for Deep Exploitation: Algebraic Persistent Fault Analysis on Lightweight Block Ciphers
Persistent Fault Analysis (PFA) is a new fault analysis method for block ciphers proposed in CHES 2018, which utilizes those faults that persist in encryptions. However, one fact that has not been raised enough attention is that: while the fault itself does persist in the entire encryption, the corresponding statistical analysis merely leverages fault leakages in the last one or two rounds, which ignores the valuable leakages in deeper rounds. In this paper, we propose Algebraic Persistent Fault Analysis (APFA), which introduces algebraic analysis to facilitate PFA. APFA tries to make full usage of the free fault leakages in the deeper rounds without incurring additional fault injections. The core idea of APFA is to build similar algebraic constraints for the output of substitution layers and apply the constraints to as many rounds as possible. APFA has many advantages compared to PFA. First, APFA can bypass the manual deductions of round key dependencies along the fault propagation path and transfer the burdens to the computing power of machine solvers such as Crypto-MiniSAT. Second, thanks to the free leakages in the deeper round, APFA requires a much less number of ciphertexts than previous PFA methods, especially for those lightweight block ciphers such as PRESENT, LED, SKINNY, etc. Only 10 faulty ciphertexts are required to recover the master key of SKINNY-64-64, which is about 155 times of reduction as compared to the state-of-the-art result. Third, APFA can be applied to the block ciphers that cannot be analyzed by PFA due to the key size, such as PRESENT-128. Most importantly, APFA replaces statistical analysis with algebraic analysis, which opens a new direction for persistent-fault related researches.
Persistent Fault Attack in Practice 📺
Persistence fault analysis (PFA) is a novel fault analysis technique proposed in CHES 2018 and demonstrated with rowhammer-based fault injections. However, whether such analysis can be applied to traditional fault attack scenario, together with its difficulty in practice, has not been carefully investigated. For the first time, a persistent fault attack is conducted on an unprotected AES implemented on ATmega163L microcontroller in this paper. Several critical challenges are solved with our new improvements, including (1) how to decide whether the fault is injected in SBox; (2) how to use the maximum likelihood estimation to pursue the minimum number of ciphertexts; (3) how to utilize the unknown fault in SBox to extract the key. Our experiments show that: to break AES with physical laser injections despite all these challenges, the minimum and average number of required ciphertexts are 926 and 1641, respectively. It is about 38% and 28% reductions of the ciphertexts required in comparison to 1493 and 2273 in previous work where both fault value and location have to be known. Furthermore, our analysis is extended to the PRESENT cipher. By applying the persistent fault analysis to the penultimate round, the full PRESENT key of 80 bits can be recovered. Eventually, an experimental validation is performed to confirm the accuracy of our attack with more insights. This paper solves the challenges in most aspects of practice and also demonstrates the feasibility and universality of PFA on SPN block ciphers.
Persistent Fault Analysis on Block Ciphers
Persistence is an intrinsic nature for many errors yet has not been caught enough attractions for years. In this paper, the feature of persistence is applied to fault attacks, and the persistent fault attack is proposed. Different from traditional fault attacks, adversaries can prepare the fault injection stage before the encryption stage, which relaxes the constraint of the tight-coupled time synchronization. The persistent fault analysis (PFA) is elaborated on different implementations of AES-128, specially fault hardened implementations based on Dual Modular Redundancy (DMR). Our experimental results show that PFA is quite simple and efficient in breaking these typical implementations. To show the feasibility and practicability of our attack, a case study is illustrated on the shared library Libgcrypt with rowhammer technique. Approximately 8200 ciphertexts are enough to extract the master key of AES-128 when PFA is applied to Libgcrypt1.6.3 with redundant encryption based DMR. This work puts forward a new direction of fault attacks and can be extended to attack other implementations under more interesting scenarios.