This paper introduces a new type of collision attack on first-order masked Advanced Encryption Standards. This attack is a known-plaintext attack, while the existing collision attacks are chosen-plaintext attacks. In addition, our method requires significantly fewer power measurements than any second-order differential power analysis or existing collision attacks. Since Kocher introduced the concept of differential power analysis (DPA) [1] , [2] , the security of block ciphers has received considerable attention, and it is now obvious that the unprotected implementations of block ciphers in embedded processors can be broken by DPA. During the past few years, much of the research on DPA attacks has focused on finding secure countermeasures. Among these countermeasures, a masking method based on algorithmic techniques is known to be inexpensive and secure against a first-order DPA (FODPA) [3] – [9] . In a masking method, all intermediate values are concealed by a random value, which is called a mask. This makes it impossible to apply an FODPA. However, masking methods have a weakness against some attack methods. One such attack method is that of a second-order DPA (SODPA) [10] – [14] . This attack exploits the power leakages related to two intermediate values of the masked cipher. In the case that the combination of these two intermediate values is related with the intermediate value of the original cipher, the secret information can be exposed by an SODPA. A second such attack method is that of a collision attack [15] – [18] . This attack serves to create a collision between two intermediate values; the instigator of the collision attack intentionally adjusts the plaintext to generate such a collision. Most existing collision attacks on Advanced Encryption Standard (AES) [19] attempt to cause a collision between masked S-box operations within the first round of a masked AES. An instigator of a collision attack (that is, the attacker) will attempt to input the same message several times over and then try to determine whether a collision occurs among masked S-box operations. Such an attack method sometimes requires fewer power measurements than that of an SODPA [16] . However, while both an FODPA and an SODPA are known-plaintext attacks [20] , all existing collision attacks on masked AESs to date have been of a chosen-plaintext attack type [20] . This demerit sometimes makes attempting a collision attack impossible in some circumstances; for example, when the input of an AES encryption is the selected nonce , as in AES-CCM [21] . Besides, these attacks require comparatively more power measurements. This paper proposes a new type of collision attack on first-order masked AESs. While existing collision attacks on first-order masked AESs utilize collisions between the power signals of masked S-box operations, the proposed new type of collision attack utilizes collisions between two power signals — one when a masked table is generated before en/decryption and another when the masked S-box is operated in the first round. The contributions of our paper are as follows: The remainder of this paper is organized as follows. In Section II, we explain a first-order masked AES, an SODPA, and the existing collision attacks. Section III describes the proposed new type of collision attack on first-order masked AESs. In Sections IV and V, we show the attack results for both a masked AES and a shuffled AES. Section VI shows a statistical analysis of collision attack methods to compare theoretically the performance of our proposed method with that of other analyses. Finally, in Section VII, we give our conclusions. The AES, also known as Rijndael, is a block cipher adopted as an encryption standard by the US government [19] . This block cipher is composed of a substitution-permutation network (SPN) structure [22] , [23] . For an N -bit SPN-type block cipher of r rounds, each round consists of three layers: key mixing layer, substitution layer, and linear transformation layer. In the key mixing layer, the round input is bitwise exclusive-ORed with the subkey for the round. In the substitution layer, the value resulting from the key mixing layer is partitioned into N / n blocks of n bits, and each block of n bits then outputs n bits through a non-linear bijective mapping, π : F _2ⁿ → F _2ⁿ . In the case of an AES, an S-box fulfills the role of this bijective mapping. The AES S-box is defined by a multiplicative inverse, b = a ⁻¹ , in GF(2 ⁸ ) (except, if a = 0 then b = 0) and an affine transformation, as in the following equations: where the value of x ²⁵⁴ is regarded as a GF(2)-vector of dimension 8, M is an 8 × 8 GF(2)-matrix, and v is an 8 × 1 GF(2)-vector. The resulting value of the substitution layer becomes the N -bit input ( i ₀ , i ₁ , … , i _N−1 ) of the linear transformation layer. The linear transformation layer consists of multiplication by an N × N matrix. That is, the resulting value of this layer is o = Li , where L is an N × N matrix and i is ( i ₀ , i ₁ , … , i _N−1 ) ^T . In an AES, “ShiftRows” and “MixColumns” play this role. The linear transformation layer is omitted from the last round, since it is easily shown that its inclusion adds no cryptographic strength. A first-order masked AES generates a random mask M and computes a masked ciphertext y' (= y ⊕ M' ) from a masked plaintext x ⊕ M for a given plaintext x , where ⊕ is the exclusive-OR operation. Then, the masking method computes y' ⊕ M' for obtaining the ciphertext y corresponding to message x (the way this masking is applied depends on the cryptographic algorithm). This prevents an FODPA, because the random mask values make it impossible for an attacker to predict intermediate values. In the masking method, we must know M' to obtain y . However, because of nonlinear parts, the block cipher has M' values that vary according to the different x values. If we try to determine a value M_x (the M' value corresponding to x ) with no exposure of the intermediate values, then this requires a significant number of operations. Namely, when designing the masking method, we must consider these nonlinear parts as a priority. An S-box operation, which is well known as being a non-linear part of an AES, outputs S ( a ) ⊕ m_a from the input value a ⊕ m . Because the m_a value is not linear with respect to a , we must make this output masking value the same for each a value. Although it is possible to compute this m_a value without the exposure of intermediate values, this method requires both memory (to keep track of all mask values) and a large number of operations. To fulfill this function, a first-order masked AES generally generates an MS table by computing MS ( x ⊕ m ) = S ( x ) ⊕ m' with new random numbers m and m' before an encryption or decryption, as shown in Algorithm 1 [5] , [7] . Algorithm 1. Generation of MS table. Input: Two masking values m, m' Output: MS 1. For u = 0 to 255 do 2. MS(u ⊕ m) = S(u) ⊕ m' 3. return MS. The following algorithm is a first-order masked AES carried out while generating an MS table. Algorithm 2. First-order masked AES [5]. Input: 16-byte plaintext P ((p₀p₁…p₁₅)₂₅₆), n-bit secret key K (n :128, 192, 256) Output: 16-byte ciphertext C ((c₀c₁…c₁₅)₂₅₆) 1. Generate six 1-byte random numbers m, m', m₁, m₂, m₃, and m₄. 2. Generate MS table with m, m' by Algorithm 1 3. (m₁', m₂', m₃', m₄') ← MixColumns(m₁, m₂, m₃, m₄) 4. Nr = 6 + n/32 5. Generate round keys k_i' (0 ≤ i < Nr) masked by ((m₁' ⊕ m)||(m₂' ⊕ m)||(m₃' ⊕ m)||(m₄' ⊕ m))⁴ and k_Nr' masked by (m'||m'||m'||m')⁴ where (a₃||a₂||a₁||a₀)⁴ is (2⁹⁶ + 2⁶⁴ + 2³² + 1) (a₃2²⁴ + a₂2¹⁶ + a₁2⁸ + a₀) (a survey is given in [5]) 6. s (= s₀s₁ … s₁₅) ← (P ⊕ (m₁'||m₂'||m₃'||m₄')⁴) ⊕ k₀' 7. For j = 1 to Nr − 1 8. For i = 0 to 15 do s_i = MS(s_i) 9. s = ShiftRows(s) 10. s = s ⊕ ((m₁ ⊕ m')||(m₂ ⊕ m')||(m₃ ⊕ m')||(m₄ ⊕ m'))⁴ 11. s = MixColumns(s) 12. s = s ⊕ k_j' 13. For i = 0 to 15 do s_i = MS(s_i) 14. s = ShiftRows(s) ⊕ k_Nr' 15. return C ← s. An SODPA can analyze a first-order masked AES by using two power signals with regard to a masked intermediate value and masking value. A general SODPA against a first-order masked AES uses a power signal, L ( t ₁ ), consumed by the masked S-box output of S ( x ⊕ k ) ⊕ m' , and a further power signal, L ( t ₂ ), consumed by the masking value of m' . If these two power signals are suitably combined, then the resulting suitably combined signal, C , is strongly related to the value of S ( x ⊕ k ). Various SODPAs have been researched based on how such power signals are combined [13] . Three representative such SODPAs, as a result of combining two power signals, L ( t ₁ ) and L ( t ₂ ), are given as follows: In an SODPA on a first-order masked AES, with the combined power signal C and a prediction function, f , defined according to some assumptions on the device leakage model, an attacker can compute Pearson’s correlation coefficient, as follows: After computing Pearson’s coefficient for each key hypothesis, one can find the secret key as k * for ρ_k * having the maximum correlation coefficients in ρ_k (0 ≤ k ≤ 255). Another analysis on first-order masked AESs is that which concerns the collision attack. This attack is carried out after collecting a great number of power traces from the plaintexts selected by an attacker. For example, if two key bytes of the first round of an AES are k ₁ and k ₂ , then the output values of the two corresponding masked S-box operations will be S ( k ₁ ) ⊕ m' , where the two corresponding bytes of plaintext are 0 and k ₁ ⊕ k ₂ , respectively. Namely, upon acquiring multiple power traces from identical inputs, the value of Pearson’s coefficient for the power signals consumed by the two masked S-box outputs will be close to 1. If an attacker sets the two input bytes of plaintext as (0, 0), (0, 1), … , (0, 255), in order, then they can find the value of k ₁ ⊕ k ₂ by confirming the collision. In addition, the rest of the key bytes can be exposed by repeating this procedure [18] , [16] . Recently, an improved version of a collision attack was reported [16] . The authors of the paper insisted that this collision attack requires a smaller number of power measurements than an SODPA to find the secret key of an AES. However, there analysis has demerits; that is, it was a chosen-plaintext attack and it required a similar number of power measurements to that of an SODPA. Although existing collision analyses require fewer power measurements than an SODPA, the analyses have the demerit that the attack is of a chosen-plaintext type. This limitation, which is not the case with an SODPA, sometimes makes such attacks impossible to implement in some situations. In this section, we introduce a new type of collision attack, which utilizes a collision that occurs between two specific types of power signal; namely, that which occurs at the time of generation of a masked table before en/decryption and that when a masked S-box is operated. Our method is not a chosen-plaintext attack, but rather a known-plaintext attack — one that requires far fewer power measurements than that of any existing collision attacks or SODPAs. We prove this fact with some experimental results in the next section. Our attack progresses (see Fig. 1 ) as follows: Algorithm 3. The function ρ_mat. Input: The set of signals of length l₁{C₁₁(t), C₁₂(t), … , C_1N(t)} and the set of signals of length l₂{C₂₁(u), C₂₂(u), … , C_2N(u)} where 1≤ t ≤ l₁, 1≤ u ≤ l₂ Output: The collision signal δ(j) of length l₁ × l₂ (1 ≤ j ≤ l₁×l₂) 1. For t = 1 to l₁ and u = 1 to l₂ do 2. δ((t − 1)l₂ + u) = ρ({C₁₁(t),…, C_1N(t)},{C₂₁(u),…, C_2N(u)}) 3. return δ(j) (1≤ j ≤ l₁ × l₂) To compare the performance of some attacks on a first-order masked AES, we first carried out simulations with artificially constructed power consumptions by way of a Hamming weight model. In the simulation for an SODPA, we generated the following two power signals: Further, we generated the following power signals to conduct our attack: Here, the offsets δ ₁ , δ ₂ , δ_u , and δ_v denote the constant parts of a power signal , and H (·) is the Hamming weight function. In addition, all noises, B ₁ , B ₂ , B _(u) , and B_x , of the generated power signals were assumed to be distributed normally, N (0, σ ² ). We conducted the attacks 100 times and calculated the success rate of each one to find the right 16 key bytes. We did not carry out a simulation of an existing collision attack method [16] , because it was difficult to count the exact number of power measurements for finding 16 key bytes. Thus, we added the performance of an existing collision attack method based on Fig. 9 of [16] . Here, the number of power measurements to find 16 key bytes is about 27.5 times more than the number depicted in Fig. 9 , as the authors of [16] explain. Figures 2 and 3 describe the success rate of the attacks on a first-order masked AES subject to a value for σ . We attempted to implement our attacks on a first-order masked AES using an ARM7TDMI microprocessor [24] , where power consumption acquisitions were taken with the microprocessor clocked at 7.37 MHz. The entire AES encryption was recorded at 500 mega samples per second and then filtered using a low-pass filter with a cutoff frequency of 7.37 MHz. Further, we compressed the signal by extracting maximum values from among the points that make up the signal (one per every 17 consecutive points), which means a single clock would have consisted of about four points. Our attack began by dividing the acquired traces into subsignals. Namely, we needed to identify SS _i,j and S _i,k in the acquired traces ( S_i ). Figure 4 shows that some suboperations such as generation of a masking table and the operations of 10 rounds are readily visible. The correlation coefficients between one block in Fig. 6 , enlarged image of Fig. 5 with a window of the same size, starting from every possible point within an acquisition, are calculated to extract each individual SS _i,j (see Fig. 7 ). We note that S _i,k can be extracted in a similar manner to the case of SS _i,j (see Fig. 8 ). We conducted our attack with the extracted SS _i,j and S _i,k by following the procedure outlined in Section III. To confirm the effect of step 6, we first confirmed the result of an attack without carrying out this step in an attack scenario. Figure 9 shows the result of the attack. All correlation traces have some high correlation coefficients, regardless of the guessed key (see Fig. 9 ). Thus, we conducted the attack again with step 6 included. This time around, most meaningless high correlation coefficients were removed (see Fig. 10 ). In our attack, the minimum number of traces needed to find 16 key bytes within the first round was only 250. To compare the performance of our attack with that of other attacks, we conducted tests using existing collision attack methods and SODPAs [13] . We first carried out two collision attacks (taken from [16] and [18] ) and counted the minimum number of traces required to find a collision between the first and second S-box outputs within the first round. In these experiments, the two attacks of [16] and [18] needed 8,250 and 76,800 power measurements, respectively. Secondly, we conducted an SODPA by using SS _i,0 and S _i,k . Here, we computed the correlation coefficient between the combined power signal and the Hamming weight of , because SS _i,0 is the power signal with regard to S (0) ⊕ m' . We carried out the attack using the method of [12] . When we conducted the three SODPAs introduced in Section II-3, the minimum numbers of traces needed to find 16 key bytes within the first round were as shown in Table 1 . We conducted attacks on both a masked AES and a shuffled AES [5] . The masked and shuffled AESs were proposed to provide better security against an SODPA than a masked-only AES. In this countermeasure, the order of masked S-box operations of the first and last rounds is randomized. To analyze this countermeasure, we summed up 16 masked S-box signals and then tried to find a collision between SS '_i,j and the summed signal. Namely, in the attack scenario of Section III, the summed signals T_i were computed by S _i,0 + S _i,1 + ⋯ + S _i,15 (1 ≤ i ≤ N ). We then computed the correlation traces between { T ₁ , T ₂ , … , T_N } and in step 5. Figure 11 shows the result of the attack without carrying out step 6 in the attack scenario. We could confirm no meaningful peaks visually. Thus, we conducted the attack again with step 6 (see Fig. 11 ). This time around, most meaningless high correlation coefficients were removed and we could confirm meaningful peaks (see Fig. 12 ). In our attacks on the masked and shuffled AESs, the minimum number of traces needed for finding 16 key bytes within the first round was 8,500. After finding 16 key bytes, we had to carry out an exhaustive search for 1.19 × 2 ⁴⁴ possible keys (16!) to find the order of the key bytes. When considering the speed of the optimized AES implementation [25] , we can find practically any secret key by this exhaustive search. In this section, we show a statistical analysis of collision attacks. In [13] , the authors calculated the correlation coefficients to deduce the correct key for two SODPAs under a Hamming weight model. The highest correlation was obtained with norm-mult SODPA (NM-SODPA), the value of which is as follows: where n is the bit length of the processed data and σ is a standard deviation of Gaussian noise. In a similar manner, we can derive the correlation ρ _collision of the collision attack. To compute this correlation, let us define two compared power signals as follows: where δ ₁ and δ ₂ denote the constant parts of a power signal, and H ( Z ) is the Hamming weight of a sensitive variable Z of length n . In addition, the noises B ₁ and B ₂ are generated from a normal distribution, N (0, σ ² ). Theorem 1 . The correlation ρ _collision for the collision attack is n / ( n + 4 σ ² ). Proof. In the collision attack, the correlation ρ _collision can be computed by Here, E[ L ( t ₁ )] and E[ L ( t ₂ )] are δ ₁ + n /2 and δ ₂ + n /2, respectively. In addition, E[ L ( t ₁ ) L ( t ₂ )] can be computed as follows: In the above equation, since B ₁ and B ₂ are independent from Z and satisfy E( B ₁ ) = E( B ₂ ) = 0, E[ B ₁ ( δ ₂ + H ( Z )) + B ₂ ( δ ₁ + H ( Z ))] = 0. Furthermore, because E[ H ( Z )] = n /2 and Var[ H ( Z )] = n × 1/2 × 1/2 = n /4, E[ H ( Z ) ² ] = Var[ H ( Z )] + E[ H ( Z )] ² = ( n ² + n ) / 4. Thus, E[ L ( t ₁ ) L ( t ₂ )] is equal to δ ₁ δ ₂ + n ( δ ₁ + δ ₂ )/2 + ( n ² + n ) / 4. Namely, the numerator E[ L ( t ₁ ) L ( t ₂ )] − E[ L ( t ₁ )]E[ L ( t ₂ )] of (1) is as follows: Meanwhile, in the denominator of (1), we need to compute E[ L ( t ₁ ) ² ] to obtain Var( L ( t ₁ )). In the equation E[ L ( t ₁ ) ² ] = E[( δ ₁ + H ( Z )) ² + 2 B ₁ ( δ ₁ + H ( Z )) + B ₁ ² ], because E[2 B ₁ ( δ ₁ + H ( Z ))] = 0 and E[ B ₁ ² ] = Var[ B ₁ ] = σ ² , E[ L ( t ₁ ) ² ] is equal to δ ₁ ² + nδ ₁ + ( n ² + n )/4 + σ ² . Thus, from the equation E[ L ( t ₁ )] = δ ₁ + n /2, we can deduce that Var[ L ( t ₁ )] is equal to n /4 + σ ² . Similarly, Var[ L ( t ₂ )] is also equal to n /4 + σ ² . From these two variance components and the numerator of (1), ρ _collision is calculated as follows: We list in Table 2 the correlation coefficients according to an increasing noise (with n = 8) . In the sine-based SODPA (SB-SODPA), we find both a better combining function and prediction function than the authors of [28] proposed. The combining function is sin{π/2[ H ( z ⊕ m ) − H ( m )] ² }, which is equal to mod [ H ( z ⊕ m ) − H ( m ), 2]. In addition, the optimal prediction function corresponding to this combining function is E{mod [ H ( z ⊕ m ) − H ( m ), 2] | z } by Corollary 8 of [13] , which is also equal to mod ( H ( z ), 2) because H ( z ⊕ m ) − H ( m ) ≡ H ( z ) (mod 2). To compare SB-SODPA with other analyses in a noisy environment, we used the combining function sin(π/2{[ P ₁ − E( P ₁ )] − [ P ₂ − E( P ₂ )]} ² ), where P ₁ and P ₂ are generated as follows: In this paper, we introduced a new type of collision attack on masked and shuffled AESs. In the category of collision attacks on AESs, ours is the first analysis method included under the known-plaintext attack category and the first to have practically analyzed a shuffled AES by way of the proposed collision attack. In addition to these contributions, we experimentally and theoretically showed that the new collision attack required far fewer power measurements than SODPAs and existing collision attack methods. The hiding of countermeasures by way of a random order in the step of generating a masked S-box can potentially block against our attack [29] . But, as mentioned in [29] , if the quality of the random-order generator is poor, then the order is easily exposed. On the other hand, a high-quality random-order generator could make the performance of a masked AES much worse than any existing one. In the future, we aim to find a fast, secure random-order generator to practically block against our proposed attack method and that of [29] . hs@kisti.re.kr Hee Seok Kim received his BS in degree mathematics from Yonsei University, Seoul, Rep. of Korea, in 2006, and the MS and PhD degrees in engineering in information security from Korea University, Seoul, Rep. of Korea, in 2008 and 2011. From 2011 to 2012, he worked as a post doctoral researcher at University of Bristol, UK. Since 2013, he has been a senior researcher in Korea Institute of Science and Technology Information, Daejeon, Rep. of Korea. Additionally, since 2015, he has been an assistant professor at the University of Science and Technology, Daejeon, Rep. of Korea. His research interests include side channel attacks, cryptography, and network security. Corresponding Author shhong@korea.ac.kr Seokhie Hong received his MA and PhD degree in mathematics from Korea University, Seoul, Rep. of Korea, in 1997 and 2001, respectively. He had worked in SECURITY Technologies Inc., Seoul, Rep. of Korea, from 2000 to 2004. From 2004 to 2005, he worked as a post doctoral researcher in Computer Security and Industrial Cryptography, Kuleuven University. Leuven, Belgium. Since 2005, he has been with Korea University, where he is now working in the School of Information Security. His specialty lies in the area of information security, and his research interests include the design and analysis of symmetric-key cryptosystems, public-key cryptosystems, and side channel attacks.