Fault Propagation Pattern Based DFA on Feistel Ciphers, with Application to Camellia

This paper presents a systematic Differential Fault Analysis (DFA) method on Feistel ciphers, the outcome of which closely links to that of the theoretical cryptanalysis with provable security. For this purpose, we introduce the notions of Fault Propagation Path (FPPath) and Fault Propagation Pattern (FPPattern). By this method, it can be programmed to automatically compute FPPaths and FPPatterns, which will facilitate the automatic DFA on Feistel ciphers. In this case, the length of FPPath can be regarded as a quantitative metric to evaluate the efficiency of DFA attacks. Moreover, one consequent result of this systematic method is performance enhancement. Specifically, not only the number of attacked rounds but also the number of fault injection points is reduced, which rapidly decrease the amount of required faulty ciphertexts for successful attacks. To verify both the correctness and the efficiency of our method, we perform FPPattern based DFA on Camellia. By making better use of the fundamental property of P-function utilized in Camellia, our attack, without any brute-force search, only requires 6 faulty ciphertexts to retrieve the 128-bit key and 22 faulty ciphertexts to recover 192/256-bit keys, respectively.