Advanced Encryption Standard (AES) is widely used for protecting wireless sensor network (WSN). At the Workshop on Cryptographic Hardware and Embedded Systems (CHES) 2012, Gérard
et al
. proposed an optimized collision attack and break a practical implementation of AES. However, the attack needs at least 256 averaged power traces and has a high computational complexity because of its byte wise operation. In this paper, we propose a novel double sieve collision attack based on bitwise collision detection, and an improved version with an errortolerant mechanism. Practical attacks are successfully conducted on a software implementation of AES in a lowpower chip which can be used in wireless sensor node. Simulation results show that our attack needs 90% less time than the work published by Gérard
et al
. to reach a success rate of 0.9.
1. Introduction
W
ireless sensor networks (WSN) provide promising solutions in a wide range of applications, such as military, healthy care, industrial monitoring, traget localization and tracing. Sensor nodes that consist the WSN are usually placed in protentially hostile enviremont and face various kinds of challenges
[1]

[3]
. For the needs of security, cryptographic algorithms are used to implement authentications and encrypted communications in WSN. Advanced Encryption Standard (AES), adopted by USA government in 2002
[4]
, is ideal for the resourcesconstrained sensor nodes because of its high speed and low cost. As a standard encryption algorithm in wireless communication
[5]
, AES is widely used in current WSN platforms.
However, wireless sensor nodes are vulnerable to sidechannel attacks. Since proposed by Kocher
et al
.
[6]
, sidechannel attacks have been known as efficient to recover the key by eavesdropping the physical information (e.g., power consumption, electromagnetic radiation) leaked by target devices
[7]

[10]
. These attacks are more efficient than traditional cryptanalysis. They do not interrupt operations of the target device, so they can be conducted stealthily on wireless sensor nodes without being detected
[11]
,
Sidechannel collision attack, as a combination of sidechannel attack and cryptanalysis, was proposed in 2003 by Schramm
et al
. against DES
[12]
, and was applied to AES
[13]
soon after that. Improved collision attacks were presented subsequently
[14]

[17]
. Most collision attacks are highly sensitive to errors, namely false positives of collision detections
[18]
, which usually happen when the noise level is high. Gérard
et al
.
[18]
introduced Low Density Parity Check (LDPC) decoding approach to deal with errors, which made their work more efficient than previous methods. However, there are two problems for LDPC method. First, the computational complexity of the offline stage is high, due to its framework. Second, the online stage (power acquisition stage) is very timeconsuming, because all the acquired power traces need to be saved.
In this paper, we propose an efficient and error robust collision attack. The new framework of our approach is based on a double sieve model, which ensures the efficiency and success rate of attacks. A bitwise collision detection method is proposed, which greatly reduces the time for online stage by reducing the number of saved traces. The computational complexity of the framework is low, so the key can be recovered very fast. Practical attacks on AES and experimental results show that our approach is more efficient than previous methods.
The rest of this paper is organized as follows. In Section 2, we briefly introduce the notations and recall previous collision attacks. In Section 3, we propose the framework of our new collision attack. In Section 4, we describe the bitwise collision detection method. In Section 5, we present the experiments of our new attack. An errortolerant version of our attack is presented in Section 6, and the efficiency is analyzed in Section 7. Finally, Section 8 concludes the paper.
2. Preliminary
 2.1 Notations
The cryptographic algorithm we focus on in this paper is AES. The 16bytes plaintext and firstround sub key are denoted as
P
= {
p
_{1}
,⋯,
p
_{16}
} and
K
= {
k
_{1}
,⋯,
k
_{16}
}. Plaintexts and power traces are numbered by superscript, and the
i
th plaintext and power trace are written as
P^{i}
and
T^{i}
. The operations of 16 SBoxes are handled sequentially, so a power trace can be cut into 16 sections, each of which is composed of
l
points. The section corresponding to the
a
th SBox is denoted as
T_{a}
= {
t_{a}
_{,1}
,
t_{a}
_{,2}
,⋯,
t_{a,l}
}. Averaged power traces are used in our attack, denoted as
 2.2 Linear Collision Attack
Collision attack proposed by Schramm
et al
.
[12]
is based on the concept of internal collision, where a function produces the same output for two inputs:
ϕ
(
x
_{1}
)=
ϕ
(
x
_{2}
)=
y
. Linear collision attack
[17]
describes how to recover the key from internal collisions based on linear equations. In AES, if a collision between the computations of SBox
a
and
b
in the first round is detected, the attackers will have the following relation:
A linear equation can be deduced:
A series of linear equations can be built with more collisions detected. Eventually, once 1 key byte is determined, the other 15 key bytes can be decided immediately. As a result, the size of key space is reduced to 2
^{8}
.
 2.3 CorrelationEnhanced Collision Attack
Two main approaches have been proposed to detect sidechannel collisions
[18]
: the binary test and the correlationenhanced method
[19]
. The former one computes the distance between two power traces. Euclidean distance and absolute deviation
[20]
are usually used here. A Collision is confirmed if the distance is less than a threshold. However, this technique is a byte wise operation. A collision only indicates
HW
(
p_{a}
⊕
k_{a}
) =
HW
(
p_{b}
⊕
k_{b}
) , and (2) is not necessarily established. This method is also sensitive to false detections of collisions. The correlationenhanced technique compares two series of (instead of two) power traces with correlation coefficient, and returns a score list of all the guessed value of Δ
k_{a,b}
. This allows an improvement: By testing several highestscored candidates instead of only the first one, the probability of finding a correct collision can be increased. But this approach needs to compute correlation coefficient for every guessed value of Δ
k_{a,b}
, so the efficient is a problem.
 2.4 LDPC Decoding Problem in Collision Attack
Gérard
et al
.
[18]
pointed out that the linear collision attack can be rewritten as a LDPC decoding problem, since there exists a relationship:
The set Δ
K
= {Δ
k_{a,b}
1 ≤
a
≠
b
≤ 16} can be regarded as a LDPC code, and (2) as paritycheck nodes. Finding the correct Δ
K
is equivalent to decode the LDPC code.
It is noteworthy that (3) provides a solution to find out errors in collision detections. In this paper, we exploit (3) as an errorchecking criterion, and detail the procedure in the next section.
3. A Novel Framework for Linear Collision Attack
In this section, we propose a new framework of collision attack. As shown in
Fig. 1
, the main body of the framework is a loop. Each iteration, called a partial attack, is based on a double sieve model, and contributes a part of information of the key. The loop iterates and accumulates the information until all the bytes of Δ
K
are determined. Finally 2
^{8}
candidate keys that are compatible to the set Δ
K
are tested.
Work flow of the new framework.
The double sieve model includes two screenings: 1) Collision detection sieves the probable candidate of the Δ
K
, and saves the result in a 1×120 array
DeltaKey1
. 2) Error detection screens out the false part of
DeltaKey1
, and saves the survivals in a 1×120 array
DeltaKey2
. Accumulated information of Δ
K
is kept in
DeltaKey3
.
The work flow of our framework is showed in
Algorithm 1
. Each partial attack consists of 4 steps. First, power traces are collected and preprocessed in the
PreparePowerTraces
step. Then in
DetectCollision
step, these power traces are used to detect collisions. These two steps will be detailed in Section 4.
In the
DetectError
step, as described in
Algorithm 2
, we use (3) to check every elements of
DeltaKey1
. A 1×120 array
Errorlist
is used to record how many times (3) is not satisfied for every Δ
k_{a,b}
. If an equation of (3) is not satisfied, the three involved Δ
k
’s will be marked. If
Errorlist
((
a
,
b
)) is larger than a threshold
Th_{EL}
, Δ
k_{a,b}
will be erased. Because there are 14 possible values of
c
which satisfy the condition (
a
≠
c
≠
b
) ∧ (1 ≤
c
≤ 16) , every Δ
k_{a,b}
has 14 relative equations in (3), so the maximum of
Errorlist
((
a
,
b
)) is 14. A wrong guess of Δ
k_{a,b}
tends to fail in most of the checks, whereas a correct guess has few failures. So we set
Th_{EL}
as a middle value, for example 7.
Accumulate
step compares the newly obtained information in
DeltaKey2
and the accumulated information in
DeltaKey3
. Then
DeltaKey3
is refreshed with the union of
DeltaKey2
and
DeltaKey3
. An exception is that for some Δ
k_{a,b}
, the corresponding values kept in
DeltaKey2
and
DeltaKey3
are different. Then they should be erased.
4. Bitwise Collision Detection
Here we detail the bitwise collision detection and the related
PreparePowerTraces
step. The essential idea is to find the 1bit collision between two bytes, and to treat other bits as noise by choosing plaintexts and acquiring power traces properly. The input of SBox, (i.e.,
K
⊕
P
), is chosen as the attack target, and Hamming Weight is used as the power model. We denote the bits in a plaintext byte and a key byte with
u
and
v
:

Pj=uj,8║uj,7║uj,6║uj,5║uj,4║uj,3║uj,2║uj,1

kj=vj,8║vj,7║vj,6║vj,5║vj,4║vj,3║vj,2║vj,1
 4.1 Preparation of Power Traces
For a partial attack, 8 power traces will be prepared. We use the most significant bit (i.e., bit 8) as an example to illustrate the process flow of the preparation of power traces:

1) Generate plaintexts of which the 8th bits of all the bytes are fixed (to zero for example). Other bits are random (e.g.,Pj= 0║uj,7║uj,6║uj,5║uj,4║uj,3║uj,2║uj,1(1 ≤j≤ 16)).

2) Acquiring power traces with an oscilloscope that can average power traces in a realtime mode. Then only 1 power trace will be saved, denoted asT8.

3) To further reduce the noise, the newly acquired power trace will be averaged along with those acquired in previous partial attacks. For thenth partial attack we have:

4) Cutinto 16 sections:(The superscriptnis omitted for simplicity.)
 4.2 Bitwise Collision Detection
As presented in
Algorithm 3
, we use
to detect the
i
thbit collision between
k_{a}
and
k_{b}
(1 ≤
a
≠
b
≤ 16) .Function
Distance
is the Euclidean distance of
:
If (5) is less than
Th_{CD}
, we can guess that
u_{a,i}
⊕
v_{a,i}
=
u_{b,i}
⊕
v_{b,i}
. Since
u_{a,i}
=
u_{b,i}
=0, we have
D
(
i
)=
v_{a,i}
⊕
v_{b,i}
=0.
Th_{CD}
should be chosen carefully to ensure the accuracy of collision detection. Since the result of
Distance
follows a chisquare distribution,
Th_{CD}
is relevant to the noise level. Here is an adaptively strategy to determine it: the median of the results of
Distance
can be chosen as
Th_{CD}
to make sure that they are divided into two groups with the similar sizes.
5. Experiments
 5.1 Measurement Setup
As shown in
Fig. 2
, we built an experimental environment to mount the sidechannel collision attacks. The target AES is implemented in a lowpower, highperformance microcontroller AT89S52, which is suitable for various applications of WSN. A resistance of 10 Ohm is put in the power supply path of the microcontroller. An Agilent MSOX 3054A oscilloscope with a differential probe is employed to acquire the voltage difference over the resistance which is related to the current consumed by the AT89S52. In our case, each raw power traces contains 10 000 points. For each partial attack, one power trace is averaged from
m
raw power traces. Here we set
m
to be 300.
Measurement setup of collision attacks on AT89S52.
 5.2 Bitwise Collision Detection
For each pair of key bytes (
k_{a}
,
k_{a}
) , we use bitwise collision detection method to find out Δ
k_{a,b}
.
Here we use (
k
_{1}
,
k
_{2}
) as an example to detail how it works, where
Fig. 3
. shows the detection results.
Fig. 3
(a)(h) correspond to the collision detection results of bit 81. For example,
Fig. 3
(a) shows
There exist obvious peaks, because
α
_{8}
≠
β
_{8}
. In
Fig. 3
(d), the curve
is close to zero, suggesting that
α
_{5}
≠
β
_{5}
. Finally, the Euclidean distances of 8 bits and a threshold line (
Th_{CD}
) are plotted in
Fig. 3
(i). Here we have Δ
k
_{1,2}
=11101001.
The result of bitwise collision detection between k_{1} and k_{2} .
 5.3 Error Detection
After collision detection, a guessed Δ
K
is produced and kept in
DeltaKey1
. Then the error detection method is used to screen out the wrong part of Δ
K
. For the sake of simplicity, we focus on the triplet Δ
k
_{1,2}
, Δ
k
_{1,3}
, and Δ
k
_{2,3}
to illustrate the workflow of our framework, where

Δk1,2=11101001 Δk1,3=11101000 Δk2,3=00000001.
As shown in
Fig. 4
, the triplet Δ
k
_{1,2}
, Δ
k
_{1,3}
, and Δ
k
_{2,3}
are recovered within 2 partial attacks. In partial attack 1, the wrong guessed Δ
k
_{2,3}
is discarded after error detection, and Δ
k
_{1,2}
, Δ
k
_{1,3}
are delivered to
DeltaKey2
. Similarly, in partial attack 2, the false guess of Δ
k
_{1,3}
is discarded. In the
Accumulate
step, the information of two partial attacks is merged together, then Δ
k
_{1,2}
, Δ
k
_{1,3}
, and Δ
k
_{2,3}
are revealed. All the other parts of Δ
K
are recovered in the same way, and finally the key of AES is recovered.
Recovery process of Δk_{1,2} , Δk_{1,3} , and Δk_{2,3}.
6. Improved Framework with ErrorTolerant Mechanism
Here we propose an errortolerant version of our approach. Our original approach is a binary test and has a low cost of computation. The correlationenhanced method produces a
list of
candidates of Δ
k_{a,b}
, and increases the success rate at the expense of larger computation amount. Our improved approach uses the concept of list to realize an errortolerant mechanism and keeps the computation amount at a reasonable level. Improvements are mainly made in
DetectCollision
and
DetectError
steps:
 6.1 Modified Bitwise Collision Detection
To increase the number of candidates of each Δ
K
, the most straight forward idea is to include the 8 hypothetic values which are onebit different from the most probable one. The output of the
DetectCollision
step,
DeltaKey1
, then becomes a 9×120 matrix. The elements of the matrix are denoted as
DeltaKey1
(
i
(
a
,
b
)) (1 ≤
i
≤ 9,1 ≤
a
≠
b
≤ 16).
 6.2 Modified Error Detection
There are two main changes in the modified error detection method as presented in
Algorithm 4
: 1)The input
DeltaKey1
becomes a 9×120 matrix, and the first row of
DeltaKey1
is checked in loop 1 (step 26); 2) In loop 2, if
Errorlist
((
a
,
b
))>
Th_{EL}
, other 8 candidates will be checked in turn, as shown in
Algorithm 5
. Only if no candidate passes the check will
DeltaKey1
(1,(
a
,
b
)) be erased, or it will be replaced by the candidate which leads to the minimum
Errorlist
((
a
,
b
)) .
7. Efficiency Comparison
We do simulations in MATLAB to compare the efficiency of our attack and the LDPC method. The comparisons include the success rate and time (online time and offline time).
 7.1 Online Time vs. Success Rate
We denote the time for the oscilloscope to capture and average a power trace as
τ_{A}
, and the time to save a trace as
τ_{S}
. In our case where one power trace contains 10 000 sample points,
τ_{S}
is roughly 50 times of
τ_{A}
. Let
m
be the number of power traces to be averaged,
n
be the number of partial attacks, the total online time
τ_{OL}
is
In Our original version, we fix
m
= 300 , so
In the errortolerant version, we set
m
= 50 , so
In order to assess the efficiency, we plot the success rates of attacks as a function of online time
τ_{OL}
, rather than the number of raw power traces, by sweeping the upper limit of
n
. As shown in
Fig. 5
, our original approach (denoted as DS) is more efficient than the LDPC method when the online time is less than 900
τ_{S}
.The errortolerant version (denoted as DSET) achieves an obvious gain in efficiency. The online time needed to reach a success rate of 0.9 is 90% less than that of LDPC method.
The success rates as a function of online time τ_{OL}.
 7.2 Online Time vs. Offline Time
Offline time reflects the computational complexity of the attack algorithm. We examined the operation time for three algorithms (LDPC, DS, and DSET) to carry out 1000 attacks. As shown in
Fig. 6
, the computational complexity of LDPC method is significantly higher than our approaches. The errortolerant version of our attack needs least offline time to recover the key.
The offline time as a function of online time τ_{OL}.
 7.3 Selection of Parameters
The former experiments are done with a fixed
m
. Here we focus on the impacts of
m
on the success rates of attacks.
As shown in
Fig. 7
, the success rate curves reach to a larger upper limit with lager
m
. However, increasing
m
also increases the time for each partial attack. So there is no need to increase
m
once the upper limit of success rate is close to 1. In our case (the errortolerant version),
m
= 50 is reasonable.
The success rates with different average times m as a function of n (the number of partial attacks).
8. Conclusion
We propose a double sieve collision attack based on bitwise collision detection in this paper, and give an errortolerant version which significantly reduces the time of online stage. Practical attacks are successfully mounted on AES implemented in a real chip which can be used in WSN. We also compare the efficiency of our attack with the work published by Gérard
et al
.
[18]
. The experiment result shows our attack saves 90% of time to reach a success rate of 0.9.
Although AES is the target algorithm in this paper, our work can be extended to other symmetry cryptography algorithms that are vulnerable to collision attack.
BIO
Yanting Ren was born in 1987. She received her B.S. degree in Tsinghua University in 2010. She is currently a Ph.D. student in Institute of Microelectronics, Tsinghua University. Her main research interests include sidechannel attack, and sidechannel attack resistant implementation in cryptography.
Liji Wu was born in 1965. He received the B.S., M.S., and Ph.D. degrees in electronic engineering from Tsinghua University, Beijing, China, in 1988, 1991 and 1997, respectively. He currently works as a professor in Tsinghua University. His main research interests include Circuits and Systems in Commercial Information Security and Automotive Electronics.
An Wang was born in 1983. He received his Ph.D. degree in Shangdong University in 2011. He currently works as a post doctor in Tsinghua University. His main research interests include sidechannel attack, embedded system, and fast implementation in cryptography. He is also the webmaster of a cryptographic website (http://www.mathmagic.cn).
Zheng J.
,
Jamalipour A.
2009
Wireless Sensor Networks: A Networking Perspective
Wiley
New York
Padmavathi G.
,
Shanmugapriya M.
2009
“A survey of attacks, security mechanisms and challenges in wireless sensor networks,”arXiv preprint arXiv: 0909.0576
http://arxiv.org/abs/0909.0576
Krauß C.
,
Schneider M.
,
Eckert C.
2008
“On handling insider attacks in wireless sensor networks,”
Information Security Technical Report
13
(3)
165 
172
DOI : 10.1016/j.istr.2008.10.011
2001
NIST Std. 197, “Announcing the Advanced encryption standard (AES),”
http://csrc.nist.gov/publications/fips/fips197/fips197.pdf
2003
IEEE Std. 802.15.4, “Wireless Medium Access Control (MAC) and Physical Layer (PHY) specifications for Low Rate Wireless Personal Area Networks (LRWPANS),”
http://ieeexplore.ieee.org/iel5/8762/27762/01237559.pdf
Kocher P. C.
“Timing attacks on implementations of Diffie–Hellman, RSA, DSS, and other systems,”
Springer
in Proc. of CRYPTO’ 1996, LNCS
Heidelberg
1996
vol. 1109
104 
113
Kocher P. C.
,
Jaffe J.
,
Jun B.
“Differential power analysis,”
Springer
in Proc. of CRYPTO’ 1999, LNCS
Heidelberg
1999
vol. 1666
388 
397
Chair S.
,
Rao J. R.
,
Rohatgi P.
“Template attacks,”
Springer
in Proc. of CHES 2002, LNCS
Heidelberg
2003
vol. 2523
13 
28
Brier E.
,
Clavier C.
,
Olivier F.
“Correlation power analysis with a leakage model,”
Springer
in Proc. of CHES 2004, LNCS
Heidelberg
2004
vol. 3156
16 
29
Gierlichs B.
,
Batina L.
,
Tuyls P.
,
Preneel B.
“Mutual information analysis,”
Springer
in Proc. of CHES 2008, LNCS
Heidelberg
2008
vol. 5154
426 
442
de Meulenaer G.
,
Standaert F. X.
2010
“Stealthy compromise of wireless sensor nodes with power analysis attacks,”
Mobile Lightweight Wireless Systems, LNICST
Springer
Heidelberg
45
229 
242
Schramm K.
,
Wollinger T. J.
,
Paar C.
“A new class of collision attacks and its application to DES,”
Springer
in Proc. of 10th Int. Workshop on Fast Software Encryption, LNCS
Heidelberg
2003
vol. 2887
206 
222
Schramm K.
,
Leander G.
,
Felke P.
,
Parr C.
“A collisionattack on AES: Combining side channel and differential attack,”
Springer
in Proc. of CHES 2004, LNCS
Heidelberg
2004
vol. 3156
163 
175
Ledig H.
,
Muller F.
,
Valette F.
“Enhancing collision attacks,”
Springer
in Proc. of CHES 2004, LNCS
Heidelberg
2004
vol. 3156
176 
190
Bogdanov A.
“Improved sidechannel collision attacks on AES,”
Springer
in Proc. of 14th Int. Workshop on Selected Areas in Cryptography, LNCS
Heidelberg
2007
vol. 4876
84 
95
Bogdanov A.
“Multipledifferential side channel collision attacks on AES,”
Springer
in Proc. of CHES 2008, LNCS
Heidelberg
2008
vol. 5154
30 
44
Clavier C.
,
Feix B.
,
Gagnerot G.
,
Roussellet M.
,
Verneuil V.
“Improved collisioncorrelation power analysis on first order protected AES,”
Springer
in Proc. of CHES 2011, LNCS
Heidelberg
2011
vol. 6917
49 
62
Gérard B.
,
Standaert F. X.
“Unified and optimized linear collision attacks and their application in a nonprofiled setting,”
Springer
in Proc. of CHES 2012, LNCS
Heidelberg
2012
vol. 7428
175 
192
Moradi A.
,
Mischke O.
,
Eisenbarth T.
“Correlationenhanced power analysis collision attack,”
Springer
in Proc. of CHES 2010, LNCS
Heidelberg
2010
vol. 6225
125 
139
Sveshnikov A. A.
,
Gelbaum B. R.
1968
Problems in Probability Theory, Mathematical Statistics and Theory of Random Functions
Courier Dover Publications
New York