Double Sieve Collision Attack Based on Bitwise Detection
Double Sieve Collision Attack Based on Bitwise Detection
KSII Transactions on Internet and Information Systems (TIIS). 2015. Jan, 9(1): 296-308
Copyright © 2015, Korean Society For Internet Information
  • Received : April 01, 2014
  • Accepted : December 13, 2014
  • Published : January 31, 2015
Export by style
Cited by
About the Authors
Yanting Ren
Liji Wu
An Wang

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 error-tolerant mechanism. Practical attacks are successfully conducted on a software implementation of AES in a low-power 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 resources-constrained 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 side-channel attacks. Since proposed by Kocher et al . [6] , side-channel attacks have been known as efficient to recover the key by eavesdropping the physical information (e.g., power consumption, electro-magnetic 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] ,
Side-channel collision attack, as a combination of side-channel 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 time-consuming, 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 error-tolerant 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 16-bytes plaintext and first-round 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 Pi and Ti . The operations of 16 S-Boxes 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 S-Box is denoted as Ta = { ta ,1 , ta ,2 ,⋯, ta,l }. Averaged power traces are used in our attack, denoted as
PPT Slide
Lager Image
- 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 S-Box a and b in the first round is detected, the attackers will have the following relation:
PPT Slide
Lager Image
A linear equation can be deduced:
PPT Slide
Lager Image
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 Correlation-Enhanced Collision Attack
Two main approaches have been proposed to detect side-channel collisions [18] : the binary test and the correlation-enhanced 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 ( pa ka ) = HW ( pb kb ) , and (2) is not necessarily established. This method is also sensitive to false detections of collisions. The correlation-enhanced technique compares two series of (instead of two) power traces with correlation coefficient, and returns a score list of all the guessed value of Δ ka,b . This allows an improvement: By testing several highest-scored 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 Δ ka,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 re-written as a LDPC decoding problem, since there exists a relationship:
PPT Slide
Lager Image
The set Δ K = {Δ ka,b |1 ≤ a b ≤ 16} can be regarded as a LDPC code, and (2) as parity-check 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 error-checking 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.
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
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 Δ ka,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 ThEL , Δ ka,b will be erased. Because there are 14 possible values of c which satisfy the condition ( a c b ) ∧ (1 ≤ c ≤ 16) , every Δ ka,b has 14 relative equations in (3), so the maximum of Errorlist (( a , b )) is 14. A wrong guess of Δ ka,b tends to fail in most of the checks, whereas a correct guess has few failures. So we set ThEL as a middle value, for example 7.
PPT Slide
Lager Image
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 Δ ka,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 1-bit collision between two bytes, and to treat other bits as noise by choosing plaintexts and acquiring power traces properly. The input of S-Box, (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 real-time 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:
PPT Slide
Lager Image
  • 4) Cutinto 16 sections:(The superscriptnis omitted for simplicity.)
- 4.2 Bitwise Collision Detection
As presented in Algorithm 3 , we use
PPT Slide
Lager Image
to detect the i th-bit collision between ka and kb (1 ≤ a b ≤ 16) .Function Distance is the Euclidean distance of
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
If (5) is less than ThCD , we can guess that ua,i va,i = ub,i vb,i . Since ua,i = ub,i =0, we have D ( i )= va,i vb,i =0.
ThCD should be chosen carefully to ensure the accuracy of collision detection. Since the result of Distance follows a chi-square distribution, ThCD 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 ThCD 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 side-channel collision attacks. The target AES is implemented in a low-power, high-performance 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 MSO-X 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.
PPT Slide
Lager Image
Measurement setup of collision attacks on AT89S52.
- 5.2 Bitwise Collision Detection
For each pair of key bytes ( ka , ka ) , we use bitwise collision detection method to find out Δ ka,b .
Here we use ( k 1 , k 2 ) as an example to detail how it works, where
PPT Slide
Lager Image
Fig. 3 . shows the detection results. Fig. 3 (a)-(h) correspond to the collision detection results of bit 8-1. For example, Fig. 3 (a) shows
PPT Slide
Lager Image
There exist obvious peaks, because α 8 β 8 . In Fig. 3 (d), the curve
PPT Slide
Lager Image
is close to zero, suggesting that α 5 β 5 . Finally, the Euclidean distances of 8 bits and a threshold line ( ThCD ) are plotted in Fig. 3 (i). Here we have Δ k 1,2 =11101001.
PPT Slide
Lager Image
The result of bitwise collision detection between k1 and k2 .
- 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.
PPT Slide
Lager Image
Recovery process of Δk1,2 , Δk1,3 , and Δk2,3.
6. Improved Framework with Error-Tolerant Mechanism
Here we propose an error-tolerant version of our approach. Our original approach is a binary test and has a low cost of computation. The correlation-enhanced method produces a list of candidates of Δ ka,b , and increases the success rate at the expense of larger computation amount. Our improved approach uses the concept of list to realize an error-tolerant 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 one-bit 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 2-6); 2) In loop 2, if Errorlist (( a , b ))> ThEL , 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 )) .
PPT Slide
Lager Image
PPT Slide
Lager Image
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
PPT Slide
Lager Image
In Our original version, we fix m = 300 , so
PPT Slide
Lager Image
In the error-tolerant version, we set m = 50 , so
PPT Slide
Lager Image
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 error-tolerant version (denoted as DS-ET) 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.
PPT Slide
Lager Image
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 DS-ET) to carry out 1000 attacks. As shown in Fig. 6 , the computational complexity of LDPC method is significantly higher than our approaches. The error-tolerant version of our attack needs least offline time to recover the key.
PPT Slide
Lager Image
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 error-tolerant version), m = 50 is reasonable.
PPT Slide
Lager Image
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 error-tolerant 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.
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 side-channel attack, and side-channel 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 side-channel attack, embedded system, and fast implementation in cryptography. He is also the webmaster of a cryptographic website (
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
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),”
2003 IEEE Std. 802.15.4, “Wireless Medium Access Control (MAC) and Physical Layer (PHY) specifications for Low Rate Wireless Personal Area Networks (LR-WPANS),”
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 collision-attack 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 side-channel 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. “Multiple-differential 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 collision-correlation 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 non-profiled setting,” Springer in Proc. of CHES 2012, LNCS Heidelberg 2012 vol. 7428 175 - 192
Moradi A. , Mischke O. , Eisenbarth T. “Correlation-enhanced 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