Sk Subidh
email: subidh@cse.iitkgp.ernet.in

Debdeep Mukhopadhyay
email: debdeep@cse.iitkgp.ernet.in

Differential Fault Analysis of AES-128 Key Schedule using a Single Multi-Byte Fault

Keywords: Differential Fault Analysis, Fault Attack, Advanced Encryption Standard, Key Schedule, DFA

In this paper we propose an improved multi-byte differential fault analysis of AES-128 key schedule using a single pair of fault-free and faulty ciphertexts. We propose a four byte fault model where the fault is induced at ninth round key. The induced fault corrupts all the four bytes of the first column of the ninth round key which subsequently propagates to the entire tenth round key. The elegance of the proposed attack is that it requires only a single faulty ciphertext and reduce the search space of the key to 2 32 possible choices. Using two faulty ciphertexts the attack uniquely determines the key. The attack improves the existing DFA of AES-128 key schedule, which requires two faulty ciphertexts to reduce the key space of AES-128 to 2 32 , and four faulty ciphertexts to uniquely retrieve the key. Therefore, the proposed attack is more lethal than the existing attack as it requires lesser number of faulty ciphertexts. The simulated attack takes less than 20 minutes to reveal 128-bit secret key; running on a 8 core Intel Xeon E5606 processor at 2.13 GHz speed.

Introduction

External noise such electromagnetic radiation, glitch in the input clock line, variation in the supply voltage can create fault in the electronic devices such as smart card. These properties of electronic devices are being exploited by the attackers. An attacker can deliberately inject fault into a device running a cryptographic algorithm. Then by analysing the faulty output he can reveal the secret key. This kind of attack is known as fault attack which was originally introduced by Boneh et. al. [START_REF] Boneh | On the Importance of Checking Cryptographic Protocols for Faults (Extended Abstract)[END_REF] in 1996 to break RSA crypto-system running on a smart-card . Subsequently, Biham and Shamir showed a modified form of the attack which is known as Differential Fault Analysis (DFA) based on combination of Differential Cryptanalysis and fault analysis [START_REF] Biham | Differential Fault Analysis of Secret Key Cryptosystems[END_REF]. The DFA was applied on DES crypto-system which successfully retrieved the secret key.

In 2001, NIST standardised Rijndael as the Advanced Encryption Standard (AES) [START_REF]Advanced Encryption Standard[END_REF]. Subsequently, many DFA were proposed on AES cryptosystem [START_REF] Blömer | Fault based cryptanalysis of the advanced encryption standard (AES)[END_REF][START_REF] Dusart | Differential Fault Analysis on A[END_REF][START_REF] Moradi | A Generalized Method of Differential Fault Attack Against AES Cryptosystem[END_REF][START_REF] Mukhopadhyay | An Improved Fault Based Attack of the Advanced Encryption Standard[END_REF][START_REF] Piret | A Differential Fault Attack Technique against SPN Structures, with Application to the AES and KHAZAD[END_REF] with the aim to reduced the number of faulty ciphertext required by the attack. However the DFA on AES can be divided into two categories. One in which the fault is induced in AES states, another in which the fault is induced in the key schedule. The literature is rich in attacks on the states. The most recent among these attacks is the attack on AES-128 proposed by M. Tunstall et. al. in [START_REF] Tunstall | Differential Fault Analysis of the Advanced Encryption Standard using a Single Fault[END_REF][START_REF] Tunstall | Differential fault analysis of the advanced encryption standard using a single fault[END_REF]. They proposed an attack where a single byte fault induced at the input of eighth round can reduce the AES-128 key space to 2 8 choices. However, there is not much research on attacks of AES key schedule.

In 2003, Giraud first proposed a DFA against the AES key schedule [START_REF] Giraud | DFA on AES[END_REF], which combined both kind of fault attack; the fault analysis in AES states as well as in key schedule. The attack was subsequently improved by Chen and Yen in [START_REF] Chen | Differential Fault Analysis on AES Key Schedule and Some Coutnermeasures[END_REF]. Chen et. al. attack required to induce fault at the ninth round key. The attack required less than thirty faulty ciphertexts to successfully retrieve the secret key. In 2006 Peacham and Thomas in [START_REF] Peacham | A DFA attack against the AES key schedule[END_REF], proposed an improved DFA against the AES key schedule, which reduced the number of faulty ciphertext required by the attack to 12. In Peacham's attack, fault was induced at the ninth round key during execution of the key schedule operation, so that the induced fault subsequently propagates to tenth round key.

Finally, Takahashi et. al. in [START_REF] Takahashi | DFA Mechanism on the AES Key Schedule[END_REF], proposed an attack, which can reduce the search space of the key to 2 48 choices using two faulty ciphertexts. The attack can reduce the key space to 2 16 choices using four faulty ciphertexts and can determine the key uniquely by using seven faulty ciphertexts. In 2008, Kim et. al. proposed an improved DFA by inducing 3-byte fault at the first column of ninth round key. Kim's attack required two faulty ciphertexts and a brute-force search of 2 32 . With four faulty ciphertexts the attack can uniquely determine the secret key.

In this paper we propose an improved attack against the AES-128 key schedule. We propose a fault model where the induced fault corrupts all the four bytes of the first column of ninth round key and the fault subsequently propagates to the entire tenth round key. Our attack requires only one faulty ciphertext to reduces the search space of the AES-128 key to 2 32 choices. Using two faulty ciphertext our attack can uniquely determine the key. We present extensive simulation results which shows that the attack takes less than 20 minutes to uniquely retrieve the 128-bit secret key.

Organization

The paper is organized as follows: We start with Section 2 where we describe the preliminaries to this paper. In Section 3 we briefly describe the existing attack. We propose our attack in Section 4. In Section 5 we present experimental results. In Section 6 we compare our work presented in this paper with the previous works, and we conclude in Section 7. SubBytes : It is the only non-linear byte-wise transformation in AES. Each element of the state matrix is replaced by its inverse and followed by an affine mapping. All the operations are under F 2 8 .

Preliminaries

ShiftRows : It is a row-wise transformations where the i th row is cyclically shifted by i bytes towards left where 0 ≤ i ≤ 3 .

MixColumns : It is a column level linear transformation of the state matrix. Each column of the state matrix is considered as a polynomial of degree 3 with coefficient in F 2 8 and multiplied with the polynomial {03}x 3 + {01}x 2 + {01}x + {02}.

AddRoundKey: In this transformation the 128-bit round key is bit-wise XOR-ed with the 128-bit state.

An additional AddRoundKey operation is performed at the beginning of first round which is known as key whitening phase. Each round key is generated by the AES key scheduling algorithm. Figure 1 shows the generation of last three rounds according to the AES-128 key schedule. For more detail on the AES key scheduling, one can refer the AES specification [START_REF]Advanced Encryption Standard[END_REF] SubWord RotWord SubWord RotWord SubWord RotWord

K 8 0,1 K 8 1,1 K 8 2,1 K 8 3,1 K 8 0,3 K 8 1,3 K 8 2,3 K 8 3,3 K 8 0,0 K 8 1,0 K 8 2,0 K 8 3,0 K 8 0,2 K 8 1,2 K 8 2,2 K 8 3,2 Rcon8 K 9 0,1 K 9 1,1 K 9 2,1 K 9 3,1 K 9 0,3 K 9 1,3 K 9 2,3 K 9 3,3 K 9 0,0 K 9 1,0 K 9 2,0 K 9 3,0 K 9 0,2 K 9 1,2 K 9 2,2 K 9 3,2

Notations

In the rest of the paper we use following symbols and notations: SubBytes, ShiftRows,and MixColumns will be referred as SB, SR and M C respectively and the corresponding inverse functions as SB -1 , SR -1 and M C -1 .

K r i,j : Represent {i, j} byte of the r th round key K r . C i,j : Represent {i, j} byte of the fault-free ciphertext C. C * i,j : Represent {i, j} byte of the faulty ciphertext C * .

Fault Model Used

It is clear from the past research on DFA of AES that the fault model is the key to successful fault analysis. Slightest change in the fault model can drastically increase or decrease the complexity of the fault analysis. This fact was clearly depicted in [START_REF] Subidh | Differential Fault Analysis of AES using a Single Multiple-Byte Fault[END_REF] where it was shown that with the increase of number of byte faults the search space of the key drastically increases. In our proposed attack we follow the fault model of Peachman and Thomas [START_REF] Peacham | A DFA attack against the AES key schedule[END_REF] where the fault is expected to induce in the ninth round key while it is being executed and subsequently propagated to the entire tenth round key. We assume that the induced fault corrupts all the four bytes of the first column of the ninth round key. Figure 2 show the flow of fault in the last two round keys.

0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1

SubWord

RotWord

SubWord

RotWord

Existing Fault Analysis

The most recent attack against the AES-128 key schedule shows that two faulty ciphertexts are enough to reduce the key space to 2 32 choices [START_REF] Hee | New Differential Fault Analysis on AES Key Schedule: Two Faults Are Enough[END_REF]. The attack assumed a fault model where the induced fault corrupts three out of four bytes of the first column of the ninth round key K 9 . As Figure 3 depicts, the induced fault subsequently propagates to the tenth round key. The three key bytes : K 9 0,0 , K 9 1,0 , and K 9 2,0 are the modified bytes and induced differences due to the faults are a, b, and c respectively. As per the AES-128 key scheduling algorithm the fault is propagated to all the subsequent three bytes of the same row of the ninth round key. As the fault is induced during the generation of key therefore the fault in the ninth round key also propagated to tenth round key bytes. The fault values d, e, and f can be calculated as follows:

0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1

SubWord

RotWord

SubWord

RotWord

d = SB(K 9 1,3 ) ⊕ SB(K 9 1,3 ⊕ b) = SB(K 10 1,3 ⊕ K 10 1,2 ) ⊕ SB(K 10 1,3 ⊕ K 10 1,2 ⊕ b) (1)
e = SB(K 9 2,3 ) ⊕ SB(K 9 2,3 ⊕ c) = SB(K 10 2,3 ⊕ K 10 2,2 ) ⊕ SB(K 10 2,3 ⊕ K 10 2,2 ⊕ c) (2)
f = SB(K 9 0,3 ) ⊕ SB(K 9 0,3 ⊕ a) = SB(K 10 0,3 ⊕ K 10 0,2 ) ⊕ SB(K 10 0,3 ⊕ K 10 0,2 ⊕ a) (3)
The fault in the ninth round key affects the AES state after the ninth round AddRoundKey. Figure 4 shows the flow of fault in the last two rounds.

The fault-free and faulty ciphertexts (C, C * ) are known to the attacker. Therefore, he can represent the fault values {c, c, c, c}, at the input of ninth round using following equations:

c = SB -1 (C2,2 ⊕ K 10 2,2 ) ⊕ SB -1 (C * (2,2) ⊕ K 10 2,2 ⊕ c) = SB -1 (C2,3 ⊕ K 10 2,3 ) ⊕ SB -1 (C * (2,3) ⊕ K 10 2,3 ) = SB -1 (C2,0 ⊕ K 10 2,0 ) ⊕ SB -1 (C * (2,0) ⊕ K 10 2,0 ⊕ c) = SB -1 (C2,1 ⊕ K 10 2,1 ) ⊕ SB -1 (C * (2,1) ⊕ K 10 2,1 ) (4)
In the above set of equations the attacker guesses the values of c and gets the corresponding values of key quartet K 10 2,2 , K 10 2,3 , K 10 2,0 , K 10 2,1 . As there are 2 8 possibilities of c therefore the above set of equations will reduce the possible choices of K 10 2,2 , K 10 2,3 , K 10 2,0 , K 10 2,1 to 2 8 choices from 2 32 choices. For more details on the analysis, one can refer to [START_REF] Hee | New Differential Fault Analysis on AES Key Schedule: Two Faults Are Enough[END_REF][START_REF] Tunstall | Differential Fault Analysis of the Advanced Encryption Standard using a Single Fault[END_REF]. Similarly, the attacker uses another faulty ciphertext and again reduces the possible choices of K 10 2,2 , K 10 2,3 , K 10 2,0 , K 10 2,1 to 2 8 . Then he takes the intersection of two sets of values of K 10 2,2 , K 10 2,3 , K 10 2,0 , K 10 2,1 generated from two different faulty ciphertexts. The intersection uniquely determine the key quartet. Now the attacker uses equation [START_REF] Subidh | Acceleration of Differential Fault Analysis of the Advanced Encryption Standard Using Single Fault[END_REF] and determines the values of e from the values of c, K 10 2,2 and K 10 2,3 . He follows the same technique to uniquely determine the quartets K 10 0,0 , K 10 0,1 , K 10 0,2 , K 10 0,3 and K 10 1,0 , K 10 1,1 , K 10 1,2 , K 10 1,3 . Therefore, using two faulty ciphertexts the attacker can retrieve 12 bytes of the tenth round key K 10 . This implies that the attacker retrieve 96-bit and need to perform 32-bit brute-force search to get the master key.

Limitation of Existing Attack

The existing attack nicely reveals the secret key of AES-128 crypto-system using only two faulty ciphertexts. However, the attack still needs two faulty ciphertexts which is the bottle neck of the attack. First of all the induced faults need to corrupt three out of the four bytes of the first row of the ninth round key. However, in real life the probability of such an event is small. Fault induction methods such as described in [START_REF] Subidh | Differential Fault Analysis of AES using a Single Multiple-Byte Fault[END_REF][START_REF] Barenghi | Low Voltage Fault Attacks on the RSA Cryptosystem[END_REF][START_REF] Fukunaga | Practical Fault Attack on a Cryptographic LSI with ISO/IEC 18033-3 Block Ciphers[END_REF][START_REF] Selmane | Practical Setup Time Violation Attacks on AES[END_REF][START_REF] Skorobogatov | Optical Fault Induction Attacks[END_REF] gives an attacker an extent of control, but cannot precisely realize the number of faults. The probability of success reduces further if more than one fault inductions are necessary. If probability of getting such fault is p then the probability of getting two such fault is p 2 . It its quite obvious from the experimental result reported in [START_REF] Subidh | Differential Fault Analysis of AES using a Single Multiple-Byte Fault[END_REF][START_REF] Barenghi | Low Voltage Fault Attacks on the RSA Cryptosystem[END_REF][START_REF] Fukunaga | Practical Fault Attack on a Cryptographic LSI with ISO/IEC 18033-3 Block Ciphers[END_REF][START_REF] Selmane | Practical Setup Time Violation Attacks on AES[END_REF][START_REF] Skorobogatov | Optical Fault Induction Attacks[END_REF] that the value of p is quite small. Therefore, ideally an attacker would want an attack which require one faulty ciphertext.

In the next section we propose an improved attack which will produce the same results as in the existing attack using only one faulty ciphertext.

Proposed Attack Using Single Faulty Ciphertext

In our proposed attack, the attacker is expected to induce a fault which corrupts all four bytes of the first column of the ninth round key as depicted in Figure 2. The proposed fault model increased the fault coverage where eventually all the bytes of the ninth round key and subsequently all the bytes of the tenth round key are corrupted by the induced fault. In the previous attack only 12 out of 16 bytes of ninth round key were corrupted by the induced fault. As in Figure 3 only the first three rows of the ninth round input state matrix is corrupted by the faulty ninth round key K 9 . Therefore, only the first three rows of K 10 participate in forming differential equations. The last row of K 10 is not related to any fault values. Hence there is no trace of getting the last row's values. But in our fault model there is no such limitations.

Attack Principle

The proposed attack exploits the relation between the faulty byte at the input of the ninth round. Figure 5 depicts the flow of faults. At the input of ninth round, all the bytes of the state matrix S 0 are corrupted. However, each of the rows have same fault values, which helps in deducing the differential equations. We have the fault-free and faulty ciphertexts (C, C * ). Therefore, we can represent the fault values {m, m, m, m} at first the row of the state matrix S 0 as follows:

m = SB -1 (C0,0 ⊕ K 10 0,0 ) ⊕ SB -1 (C * (0,0) ⊕ K 10 0,0 ⊕ m ⊕ w) = SB -1 (C0,1 ⊕ K 10 0,1 ) ⊕ SB -1 (C * (0,1) ⊕ K 10 0,1 ⊕ w) = SB -1 (C0,2 ⊕ K 10 0,2 ) ⊕ SB -1 (C * (0,2) ⊕ K 10 0,2 ⊕ m ⊕ w) = SB -1 (C0,3 ⊕ K 10 0,3 ) ⊕ SB -1 (C * (0,3) ⊕ K 10 0,3 ⊕ w) (5)
Similarly, the fault values in the rest of the three rows of S 0 can be represented by the following equations:

n = SB -1 (C1,3 ⊕ K 10 1,3 ) ⊕ SB -1 (C * (1,3) ⊕ K 10 1,3 ⊕ x) = SB -1 (C1,0 ⊕ K 10 1,0 ) ⊕ SB -1 (C * (1,0) ⊕ K 10 1,0 ⊕ x ⊕ n) = SB -1 (C1,1 ⊕ K 10 1,1 ) ⊕ SB -1 (C * (1,1) ⊕ K 10 1,1 ⊕ x) = SB -1 (C1,2 ⊕ K 10 1,2 ) ⊕ SB -1 (C * (1,2) ⊕ K 10 1,2 ⊕ x ⊕ n) (6)
o = SB -1 (C2,2 ⊕ K 10 2,2 ) ⊕ SB -1 (C * (2,2) ⊕ K 10 2,2 ⊕ y ⊕ o) = SB -1 (C2,3 ⊕ K 10 2,3 ) ⊕ SB -1 (C * (2,3) ⊕ K 10 2,3 ⊕ y) = SB -1 (C2,0 ⊕ K 10 2,0 ) ⊕ SB -1 (C * (2,0) ⊕ K 10 2,0 ⊕ y ⊕ o) = SB -1 (C2,1 ⊕ K 10 2,1 ) ⊕ SB -1 (C * (2,1) ⊕ K 10 2,1 ⊕ y) (7)
p = SB -1 (C3,1 ⊕ K 10 3,1 ) ⊕ SB -1 (C * (3,1) ⊕ K 10 3,1 ⊕ z) = SB -1 (C3,2 ⊕ K 10 3,2 ) ⊕ SB -1 (C * (3,2) ⊕ K 10 3,2 ⊕ z ⊕ p) = SB -1 (C3,3 ⊕ K 10 3,3 ) ⊕ SB -1 (C * (3,3) ⊕ K 10 3,3 ⊕ z) = SB -1 (C3,0 ⊕ K 10 3,0 ) ⊕ SB -1 (C * (3,0) ⊕ K 10 3,0 ⊕ z ⊕ p) (8)
As per the AES-128 key scheduling algorithm the fault value w in the tenth round key K 10 can be express in terms of n by the following equations:

w = S(K 9 1,3 ) ⊕ S(K 9 1,3 ⊕ n) = S(K 10 1,3 ⊕ K 10 1,2 ) ⊕ S(K 10 1,3 ⊕ K 10 1,2 ⊕ n) (9)
Similarly, we can represent x, y, z by n, o, p respectively and K 10 using the following equations:

x = S(K 10 2,3 ⊕ K 10 2,2 ) ⊕ S(K 10 2,3 ⊕ K 10 2,2 ⊕ o) (10)
y = S(K 10 3,3 ⊕ K 10 3,2 ) ⊕ S(K 10 3,3 ⊕ K 10 3,2 ⊕ p) (11)
z = S(K 10 0,3 ⊕ K 10 0,2 ) ⊕ S(K 10 0,3 ⊕ K 10 0,2 ⊕ m) (12)
Now we have four sets of differential equations for the four quartets of key bytes like the attack in [START_REF] Tunstall | Differential Fault Analysis of the Advanced Encryption Standard using a Single Fault[END_REF]. However, we can not directly apply the solving technique proposed in [START_REF] Tunstall | Differential Fault Analysis of the Advanced Encryption Standard using a Single Fault[END_REF]. The reason is each set of equations contain six unknown variables. For, example the unknown variables in the first set of equations ( 5) are {K 10 0,0 , K 10 0,1 , K 10 0,2 , K 10 0,3 , m, w}. Therefore, in this case we have to guess all possible values of m and w. For one choice of (m, w) on an average we get one choice of K 10 0,0 , K 10 0,1 , K 10 0,2 , K 10 0,3 . Therefore, for all possible 2 16 choices of (m, w) we get 2 16 choices of the key quartet. If we apply the same technique to the other three sets of equations ( 6), ( 7), ( 8) we get 2 16 choices for each of the three quartets. Therefore, finally we get (2 16 ) 4 = 2 64 choices of the key K 10 which is not in practical limits. This means the previous solving technique is not directly applicable.

We follow divide and conquer technique to solve the above four sets of differential equations [START_REF] Subidh | Acceleration of Differential Fault Analysis of the Advanced Encryption Standard Using Single Fault[END_REF]. We use S-box difference table so that we can directly get the values of the key byte from the given S-box input difference and the output difference. We start with the first set of differential equations [START_REF] Biham | Differential Fault Analysis of Secret Key Cryptosystems[END_REF]. In these sets of equation we guess the possible values of (m, w). For one choice of (m, w) we directly get on an average one choice of K 10 0,0 , K 10 0,1 , K 10 0,2 , K 10 0,3 using S-box difference table. Therefore, for 2 16 possible choices of (m, w) we get 2 16 choices of the key quartet with time complexity 2 16 . For, each value of m and the corresponding value of K 10 0,2 , K 10 0,3 we get the values of z using equation [START_REF] Fukunaga | Practical Fault Attack on a Cryptographic LSI with ISO/IEC 18033-3 Block Ciphers[END_REF]. Next we consider the fourth set of equations [START_REF]Sixth International Workshop on Fault Diagnosis and Tolerance in Cryptography, FDTC 2009[END_REF] where the values of z are already known from the previous steps. Therefore, in [START_REF]Sixth International Workshop on Fault Diagnosis and Tolerance in Cryptography, FDTC 2009[END_REF] we only guess the values of p and get the values corresponding to the quartet K 10 3,0 , K 10 3,1 , K 10 3,2 , K 10 3,3 . For each values of (m, w, z) and p we get one value of K 10 3,0 , K 10 3,1 , K 10 3,2 , K 10 3,3 . There are 2 16 possible choices of (m, w, z) and 2 8 choices of p. Therefore, together we have 2 24 choices of first and fourth quartets of key bytes from the first and fourth set of equations and the time complexity of the process is 2 24 . Now we use the values of K 10 3,3 , K 10 3,2 and p to get the corresponding values of y using equations [START_REF] Dusart | Differential Fault Analysis on A[END_REF]. Similarly, we choose the third set of equations [START_REF] Boneh | On the Importance of Checking Cryptographic Protocols for Faults (Extended Abstract)[END_REF] and get the 2 8 values K 10 2,0 , K 10 2,1 , K 10 2,2 , K 10 2,3 . Therefore, from the three sets of equations ( 5), [START_REF] Boneh | On the Importance of Checking Cryptographic Protocols for Faults (Extended Abstract)[END_REF], and ( 8) we get 2 32 choices of the first, third and fourth quartet of key bytes. Following the same technique we get the values of x from equation [START_REF] Giraud | DFA on AES[END_REF] and then get the 2 8 values of the second quartet of key bytes K 10 1,0 , K 10 1,1 , K 10 1,2 , K 10 1,3

using the second set of equations ( 6). Therefore, now we have 2 40 choices of all the four quartets of key bytes which is the tenth round key K 10 .

But still we have one equation left unchecked i.e. equation [START_REF] Chen | Differential Fault Analysis on AES Key Schedule and Some Coutnermeasures[END_REF]. Each of the tenth round key and the corresponding values of w is tested by equation [START_REF] Chen | Differential Fault Analysis on AES Key Schedule and Some Coutnermeasures[END_REF]. Those which satisfy are considered and the rest are discarded. Finally, 2 32 out of 2 40 candidates will satisfy equation [START_REF] Chen | Differential Fault Analysis on AES Key Schedule and Some Coutnermeasures[END_REF]. Therefore, finally we have 2 32 possible choices of the tenth round key K 10 . So, we need to do 32-bit brute-force search to get the master key.

However, the attack time complexity is 2 40 which is in practical limits. But the entire attack takes around 14 hours to generate all the possible 2 32 keys which is not feasible in terms of side-channel cryptanalysis.

In the next section we show a technique which further reduces the time complexity of the attack.

Time Complexity Reduction Technique

The proposed attack has got four steps. In the first step we deduce the possible choices K 10 0,i where 0 ≤ i ≤ 3 and z. Similarly, in second, third and fourth steps we get the possible choices of K 10 1,i , K 10 2,i ,and K 10 3,i respectively and the corresponding values of y, x, w.

In the first step, for a given value of w we get 2 8 choices of the quartet K 10 0,i from which we calculate z. However for getting z from equation ( 12) we need only two key bytes (K 10 0,3 , K 10 0,2 ) of quartet K 10 0,i . Therefore, we only consider the unique values of (K 10 0,3 , K 10 0,2 ) out of 2 8 values of K 10 0,i . The number of unique values of (K 10 0,3 , K 10 0,2 ) is given by

2 8 2 2 = 2 6 [2].
Similarly, in the rest of the three steps we consider 2 6 choices of (K 10 3,3 , K 10 3,2 ), (K 10 2,3 , K 10 2,2 ) and (K 10 1,3 , K 10 1,2 ) each for getting the values of y, x, and w respectively. This implies, for testing equation ( 9) indirectly we need only eight key bytes. For a given value of w the possible choices of these eight key bytes is (2 6 ) 4 = 2 24 . For all possible 2 8 choices of w we have 2 24 ×2 8 = 2 32 choice of the required eight bytes. Each choice of these eight key bytes are tested by equation ( 9) if they satisfy they are accepted, else they are discarded. Thus only 2 24 out of 2 32 choices satisfy the test. Those which satisfy are combined with rest of the eight key bytes (K 10 0,0 , K 10 0,1 ), (K 10 1,0 , K 10 1,1 ), (K 10 2,0 , K 10 2,1 ), (K 10 3,0 , K 10 3,1 ) . There are 2 2 × 2 2 × 2 2 × 2 2 = 2 8 choices for rest of the eight key bytes. Therefore, using this technique the equation ( 9) is tested for 2 32 times which correspond to the time complexity of the attack. This implies, that using this technique the time complexity of the attack reduced to 2 32 from 2 40 and hence comes in practical limits.

The simulated, attack written in C programing language was run on a 8 core Intel Xeon E5606 processor at 2.13 GHz speed. The attack takes less than 20 minutes to deduce the master key. Algorithm 1 summarizes the attack procedure. Get y from equation [START_REF] Dusart | Differential Fault Analysis on A[END_REF]. Test equation [START_REF] Chen | Differential Fault Analysis on AES Key Schedule and Some Coutnermeasures[END_REF]. for Each values of 16 {K 10 0,0 , K 10 0,1 , K 10 1,0 , K 10 1,1 , K 10 2,0 , K 10 2,1 , K 10 3,0 , K 10 3,1 } do Get K 10 . 17 Get the AES key K using AES Key Schedule.

Analysis of The Proposed Attack

There are total 20 differential equations in the proposed attack: 16 in four sets of equations ( 5), ( 6), [START_REF] Boneh | On the Importance of Checking Cryptographic Protocols for Faults (Extended Abstract)[END_REF], [START_REF]Sixth International Workshop on Fault Diagnosis and Tolerance in Cryptography, FDTC 2009[END_REF], and 4 more for equations ( 9), [START_REF] Giraud | DFA on AES[END_REF], [START_REF] Dusart | Differential Fault Analysis on A[END_REF], and [START_REF] Fukunaga | Practical Fault Attack on a Cryptographic LSI with ISO/IEC 18033-3 Block Ciphers[END_REF]. Each of these equations reduces the 2 16 possible choices of right hand side (corresponding to two S-box output) to 2 8 choices in the left hand side. Therefore, the reduction is given by ( 1 2 8 ). If there are N differential equations then the reduction is given by ( 12 8 ) N . If N equations contain M unknown variables then the reduced search space is give by ( 28 ) (M-N ) . For more details on the analysis, one can refer to the paper [START_REF] Tunstall | Differential Fault Analysis of the Advanced Encryption Standard using a Single Fault[END_REF]. We have 20 equations with 24 unknown variables; namely m, n, o, p, w, x, y, z and 16 unknown key bytes. Therefore, we have (2 8 ) (24-20) = 2 32 choices of final round key.

The time complexity of the attack is also 2 32 as explained in the previous section.

Note :

In some cases the attacker may not have access to the plaintext. So, he can not perform brute-force search on the possible guessed keys. In that case the attacker need to uniquely determine the key. Our attack can be applied in such a situation with two faulty ciphertexts. Say the faulty ciphertexts are (C * 1 , C * 2 ). If we apply our proposed attack on these two faulty ciphertexts, we will have two sets of fault values m 1 , n 1 , o 1 , p 1 , w 1 , x 1 , y 1 , z 1 and m 2 , n 2 , o 2 , p 2 , w 2 , x 2 , y 2 , z 2 . Each of these sets will produce corresponding 20 differential equations. Now we can apply our attack on each of these sets in step by step fashion. In the first step we guess the values of (w 1 , m 1 ) and get 2 16 choices of K 10 0,i where 0 ≤ i ≤ 3. For each of these choices we guess one value of w 2 and test equations [START_REF] Biham | Differential Fault Analysis of Secret Key Cryptosystems[END_REF] with the deduced key quartet K 10 0,i . If these two values satisfy the equations we accept them, else we discard them. There are 8 equations (two sets of equations ( 5) from two faulty ciphertexts ) and 8 unknown variables ( m 1 , m 2 , w 1 , w 2 and K 10 0,i ). This implies only one key candidate will satisfy the test.

In the second step we get the values of z 1 , z 2 and guess the possible values of p 1 , and p 2 each of which will produce 2 8 choices K 10 3,i . Intersection of these two sets will uniquely determine K 10 3,i . Following the same technique in third and fourth steps we can uniquely identify rest of the two key quartets K 10 1,i and K 10 2,i . So, finally we will have one choice of K 10 . The time complexity of these attack is 2 24 as initially we need to guess w 1 , w 2 , and m 1 to get the values K 10 0,i . The attack analysis is quite obvious. One faulty ciphertext reduces the key space to 2 32 from 2 128 . Therefore, two faulty ciphertexts will reduce the search space to ( 2 32 2 128 ) 2 × 2 128 = 1 2 64 . This implies only the actual key will left and rest of the guessed keys will be discarded by the attack.

Experimental Results

In order validate our attack we performed extensive simulations. Some of the simulation results are presented in this section. We used 8 core Intel Xeon E5606 processor of 2.13 GHz speed running on Linux (Ubuntu 10.4). The attack code was written in C programming language and compiled with gcc-4.4.3 with O3 optimization. The simulation was performed over 100 times on different random keys. Some of the results are shown in Table 1. The attack takes less than 20 minutes to reveal the secret key. The first column of Table 1 represents the random 16-bytes keys which were attacked. The second column represents the number of possible key generated by the attack. The last column represents the total time taken by the attack which corresponds to generating possible keys and then performing brute-force search on them to get the master key. In this section we compare our attack with some of the existing attacks in these area. The first DFA on AES key schedule was proposed by Giraud [START_REF] Giraud | DFA on AES[END_REF]. Giraud's attack requires 250 faulty ciphertexts and five days execution time to retrieve the secret key. The attack proposed by Chen and Yen in [START_REF] Chen | Differential Fault Analysis on AES Key Schedule and Some Coutnermeasures[END_REF], was an improvement over Giraud's attack where around 30 faulty ciphertexts were used. Peacham et. al. in [START_REF] Peacham | A DFA attack against the AES key schedule[END_REF] proposed an attack using 12 faulty ciphertext. DFA on AES key schedule using two faulty ciphertexts was first time proposed by Junko Takahashi et. al. [START_REF] Takahashi | DFA Mechanism on the AES Key Schedule[END_REF], which reduced the AES key space to 2 48 choices. Kim et. al. in [START_REF] Hee | New Differential Fault Analysis on AES Key Schedule: Two Faults Are Enough[END_REF], further improved the attack and reduced the key space to 2 32 possible choices using two faulty ciphertexts.

Compared to these attacks our attack requires only one faulty ciphertext. The required brute-force search for our attack is 32-bit which is same as in Kim et. al.'s attack [START_REF] Hee | New Differential Fault Analysis on AES Key Schedule: Two Faults Are Enough[END_REF]. Therefore, the proposed attack required minimal faulty ciphertexts to mount an attack on AES key schedule. Table 2 shows the comparison. Our Attack Multi byte fault 1 2 32

Conclusions

We proposed an improved attack on AES-128 key schedule. The attack require only one pair of fault-free and faulty ciphertexts. The proposed attack reduces the AES-128 key space to 32-bit. The time complexity of the attack is 2 32 . In order to validate the attack we have provided extensive simulation results. The simulated attack retrieves the secret key on less than 20 minutes on an 8 core Intel Xeon E5606 processor at 2.13 GHz speed. This shows that the attack is indeed practical.

2. 1

 1 The AES algorithm AES [1] is a 128-bit symmetric key block cipher comes in three different versions AES-128, AES-192, and AES-256 with key length 128-bit, 192-bit, and 256-bit respectively. The 128-bit intermediate results are represented as 4 × 4 matrix, known as state. Each elements of the matrix is a byte. The algorithm is divided into round function. Each round function except the last round consists of four transformations namely: SubBytes, ShiftRows, MixColumns and AddRoundKey. The three versions of AES has three different number of rounds : AES-128 has 10 rounds, AES-192 has 12 rounds, and AES-256 has 14 rounds. The last round of each of the three versions of AES does not have MixColumns operation. The four basic transformations are described as follows:

Fig. 1 .

 1 Fig. 1. Last three rounds of AES-128 key scheduling algorithm

Fig. 2 .

 2 Fig. 2. Fault induced in 9 th round key corrupting entire first column

Fig. 3 .

 3 Fig. 3. Fault induced in 9 th round key

Fig. 4 .

 4 Fig. 4. Propagation of Faults in the AES-datapath due to the 3-byte Fault Induction in the first column of K 9

Fig. 5 .

 5 Fig. 5. Flow 4 Bytes Fault Induced At First Column of K 9

Algorithm 1 : 1 for 2 for

 112 DFA on AES-128 Key Scheduling using Single Faulty Ciphertexts Input: P, C, C * Output: 128-bit AES key /*P is the plaintext */ Each candidates of w do Each candidates of m do 3 Get {K 10 0,2 , K 10 0,3 } from equations (5) 4 Get z from equation (12).

5 for Each candidates of p do 6 Get {K 10 3 , 2 , K 10 3 , 3 }

 563233 from the equations[START_REF]Sixth International Workshop on Fault Diagnosis and Tolerance in Cryptography, FDTC 2009[END_REF].

7

 7

8 for Each candidates of do 9 Get 10 Get

 8910 x from equation[START_REF] Giraud | DFA on AES[END_REF].

11 for Each candidates of n do 12 Get {K 10 1 , 2 , K 10 1 , 3 }

 11121213 from equations[START_REF] Blömer | Fault based cryptanalysis of the advanced encryption standard (AES)[END_REF].

13

 13

14 if Satisfied then 15

 15

Table 1 .

 1 Experimental Results

	Random 128-bit	Number of Possible Running Time
	Key	Keys	(Minutes)
	aaf3100fdf183ef427464fbf4db85f7a 3976380416 ≈ 2 31.88	17.65
	5da4e5407bae5f94cc4a264bf694c0d2 8744409088 ≈ 2 33.025	18.533
	19345421476b4e2b72191a845d30942a 8424587264 ≈ 2 32.971	18.791
	226156432112475303294a5bc2326a96 4018579456 ≈ 2 31.90	18.883
	5da4e5407bae5f94cc4a264bf694c0d2 4223047680 ≈ 2 31.975	19
	6 Comparison With the Previous Works

Table 2 .

 2 Comparison with existing attack on AES-128 key schedule

	Reference	Fault Model Number Exhaustive
			of Faults Search
	[9]	Single byte fault 22 to 44	1
	[16]	Multi byte fault	12	1
	[20]	Multi byte fault	2	2 48
	[13]	Multi byte fault	2	2 32

Acknowledgment

The authors would like to thank the anonymous reviewers for their comments and suggestions. The authors also extend their gratitude to the Department of Information Technology, India for funding this work.


Erich Wenger
email: erich.wenger@iaik.tugraz.at

Michael Hutter
email: michael.hutter@iaik.tugraz.at

A Hardware Processor Supporting Elliptic Curve Cryptography for Less Than 9 kGEs

Keywords: Low-Resource Hardware Implementation, Elliptic Curve Cryptography, Binary Extension Field, Embedded Systems

Elliptic Curve Cryptography (ECC) based processors have gained large attention in the context of embedded-system design due to their ability of efficient implementation. In this paper, we present a lowresource processor that supports ECC operations for less than 9 kGEs. We base our design on an optimized 16-bit microcontroller that provides high flexibility and scalability for various applications. The design allows the use of an optimized RAM-macro block and reduces the complexity by sharing various resources of the controller and the datapath. Our results improves the state of the art in low-resource F 2 163 ECC implementations (14 % less area needed compared to the best solution reported). The total size of the processor is 8,958 GEs for a 0.13 µm CMOS technology and needs 285 kcycles for a point multiplication. It shows that the proposed solution is well suitable for low-power designs by providing a power consumption of only 3.2 µW at 100 kHz.

Introduction

With the rapid development of more powerful and energy-saving devices, we unwittingly move towards the vision of the Internet of things. The required security services within this vision can be particularly achieved using Elliptic Curve Cryptography (ECC). This paper focuses on a low-resource hardware processor that provides ECC capabilities while meeting the low-area and lowpower requirements of embedded systems.

There exist many proposals for low-resource ECC processors. Most of the processors operate on binary-field elliptic curves and use full-precision arithmetic to increase the performance of point multiplication [START_REF] Bock | A Milestone Towards RFID Products Offering Asymmetric Authentication Based on Elliptic Curve Cryptography[END_REF][START_REF] Fürbass | ECC Processor with Low Die Size for RFID Applications[END_REF][START_REF] Kumar | Are standards compliant Elliptic Curve Cryptosystems feasible on RFID?[END_REF][START_REF] Wolkerstorfer | Is Elliptic-Curve Cryptography Suitable for Small Devices?[END_REF]. One of the most efficient solutions in terms of low-resource requirements has been reported by Lee et al. [START_REF] Lee | Elliptic-Curve-Based Security Processor for RFID[END_REF].

They presented a processor supporting a small elliptic curve over F 2 163 which makes use of a tiny 8-bit microcontroller to handle higher-level protocol implementations. The ECC operation of k • P is performed by a separated Modular Arithmetic Logic Unit (MALU). The processor needs 12,506 GEs and 276 kcycles to perform a point multiplication. However, the area estimations do not including program ROM and RAM to store intermediate results and the necessary secret scalar k. Similar datapath architectures have been reported by Batina et al. [START_REF] Batina | Low-Cost Elliptic Curve Cryptography for Wireless Sensor Networks[END_REF] and Sakiyama et al. [START_REF] Sakiyama | Smallfootprint ALU for public-key processors for pervasive security[END_REF]. Hein et al. [START_REF] Hein | ECC is Ready for RFID -A Proof in Silicon[END_REF] reported a very efficient co-processor (without microcontroller) for the same elliptic curve supporting multi-precision arithmetics. They applied a finite-state machine based control-engine needing 11,904 GEs including a standard-cell based RAM memory.

In this paper, we present a low-resource hardware processor that is based on a 16-bit multi-precision architecture and an area-optimized custom microcontroller. This combination allows several optimizations. First, it allows the use of an efficient RAM-macro block that reduces the area requirements for short-term memory significantly. Second, since both the microcontroller and the datapath use a 16-bit architecture, all resources are shared to minimize the area footprint of the processor. As an outcome, we present a complete solution including memory for short-term (RAM) as well as long-term storage (program ROM), controller, and datapath using a polynomial multiply-accumulate (MAC) unit. In addition, we present results of higher-level protocol implementations of the Elliptic Curve Digital Signature Algorithm (ECDSA) [START_REF]3: Digital Signature Standard (DSS)[END_REF] and give results for digital signature generation as well as verification. For a point multiplication, our NIST B-163 based processor needs only 8,958 GEs in total and performs a point multiplication within 285 kcycles. We demonstrate that the proposed solution is also well suitable for low-resource embedded systems by providing a power consumption of only 3.2 µW at 100 kHz.

The rest of the article is structured as follows. In Section 2, a brief introduction into elliptic curve cryptography is given. In Section 3, we face the challenge of low-resource ECC hardware implementations and explore various design possibilities. We evaluate appropriate word sizes of a processor and analyze different memory types. Section 4 presents details about the hardware architecture of our processor. Details about the implementation are given in Section 5. In Section 6, the results are presented. Conclusions are drawn in Section 7.

Elliptic Curve Cryptography

Within Elliptic Curve Cryptography (ECC), not only a single number or polynomial is used, but a pair of those. Each pair (x, y) of such numbers that satisfy the general Weierstrass equation

E : y 2 + a 1 xy + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6 (1)
is called a point on an elliptic curve. When a certain type of number is used, in our case binary polynomials within GF (2 m ), the Weierstrass equation can be reduced to

y 2 + xy = x 3 + ax 2 + b.
(2)

Among the most critical operation in terms of speed and security is the ECC point multiplication. The implementation of this multiplication has to be secure against various implementation attacks such as side-channel and fault-analysis attacks. The Montgomery ladder [START_REF] Montgomery | Speeding the Pollard and Elliptic Curve Methods of Factorization[END_REF][START_REF] Joye | The Montgomery Powering Ladder[END_REF] provides very beneficial properties in this context. We therefore decided to use it for our design and applied the very fast group-operation formulas of López and Dahab [START_REF] López | Fast Multiplication on Elliptic Curves over GF(2 m ) without Precomputation[END_REF]. The formulas are based on projective coordinates (which avoid expensive field inversions) that can be nicely combined with proposed countermeasures (see also the work of Junfeng Fan et al. [START_REF] Fan | State-of-the-Art of Secure ECC Implementations: A Survey on known Side-Channel Attacks and Countermeasures[END_REF]) such as randomized projective coordinates (RPC) [START_REF] Coron | Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems[END_REF] or pointvalidity checks [START_REF] Ebeid | Securing the Elliptic Curve Montgomery Ladder Against Fault Attacks[END_REF].

We use the following notations throughout the paper (similar to [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]). Let f (z) = z m + r(z) denote an irreducible binary polynomial of degree m. The elements of F 2 m are binary polynomials of degree at most m -1. An addition of field elements is the usual addition of binary polynomials. Multiplication is

performed modulo f (z). A field element a(z) = a m-1 z m-1 + • • • + a 2 z 2 + a 1 z + a 0 is
associated with the binary vector a = (a m-1 , . . . , a 2 , a 1 , a 0 ) of length m. Furthermore, let N = m/W be the number of words with width W needed to store a(z). A = (A[N -1], . . . , A [START_REF] Batina | Low-Cost Elliptic Curve Cryptography for Wireless Sensor Networks[END_REF], A [START_REF] Avanzi | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF], A[0]), where the rightmost bit of A[0] is a 0 , and the leftmost (W N -m) bits of A[N -1] are unused (always set to zero).

For further readings on ECC we refer to several books [START_REF] Avanzi | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF][START_REF] Blake | Elliptic Curves in Cryptography[END_REF][START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF][START_REF] Koblitz | A Course in Number Theory and Cryptography[END_REF] that discuss the topic extensively.

Design-Space Exploration

In this section, we will explore different hardware-design options to obtain best results for a low-resource ECC processor. The design goals have been to meet all requirements of embedded systems which are low area (due to the production costs), low power (due to a possible contactless operation), appropriate speed (required for certain applications), security and flexibility. Due to the latter requirement, we decided to base our design on a customized microcontroller. This has the advantage of being modular in terms of protocol implementations and modifications of already implemented solutions.

By following the principles of hardware/software co-design, it showed that the dominant factors of ECC processors are the finite-field hardware multiplier and the type and size of the applied data memory. In the following, we discuss these factors and explore the design space to find the best solution for our objectives.

The Hardware Multiplier

One of the most area consuming parts within the ALU of an ECC-hardware design is the finite-field multiplier. The size, speed, and power consumption of such a multiplier largely depends on the word size of the processor and the underlying finite field. Figure 1 shows the hardware architecture of a 4-bit multiplier for binary-field (carry-less multiplier), prime-field (integer multiplier), and dualfield arithmetic. The basic structure of all three types of multiplier is the same. Only the adder structure needs to be adopted. Table 1 shows the area evaluation of different hardware-multiplier types. We evaluated multipliers for prime-field, binary-field, and dual-field arithmetic for word sizes of 8, 16, 32, and 64 bits (on register-transfer level). For the evaluation we used the UMC-L130 CMOS technology where an AND gate needs 1.25 GEs, a XOR gate needs 2.75 GEs, and a full-adder cell needs 5.5 GEs.

Obviously the area requirement scales quadratically with the given word size and carry-less multipliers provide the lowest area footprint and lowest increase in area for all given word sizes. Runtime approximations for an ECC point multiplication showed that the word size of the carry-less multiplier must be at least 16 bits in order to achieve a sensible runtime.

Next to a carry-less multiplier, an integer multiplier is necessary to provide operations for higher-level protocols (e.g. ECDSA). Note that this multiplier is needed only very few times for most protocols (only four prime field multiplications are required for ECDSA signature generation, for instance). Thus, lower word sizes are acceptable since no significant reduction in speed is expected. We therefore decided to implement a 16-bit carry-less multiplier (to provide an appropriate speed for a point multiplication) and an 8-bit integer multiplier instead of a dual-field 16-bit multiplier (which needs 1,946 GEs). This would sum up to 1,226 GEs which is 720 GEs less than for a dual-field multiplier.

The Memory Type and Architecture

One of the most area expensive chip components of ECC processors is the Random Access Memory (RAM). RAM is necessary to store intermediate values (e.g. point coordinates during point multiplication k • P ) and the secret scalar k. The size of the memory varies depending on the requirements of the ECC formulas (the formulas of López Dahab [START_REF] López | Fast Multiplication on Elliptic Curves over GF(2 m ) without Precomputation[END_REF] need at least 5 registers of memory for full-precision architectures and 6 registers for multi-precision architectures due to the need of intermediate storage of in-place operations).

In Table 2, we compare different 16 × 128-bit RAM types concerning their area requirements. We compare standard-cell based implementations with dedicated RAM macro blocks synthesized in CMOS UMC-L130 technology. The standard-cell based RAM implementations (register and latch based) have been designed on RTL-level and synthesized using Cadence RTL compiler [START_REF]The Cadence Design Systems Website[END_REF]. The RAM-macro blocks have been generated using the Standard Memory Compiler FSA0A Memaker 200901.1.1 by the Faraday Technology Corporation [START_REF]Faraday FSA0A C 0.18 µm ASIC Standard Cell Library[END_REF]. All except of one type of RAM provide a single read-port and a single write-port. There is one S-RAM macro that features a dual-port read/write interface.

It shows that the latch-based RAM is about 12 % smaller than the registerbased RAM. This is because the size of a flip-flop is 5 GE and the size of a latch is 4 GE. This 25 % difference in area is debilitated because some additional registers and control logic is required so that the latch-based RAM works the same way as the register-based RAM. Adding a second read port to those RAMs would be relatively cheap in terms of chip area (it would require about 3,000 GEs in addition by introducing a second multiplexer at the output). Note that a dualport memory would increase the performance of a multi-precision multiplication by a factor of about two.

From the two available single-port RAM macros, the register-file macro is about 50 % smaller than the S-RAM macro. The dual-port S-RAM macro, in contrast, is only 12 % larger than the single-port S-RAM macro, however, it is about 2.3 times larger than the register-file based RAM macro.

The register-file RAM macro provides best performance in our evaluation scenario. We performed several power simulations using Cadence Encounter and obtained similar results for the register-file RAM macro and the standard-cell based RAM architectures. The main disadvantages of the register-file macro are the lack of a second read port (speed) and the limit of clock-synchronous read operations. The lack of a second read port can be compensated by using temporary working registers. The lack of an asynchronous read functionality can be balanced with a more difficult control logic.

Hardware Architecture

In this section, we introduce the hardware architecture of our processor. It is based on the microprocessor design called Neptun [START_REF] Wenger | Low-Resource Hardware Design of an Elliptic Curve Processor for Contactless Devices[END_REF], which uses a Harvard architecture. This allows to fetch, decode, execute, and store data within the same clock cycle and allows low-area optimizations due to the choice of different memory types and sizes. Figure 2 shows the block diagram of the architecture. It is mainly composed of a Central Processing Unit (CPU) including register file and Arithmetic Logic Unit (ALU), and memories for program code, constants, and data.

Central Processing Unit (CPU)

The heart of the processor is the 16-bit CPU. It is composed of several internal registers and an ECC optimized ALU. The register file consists of a program counter (PC), a stack pointer (SP), three base registers, four working registers, and an accumulator register: The program counter is used as index for the program memory. The stack pointer (SP) is needed to store registers on the data memory. The stack is also used to store program-return addresses that are needed for function calls. In order to address certain base addresses within the data memory, three base registers are used. We integrated two source registers and one destination register. They are used together with a 4-bit offset to address data in the memory. The offset address is stored within a program word. We implemented four 16-bit working registers that can be used as general-purpose registers. The registers are needed for almost any ECC operation and are used to reduce the number of memory-read cycles within the finite-field multiplication.

The accumulator register (ACC) is needed for the multiply-accumulate operation of the 163-bit multi-precision multiplication.

We integrated several optimizations to increase the performance of ECC operations. First, the ALU accesses data directly without loading it first into CPU registers (as it is in the case of conventional microcontrollers). In the first clock cycle, the data is addressed in the memory. In the second cycle, the data is processed by the ALU and the result is stored back in memory within the same clock cycle. This increases the performance of memory-access operations significantly. Second, loading and processing of data is done simultaneously by the processor. This avoids unnecessary idle cycles and improves the efficiency of multi-precision arithmetic operations. Those optimizations are described in more detail in [START_REF] Wenger | Low-Resource Hardware Design of an Elliptic Curve Processor for Contactless Devices[END_REF].

Arithmetic Logic Unit (ALU). The arithmetic logic unit (ALU) mainly consists of a reduction-logic unit, a carry-less multiplier, an arithmetic unit (addition/subtraction), and a logic unit (supporting OR, AND, XOR, and shift operations). For higher-level protocols, an integer multiplier is needed in addition (drawn with dashed lines). Figure 3 shows a high-level diagram of the ALU. We also integrated an operand isolation technique for each submodule which reduces the power-consumption significantly.

Memory for Program, Data, and Constants

Our processor provides a long-term storage memory that mainly stores the program for ECC point multiplication. The memory provides 72 control signals and contains up to 1,800 entries depending on the implemented algorithms and higher-level protocols. Most of the control signals are used to control the dataflow within the CPU. Best area results have been achieved by directly synthesizing the memory table as Read Only Memory (ROM) using standard cells. Experiments in which a 16-bit instruction set or a ROM macro have been introduced resulted in a larger area requirement.

For short-term data storage, we used a 16-bit RAM macro (register-file based) as discussed in Section 3. Note that in contrast to most processors reported in literature [START_REF] Bock | A Milestone Towards RFID Products Offering Asymmetric Authentication Based on Elliptic Curve Cryptography[END_REF][START_REF] Kumar | Are standards compliant Elliptic Curve Cryptosystems feasible on RFID?[END_REF][START_REF] Lee | Elliptic-Curve-Based Security Processor for RFID[END_REF][START_REF] Öztürk | Low-Power Elliptic Curve Cryptography Using Scaled Modular Arithmetic[END_REF], we include the number for the required storage of the secret scalar k. For an ECC point multiplication, 1,296 bits (81 entries) are necessary (we used a 16 × 84 macro in that case). For higher-level protocols, additional memory is needed (e.g. 1,536 bits for ECDSA signature generation (16 × 96 macro) and 2,384 bits for ECDSA signature verification (16 × 152 macro)).

ECC constants have been stored in a ROM. The ROM has been implemented as a look-up table and stores between 880 and 2,564 bits such as the x and y coordinate of the base point P , the ECC parameters a and b (see Equation ( 2)), and the irreducible polynomial f (z).

The input/output of data has been realized via memory mapped I/O. Data can be written and read using a 16-bit parallel interface.

Implementation Details

In the following, we give details about the implemented carryless multiplyaccumulate unit and the modular arithmetics in order to perform ECC operations.

Carry-Less Multiply-Accumulate Unit

The multi-precision multiplication over F 2 163 has been realized following a multiply-accumulate (MAC) approach. There exist several publications that make use of MAC units to increase the performance of modular multiplication (see e.g. the work of [START_REF] Eberle | A Public-key Cryptographic Processor for RSA and ECC[END_REF][START_REF] Großschädl | Full-Custom VLSI Design of a Unified Multiplier for Elliptic Curve Cryptography on RFID Tags[END_REF][START_REF] Großschädl | Optimized RISC Architecture for Multiple-Precision Modular Arithmetic[END_REF][START_REF] Hein | ECC is Ready for RFID -A Proof in Silicon[END_REF][START_REF] Tillich | VLSI Implementation of a Functional Unit to Accelerate ECC and AES on 32-bit Processors[END_REF]). We implemented the multiplication by a product-scanning form (often referred as Comba multiplication), where each partial product of

A[i]•B[j] gets accumulated to a common sum (ACC 1 , ACC 0 ), i.e. (ACC 1 , ACC 0 ) ← (ACC 1 , ACC 0 ) + A[i] • B[j].
Note that for the polynomial MAC unit the handling of carry propagation is not needed. Thus, the accumulator register needs a size of only (2W -1) bits.

We implemented several improvements to increase the performance. First, the entire multiplication algorithm has been unrolled so that no extra cycles are wasted for loop operations. Second, we reused the working registers as a memory cache to reduce the number of necessary load operations. With each working register used, the total number of read operations has been reduced by about 2N . Third, we added a third word to the accumulator register (ACC 2 , ACC 1 , ACC 0 ) in order to allow efficient reduction of the accumulated sum. Thus, the MAC operation is performed on the words (ACC 2 , ACC 1 ) instead of (ACC 1 , ACC 0 ) and Algorithm 1 Polynomial multiplication with interleaved reduction.

Require: Binary polynomials a(z) and b(z) of degree at most m -1. Ensure: c(z) = a(z) • b(z) mod f (z).

1: ACC ← 0 2: for i from 0 to N -1 do 3:

for each element of {(i, j)|i + j = k, 0 ≤ i, j ≤ N -1} do 4: (ACC2, ACC1) ← (ACC2, ACC1) + A[i] • B[j]. 5:
end for 6:

C[k] ← ACC1.

7:

ACC ← ACC W . 8: end for 9: ACC ← higher(ACC). 10: for k from t to 2N -2 do 11:

for each element of {(i, j)|i

+ j = k, 0 ≤ i, j ≤ t -1} do 12: (ACC2, ACC1) ← (ACC2, ACC1) + A[i] • B[j]. 13:
end for 14:

C[k -N -1] ← C[k -N -1] + reduce(ACC). 15: ACC ← ACC W . 16: end for 17: C[N -1] ← lower(C[N -1]) + reduce(ACC). 18: ACC ← ACC W . 19: C[0] ← C[0] + reduce(ACC + higher(C[N -1])) W . 20: C[N -1] ← lower(C[N -1]) W . 21: Return(c).
ACC 0 is used to store the previous intermediate result. A detailed description of the reduction method is given in the following subsection.

Algorithm 1 shows the algorithm of the implemented polynomial multiplication. The polynomials a(z) and b(z) get multiplied and the reduced result is stored in c(z). In the lines 1 to 8, the lower N words of the result c(z) are calculated. Note that in this phase the ACC 0 register is not used. In line 9, the lower (m -W (N -1)) bits of the accumulator need to be cleared. Those are the bits of the results that do not need to be reduced. The lines 10-16 calculate the higher N words of c(z) and reduce them immediately. According to the recommended NIST irreducible polynomial B-163 f (z) = z 163 + z 7 + z 6 + z 3 + 1, the reduction function (line 14) can be written as

reduce(ACC) = ACC (W + 3) + ACC W + (3) ACC (W -3) + ACC (W -4) ∧ (2 W -1).
Finally, in lines 17-20 the rest of the accumulator and the higher bits of C[N -1] get reduced.

Polynomial NIST B-163 Reduction Logic. We make use of the recommended NIST irreducible polynomial B-163 to perform a very efficient modular It should be noted that although the reduction logic has been specially optimized for NIST B-163, the CPU is capable of handling arbitrary irreducible polynomials. Thus requirements such as flexibility and extendability are ensured.

Modular Arithmetic

Modular Addition. The simplest operation is the modular addition. It is a simple XOR operation. Neither a carry flag nor a finite-field reduction need to be considered. Modular addition over F 2 163 needs 35 clock cycles on our processor. Modular Multiplication. Modular multiplication has been realized using the carryless multiply-accumulate unit described in Section 5.1. Our processor needs 222 clock cycles for a 163-bit multiplication. Modular Squaring. Modular squaring can be performed very efficiently. The binary representation of the polynomial can be easily squared by inserting a 0 between each consecutive bit of the polynomial, e.g.

a(z) = a m-1 z m-1 +• • •+ a 2 z 2 + a 1 z + a 0 would results in a(z) 2 = a m-1 z 2m-2 + • • • + a 2 z 4 + a 1 z 2 + a 0 .
This can be realized with only a few additional hardware components. The polynomial-reduction logic can be reused for squaring. One modular squaring needs 41 clock cycles on our processor and thus is 5.4 times faster than a modular multiplication. Modular Inversion. Modular inversion is required to transform the projective coordinates back into affine. For this operation, we made use of Fermat's little theorem [START_REF] Itoh | Effective recursive algorithm for computing multiplicative inverses in GF (2 m )[END_REF] that states that a = a 2 m mod f (z) ∀a ∈ F 2 m . As a result, a -1 ≡ a 2 m -2 mod f (z). This exponentiation can be performed using 162 squaring and only 9 multiplications for the NIST B-163 binary field. As a result 11,031 cycles are needed for an inversion.

Results

We synthesized our processor using different CMOS technologies from various manufacturers. For synthesis, we used the Cadence RTL compiler [START_REF]The Cadence Design Systems Website[END_REF] Version v08.10. Table 3 shows the total area and power-consumption estimation of the processor using latch-based RAMs 1 (described in Section 3.2). The powerconsumption estimations were made using Cadence Encounter Version v08.10. All obtained area results are within a 20 % margin. In view of power consumption, best performance had been obtained for the UMC-L130 technology. For all following approximations we used register-based RAM macros.

In Table 4, the area and power requirements for individual chip components are listed. The memory needs most of the area which is 5,399 GEs. The CPU needs 3,556 GEs in total where only 849 GEs are used for the carry-less multiplier. The total size of the processor sums up to 8,958 GEs.

In Table 5, we compare our results with related work. There exist many publications of ECC processors over F 2 163 . Most of those processors use full-precision arithmetic to perform the point multiplication. For a fair comparison, we listed the results of the authors for different digit sizes (d=1...8). All implementations need between 10,392 GEs and 16,247 GEs of chip area and between 47 and 430 kcycles for the computation of k •P . Our implementation needs 8,958 GEs of area which is 1,434 GEs less area than the best reported solution. This is an area improvement by about 14 %. The number of needed clock cycles can be compared with the full-precision solutions with d=1. The power and energy consumption is very low and fulfills most requirements of embedded-system designs.

Results for Higher-Level Protocol Implementations

As a higher-level protocol, we implemented the Elliptic Curve Digital Signature Algorithm (ECDSA) [START_REF]3: Digital Signature Standard (DSS)[END_REF]. In addition to a point multiplication over the binary field F 2 163 , ECDSA needs a hash function and several prime-field arithmetic operations to generate and verify a digital signature. As a hash function, we implemented the 160-bit SHA-1 algorithm according to ISO/IEC FIPS-180-3 [START_REF]Secure Hash Standard[END_REF].

Replacing the SHA-1 algorithm with one of the current SHA-3 candidates [START_REF] Iaik | Hash Function Zoo[END_REF] would be easily possible. For prime-field multiplications and inversion, we decided to implemented Montgomery-arithmetic operations. We implemented the Finely Integrated Product Scanning Form (FIPS) according to Koç et al. [START_REF] Koç | Analyzing and Comparing Montgomery Multiplication Algorithms[END_REF]. The algorithm is used only four times, so we optimized the code for low area (no a The numbers include y-recovery, randomized projective coordinates (RPC) sidechannel countermeasure [START_REF] Coron | Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems[END_REF], and ECC point-validity check [START_REF] Ebeid | Securing the Elliptic Curve Montgomery Ladder Against Fault Attacks[END_REF]. b Includes the SHA-1 hash function [START_REF]Secure Hash Standard[END_REF], Random Number Generation (RNG) [START_REF]3: Digital Signature Standard (DSS)[END_REF], and prime-field arithmetics.

loop unrolling etc.). Furthermore, we implemented the Montgomery-inversion algorithm according to Kalinski et al. [START_REF] Kaliski | The Montgomery Inverse and its Applications[END_REF].

For signature verification, we applied Shamir's trick [START_REF] De Rooij | Efficient Exponentiation using Procomputation and Vector Addition Chains[END_REF][START_REF]A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms[END_REF] to improve the performance of multiple-point multiplication. All described operations for ECDSA have been implemented as Assembler functions for our processor and have been stored in program memory. Table 6 shows the results after synthesizing the processor. For ECDSA signature generation, our processor needs 15,387 GEs which outperforms existing solutions in terms of area, power, and speed [START_REF] Fürbass | ECC Processor with Low Die Size for RFID Applications[END_REF][START_REF] Hutter | An ECDSA Processor for RFID Authentication[END_REF][START_REF] Wenger | Low-Resource Hardware Design of an Elliptic Curve Processor for Contactless Devices[END_REF][START_REF] Wolkerstorfer | Is Elliptic-Curve Cryptography Suitable for Small Devices?[END_REF]. Signature verification can be realized using a chip area of 16,005 GEs.

Conclusions

In this paper, we presented a low-resource implementation of an ECC hardware processor. The processor needs 8,958 GEs and performs a point multiplication within 285 kcycles. The power consumption is about 3.2 µW at 100 kHz. We met the low-resource constraints of embedded systems by applying a very modular microcontroller architecture that allows the execution of higher-level protocols like ECDSA. The elliptic-curve operations have been performed over the NIST F 2 163 elliptic curve using multi-precision arithmetic. The outcome improves the state of the art in low area ECC hardware designs and provides even a smaller area footprint than most of the proposed SHA-3 candidates [START_REF] Iaik | Hash Function Zoo[END_REF].

A Statistics for ECC multiplication

During the development of the ECC and ECDSA functions we used a statistics feature of our tool-chain to investigate the code-line and cycle consumption of each function. Table 7 shows the number of times each function is called, the size of each function in code lines and the total runtime of each function. Even though the multiplication algorithm is optimized down to 222 cycles it still covers 74 % of the total runtime. Table 8 shows how often each and every type of instruction is used. The parallelized commands are a combination of other commands. They cover 71 % of the total runtime. Note that only 4.4 % of the total runtime is used for programflow instructions such as RET, CALL, BRA, and JMP. This overhead would not exist if a dedicated state machine instead of a CPU with instruction set would be used.

Fig. 1 .

 1 Fig. 1. General 4-bit multiplier structure to the left. Carry-less, integer, and dual-field adder (from top to bottom) on the right.

Fig. 3 .

 3 Fig. 3. High-level diagram of the arithmetic logic unit.

Fig. 4 .

 4 Fig. 4. Using the dedicated reduction logic, the content of the accumulator is reduced and stored in C [i] (hold in data memory) with index i.

Figure 4

 4 shows the dedicated reduction logic.

Table 1 .

 1 Area evaluation of different hardware-multiplier types.

	Finite	Required adder	8 bit	16 bit	32 bit	64 bit
	Field	cells per bit	[GE]	[GE]	[GE]	[GE]
	GF (2 m )	XOR	211	850	3,389	13,508
	GF (p)	FA	376	1,616	6,688	26,336
	Dual field	AND + FA	458	1,946	8,018	31,514

Table 2 .

 2 Area evaluation of different 16 × 128-bit RAM architectures.

	Type	Port	Storage	Logic	Total
			[GEs]	[GEs]	[GEs]
	Std. cells (registers)	Single	10,281	2,941	13,926
	Std. cells (latches)	Single	8,388	3,119	12,221
	Macro S-RAM	Dual	-	-	6,737
	Macro S-RAM a	Single	-	-	6,000
	Macro register-file	Single	-	-	2,955

a Approximated based on UMC 180 nm technology.

Table 3 .

 3 Size and power estimations of our processor for different CMOS technologies using Latch-based RAMs.

	Technology	Area NAND Gate Total Area	Power Leakage
		[µm 2 ]	[µm 2 ]	[GE] [µW @1MHz]	[µW ]
	AMS c35b4	693,948	54.600	12,710	696.3	0.63
	UMC f180GII	139,469	9.374	14,878	107.1	0.53
	UMC f130SP	71,745	5.120	14,013	31.4	1.37
	UMC f090SP	39,550	3.136	12,612	70.1	54.32

Table 4 .

 4 Size and power consumption of individual chip components.

	Component	Area	Area	Power	Power
		[GE]	[%]	[µW @1MHz]	[%]
	Memory	5,399	60.27	11.57	35.77
	Program memory	2,471	27.58	4.24	13.10
	Data RAM	2,528	28.22	4.66	14.41
	Constant ROM	256	2.56	1.62	5.01
	CPU	3,556	39.70	18.93	58.54
	ALU	1,837	20.51	11.05	34.16
	Carry-less multiplier	849	9.48	2.30	7.12
	Logic unit	348	3.88	2.15	6.65
	Arithmetic unit	93	1.04	0.37	1.15
	Register Set	875	9.77	1.48	4.58
	Total Area	8,958	100.00	32.34	100.00

Table 5 .

 5 Comparison with related work.

	Related	Area	Cycles	Power Energy	CMOS
	Work	[GE] [kCycles] [µW @1MHz]	[µJ]	Technology
	Kumar06 d=1 [25]	15,094	430	-	-	AMI C35
	Batina06 a d=4 [2]	14,816	95	27.00	2.57	130 nm
	Batina06 a d=3 [2]	14,258	125	27.00	3.38	130 nm
	Batina06 a d=2 [2]	13,681	182	27.00	4.91	130 nm
	Batina06 a d=1 [2]	13,104	354	27.00	9.56	130 nm
	Bock08 d=8 [4]	16,247	47	148.76	6.99	INF SRF55V01P
	Bock08 d=4 [4]	12,876	80	93.27	7.46	INF SRF55V01P
	Bock08 d=1 [4]	10,392	280	54.31	15.21	INF SRF55V01P
	Lee08 d=4 [26]	15,356	79	37.39	2.95	UMC L130
	Lee08 d=3 [26]	14,729	101	38.32	3.87	UMC L130
	Lee08 d=2 [26]	14,064	145	36.52	5.30	UMC L130
	Lee08 d=1 [26]	12,506	276	32.42	8.95	UMC L130
	Hein08 16-bit [17]	11,904	296	101.87	30.15	UMC L180
	This work 16-bit 8,958	286	32.34	9.25	UMC L130
	a For a fair comparison a RAM approximated with 4,890 GE was added. The power
	values lack the power consumption of this RAM.

Table 6 .

 6 Area and power estimations of our processor supporting ECDSA.

	Program	Area	Cycles Lines of	Power Energy
		[GE] [kCycles]	Code [µW @1MHz]	[µJ]
	ECC Only	8,958	294	637	32.09	9.43
	ECC Protected a	9,728	298	828	32.48	9.68
	ECDSA Sign a,b	15,387	378	1771	41.11	15.54
	ECDSA Verify b	16,005	605	1784	40.76	24.66

Table 7 .

 7 Functions used during ECC point multiplication with y-recovery and pointvalidity check.

	Function	Calls	Code Lines	Cycles
	B163.Multiplication	990	222	219,780
	B163.Square	969	41	39,729
	B163.Add	490	35	17,150
	PointOperation.Multiplication	1	148	16,636
	B163.FermatInverseHelp	7	31	2,041
	Utilities.Copy	16	24	384
	PointOperation.yRecovery	1	90	90
	B163.FermatInverse	1	88	88
	PointOperation.isValidPoint	1	44	44
	Utilities.CMP	1	35	35
	Utilities.Clear	2	13	26
	TOTAL	2,479	771	296,003
	TOTAL including test functions	2,480	828	296,547

Table 8 .

 8 Instructions used during an ECC point multiplication with y-recovery and point-validity check.

	Mnemonic Description	CPI Cycles Used
	PAR: BMULACC | LD	1 109,869	111
	PAR: MOVNF | LD	1	65,707	83
	LD	Load from memory	1	35,410	65
	PAR: BREDUCE ADD ST | BRSACC	1	13,818	14
	PAR: BMULACC | ST | BRSACC	1	11,859	12
	PAR: BREDUCE ADDBYTE ST | BRSACC	1	9,690	10
	CALL	Call a function	3	7,440	70
	LDI	Load Immediate	1	6,900	105
	AND	Logic AND	1	6,038	7
	PAR: XOR | ST		1	5,390	11
	MOVNF	Copy register to register without flag update	1	5,269	47
	RET	Return from function	2	4,960	13
	BMULACC	Binary multiply-accumulate	1	3,876	4
	STR	Store a register to memory	1	2,725	32
	XOR	Logic XOR	1	2,120	3
	LDR	Load from memory and store to register	2	1,942	10
	ADDI	Add with carry	1	573	11
	BRA	Branch if flag is set/cleared	1	488	6
	PUSH	Push a value to the stack	2	338	5
	POP	Pop a value from the stack	2	336	4
	LSI	Left shift by immediate	1	326	4
	SUBI	Subtract with carry	1	324	6
	ADD	Add	1	163	2
	RS	Right shift	1	163	2
	RSI	Right shift immediate	1	163	2
	SUB	Subtract	1	163	2
	ASRI	Arithmetic shift right	1	161	1
	JMP	Jump to address	1	160	1
	CMP	Compare	1	84	2
	MOV	Copy register to register	1	82	1
	CMPC	Compare with carry	1	10	10
	TOTAL			296,547	656

FA FA FA FA En En En En

We did not have access to RAM macros for all those technologies.

Acknowledgements

We would like to thank Mario Kirschbaum and Martin Feldhofer for several fruitful discussions.

This work has been supported by the Austrian Government through the research program FIT-IT Trust in IT Systems under the project number 825743 (project PIT).