Advanced
New Type of Collision Attack on First-Order Masked AESs
New Type of Collision Attack on First-Order Masked AESs
ETRI Journal. 2016. Apr, 38(2): 387-396
Copyright © 2016, Electronics and Telecommunications Research Institute (ETRI)
  • Received : July 15, 2014
  • Accepted : November 23, 2015
  • Published : April 01, 2016
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Hee Seok Kim
Seokhie Hong

Abstract
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.
Keywords
I. Introduction
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:
  • 1) Our proposed new type of collision attack is the first of its kind to fall under the category of known-plaintext attack. As already previously mentioned, existing collision attacks can be successful only when an attacker is able to input the same message several times over and successfully determine whether a collision has occurred. That is, all collision attacks of the current era fall under the category of chosen-plaintext attack. This limitation, which is not to be found in an SODPA, sometimes makes an attack of this kind impossible to implement. However, our new type of collision attack is a known-plaintext attack, which is comparable to an SODPA.
  • 2) Our proposed new type of collision attack requires the fewest power measurements among the existing non-profiling attacks on first-order masked AESs. The reason existing collision attack methods require large numbers of power measurements is due to the fact that an attacker using such a method has to input a selected plaintext several times over in order to create a collision; this process must, of course, be repeated for each and every plaintext inputted. However, our method utilizes a power signal at the time of generation of a masked table. The utilized power signal at such a time holds much valuable information; thus, we can considerably reduce the required number of power measurements as a result of using such an important power signal. In our practical experiments, the new type of collision attack requires at most only 250 power measurements to find a 16-byte key within the first round of an AES, whereas the minimum an SODPA requires is 1,850 power measurements. With our experimental results, we also show a statistical analysis of our new type of collision attack to support this fact theoretically.
  • 3) Our new type of attack if the first of its kind to be practically implemented against both a masked AES and a shuffled AES[5]. It has been difficult to implement existing collision attack methods against shuffled AESs, because such methods use collisions between only two masked S-box operations. However, our attack is easy to implement against a shuffled AES. When we tried the attack method practically, we could find 1.19 × 244key candidates with 8,500 power measurements.
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.
II. Preliminaries
- 1. AES
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 2n F 2n . 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 −1 , in GF(2 8 ) (except, if a = 0 then b = 0) and an affine transformation, as in the following equations:
S: GF( 2 8 ) → GF( 2 8 ), x → M x 254 ⊕v,
where the value of x 254 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 0 , i 1 , … , 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 0 , i 1 , … , 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.
- 2. First-Order Masked AES
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 Mx (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 ) ⊕ ma from the input value a m . Because the ma 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 ma 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(um) = 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 ((p0p1p15)256), n-bit secret key K (n :128, 192, 256) Output: 16-byte ciphertext C ((c0c1c15)256) 1. Generate six 1-byte random numbers m, m', m1, m2, m3, and m4. 2. Generate MS table with m, m' by Algorithm 1 3. (m1', m2', m3', m4') ← MixColumns(m1, m2, m3, m4) 4. Nr = 6 + n/32 5. Generate round keys ki' (0 ≤ i < Nr) masked by ((m1'm)||(m2'm)||(m3'm)||(m4'm))4 and kNr' masked by (m'||m'||m'||m')4 where (a3||a2||a1||a0)4 is (296 + 264 + 232 + 1) (a3224 + a2216 + a128 + a0) (a survey is given in [5]) 6. s (= s0s1s15) ← (P ⊕ (m1'||m2'||m3'||m4')4) ⊕ k0' 7. For j = 1 to Nr − 1 8. For i = 0 to 15 do si = MS(si) 9. s = ShiftRows(s) 10. s = s ⊕ ((m1m')||(m2m')||(m3m')||(m4m'))4 11. s = MixColumns(s) 12. s = skj' 13. For i = 0 to 15 do si = MS(si) 14. s = ShiftRows(s) ⊕ kNr' 15. return Cs.
- 3. SODPA
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 1 ), consumed by the masked S-box output of S ( x k ) ⊕ m' , and a further power signal, L ( t 2 ), 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 1 ) and L ( t 2 ), are given as follows:
  • ▪ abs-diff:C= |L(t1) −L(t2)|
  • ▪ diff-square:C= (L(t1) −L(t2))2
  • ▪ norm-mult:C= (L(t1) − E(L(t1)))(L(t2) − E(L(t2)))
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:
ρ k =ρ(C,f(S(x⊕k)))       ( 0 ≤k≤ 255 )).
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).
- 4. Collision Attack
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 1 and k 2 , then the output values of the two corresponding masked S-box operations will be S ( k 1 ) ⊕ m' , where the two corresponding bytes of plaintext are 0 and k 1 k 2 , 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 1 k 2 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.
III. New Type of Collision Attack on Masked AESs
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:
  • 1) AcquireNpower signals (Si) withN16-byte plaintexts (Pi),pi0,pi1, … ,pi15, 1 ≤i≤N.
  • 2) Split the part ofSicorresponding to Algorithm 1 into 256 sub-signals, SSi,j(0 ≤j≤ 255); that is, the signal including the power consumption with regard toMS(j⊕m) =S(j) ⊕m'.
  • 3) For the first plaintext byte,pi0, rearrange SSi,j: SS'i,j← SSi,j⊕pi0(1 ≤i≤N, 0 ≤j≤ 255); SS'i,jincludes power consumption with regard toS(pi0⊕j) ⊕m'.
  • 4) In the first round of an AES, identify the power consumed by the first S-box operation,Si,0, whereSi,0includes power consumption with regard toS(pi0⊕k0) ⊕m'.
  • 5) Compute the collision signalsδk¯0(0≤k¯0≤255)betweenSi,0and SS'i,jby
ρ k ¯ 0 = ρ mat ( { S 1,0 , S 2,0 ,…, S N,0 },  { SS ' 1, k ¯ 0 , SS ' 2, k ¯ 0 ,…, SS ' N, k ¯ 0 } )
Algorithm 3. The function ρmat. Input: The set of signals of length l1{C11(t), C12(t), … , C1N(t)} and the set of signals of length l2{C21(u), C22(u), … , C2N(u)} where 1≤ tl1, 1≤ ul2 Output: The collision signal δ(j) of length l1 × l2 (1 ≤ jl1×l2) 1. For t = 1 to l1 and u = 1 to l2 do 2. δ((t − 1)l2 + u) = ρ({C11(t),…, C1N(t)},{C21(u),…, C2N(u)}) 3. return δ(j) (1≤ jl1 × l2)
  • 6) The collision signals sometimes have high correlation coefficients at certain points in time, regardless of the existence of collisions (see[16]and Sections IV-2 and V). To ignore these high correlation coefficients, we need to subtract the mean signal,δ, from every collision signal,δk¯0,, whereδ¯= E(δk¯0) (0≤k¯0≤255).Namely, this step gives rise to the following equation:
δ k ¯ 0 = δ k ¯ 0 − δ ¯  (0≤ k ¯ 0 ≤255).
  • 7) Decide the keyk0ask* forδk*having the maximum correlation coefficients inδk¯0(0≤k¯0≤255).
  • 8) For the rest of the 15 bytes, carry out steps 3 to 7 repeatedly.
PPT Slide
Lager Image
Attack scenario.
IV. Performance Analysis
- 1. Simulation Results
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:
L( t 1 ) =  δ 1  + H( m ' )+ B 1 , L( t 2 ) =  δ 2  + H(S(x ⊕k) ⊕  m ' )+ B 2 .
Further, we generated the following power signals to conduct our attack:
S S i ,u  =  δ u  + H(S( u )⊕  m ' ) +  B ( u )  ( 0 ≤u≤ 255 ),    S i ,v  =  δ v  + H(S( x v  ⊕ k v )⊕  m ' ) +  B x .
Here, the offsets δ 1 , δ 2 , δu , and δv denote the constant parts of a power signal , and H (·) is the Hamming weight function. In addition, all noises, B 1 , B 2 , B (u) , and Bx , of the generated power signals were assumed to be distributed normally, N (0, σ 2 ).
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 σ .
PPT Slide
Lager Image
Success rate of attacks on first-order masked AES (σ = 0.75).
PPT Slide
Lager Image
Success rate of attacks on first-order masked AES (σ = 2).
- 2. Experimental Results with Real Traces
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 ( Si ). Figure 4 shows that some suboperations such as generation of a masking table and the operations of 10 rounds are readily visible.
PPT Slide
Lager Image
Mean trace of first-order masked AES.
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 ).
PPT Slide
Lager Image
Signals with regard to generating masked table in Fig. 4.
PPT Slide
Lager Image
Enlarged image of Fig. 5.
PPT Slide
Lager Image
Extracting SSi,j: correlation coefficients of one block of Fig. 6 with window of same size starting from every possible point within acquisition.
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.
PPT Slide
Lager Image
Extracting Si,k: correlation coefficients of one masked S-box signal with window of same size starting from every possible point within acquisition.
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 ).
PPT Slide
Lager Image
Correlation traces using 2,000 traces without carrying out step 6 in attack scenario of Section III.
PPT Slide
Lager Image
Correlation traces using 2,000 traces with carrying out step 6.
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
S(x ⊕  k ¯ 0 ) ⊕ S( 0 )
, 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 .
Number of traces needed to find 16 key bytes.
Attack SODPAs
abs-diff diff-square norm-mult
# of traces 6,200 5,800 1,850
Attack Collision attacks
[18] [16] Ours
# of traces 76,800 8,250 250
V. Experimental Results of New Attack Method on Masked and Shuffled AESs
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 Ti were computed by S i,0 + S i,1 + ⋯ + S i,15 (1 ≤ i N ). We then computed the correlation traces between { T 1 , T 2 , … , TN } and
{ S S 1, k ¯ 0 ′ , S S 2, k ¯ 0 ′ ,  ...  , S S N, k ¯ 0 ′ }
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 ).
PPT Slide
Lager Image
Correlation traces using 5,000 traces without carrying out step 6 in attack scenario.
PPT Slide
Lager Image
Correlation traces using 5,000 traces with carrying out step 6.
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 44 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.
VI. Statistical Analysis of Collision Attacks
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:
ρ norm−mult = n n 2 +8n σ 2 +16 σ 4 ,
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:
L( t 1 ) = δ 1  + H( Z )+  B 1 ,       L( t 2 )=  δ 2  + H( Z )+  B 2 ,
where δ 1 and δ 2 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 1 and B 2 are generated from a normal distribution, N (0, σ 2 ).
Theorem 1 . The correlation ρ collision for the collision attack is n / ( n + 4 σ 2 ).
Proof. In the collision attack, the correlation ρ collision can be computed by
(1) ρ collision = E[ L( t 1 )L( t 2 ) ]−E[ L( t 1 ) ]E[ L( t 2 ) ] Var[ L( t 2 ) ]Var[ L( t 2 ) ] .
Here, E[ L ( t 1 )] and E[ L ( t 2 )] are δ 1 + n /2 and δ 2 + n /2, respectively. In addition, E[ L ( t 1 ) L ( t 2 )] can be computed as follows:
E[ L( t 1 )L( t 2 ) ] =E[ ( δ 1 +H(Z)+ B 1 )( δ 2 +H(Z)+ B 2 ) ] = δ 1 δ 2 +( δ 1 + δ 2 )E[ H(Z) ]+E [ H (Z) 2 ]    +E[ B 1 ( δ 2 +H(Z) )+ B 2 ( δ 1 +H(Z) ) ].
In the above equation, since B 1 and B 2 are independent from Z and satisfy E( B 1 ) = E( B 2 ) = 0, E[ B 1 ( δ 2 + H ( Z )) + B 2 ( δ 1 + H ( Z ))] = 0. Furthermore, because E[ H ( Z )] = n /2 and Var[ H ( Z )] = n × 1/2 × 1/2 = n /4, E[ H ( Z ) 2 ] = Var[ H ( Z )] + E[ H ( Z )] 2 = ( n 2 + n ) / 4. Thus, E[ L ( t 1 ) L ( t 2 )] is equal to δ 1 δ 2 + n ( δ 1 + δ 2 )/2 + ( n 2 + n ) / 4. Namely, the numerator E[ L ( t 1 ) L ( t 2 )] − E[ L ( t 1 )]E[ L ( t 2 )] of (1) is as follows:
δ 1 δ 2  + n 2  ( δ 1 + δ 2 )+  n 2 +n 4  − ( δ 1 +  n 2 )( δ 2 +  n 2 )=  n 4 .
Meanwhile, in the denominator of (1), we need to compute E[ L ( t 1 ) 2 ] to obtain Var( L ( t 1 )). In the equation E[ L ( t 1 ) 2 ] = E[( δ 1 + H ( Z )) 2 + 2 B 1 ( δ 1 + H ( Z )) + B 1 2 ], because E[2 B 1 ( δ 1 + H ( Z ))] = 0 and E[ B 1 2 ] = Var[ B 1 ] = σ 2 , E[ L ( t 1 ) 2 ] is equal to δ 1 2 + 1 + ( n 2 + n )/4 + σ 2 . Thus, from the equation E[ L ( t 1 )] = δ 1 + n /2, we can deduce that Var[ L ( t 1 )] is equal to n /4 + σ 2 . Similarly, Var[ L ( t 2 )] is also equal to n /4 + σ 2 . From these two variance components and the numerator of (1), ρ collision is calculated as follows:
n/4 n/4+ σ 2 = n n+4 σ 2 .                   ■
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 )] 2 }, 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 1 − E( P 1 )] − [ P 2 − E( P 2 )]} 2 ), where P 1 and P 2 are generated as follows:
P 1 = δ 1 +H(Z⊕m)+ B 1 ,        P 2 = δ 2 +H( m )+ B 2 .
Correlations for different analyses according to noise deviationσ.
Target algorithm 0 0.1 0.3 0.4 0.5 1 5
Unmasked FODPA 1.00 1.00 0.98 0.96 0.94 0.82 0.27
Masked NM-SODPA 0.35 0.35 0.34 0.33 0.31 0.24 0.03
SB-SODPA 1.00 1.00 0.64 0.35 0.14 0.02 0.00
Collision attack 1.00 1.00 0.96 0.93 0.89 0.67 0.07
PPT Slide
Lager Image
Correlations for different attack methods according to noise deviation σ.
VII. Conclusion
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] .
This research was supported by the MSIP(Ministry of Science, ICT and Future Planning), Korea, under the ITRC(Information Technology Research Center) support program (IITP-2015-H8501-15-1003) supervised by the IITP(Institute for Information & communications Technology Promotion).
The offsets are sometimes different for each power consumption, but norm-mult SODPA and our attack are unaffected by this difference. On the other hand, abs-diff and diff-square SODPAs have the best performance when the offsets are the same. Here, we carried out the simulation with power signals generated from the same offset.
Sensitive variable, as defined and used in previous literature related to higher-order masking methods [26], [27]; that is, the intermediate variable of the original cipher, which is dependent upon both the plaintext and the secret key.
The correlation of FODPA on unmasked cipher can be easily computed as n / n+4 σ 2 by some lemmas of [13].
BIO
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.
References
Kocher P. , Jaffe J. , Jun B. “Differential Power Analysis,” Int. Cryptology Conf. Santa Barbara, CA, USA Aug. 15–19, 1999 388 - 397
Kim H. , Han D.-G. , Hong S. 2011 “First-Order Side Channel Attacks on Zhang’s Countermeasures,” Inf. Sci. 181 (18) 4051 - 4060    DOI : 10.1016/j.ins.2011.04.049
Akkar M.-L. , Giraud C. 2001 “An Implementation of DES and AES, Secure against Some Attacks,” Int. Workshop Cryptographic Hardware Embedded Syst. Paris, France 309 - 318
Blömer J. , Guajardo J. , Krummel V. “Provably Secure Masking of AES,” Int. Workshop Sel. Areas Cryptography Waterloo, Canada Aug. 9–10, 2004 69 - 83
Herbst C. , Oswald E. , Mangard S. “An AES Smart Card Implementation Resistant to Power Analysis Attacks,” Int. Conf. Appl. Cryptography Netw. Security Singapore June 6–9, 2006 239 - 252
Kim H. 2011 “Efficient Masked Implementation for SEED Based on Combined Masking,” ETRI J. 33 (2) 267 - 274    DOI : 10.4218/etrij.11.1510.0112
Kim H. 2010 “Efficient Masking Methods Appropriate for the Block Ciphers ARIA and AES,” ETRI J. 32 (3) 370 - 379    DOI : 10.4218/etrij.10.0109.0181
Oswald E. “A Side-Channel Analysis Resistant Description of the AES S-Box,” Int. Workshop Fast Softw. Encryption Paris, France Feb. 21–23, 2005 413 - 423
Oswald E. , Schramm K. “An Efficient Masking Scheme for AES Software Implementations,” Int. Workshop Inf. Security Appl. Jeju Island, Rep. of Korea Aug. 22–24, 2005 292 - 305
Joye M. , Paillier P. , Schoenmakers B. “On Second-Order Differential Power Analysis,” Int. Workshop Cryptographic Hardware Embedded Syst. Edinburgh, UK Aug. 29–Sept. 1, 2005 293 - 308
Messerges T. “Using Second-Order Power Analysis to Attack DPA Resistant Software,” Int. Workshop Cryptographic Hardware Embedded Syst. Worcester, MA, USA Aug. 17–18, 2000 238 - 251
Oswald E. “Practical Second-Order DPA Attacks for Masked Smart Card Implementations of Block Ciphers,” Cryptographers’ Track RSA Conf. San Jose, CA, USA Feb. 13–17, 2005 192 - 207
Prouff E. , Rivain M. , Bevan R. 2009 “Statistical Analysis of Second Order Differential Power Analysis,” IEEE Trans. Comput. 58 (6) 799 - 811    DOI : 10.1109/TC.2009.15
Schramm K. , Paar C. “Higher Order Masking of the AES,” Cryptographers’ Track RSA Conf. San Jose, CA, USA Feb. 13–17, 2005 208 - 225
Bogdanov A. “Improved Side-Channel Collision Attacks on AES,” Int. Workshop Sel. Areas Cryptography Ottawa, Canada Aug. 16–17, 2007 84 - 95
Clavier C. “Improved Collision-Correlation Power Analysis on First Order Protected AES,” Int. Workshop Cryptographic Hardware Embedded Syst. Nara, Japan Sept. 28–Oct. 1, 2011 49 - 62
Moradi A. , Mischke O. , Eisenbarth T. “Correlation-Enhanced Power Analysis Collision Attack,” Int. Workshop Cryptographic Hardware Embedded Syst. Santa Barbara, CA, USA Aug. 17–20, 2010 125 - 139
Schramm K. “A Collision-Attack on AES: Combining Side Channel- and Differential-Attack,” Int. Workshop Cryptographic Hardware Embedded Syst. Cambridge, MA, USA Aug. 11–13, 2004 163 - 175
Daemen J. , Rijmen V. 1999 AES Proposal: Rijndael NIST, US Department of Commerce http://csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended.pdf
Welchman G. 1982 “The Hut Six Story: Breaking the Enigma Codes,” McGraw-Hill New York
Dworkin M. 2007 Recommendation for Block Cipher Modes of Operation: The CCM Mode for Authentication and Confidentiality NIST, US Department of Commerce http://csrc.nist.gov/publications/nistpubs/800–38C/SP800–38C_updated-July20_2007.pdf
Adams C. , Tavares S. 1990 “The Structured Design of Cryptographically Good S-Boxes,” J. Cryptology 3 (1) 27 - 41
O’Connor L. 1995 “On the Distribution of Characteristics in Bijective Mappings,” J. Cryptology 8 (2) 67 - 86
ARM Limited 2001 ARM7TDMI Tech. Reference Manual (revision r4p1) ARM http://infocenter.arm.com/help/topic/com.arm.doc.ddi0210c/DDI0210B.pdf
2015 eBACS: ECRYPT Benchmarking of Cryptographic Systems http://bench.cr.yp.to/results-stream.html
Genelle L. , Prouff E. , Quisquater M. “Thwarting Higher-Order Side Channel Analysis with Additive and Multiplicative Maskings,” Int. Workshop Cryptographic Hardware Embedded Syst. Nara, Japan Sept. 28–Oct. 1, 2011 240 - 255
Kim H. , Hong S. , Lim J. “A Fast and Provably Secure Higher-Order Masking of AES S-Box,” Int. Workshop Cryptographic Hardware Embedded Syst. Nara, Japan Sept. 28–Oct. 1, 2011 95 - 107
Oswald E. , Mangard S. “Template Attacks on Masking-Resistance is Futile,” Cryptographers’ Track RSA Conf. San Francisco, CA, USA Feb. 5–9, 2007 243 - 256
Tunstall M. , Whitnall C. , Oswald E. “Masking Tables – An Underestimated Security Risk,” Int. Workshop Fast Softw. Encryption Singapore Mar. 11–13, 2013 425 - 444