Method for Continuous Fault Injection in Multi-Failure Scenarios

Written by | Lu Zeyuan

Edited by | Liu Mengdi

In 2018, Zhang Fan and others from Zhejiang University attacked a cryptographic system running the AES algorithm based on statistical ideas, termed Persistent Fault Analysis (PFA)^[1]. This paper first introduced the concept of continuous faults. Compared to transient faults and permanent faults in past studies, continuous faults exist in a cycle between the two, and the effects of continuous fault injection persist until the device is restarted. Continuous faults achieve a higher efficiency in obtaining faulty ciphertext than transient faults; unlike permanent faults, continuous fault injection does not leave significant evidence. After the round key expansion operation of the AES algorithm is completed, injecting a continuous fault into the S-box before the ten rounds of encryption begins will change the output value at one position of the S-box. By analyzing the distribution of the ciphertext values obtained from faulty encryption, PFA can recover the initial AES key using about 2000 ciphertexts.

At the 2022 CHES conference, Soleimany et al. built upon the classic PFA by injecting multiple continuous faults into the S-box to efficiently recover the AES algorithm’s key^[2]. This article focuses on the scenario of injecting multiple continuous faults to fill the gap in the application of classic PFA in this context. Compared to the attack scenarios of classic PFA, this paper maintains the ciphertext-only attack basis while injecting multiple continuous faults into the S-box, making the application scenario more relaxed and more aligned with actual attack needs. The main contributions of the paper are twofold:

1) A new multi-fault attack technique is proposed, applying continuous faults to multiple positions in the S-box, achieving the reduction of candidate key numbers and the required number of encryptions by statistically analyzing the ciphertext byte values.

2) The paper develops a general framework for recovering keys of such cryptographic algorithms in a pure ciphertext model, making the execution of continuous fault attacks and key recovery more generalized. Further calculations uniquely determine the key attack results based on the algorithm. Additionally, a trade-off between the required number of ciphertexts and computational time complexity is provided.

(1) Obtaining the XOR values between key bytes

The attack scenario in this paper is as follows: injecting λ continuous faults into the S-box causes the outputs at λ positions in the S-box to change due to faults, and the set of output values at the faulty positions in the S-box has no intersection with the original output value set. Assuming that the positions of λ injected faults in the S-box form the original output value set V, then after injecting faults, the faulty S-box will not output values from set V. The attacker uses the faulty S-box to encrypt and obtains N erroneous ciphertexts, counting the values that do not appear in the first byte (0th byte) as D[0], and counting the values that do not appear in the other bytes (jth byte) as D[j]. Then, the XOR value of D[0] and D[j] is the XOR value between the 0th byte of the key and the jth byte of the key. Assuming sk_R[j] represents the value of the jth byte of the key, D[0], D[j], and δ_j have the following relationship:

Where D[0] and D[j] can be obtained by counting the distribution of faulty ciphertext byte values, that is, with enough faulty ciphertext obtained, the XOR values between key bytes can be achieved, thus reducing the candidate key space. The algorithm is shown as Algorithm 1:

(2) Determining the final key result from the key candidate space based on the output values of the faulty S-box in the first nine rounds.

Through Step 1, a set of candidate keys can be obtained. Based on the candidate key K[i] and the values that do not appear in the faulty ciphertext bytes, the original output value V[i] of the S-box before fault injection can be calculated. Theoretically, the output values of the faulty S-box should not include the values in V[i]. Through the algorithm described as Algorithm 2, the faulty S-box output values from the ninth round to the first round can be obtained based on the faulty ciphertext C and the candidate key, and theoretically, the calculated output values should not appear in V[i]; otherwise, it indicates that the candidate key value is not the real key. The algorithm is shown as Algorithm 2:

Using Electromagnetic Fault Injection (EMFI) to inject continuous faults into the DUT. There are several reasons for choosing EMFI: first, electromagnetic fault injection is a non-invasive fault attack. Additionally, it can be used to inject faults from the front side of the chip, thus requiring very little time. In the paper, the EMFI device consists of a pulse generator that can produce high voltage pulses (up to 200V) with a very low rise time (<4ns). The pulse generator is triggered directly by an external trigger signal from the DUT, synchronizing the voltage pulse with the operation of the DUT. The EM pulse injector is a custom handmade EM probe designed as a simple loop antenna. The setup also includes an additional relay switch for performing automatic power reset of the device to verify whether continuous faults are injected. For the EM probe used in the experiment, please refer to the figure below:

Figure 1: Electromagnetic Fault Injection Setup on STM32F407VG Microcontroller Based on 32-bit ARM Cortex-M4F Core

When the number of collected faulty ciphertexts is sufficient, the number of values that do not appear in a single byte of the ciphertext equals the number of fault injections λ. The required number of faulty ciphertexts is about 1448, accompanied by a certain key search space.

Table 1: Number of Ciphertexts Required for Attack and Key Search Space When Ciphertext is Sufficient

When the number of collected faulty ciphertexts is insufficient, the number of values that do not appear in a single byte of the ciphertext λ’ is greater than the number of fault injections λ (λ’>λ). The required number of faulty ciphertexts is about 1024, accompanied by a certain key search space.

Table 2: Number of Ciphertexts Required for Attack and Key Search Space When Ciphertext is Insufficient

Although existing research literature on continuous fault attacks has demonstrated the feasibility of performing continuous fault analysis under the injection of a single fault, extending known fault injection techniques to multi-fault scenarios still presents challenges. In this article, we propose a new method for continuous fault analysis in multi-fault scenarios and verify the possibility of multi-fault injection in practice, providing new insights for PFA.

[1] Fan Zhang, Xiaoxuan Lou, Xinjie Zhao, Shivam Bhasin, Wei He, Ruyi Ding, Samiya Qureshi, and Kui Ren. Persistent fault analysis on block ciphers. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2018(3):150–172, 2018.

[2] Soleimany, H., Bagheri, N., Hadipour, H., Ravi, P., Bhasin, S., & Mansouri, S. (2021). Practical Multiple Persistent Faults Analysis. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(1), 367–390.