General Extensions and Improvements of Algebraic Persistent Fault Analysis

Algebraic Persistent Fault Analysis (APFA) combines algebraic analysis with persistent fault analysis, providing a novel approach for examining block cipher implementation security. Since its introduction, APFA has attracted considerable attention. Traditionally, APFA has assumed that fault injection occurs solely within the S-box during the encryption process. Yet, algorithms like PRESENT and AES also utilize S-boxes in the key scheduling phase, sharing the same S-box implementation as encryption. This presents a previously unaddressed challenge for APFA. In this work, we extend APFA’s fault injection and analysis capabilities to encompass the key scheduling stage, validating our approach on PRESENT. Our experimental findings indicate that APFA continues to be a viable approach. However, due to faults arising during the key scheduling process, the number of feasible candidate keys does not converge. To address this challenge, we expanded the depth of our fault analysis without increasing the number of faulty ciphertexts, effectively narrowing the key search space to near-uniqueness. By employing a compact S-box modeling approach, we were able to construct more concise algebraic equations with solving efficiency improvements ranging from tens to hundreds of times for PRESENT, SKINNY and CRAFT block ciphers. The efficiency gains became even more pronounced as the depth of the fault leakage increased, demonstrating the robustness and scalability of our approach.