New Type of Collision Attack on First-Order Masked AESs

ETRI Journal.
2016.
Apr,
38(2):
387-396

- Received : July 15, 2014
- Accepted : November 23, 2015
- Published : April 01, 2016

Download

PDF

e-PUB

PubReader

PPT

Export by style

Article

Metrics

Cited by

TagCloud

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.
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.
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:
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.
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]
.
The following algorithm is a first-order masked AES carried out while generating an
MS
table.
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:
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
* for
ρ_{k}
* having the maximum correlation coefficients in
ρ_{k}
(0 ≤
k
≤ 255).
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.
Attack scenario.
δ
_{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
B_{x}
, 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
σ
.
Success rate of attacks on first-order masked AES (σ = 0.75).
Success rate of attacks on first-order masked AES (σ = 2).
_{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.
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
).
Signals with regard to generating masked table in Fig. 4 .
Enlarged image of Fig. 5 .
Extracting SS_{i,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.
Extracting S_{i,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
).
Correlation traces using 2,000 traces without carrying out step 6 in attack scenario of Section III.
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
_{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
.

'_{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
_{1}
,
T
_{2}
, … ,
T_{N}
} and
Correlation traces using 5,000 traces without carrying out step 6 in attack scenario.
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.
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:
δ
_{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
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:
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:
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}
+
nδ
_{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
= 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:

Correlations for different attack methods according to noise deviation σ .
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).
1) 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.
2) 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.
3) The correlation of FODPA on unmasked cipher can be easily computed as $\sqrt{n}/\sqrt{n+4{\sigma}^{2}}$ by some lemmas of [13] .
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.

Side-channel attack
;
power analysis
;
collision attack
;
masking method
;
shuffling method
;
second-order differential power analysis
;
AES

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
- 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.

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
S: GF( 2 8 ) → GF( 2 8 ), x → M x 254 ⊕v,

where the value of
- 2. First-Order Masked AES

A first-order masked AES generates a random mask
- 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,
- ▪ 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)))

ρ 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
- 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
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 } )

- 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

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
PPT Slide

Lager Image

PPT Slide

Lager Image

- 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
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

S(x ⊕ k ¯ 0 ) ⊕ S( 0 )

, because SS
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 | ||

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
{ 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

PPT Slide

Lager Image

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
L( t 1 ) = δ 1 + H( Z )+ B 1 , L( t 2 )= δ 2 + H( Z )+ B 2 ,

where
(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[
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
δ 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[
n/4 n/4+ σ 2 = n n+4 σ 2 . ■

We list in
Table 2
the correlation coefficients according to an increasing noise (with
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

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]
.
BIO

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

Citing 'New Type of Collision Attack on First-Order Masked AESs
'

@article{ HJTODO_2016_v38n2_387}
,title={New Type of Collision Attack on First-Order Masked AESs}
,volume={2}
, url={http://dx.doi.org/10.4218/etrij.16.0114.0854}, DOI={10.4218/etrij.16.0114.0854}
, number= {2}
, journal={ETRI Journal}
, publisher={Electronics and Telecommunications Research Institute}
, author={Kim, Hee Seok
and
Hong, Seokhie}
, year={2016}
, month={Apr}