Generalized differential fault analysis on block ciphers and its applications

다국어 초록 (Multilingual Abstract)

Block cipher is the most prominent and important element in many cryptographic systems and it provides confidentiality for data transmitted in insecure communication environments. It can also be used to constrict other secret-key cryptographic primitives, such as hash functions, pseudorandom number generators, message authentication codes (MACs), stream ciphers.
The security of block ciphers is the well-researched subject. The traditional cryptanalysis on block ciphers such as differential cryptanalysis and linear cryptanalysis focus on the weakness of the target block ciphers. However, the results of the traditional cryptanalysis on block ciphers are often impractical. Contrastively a side-channel analysis is based on the information gained from physical implementation of them; power consumptions, timing information and input-output behavior under malfunctions. A differential fault analysis is one of the powerful side-channel analysis on block ciphers. It is possible to reveal the secret key of the various block cipher
within a practical complexity if the implementation of it does not protected fault injections.
This thesis, we study differential fault analysis on block ciphers and introduce a generalized differential fault analysis on block ciphers. The main contributions of this thesis are as follows.
• Differential fault analysis on HIGHT
– We propose differential fault attack on HIGHT. The proposed attack can recover the 128-bit secret key with more than 4 faulty ciphertexts. Our attack has O(2^{32}) computational complexity and O(2^{32}) memory complexity. This result is the first known differential fault analysis on HIGHT.
• Improved differential fault analysis on block cipher SEED
– We propose improved differential fault attacks on SEED. In our attack, an attacker can induce 1-byte random fault to input registers of the second G function in the target round. By using 4, 6 fault injections, the proposed attacks can recover the secret key of SEED-128/192 within a few minutes, respectively. In case of SEED-256, we can recover the 4 consecutive round key with 8 fault injections. These are superior to known differential fault analysis on them.
• Improved differential fault analysis on block cipher PRESENT
– We propose improved differential fault attacks on PRESENT. To recover the 80/128-bit secret keys of PRESENT-80/128, our attacks require only two(three) fault injections and an exhaustive search of 1.7(2^{22.3}), respectively. These are superior to known differential fault analysis on them.
• Generalized differential fault analysis on block ciphers
– We propose generalized differential fault analysis on SPN block ciphers. First, we adopt a differential equations which consist of some conditions of differences and a set of round key bits. Then we introduce how to construct the differential equations and to determine computational complexity and the number of fault injections by using differential equations. Finally, we show that our method can be applied to Feistel block ciphers where the round function is invertible.
• Efficient differential fault analysis on block cipher ARIA with small number of fault injections.
– We propose efficient differential fault attacks on ARIA using
the proposed method. Based on random byte fault model, our attacks can recover the secret key of ARIA-128/192/256 by using 6 fault injections within a few minutes. Moreover, in cases of ARIA-128 and ARIA-256, it is possible to recover the secret key using only 4 fault injections under a fault assumption where an attacker can induce some faults during both encryption and decryption process, respectively. Our results on ARIA-192/256 are the first known differential fault analysis on them.

목차 (Table of Contents)

• 1 Introduction 1
• 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
• 1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . 4
• 1.3 Organization of thesis . . . . . . . . . . . . . . . . . . . . . 6
• 2 Differential fault analysis on block ciphers 7
• 2.1 Fault model . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
• 2.2 Differential fault analysis on block ciphers . . . . . . 9
• 3 Improved differential fault analysis on block cipher HIGHT 11
• 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
• 3.2 Description of HIGHT . . . . . . . . . . . . . . . . . . . . . 12
• 3.3 Fault model and the differential property . . . . . . . . .. 15
• 3.4 Differential fault analysis on HIGHT . . . . . . . . . . . . . 18
• 3.4.1 Data collection . . . . . . . . . . . . . . . . . . . . . 20
• 3.4.2 Computation of the candidates of subkeys . . . . 20
• 3.4.3 Recovery of the 128-bit secret key . . . . . . . . . . 23
• 3.5 The attack complexity and the simulation results . 23
• 3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
• 4 Improved differential fault analysis on block cipher SEED 26
• 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
• 4.2 Block cipher SEED . . . . . . . . . . . . . . . . . . . . . .28
• 4.2.1 Description of SEED-128/192/256 . . . . . . . . . . 29
• 4.2.2 Computation of secret key from round keys . . .33
• 4.3 Fault model and differential property . . . . . . . . . .35
• 4.4 Differential fault analysis on SEED . . . . . . . . . . . 39
• 4.4.1 Differential fault analysis on SEED-128 . . . . . . . 39
• 4.4.2 Differential fault analysis on SEED-192 . . . . . . . 40
• 4.4.3 Differential fault analysis on SEED-256 . . . . . . . 41
• 4.5 DFA on SEED using small number of faults . . . . . 42
• 4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
• 5 Improved differential fault analysis on PRESENT 45
• 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
• 5.2 Description of PRESENT . . . . . . . . . . . . . . . . . . . 47
• 5.3 Fault assumptions and the basic idea . . . . . . . . . . 50
• 5.4 Differential fault analysis on PRESENT-80 . . . . . . . 53
• 5.4.1 Computation of candidates of (RK31,RK32) . . . . 53
• 5.4.2 Recovery of the 80-bit secret key . . . . . . . . . . . 57
• 5.5 Differential fault analysis on PRESENT-128 . . . . . .. 58
• 5.6 Simulation results . . . . . . . . . . . . . . . . . . . . . . . 60
• 5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
• 6 Generalized differential fault analysis on block ciphers 63
• 6.1 Description of SPN block cipher and fault model . . . 65
• 6.1.1 SPN block cipher . . . . . . . . . . . . . . . . . . . . 65
• 6.1.2 Fault model . . . . . . . . . . . . . . . . . . . . . . . 66
• 6.2 Construction of differential equations for SPN block cipher 67
• 6.3 Generalized differential fault analysis on SPN block ciphers 70
• 6.4 Applying to Feistel block cipher . . . . . . . . . . . . . 71
• 7 Efficient differential fault attack on block cipher ARIA using
• small number of fault injections. 74
• 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
• 7.2 Description of ARIA . . . . . . . . . . . . . . . . . . . . . . 77
• 7.3 Fault assumptions and the basic idea . . . . . . . . 80
• 7.3.1 Fault assumptions . . . . . . . . . . . . . . . . . . . 80
• 7.3.2 Constructing differential equations . . . . . . . . . . 82
• 7.3.3 Recovery of the secret key from round keys . . . . . 84
• 7.4 Computation of round keys . . . . . . . . . . . . . . . . . . 86
• 7.4.1 Assumption A1 . . . . . . . . . . . . . . . . . . . . . 87
• 7.4.2 Assumption A2 . . . . . . . . . . . . . . . . . . . . . 93
• 7.5 DFAs on ARIA . . . . . . . . . . . . . . . . . . . . . . . . 94
• 7.5.1 DFA on ARIA under A1E . . . . . . . . . . . . . . . 94
• 7.5.2 DFA on ARIA under A2E . . . . . . . . . . . . . . . 96
• 7.5.3 DFAs on ARIA-128/256 under A1DE and A2DE . . 97
• 7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
• 8 Conclusion 99