International Association
for Cryptologic Research

In 2018, Zhang et al. introduced the Persistent Fault Analysis (PFA) for the first time, which uses statistical features of ciphertexts caused by faulty Sbox to recover the key of block ciphers. However, for most of the variants of PFA, the prior knowledge of the fault (location and value) is required, where the corresponding analysis will get more difficult under the scenario of multiple faults. To bypass such perquisite and improve the analysis efficiency for multiple faults, we propose Chosen-Plaintext based Persistent Fault Analysis (CPPFA). CPPFA introduces chosen-plaintext to facilitate PFA and can reduce the key search space of AES-128 to extremely small. Our proposal requires 256 ciphertexts, while previous state-of-the-art work still requires 1509 and 1448 ciphertexts under 8 and 16 faults, respectively, at the only cost of requiring 256 chosen plaintexts. In particular, CPPFA can be applied to the multiple faults scenarios where all fault locations, values and quantity are unknown, and the worst time complexity of CPPFA is O(28+nf ) for AES-128, where nf represents the number of faults. The experimental results show that when nf > 4, 256 pairs of plaintext-ciphertext can recover the master key of AES-128. As for LED-64, only 16 pairs of plaintext-ciphertext reduce the remaining key search space to 210.

Algebraic Fault Analysis (AFA) is a cryptanalysis for block ciphers proposed by Courtois et al., which incorporates algebraic cryptanalysis to overcome the complexity of manual analysis within the context of Differential Fault Analysis (DFA). The effectiveness of AFA on lightweight block ciphers has been demonstrated. However, the complexity of the algebraic systems prevents it from attacking heavyweight block ciphers efficiently. In this paper, we propose a novel cryptanalysis called Redundancies-assisted Algebraic Fault Analysis (RAFA) to facilitate the solution of algebraic systems in the setting of heavyweight block ciphers. The core idea of RAFA is to expedite SAT solvers by modifying the algebraic systems, which is accomplished via two methods. The first method introduces redundant constraints, which is proposed for the first time in the context of algebraic cryptanalysis. The second one is a sophisticated linearization of the nonlinear Algebraic Normal Form (ANF). It takes RAFA for about 9.68 hours to attack AES-128. To the best of our knowledge, this is the first work that uses a general SAT solver to attack AES with only a single injection of byte-fault. Moreover, RAFA can attack AES-128 in 50.92 and 27.54 minutes for nibble- and bit-based fault model, respectively. In comparison, the traditional DFA algorithm implemented by pure C takes 4 ~ 5 hours under all three fault models investigated in this work. Moreover, in order to show the generality of RAFA, we also apply it to other heavyweight block ciphers. The best results show that RAFA could recover the key of Serpent-256 and SPEEDY-r-192 in 20.7 and 1.5 hours using only three faults, respectively. In comparison, AFA could not break these two ciphers even when 30 bits and 50 bits of their keys are known, respectively. Furthermore, no DFA work on Serpent or SPEEDY is known using comparable fault models.

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.