# A Novel Multiple-Bits Collision Attack Based on Double Detection with Error-Tolerant Mechanism

Authors: Ye Yuan; Liji Wu; Yijun Yang; Xiangmin Zhang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Side-channel collision attacks are more powerful than traditional side-channel attack without knowing the leakage model or establishing the model. Most attack strategies proposed previously need quantities of power traces with high computational complexity and are sensitive to mistakes, which restricts the attack efficiency seriously. In this paper, we propose a multiple-bits side-channel collision attack based on double distance voting detection (DDVD) and also an improved version, involving the error-tolerant mechanism, which can find all 120 relations among 16 key bytes when applied to AES (Advanced Encryption Standard) algorithm. In addition, we compare our collision detection method called DDVD with the Euclidean distance and the correlation-enhanced collision method under different intensity of noise, which indicates that our detection technique performs better in the circumstances of noise. Furthermore, 4-bit model of our collision detection method is proven to be optimal in theory and in practice. Meanwhile the corresponding practical attack experiments are also performed on a hardware implementation of AES-128 on FPGA board successfully. Results show that our strategy needs less computation time but more traces than LDPC method and the online time for our strategy is about 90% less than CECA and 96% less than BCA with 90% success rate.


---

## Body

## 1. Introduction

Although modern cryptographic algorithms have been proven to be safe mathematically, this does not mean that the physical implementation is safe enough, where attacker can obtain some physical information from side channel. Side-channel attack (SCA) was proposed almost 20 years ago, which was first put forward in 1996 by Kocher [1] and became a powerful cryptanalysis technique. Power consumption analyses are widely used in SCA, which utilizes the relation between power consumption or electromagnetic signal of the executing device and processed data in order to recover the key value. Since Differential Power Analysis (DPA) was proposed in 1997 [2], whose distinguisher is the difference of the mean traces, various distinguishers have been designed and improved to enhance attack ability and efficiency, for example, Pearson correlation coefficient as a distinguisher for Correlation Power Analysis (CPA)[3], mutual information for Mutual Information Analysis (MIA)[4], and maximum likelihood for Template Attack [5, 6] (TA) and Template Based DPA [7]. However, the necessity of estimating and establishing the leakage model has been a serious restriction for SCA, which collision attack can ignore. Collision attack was first proposed to analyze Hash algorithm [8] and has become a branch of mathematical cryptanalysis, but it only reveals relation between input and output without exploiting internal information as SCA.As a combination of SCA and collision attack, side-channel collision attack can exploit the information of internal leakage without a large number of power traces as well as the knowledge of the leakage model. Side-channel collision attack showed strong ability of attack, when first presented [9] against Data Encryption Standard (DES) by Schramm et al., which was applied to AES [10] successfully later. Then all kinds of improved versions [11–17] of side-channel collision attack sprang up, and most of these methods show high sensitivity to errors, where the recovered key is totally wrong even when error occurs only in 1 bit under the high noise level circumstance, leading to a low efficiency. Bogdanov presented some voting detection methods that seemed to be more practical [14], but they need too many traces in a profiling phase and encrypting the same plaintexts repeatedly for decreasing the influence of noise may not be realistic. In 2010, Moradi proposed a correlation-enhanced method [15] that improves the probability of collision, but it may need lots of average power traces to process an attack and is sensitive to errors. In 2011, Bogdanov proposed an attack strategy [17] that uses the results of DPA to test chain separately. This method can improve the success probability in a sense that it cannot check the mistakes in collision detection which highly impact the attack results. Then Gérard et al. combined Low Density Parity Check (LDPC) decoding with correlation-enhanced and Euclidean Distance detection method in 2012 [16], which can be a globally efficient attack strategy in noisy settings. Two side-channel collision attack procedures based on bitwise collision detection were proposed, respectively, by Ren et al [18] in 2015 and by Wang et al [19] in 2017, which may have a poor performance on the detection success rate with high level noise. However, efficiency of collision detection and lack of error-tolerant and check mechanism are two main issues of existing side-channel collision attack.Our Contribution. In this paper, we propose a novel multiple-bits collision attack framework. In particular, double distance voting detection (DDVD) and the error-tolerant and check mechanism are presented to ensure the high accuracy. In addition, we compare our collision detection method called DDVD with the Euclidean Distance and the correlation-enhanced collision methods under different intensity of noise, which indicates that our detection technique has a better performance in the circumstances of noise. Furthermore, 4-bit collision attack is proven to be optimal in theory and experiments. Practical attack experiments are performed successfully on a hardware implementation of AES in FPGA board.The remainder of this paper is organized as follows. In Section2, for a better understanding, we introduce some notations of our method as well as the basic linear collision attacks and then review the binary and ternary voting detection methods, correlation-enhanced collision attack, and LDPC decoding method in collision attack. In Section 3, a novel framework of multiple-bits collision attack is presented and we take the 4-bit model as an example to explain the attack procedure. In Section 4, we propose an improved version with an error-tolerant and check mechanism. In Section 5, we compare our collision detection method with other widely used detection techniques under different intensity of noise and analyze our model, and the experiments as well as the comparisons are also shown. Finally, we give the conclusion in Section 6.


## 2. Preliminaries

In order to understand the strategy easily, AES is chosen as the target block cipher to perform the attack method. As for the hardware implementation of this paper, it operates each of 16 S-boxes, which are used for the SubBytes operation, sequentially one by one. The following proposed statements and techniques can be successfully utilized in other cryptographic symmetric algorithms.


### 2.1. Notations

For a better description of the proposed method, we define some notations as follows. First we use letters k and p for 16-byte plaintext and first round subkey, with subscripts indicating a particular byte:(1)P≜p1,p2,p3,⋯,p16,K≜k1,k2,k3,⋯,k16.Then we use the superscripts letters m and l for the 4 most significant bits and 4 least significant bits separately, meaning that pim≜pi7:4,kim≜ki7:4,pil≜pi3:0,kil≜ki3:0. Next, the attacker is able to choose the value of plaintext with key value all the same. The superscripts m_f and l_g state that the 4 most significant bits and 4 least significant bits are equal to values f and g in decimal format: (2)pim_f≜pim=f,pil_g≜pil=g.Each trace acquired corresponding to first-round encryption contains 16 subtraces due to 16 sequential S-boxes, with subscripts indicating a particular S-box and each subtrace contains a number p of points, which are denoted by the subscripts:(3)T≜T1,T2,T3,⋯,T16,Ta≜ta,1,ta,2,ta,3,⋯ta,p.Furthermore, we use Tm_f (Tl_g) to denote the power trace corresponding to the plaintext, where the value of 4 most (least) significant bits of all 16 bytes isf (g) in decimal format; namely, pim=fi=116pil=gi=116.However, if the superscript is a certain digit, it shows that the plaintext is this value or power trace is corresponding to the plaintext with this value. For example,p1128 means that the first byte of plaintext equals 128 in decimal format and T1128 is denoted as the power trace of the first S-box operation with the corresponding plaintext byte being 128. Meanwhile, we use T(n) and Pn for thenth acquisition of power traces and plaintexts, respectively.


### 2.2. Linear Collision Attack

The internal collision was first presented for attacking DES [9]. It is based on the fact that if a collision on a key-dependent function can be detected, the attacker can acquire some relations between the different inputs.Linear collision is based on the internal collision. When it is applied to AES, if a collision between two S-boxes operations of the first round is detected (e.g., the collision between theith and thejth S-boxes in Figure 1), it is obvious that (4) is tenable:(4)S_boxpi⊕ki=S_boxpj⊕kjThen one can obtain a linear equation about the relation between plaintexts and first round subkey:(5)pi⊕pj=ki⊕kj=Δki,jIf the attacker can find all possible relations among 16 key bytes by detecting the collision ofS-boxes, then he will obtain an equation set about the key bytes of the first round containing 15 linear equations: (6)k1⊕k2=Δk1,2k2⊕k3=Δk2,3⋮k15⊕k16=Δk15,16Note that all the equations in the set are relevant, and there is only one free variable. Thus, this equation set only has 28 possible solutions, which means that we just need to enumerate all 256 possible candidates of 1 key byte to recover the whole key value.Figure 1
Collisions between two S_boxes.However, under the noisy experiment setting, the collision detection method may detect wrong collisions, which lead to some incorrect equations in (6). For all equations in (6) are relevant, even if only one bit error occurs in any equation, the equation system will have no solution. Thus, in this paper, we propose a detection method called DDVD which is to ensure a high detection success rate.


### 2.3. Voting Detection Methods

In [14], Bogdanov proposed the voting detection containing binary voting test and ternary voting test. Both binary and ternary voting tests are based on Euclidean Distance. For binary voting test, if an attacker can acquire a lot of power traces of the same plaintexts, he will calculate the Euclidean Distance between two trace pairs of different plaintexts. Then the attacker should calculate the total number of the trace pairs whose distance is less than a predetermined threshold. When the total number is more than the predetermined voting value, it can be confirmed that one collision is detected. However, the basic strategy of ternary voting test is the same as binary voting test, but instead of calculating the Euclidean Distance directly, this method requires calculating the distance between each of the obtained power traces with certain plaintexts and the reference power traces that are obtained during a profiling phase preparing a set of reference traces without knowing related encrypting values.


### 2.4. Correlation-Enhanced Collision Attack

Correlation-enhanced collision attack was one of the last major advanced detection techniques proposed by Moradi et al in 2010 [15]. This method compares the correlation coefficient between two sets of power traces corresponding to two different S-boxes rather than detecting the collision between two single power traces.As can be seen in Algorithm1, we take the detection between S-box 1 and S-box 2 as an example. In the online stage, an attacker should obtainN power traces corresponding toN plaintexts. When in offline stage, the attacker cuts the power trace into 16 sections based on the operation of 16 S-boxes and takes the section for S-box 1 and S-box 2. ThenT1n is divided into 256 groups according to the plaintext byte value and the attacker can get the averaged power traces of each group (T1b-b=0255), which is the same for S-box 2. Next, for each value of Δ∈GF28, the attacker rearranges T2- based on the value of b⊕Δ and calculates correlation coefficients ρΔ between T1b-b=0255 and T2b⊕Δ-b=0255. If Δ=k1⊕k2, the correlation ρΔ shall reach a maximum value; otherwise, it should have a pretty low value.Algorithm 1:Correlation enhanced detection of S-box 1 and S-box 2.
Online Stage: (1) Pn∣n=0,1,2,3,⋯,N←Plaintexts (2) Tn∣n=0,1,2,3,⋯,N←AcquireTrace(Pnn=0N) Offline Stage: (3) T1n∣n=0,1,2,3,⋯,N←CutTrace(Tnn=0N) (4) T2n∣n=0,1,2,3,⋯,N←CutTrace(Tnn=0N) (5) T1b-∣b=0,1,2,3,⋯,255←AverageTraces(T1(n)n=0N) (6) T2b-∣b=0,1,2,3,⋯,255←AverageTraces(T2(n)n=0N) (7)for  Δ∈0,1,2,3,⋯,255 (8)ρΔ←Correlation(T1b-b=0255,T2b⊕Δ-b=0255) (9)end for (10) return  arg⁡maxΔ⁡ρΔ


### 2.5. LDPC Decoding Problem in Collision Attack

In [16], Gérard et al. proposed a unified and optimized collision attack method. The proposed method rewrote the linear collision attack as a LDPC decoding problem, according to the linear relationship:(7)Δki1,i2⊕Δki2,i3=Δki1,i3∀1≤i1<i2<i3≤16The vector ΔK=(Δk1,2,Δk2,3,⋯,Δk15,16) can be seen as an LDPC codeword whose dimension is 15 and length is 120. Finding the right key value is just to decode the LDPC code. Furthermore, in order to make the attack method have a better performance in the noisy settings, actual posteriori probability value of each code was used for LDPC decoding, which is called soft decision decoding. Unlike soft decision decoding, hard decision decoding uses bit value for decoding. Compared to soft decision decoding, the effect of hard decision decoding is worse in a noise setting but the computation complexity is lower.In this paper, for the error-tolerant and check mechanism, we choose top three possible values for eachΔki1,i3 as candidates and find the likeliest value based on (7). It may be seen as a kind of hard decision decoding procedure. However, due to the DDVD, the detection success rate may remain in a high level in some noisy settings.


## 2.1. Notations

For a better description of the proposed method, we define some notations as follows. First we use letters k and p for 16-byte plaintext and first round subkey, with subscripts indicating a particular byte:(1)P≜p1,p2,p3,⋯,p16,K≜k1,k2,k3,⋯,k16.Then we use the superscripts letters m and l for the 4 most significant bits and 4 least significant bits separately, meaning that pim≜pi7:4,kim≜ki7:4,pil≜pi3:0,kil≜ki3:0. Next, the attacker is able to choose the value of plaintext with key value all the same. The superscripts m_f and l_g state that the 4 most significant bits and 4 least significant bits are equal to values f and g in decimal format: (2)pim_f≜pim=f,pil_g≜pil=g.Each trace acquired corresponding to first-round encryption contains 16 subtraces due to 16 sequential S-boxes, with subscripts indicating a particular S-box and each subtrace contains a number p of points, which are denoted by the subscripts:(3)T≜T1,T2,T3,⋯,T16,Ta≜ta,1,ta,2,ta,3,⋯ta,p.Furthermore, we use Tm_f (Tl_g) to denote the power trace corresponding to the plaintext, where the value of 4 most (least) significant bits of all 16 bytes isf (g) in decimal format; namely, pim=fi=116pil=gi=116.However, if the superscript is a certain digit, it shows that the plaintext is this value or power trace is corresponding to the plaintext with this value. For example,p1128 means that the first byte of plaintext equals 128 in decimal format and T1128 is denoted as the power trace of the first S-box operation with the corresponding plaintext byte being 128. Meanwhile, we use T(n) and Pn for thenth acquisition of power traces and plaintexts, respectively.


## 2.2. Linear Collision Attack

The internal collision was first presented for attacking DES [9]. It is based on the fact that if a collision on a key-dependent function can be detected, the attacker can acquire some relations between the different inputs.Linear collision is based on the internal collision. When it is applied to AES, if a collision between two S-boxes operations of the first round is detected (e.g., the collision between theith and thejth S-boxes in Figure 1), it is obvious that (4) is tenable:(4)S_boxpi⊕ki=S_boxpj⊕kjThen one can obtain a linear equation about the relation between plaintexts and first round subkey:(5)pi⊕pj=ki⊕kj=Δki,jIf the attacker can find all possible relations among 16 key bytes by detecting the collision ofS-boxes, then he will obtain an equation set about the key bytes of the first round containing 15 linear equations: (6)k1⊕k2=Δk1,2k2⊕k3=Δk2,3⋮k15⊕k16=Δk15,16Note that all the equations in the set are relevant, and there is only one free variable. Thus, this equation set only has 28 possible solutions, which means that we just need to enumerate all 256 possible candidates of 1 key byte to recover the whole key value.Figure 1
Collisions between two S_boxes.However, under the noisy experiment setting, the collision detection method may detect wrong collisions, which lead to some incorrect equations in (6). For all equations in (6) are relevant, even if only one bit error occurs in any equation, the equation system will have no solution. Thus, in this paper, we propose a detection method called DDVD which is to ensure a high detection success rate.


## 2.3. Voting Detection Methods

In [14], Bogdanov proposed the voting detection containing binary voting test and ternary voting test. Both binary and ternary voting tests are based on Euclidean Distance. For binary voting test, if an attacker can acquire a lot of power traces of the same plaintexts, he will calculate the Euclidean Distance between two trace pairs of different plaintexts. Then the attacker should calculate the total number of the trace pairs whose distance is less than a predetermined threshold. When the total number is more than the predetermined voting value, it can be confirmed that one collision is detected. However, the basic strategy of ternary voting test is the same as binary voting test, but instead of calculating the Euclidean Distance directly, this method requires calculating the distance between each of the obtained power traces with certain plaintexts and the reference power traces that are obtained during a profiling phase preparing a set of reference traces without knowing related encrypting values.


## 2.4. Correlation-Enhanced Collision Attack

Correlation-enhanced collision attack was one of the last major advanced detection techniques proposed by Moradi et al in 2010 [15]. This method compares the correlation coefficient between two sets of power traces corresponding to two different S-boxes rather than detecting the collision between two single power traces.As can be seen in Algorithm1, we take the detection between S-box 1 and S-box 2 as an example. In the online stage, an attacker should obtainN power traces corresponding toN plaintexts. When in offline stage, the attacker cuts the power trace into 16 sections based on the operation of 16 S-boxes and takes the section for S-box 1 and S-box 2. ThenT1n is divided into 256 groups according to the plaintext byte value and the attacker can get the averaged power traces of each group (T1b-b=0255), which is the same for S-box 2. Next, for each value of Δ∈GF28, the attacker rearranges T2- based on the value of b⊕Δ and calculates correlation coefficients ρΔ between T1b-b=0255 and T2b⊕Δ-b=0255. If Δ=k1⊕k2, the correlation ρΔ shall reach a maximum value; otherwise, it should have a pretty low value.Algorithm 1:Correlation enhanced detection of S-box 1 and S-box 2.
Online Stage: (1) Pn∣n=0,1,2,3,⋯,N←Plaintexts (2) Tn∣n=0,1,2,3,⋯,N←AcquireTrace(Pnn=0N) Offline Stage: (3) T1n∣n=0,1,2,3,⋯,N←CutTrace(Tnn=0N) (4) T2n∣n=0,1,2,3,⋯,N←CutTrace(Tnn=0N) (5) T1b-∣b=0,1,2,3,⋯,255←AverageTraces(T1(n)n=0N) (6) T2b-∣b=0,1,2,3,⋯,255←AverageTraces(T2(n)n=0N) (7)for  Δ∈0,1,2,3,⋯,255 (8)ρΔ←Correlation(T1b-b=0255,T2b⊕Δ-b=0255) (9)end for (10) return  arg⁡maxΔ⁡ρΔ


## 2.5. LDPC Decoding Problem in Collision Attack

In [16], Gérard et al. proposed a unified and optimized collision attack method. The proposed method rewrote the linear collision attack as a LDPC decoding problem, according to the linear relationship:(7)Δki1,i2⊕Δki2,i3=Δki1,i3∀1≤i1<i2<i3≤16The vector ΔK=(Δk1,2,Δk2,3,⋯,Δk15,16) can be seen as an LDPC codeword whose dimension is 15 and length is 120. Finding the right key value is just to decode the LDPC code. Furthermore, in order to make the attack method have a better performance in the noisy settings, actual posteriori probability value of each code was used for LDPC decoding, which is called soft decision decoding. Unlike soft decision decoding, hard decision decoding uses bit value for decoding. Compared to soft decision decoding, the effect of hard decision decoding is worse in a noise setting but the computation complexity is lower.In this paper, for the error-tolerant and check mechanism, we choose top three possible values for eachΔki1,i3 as candidates and find the likeliest value based on (7). It may be seen as a kind of hard decision decoding procedure. However, due to the DDVD, the detection success rate may remain in a high level in some noisy settings.


## 3. A Novel Framework of Multiple-Bits Collision Attack

In this section, a framework of multiple-bits side-channel collision attack is presented. As can be seen in Figure2, plaintexts need to be chosen based on multiple-bits (n-bits) model and then we prepare the power trace. Double distance voting detection is the important part of the framework ensuring the high success probability along with high efficiency. However, the principal part of the framework is based on a circulation. Each iteration stands for an attack, where we obtain only n-bits of a byte relation between all key bytes. After several iterations, the whole byte value of Δ between all key bytes can be acquired, which will be utilized to recover the key value.Figure 2
Framework of multiple-bits (n bits) collision attack.Due to the fact that the 4-bit collision attack leads to the highest efficiency, which will be proven and verified in Section5, we take the 4-bit model as an example to explain our attack method. According to our attack framework, for 4-bit model, 2 iterations are enough to recover the key value, whereof one is for the four most significant bits and the other is for the four least significant bits. In the rest of this paper, we only describe the strategy for the four most significant bits of one byte. The remaining four least significant bits can be found using the same technique.


### 3.1. The Idea in a Nutshell

For a better understanding, we describe the main flow of our attack strategy in Algorithm2. As our description is based on 4-bit model, all the following statements can be applied to our multiple-bits models. For example, some parameters of 4-bit model are 15 or 16, which can be interpreted as 24-1 or 24, and thus for other n-bits model, the parameters should be 2n-1 or 2n.Algorithm 2:Multiple-bits side-channel collision attack.
(1) Pn∣n=1,2,3,⋯,16N←ChoosePlaintexts() (2) Tm_jn∣n=1,2,3,⋯,Nj=015←AcquireTrace(P(n)n=116N) (3) t-im_j∣1≤i≤16j=015←PreProTrace(Tm_jn∣0≤n≤Nj=015) (4)  for each (i1,i2∣1≤i1<i2≤16) (5)Δki1,i2←DDVD(t-i1m_jj=015,t-i2m_jj=015) (6)  end for (7) Recoverkey(Δi1,i2(1≤i1<i2≤16))Like most of other attack strategies, our method also first gets some traces and proceeds with some preprocessing, seen from Steps1, 2, and 3. Double distance voting detection is the core of our method combining enhanced Euclidean Distance detection and voting detection, which ensures our success rate. Finally, based on the main idea in Section2.2, when we find all possible relations among 16 key bytes, the brute force way is able to find the right key value quickly, for we only need to enumerate 256 key values. Some details will be presented in the following sections.


### 3.2. Choose Plaintexts

According to our attack strategy, we assume that the attacker is able to choose the plaintext. The 4-bit side-channel collision attack model aims to detect the collision of 4 bits between 2 different S-boxes, and in this situation other 4 bits are the noise for the detection. It is important for improving the efficiency of our method to determine how to choose the value ofpimi=116. Algorithm 3 presents the strategy of plaintexts choice, which can generate 16N plaintexts. For pimi=116 equal to each of the values belonging to GF(24),N plaintexts can be obtained with the other 4 bits (pili=116) being random. Due to the fact that the value belonging to GF(24) ranges from (0000)2 to (1111)2, 16N plaintexts should be obtained.Algorithm 3: ChoosePlaintexts.
Input: the total number of plaintexts 16N Output: 16N plaintexts:   Pn(1≤n≤16N) (1) for  j=0:15 (2)for  h=1:N (3)P(16j+h)=pi∣pim=j,pil=random(16)i=116 (random(n) is to generate an integer ranging from 0 to n-1) (4)end for (5)end for (6) return  Pn(1≤n≤16N)


### 3.3. Acquire Traces and Preprocess Traces

We can obtain 16N power traces of the first round operation corresponding to 16N plaintexts. The obtained power traces can be divided into 16 sets according to the values of pimi=116. For the values of pimi=116 are the same all the time ranging from 0 to 15 referred to Section 3.2 and each value corresponds toN random value for pili=116, the number of the sets is 16 and each set containsN power traces.This can be easily expanded to the attack for the four least significant bits withpili=116 ranging from 0 to 15 and pimi=116 being random.As for preprocessing the power traces, the detailed procedures are stated in Algorithm4. For each of the trace sets, we can average all N power traces in this set to a single averaged trace. Each of the averaged power traces is composed of 16 subtraces corresponding to 16 sequential S-boxes operations and can be cut into 16 subtraces. Thus, we can obtain 16 averaged power traces containing 16 subtraces.Algorithm 4: PreprocessTraces.
Input:16 sets of power traces:Tm_jn∣n=1,2,3,⋯,Nj=015 Output: 16 averaged traces:T-m_jj=015=t-im_j∣i=1,2,3,⋯,16j=015 (1) for  j=0:15 (2)T-m_j=1/N∑n=1NTm_j(n) (3)Cut  T-m_j  into 16 sub-traces:  T-m_j=t-im_j∣i=1,2,3,⋯,16 (4) end for (5) return  T-m_jj=015=t-im_j∣i=1,2,3,⋯,16j=015


### 3.4. Double Distance Voting Detection

Double distance voting detection is the core of our attack technique ensuring the high success rate and stability. As is seen in Algorithm5, DDVD is composed of enhanced Euclidean Distance detection and voting detection. For a better understanding of our DDVD technique, a diagrammatic sketch is shown in Figure 3. Taking S-boxes i1 and i2 as an example, there shall be 16 subtraces t-i1m_j1j1=015 and t-i2m_j2j2=015 for S-boxes i1 and i2, respectively, after the former operation. Each single trace t-i1m_j1 of t-i1m_j1j1=015 should operate the enhanced Euclidean Distance detection with the trace set t-i1m_j1j1=015 with 16 traces, which is seen as a decision making unit.Algorithm 5:Double distance voting detection.
Input:2 sets of sub-traces:t-i1mj1j1=015,t-i2mj2j2=015 Output:the 4 most significant bits of  Δki1,i2:  Δki1,i2m Enhanced Euclidean Distance Detection: (1) for  (0≤j1≤15) (2)for  (0≤j2≤15) (3)Distancej1⊕j2=∑l=1L(t-i1,lmj1-t-i2,lmj2)2 (4)end for (5)Δj1=arg⁡minj1⊕j2⁡Distance(j1⊕j2) (6) end for Voting Detection: (7)numn=0(0≤n≤15) (8) for  (0≤j≤15) (9)for  (0≤n≤15) (10)if  (Δj=n) (11)numn=numn+1 (12)else (13)numn=numn (14)end if (15)end for (16) end for (17) Δki1,i2m=arg⁡maxn⁡numn (18) return  Δki1,i2mFigure 3
Flow of double distance voting detection.For example, we compute the Euclidean distance betweent-i1m_6 and each trace oft-i2m_j2j2=015, and if the minimum distance is between t-i1m_6 and t-i2m_j2, this decision making unit generates one of the possible values for Δki1,i2m, namely, Δ6=(0110)2⊕j2. This must be done for all 16 single traces of t-i1m_j1j1=015; therefore there shall be 16 decision making units generating 16 possible values Δj1j1=015 for the candidates of Δki1,i2m. During voting detection stage, the value that occurs the maximum times among Δj1j1=015 will be voted as the final value of Δki1,i2m.


## 3.1. The Idea in a Nutshell

For a better understanding, we describe the main flow of our attack strategy in Algorithm2. As our description is based on 4-bit model, all the following statements can be applied to our multiple-bits models. For example, some parameters of 4-bit model are 15 or 16, which can be interpreted as 24-1 or 24, and thus for other n-bits model, the parameters should be 2n-1 or 2n.Algorithm 2:Multiple-bits side-channel collision attack.
(1) Pn∣n=1,2,3,⋯,16N←ChoosePlaintexts() (2) Tm_jn∣n=1,2,3,⋯,Nj=015←AcquireTrace(P(n)n=116N) (3) t-im_j∣1≤i≤16j=015←PreProTrace(Tm_jn∣0≤n≤Nj=015) (4)  for each (i1,i2∣1≤i1<i2≤16) (5)Δki1,i2←DDVD(t-i1m_jj=015,t-i2m_jj=015) (6)  end for (7) Recoverkey(Δi1,i2(1≤i1<i2≤16))Like most of other attack strategies, our method also first gets some traces and proceeds with some preprocessing, seen from Steps1, 2, and 3. Double distance voting detection is the core of our method combining enhanced Euclidean Distance detection and voting detection, which ensures our success rate. Finally, based on the main idea in Section2.2, when we find all possible relations among 16 key bytes, the brute force way is able to find the right key value quickly, for we only need to enumerate 256 key values. Some details will be presented in the following sections.


## 3.2. Choose Plaintexts

According to our attack strategy, we assume that the attacker is able to choose the plaintext. The 4-bit side-channel collision attack model aims to detect the collision of 4 bits between 2 different S-boxes, and in this situation other 4 bits are the noise for the detection. It is important for improving the efficiency of our method to determine how to choose the value ofpimi=116. Algorithm 3 presents the strategy of plaintexts choice, which can generate 16N plaintexts. For pimi=116 equal to each of the values belonging to GF(24),N plaintexts can be obtained with the other 4 bits (pili=116) being random. Due to the fact that the value belonging to GF(24) ranges from (0000)2 to (1111)2, 16N plaintexts should be obtained.Algorithm 3: ChoosePlaintexts.
Input: the total number of plaintexts 16N Output: 16N plaintexts:   Pn(1≤n≤16N) (1) for  j=0:15 (2)for  h=1:N (3)P(16j+h)=pi∣pim=j,pil=random(16)i=116 (random(n) is to generate an integer ranging from 0 to n-1) (4)end for (5)end for (6) return  Pn(1≤n≤16N)


## 3.3. Acquire Traces and Preprocess Traces

We can obtain 16N power traces of the first round operation corresponding to 16N plaintexts. The obtained power traces can be divided into 16 sets according to the values of pimi=116. For the values of pimi=116 are the same all the time ranging from 0 to 15 referred to Section 3.2 and each value corresponds toN random value for pili=116, the number of the sets is 16 and each set containsN power traces.This can be easily expanded to the attack for the four least significant bits withpili=116 ranging from 0 to 15 and pimi=116 being random.As for preprocessing the power traces, the detailed procedures are stated in Algorithm4. For each of the trace sets, we can average all N power traces in this set to a single averaged trace. Each of the averaged power traces is composed of 16 subtraces corresponding to 16 sequential S-boxes operations and can be cut into 16 subtraces. Thus, we can obtain 16 averaged power traces containing 16 subtraces.Algorithm 4: PreprocessTraces.
Input:16 sets of power traces:Tm_jn∣n=1,2,3,⋯,Nj=015 Output: 16 averaged traces:T-m_jj=015=t-im_j∣i=1,2,3,⋯,16j=015 (1) for  j=0:15 (2)T-m_j=1/N∑n=1NTm_j(n) (3)Cut  T-m_j  into 16 sub-traces:  T-m_j=t-im_j∣i=1,2,3,⋯,16 (4) end for (5) return  T-m_jj=015=t-im_j∣i=1,2,3,⋯,16j=015


## 3.4. Double Distance Voting Detection

Double distance voting detection is the core of our attack technique ensuring the high success rate and stability. As is seen in Algorithm5, DDVD is composed of enhanced Euclidean Distance detection and voting detection. For a better understanding of our DDVD technique, a diagrammatic sketch is shown in Figure 3. Taking S-boxes i1 and i2 as an example, there shall be 16 subtraces t-i1m_j1j1=015 and t-i2m_j2j2=015 for S-boxes i1 and i2, respectively, after the former operation. Each single trace t-i1m_j1 of t-i1m_j1j1=015 should operate the enhanced Euclidean Distance detection with the trace set t-i1m_j1j1=015 with 16 traces, which is seen as a decision making unit.Algorithm 5:Double distance voting detection.
Input:2 sets of sub-traces:t-i1mj1j1=015,t-i2mj2j2=015 Output:the 4 most significant bits of  Δki1,i2:  Δki1,i2m Enhanced Euclidean Distance Detection: (1) for  (0≤j1≤15) (2)for  (0≤j2≤15) (3)Distancej1⊕j2=∑l=1L(t-i1,lmj1-t-i2,lmj2)2 (4)end for (5)Δj1=arg⁡minj1⊕j2⁡Distance(j1⊕j2) (6) end for Voting Detection: (7)numn=0(0≤n≤15) (8) for  (0≤j≤15) (9)for  (0≤n≤15) (10)if  (Δj=n) (11)numn=numn+1 (12)else (13)numn=numn (14)end if (15)end for (16) end for (17) Δki1,i2m=arg⁡maxn⁡numn (18) return  Δki1,i2mFigure 3
Flow of double distance voting detection.For example, we compute the Euclidean distance betweent-i1m_6 and each trace oft-i2m_j2j2=015, and if the minimum distance is between t-i1m_6 and t-i2m_j2, this decision making unit generates one of the possible values for Δki1,i2m, namely, Δ6=(0110)2⊕j2. This must be done for all 16 single traces of t-i1m_j1j1=015; therefore there shall be 16 decision making units generating 16 possible values Δj1j1=015 for the candidates of Δki1,i2m. During voting detection stage, the value that occurs the maximum times among Δj1j1=015 will be voted as the final value of Δki1,i2m.


## 4. Improved Framework

In this section, we propose an improved framework of multiple-bits side-channel collision attack, where we modify our double distance voting detection and insert the error-tolerant and check mechanism. As is shown in Figure4, in this new framework, the modified double distance detection works with the error-tolerant and check mechanism, which leads to a remarkable promotion in the success rate as well as the attack efficiency.Figure 4
Improved framework with error-tolerant mechanism.We still take the 4-bit model as an example to describe the improved attack framework of our method. The procedure is shown in Algorithm6. Like Section 3, we only care about the four most significant bits, with the four least significant bits being almost the same. Algorithms ofChoosePlaintexts,AcquireTrace, andPreprocessTrace are all the same. In the rest of this section, we only explain the modified double distance voting detection and the fresh error-tolerant and check mechanism.Algorithm 6:Improved framework.
(1)P(n)n=1,2,3,⋯,16N←ChoosePlaintexts() (2)Tmjn∣n=0,1,2,3,⋯,Nj=015←AcquireTrace({P(n)}n=116N) (3)t-imj∣1≤i≤16j=015←PreProcessTrace(Tmjn∣0≤n≤Nj=015) (4) foreach (i1,i2∣1≤i1<i2≤16) (5)Δki1,i2m[1:3]←DDVD(t-i1mjj=015,t-i2mjj=015) (6) end for (7)Δkm1:15,pass}←Error_tolerant(Δki1,i2m1:3∣1≤i1<i2≤16) (8)if  (pass=1) (9)Recoverkey (Δkm1:15) (10) else (11)Back to (1) (12) end if


### 4.1. Modified Double Distance Voting Detection

The modified detection method is shown in Algorithm7. Just like the original one, the input of the DDVD is still 2 sets of subtraces corresponding to 2 different S-boxes, but the output changes from a single value to a 1×3 matrix including 3 candidate values of Δki1,i2m. Euclidean Distance between each subtrace of a certain S-box and a set of subtraces of another S-box also should be calculated first. Then, instead of choosing n with the maximum number as the result, we prefer three values whose number is in the top three Δki1,i2m where i1 and i2 range from 1 to 15.Algorithm 7:Double distance voting detection (modified).
Input: 2 sets of sub-traces:t-i1m_j1j1=015,t-i2m_j2j2=015 Output: the 4 most significant bits of Δki1,i2m:Δki1,i2m(1×3matrix) Enhanced Euclidean Distance Detection: (1) for  (0≤j1≤15) (2)for  (0≤j2≤15) (3)Distancej1⊕j2=∑l=1L(t-i1,lm_j1-t-i2,lm_j2)2 (4)end for (5)Δj1=arg⁡minj1⊕j2⁡Distance(j1⊕j2) (6) end for Improved Voting Detection: (7) numn=0(0≤n≤15) (8) for  (0≤j≤15) (9)for  (0≤n≤15) (10)if  (Δj=n) (11)numn=numn+1 (12)else (13)numn=numn (14)end if (15)end for (16) end for (17) Δki1,i2m[1]=arg⁡maxn⁡numn (18) Δki1,i2m[2]=arg⁡maxn⁡numn(n≠Δki1,i2m[1]) (19) Δki1,i2m3=arg⁡maxn⁡numn(n≠Δki1,i2m1,Δki1,i2m[2]) (20) return  Δki1,i2m


### 4.2. Error-Tolerant and Check Mechanism

Error-tolerant and check mechanism is presented in Algorithm8. Three candidate values ensure the error-tolerant mechanism. The main thought of the error detection and tolerance is based on (6), which provides a way to find errors occurring in collision detections.Algorithm 8:Error-tolerant.
Input: 3 candidates for each Δki1,i2m:Δki1,i2m1:3∣1≤i1<i2≤16 Output:  Δkm1:15,pass (1) for  (1≤i1≤14) (2)i2=i1+1 (3)for  (1≤t≤3) (4)if (existing  x∈Δki2,hm1:3andy∈Δki1,hm[1:3](i2<h≤16) satisfying  Δki1,i2m[t]=x⊕y) (5)Δkm[i1]=Δki1,i2m[t]          pass=1 (6)else (7)pass=0       exiting all loops (8)end if (9)end for (10)end forIn order to recover the key value correctly, 15 delta values (Δk1,2,Δk2,3,…,Δk15,16) should be right. Thus, for each candidate of Δkn,n+1, any exiting relations in (7) should be checked. If there exists a candidate of Δkn,n+1 that can pass the check, it will be the final result of Δkn,n+1; otherwise this attack is considered to have failed and should start from the beginning again.


## 4.1. Modified Double Distance Voting Detection

The modified detection method is shown in Algorithm7. Just like the original one, the input of the DDVD is still 2 sets of subtraces corresponding to 2 different S-boxes, but the output changes from a single value to a 1×3 matrix including 3 candidate values of Δki1,i2m. Euclidean Distance between each subtrace of a certain S-box and a set of subtraces of another S-box also should be calculated first. Then, instead of choosing n with the maximum number as the result, we prefer three values whose number is in the top three Δki1,i2m where i1 and i2 range from 1 to 15.Algorithm 7:Double distance voting detection (modified).
Input: 2 sets of sub-traces:t-i1m_j1j1=015,t-i2m_j2j2=015 Output: the 4 most significant bits of Δki1,i2m:Δki1,i2m(1×3matrix) Enhanced Euclidean Distance Detection: (1) for  (0≤j1≤15) (2)for  (0≤j2≤15) (3)Distancej1⊕j2=∑l=1L(t-i1,lm_j1-t-i2,lm_j2)2 (4)end for (5)Δj1=arg⁡minj1⊕j2⁡Distance(j1⊕j2) (6) end for Improved Voting Detection: (7) numn=0(0≤n≤15) (8) for  (0≤j≤15) (9)for  (0≤n≤15) (10)if  (Δj=n) (11)numn=numn+1 (12)else (13)numn=numn (14)end if (15)end for (16) end for (17) Δki1,i2m[1]=arg⁡maxn⁡numn (18) Δki1,i2m[2]=arg⁡maxn⁡numn(n≠Δki1,i2m[1]) (19) Δki1,i2m3=arg⁡maxn⁡numn(n≠Δki1,i2m1,Δki1,i2m[2]) (20) return  Δki1,i2m


## 4.2. Error-Tolerant and Check Mechanism

Error-tolerant and check mechanism is presented in Algorithm8. Three candidate values ensure the error-tolerant mechanism. The main thought of the error detection and tolerance is based on (6), which provides a way to find errors occurring in collision detections.Algorithm 8:Error-tolerant.
Input: 3 candidates for each Δki1,i2m:Δki1,i2m1:3∣1≤i1<i2≤16 Output:  Δkm1:15,pass (1) for  (1≤i1≤14) (2)i2=i1+1 (3)for  (1≤t≤3) (4)if (existing  x∈Δki2,hm1:3andy∈Δki1,hm[1:3](i2<h≤16) satisfying  Δki1,i2m[t]=x⊕y) (5)Δkm[i1]=Δki1,i2m[t]          pass=1 (6)else (7)pass=0       exiting all loops (8)end if (9)end for (10)end forIn order to recover the key value correctly, 15 delta values (Δk1,2,Δk2,3,…,Δk15,16) should be right. Thus, for each candidate of Δkn,n+1, any exiting relations in (7) should be checked. If there exists a candidate of Δkn,n+1 that can pass the check, it will be the final result of Δkn,n+1; otherwise this attack is considered to have failed and should start from the beginning again.


## 5. Model Analysis and Experiments Results

### 5.1. Comparison of Detection Success Rate under Noise

Collision detection technique has played an important role in side-channel collision attack. In this section, we compare double distance voting detection (DDVD) proposed in this paper with other two widely used detection techniques, which are correlation-enhanced detection[15] and traditional Euclidean Distance detection with dimension reduction[17], respectively.The detailed procedure of correlation-enhanced detection is already proposed in Section2.4. In [17], Bogdanov presented a collision attack method based on Euclidean Distance combining DPA. However, according to the method, if collision detection generates incorrect results, DPA makes no sense for recovering the right key value. Therefore, the success rate of Euclidean Distance detection for that method is the key part.The power traces are obtained from an AES hardware design implemented on a SAKURA-G board. Each trace shall be averaged by four power traces with the same input. The noise of the traces usually comes from both electronic noise mainly containing power supply noise, clock generator noise, conducted emissions, and radiated emissions and algorithm noise which are the power assumption of other uncorrelated operations. For SAKURA-G is a dedicated board that may be far from being noisy, we can add the Gaussian noise of different intensity into the averaged traces to model the noise, which can be used for an initial analysis of efficiency of different detection techniques [14]. SNR (signal-to-noise ratio) is used for indicating the intensity of the noise, which is defined as follows:(8)SNR=10log10⁡PsignalPnoiseThe comparison result is shown in Figure5. Detection technique proposed in this paper is marked with DDVD, and correlation-enhanced method in [15] and Euclidean Distance in [17] are denoted as CE and ED, respectively. The value of SNR ranges from 0 dB to 30 dB. Each technique is done for 1000 times to calculate the success rate. As is shown in Figure 5, our detection technique performs better under the noise.Figure 5
Comparison of detection success rate.


### 5.2. How Many Bits Are Best for Multiple-Bits Model

In this paper, we propose a multiple-bits collision attack model, and all the statements are based on the 4-bit model, which can be expanded to other n-bits (n ranging from 1 to 8) models. However, one question we should figure out is how many bits are best for the multiple-bits model of our attack method.What matters in our attack strategy is the necessary number of power traces to reach a given success rate, which reflects the attack efficiency. Therefore, we will analyze the necessary number of power traces for different model both in theory and in experiment.In Section5.1, the performance of our detection method in noise environment is presented; thus, for a simple analysis in this section, we assume that the noise for an n-bits model only comes from the operation of other8-n bits and all 2n decision making units in Figure 3 are independent. So, for the n-bits model, when preparing the power traces (Sections 3.2 and 3.3), we needh power traces of each byte to obtain the averaged traces. When we compute the Euclidean Distance between two single averaged traces whose n-bits can cause the collision (e.g., pi1[n-1:0]⊕pi2[n-1:0]=Δki1i2[n-1:0]), the probability that these two averaged traces have the least Euclidean Distance is(9)Pr=1-C28-nh×C28-n-hhC28-nh×C28-nhwhere letterC is denoted as combinatorial number,n equals the number of bits in the model, andh equals the number of traces for calculating the average. Due to the fact that 8n-bits of one byte are random, there are a total of C28-nh×C28-nh kinds of choices to determine these two averaged power traces. Since there shall be only one corresponding plaintext of one byte which can cause a collision with each plaintext of another byte, there are a total of C28-nh×C28-n-hh kinds of choices that include no collision plaintext pair.The probability of successful detection for the method proposed in Section3 and the improved method presented in Section 4 is calculated separately as follows: (10)Pr_det=1-∑i=2n-12nC2ni×1-Pri×Pr2n-i(11)Pr⁡_impro=1-∑i=2n-2n-22nC2ni×1-Pri×Pr2n-iwherePr is equal to (9) andn is the number of bits in the model. From the illustration of Figure 3, there are 2n decision making units for the n-bits model. According to the rules of voting detection that the value that occurs the maximum times is chosen as the final result, if more than half of the decision making units generate the wrong answer, the voting detection shall fail. Result of all 2n decision making units can be seen as the binomial distribution, so the probability that more than half of the units generate wrong result is ∑i=2n-12nC2ni×1-Pri×Pr2n-i. Analysis for the improved method in Section 4 is similar, and if more than three-quarters of the decision making units generate the wrong answer, the voting detection shall fail.As for the necessary number of the power traces, it can be calculated as follows:(12)Trace_Number=2n×h×8nwhere n stands for the minimum integer that is larger thann. According to our attack strategy, for eachn-bits model, we should get 2n averaged power traces and each trace is averaged byh original power traces. Obviously, the method should be operated for 8/n times.According to (9), (10), (11), and (12), we estimate the necessary number of the power traces to reach a 90% success rate for the basic attack method in Section 3 and an improved version in Section 4, shown in Tables 1 and 2, respectively. The 1-bit model only has two possible results, so improved method makes no sense for it. It is obvious that, in theory, 4-bit model collision attack needs the least number of traces with high efficiency, which will be verified later in experiments.Table 1
The necessary number of original attacks to reach 90% success rate.
n-bits 1 2 3 4 5 6 7 8 Number 288 160 168 128 192 256 512 256Table 2
The necessary number of improved attacks to reach 90% success rate.
n-bits 1 2 3 4 5 6 7 8 Number No 128 120 96 140 256 256 256Furthermore, the practical experiments have been carried out to find how many bits are best for the proposed multiple-bits model. Figure6 shows the necessary number of power traces to reach a 90% success rate for the original approach presented in Section 3 (denoted as MBDD), while Figure 7 shows the he necessary number of power traces for the improved version proposed in Section 4 (denoted as MBDD-ET). As can be seen in Figures 6 and 7, it is verified that 4-bit model (in black) is the best choice when operating the proposed attack strategy.Figure 6
Necessary number of traces for MBDD to reach 90% success rate.Figure 7
Necessary number of traces for MBDD-ET to reach 90% success rate.


### 5.3. Experiments and Results

The attack method and the improved method with error-tolerant mechanism have been performed successfully in practice against a hardware design with an 8-bit data path of AES, where 16 S-boxes are sequentially operated in every round operation. The target AES is implemented on a Xilinx SPARTAN-6 FPGA of a SAKURA-G circuit board. An Agilent MSO-X 9104A oscilloscope is employed to collect original power traces. In our case, each power trace obtained contains about 32365 points.For a better understanding, operation onk1m and k2m corresponding to S-box 1 and S-box 2 is taken as an example to present the process of double distance voting detection. Without loss of generality, k1m and k2m are fixed as(13)k1m=11012,k2m=01102,Δk1,2m=10112.Two corresponding sets of subtraces are denoted as t-1m_j1j1=015 and t-2m_j2j2=015. Figure 4 shows square of difference between each subtrace t-1m_j1 of t-1m_j1j1=015 and the trace set t-2m_j1j1=015 with 16 traces. Figures 8(a)–8(p) are like 16 decision making units in Figure 3 corresponding to j1 ranging from 0 to 15. The accumulation of all points’ square of difference between two subtraces is the value of Euclidean Distance.Figure 8
Square of difference between each subtrace in sett-1mj1j1=015 and all subtraces in set t-2mj1j1=015.We take Figure8(a) as an example to describe its meaning. Figure 8(a) shows the result of (t-1,lm_0-t-2,lm_j2)2 for each point l ranging from 1 to 32365 and each value of j2 ranging from 0 to 15. The black curve represents the square of difference between each point of t-1,lm_0and t-2,lm_0⊕Δk1,2m, which are two traces corresponding to a collision in theory. However, square of differences between t-1,lm_0 and other traces in the trace set t-2m_j1j1=015 is marked by grey curves. If the black curve is lower than any other grey curves, the decision making unit will generate the right candidate. An initial and rough conclusion can be drawn that when in situations like Figure 8(a), whose black curve is close to zero, two traces corresponding to a collision may have the lowest distance, meaning that the corresponding decision making unit generates the right candidate, but in some exceptional situations such as Figure 8(p), whose black curve is higher than some grey curves, collision cannot be assured by minimum Euclidean Distance and the unit generates the wrong candidate. Therefore, voting detection works to determine the final value of Δk1,2m. As is shown in Figure 9, (1011)2 occurs the maximum times, and voting detection chooses it to be the final result.Figure 9
Result of the voting stage.


### 5.4. Comparison

In this section, we compare our improved attack version denoted as MBDD with correlation-enhanced collision attack [15], bitwise collision attack [19], and LDPC method with Euclidean Distance detection [16] denoted as CECA, BCA, and LDPC, respectively. Comparisons are done from three aspects, which are relation between success rate and necessary number of traces, relation between success rate and online time, and relation between offline time and online time. Each compared method was performed 1000 times for calculating an actual success rate.In this section,tave is used for indicating the total time that the oscilloscope spends on capturing and averaging one power trace in real time, and ts is for indicating the time that the oscilloscope spends on acquiring and saving one trace. Taking Agilent MSO-X 9104A oscilloscope that we use for acquiring power traces as an example, ts is about 50 times of tave. The number of power traces used to obtain one averaged power trace in oscilloscope is denoted asq, and the number of saved averaged power traces isn. Therefore, the online time denoted as tol can be written as (14)tol=nqtave+ts=n0.02q+1ts.And we fix q=6 for this experiment, so(15)tol=1.12nts.Figure10 presents the relations between success rate and number of traces. As can be seen from Figure 10, LDPC has a better performance. To get a high given success rate, LDPC needs less number of traces. However, in Figure 11, the success rate is as a function of the total online time rather than the number of original power traces. As is mentioned above, we can decrease the online time due to the fact that the time an oscilloscope spends on averaging one trace is much less than saving one trace. It is obvious in Figure 11 that the performance of MBDD with error-tolerant mechanism got a promotion under this setting. Due to the fact that the 4-bit model of MBDD can find all 120 relations among 16 key bytes with 32 averaged power traces, the fact that the oscilloscope spends less time on averaging traces does a favor for MBDD to have a higher success rate with the same online time. Meanwhile, it seems that LDPC method does not have a remarkable promotion as MBDD with the help of averaging traces. The reason may be that the collision detection method of LDPC will need more averaged traces to detect all collisions occurring among 16 key bytes, even if traces are far from being noisy. However, the results of Figures 10 and 11 can reflect that LDPC is more tolerant to noise because the performance of LDPC in a noisy setting is almost the same as that in a less noisy setting.Figure 10
Relations between success rate and number of traces.Figure 11
Relations between success rate and online time.Finally, we show the relation between offline time and online time for LDPC and MBDD. The offline time, which reflects the computational complexity, was estimated by MATLAB. As is shown in Figure12, LDPC is more costly in terms of computation time than MMBD. However, the increased time overhead is slight. For LDPC, the offline time decreases as the online time increases, which indicates that the number of iterations for LDPC decoding decreases. For MBDD, the offline time increases as the online time increases, and it quickly converges to a certain value.Figure 12
Relations between success rate and online time.From these comparisons, it can be confirmed that LDPC with soft decision decoding has less trace overhead but more computation time overhead than MBDD, which can be seen as a kind of hard decision decoding procedure. In addition, the necessary number of traces for our method is 90% less than CECA and 96% less than BCA.


## 5.1. Comparison of Detection Success Rate under Noise

Collision detection technique has played an important role in side-channel collision attack. In this section, we compare double distance voting detection (DDVD) proposed in this paper with other two widely used detection techniques, which are correlation-enhanced detection[15] and traditional Euclidean Distance detection with dimension reduction[17], respectively.The detailed procedure of correlation-enhanced detection is already proposed in Section2.4. In [17], Bogdanov presented a collision attack method based on Euclidean Distance combining DPA. However, according to the method, if collision detection generates incorrect results, DPA makes no sense for recovering the right key value. Therefore, the success rate of Euclidean Distance detection for that method is the key part.The power traces are obtained from an AES hardware design implemented on a SAKURA-G board. Each trace shall be averaged by four power traces with the same input. The noise of the traces usually comes from both electronic noise mainly containing power supply noise, clock generator noise, conducted emissions, and radiated emissions and algorithm noise which are the power assumption of other uncorrelated operations. For SAKURA-G is a dedicated board that may be far from being noisy, we can add the Gaussian noise of different intensity into the averaged traces to model the noise, which can be used for an initial analysis of efficiency of different detection techniques [14]. SNR (signal-to-noise ratio) is used for indicating the intensity of the noise, which is defined as follows:(8)SNR=10log10⁡PsignalPnoiseThe comparison result is shown in Figure5. Detection technique proposed in this paper is marked with DDVD, and correlation-enhanced method in [15] and Euclidean Distance in [17] are denoted as CE and ED, respectively. The value of SNR ranges from 0 dB to 30 dB. Each technique is done for 1000 times to calculate the success rate. As is shown in Figure 5, our detection technique performs better under the noise.Figure 5
Comparison of detection success rate.


## 5.2. How Many Bits Are Best for Multiple-Bits Model

In this paper, we propose a multiple-bits collision attack model, and all the statements are based on the 4-bit model, which can be expanded to other n-bits (n ranging from 1 to 8) models. However, one question we should figure out is how many bits are best for the multiple-bits model of our attack method.What matters in our attack strategy is the necessary number of power traces to reach a given success rate, which reflects the attack efficiency. Therefore, we will analyze the necessary number of power traces for different model both in theory and in experiment.In Section5.1, the performance of our detection method in noise environment is presented; thus, for a simple analysis in this section, we assume that the noise for an n-bits model only comes from the operation of other8-n bits and all 2n decision making units in Figure 3 are independent. So, for the n-bits model, when preparing the power traces (Sections 3.2 and 3.3), we needh power traces of each byte to obtain the averaged traces. When we compute the Euclidean Distance between two single averaged traces whose n-bits can cause the collision (e.g., pi1[n-1:0]⊕pi2[n-1:0]=Δki1i2[n-1:0]), the probability that these two averaged traces have the least Euclidean Distance is(9)Pr=1-C28-nh×C28-n-hhC28-nh×C28-nhwhere letterC is denoted as combinatorial number,n equals the number of bits in the model, andh equals the number of traces for calculating the average. Due to the fact that 8n-bits of one byte are random, there are a total of C28-nh×C28-nh kinds of choices to determine these two averaged power traces. Since there shall be only one corresponding plaintext of one byte which can cause a collision with each plaintext of another byte, there are a total of C28-nh×C28-n-hh kinds of choices that include no collision plaintext pair.The probability of successful detection for the method proposed in Section3 and the improved method presented in Section 4 is calculated separately as follows: (10)Pr_det=1-∑i=2n-12nC2ni×1-Pri×Pr2n-i(11)Pr⁡_impro=1-∑i=2n-2n-22nC2ni×1-Pri×Pr2n-iwherePr is equal to (9) andn is the number of bits in the model. From the illustration of Figure 3, there are 2n decision making units for the n-bits model. According to the rules of voting detection that the value that occurs the maximum times is chosen as the final result, if more than half of the decision making units generate the wrong answer, the voting detection shall fail. Result of all 2n decision making units can be seen as the binomial distribution, so the probability that more than half of the units generate wrong result is ∑i=2n-12nC2ni×1-Pri×Pr2n-i. Analysis for the improved method in Section 4 is similar, and if more than three-quarters of the decision making units generate the wrong answer, the voting detection shall fail.As for the necessary number of the power traces, it can be calculated as follows:(12)Trace_Number=2n×h×8nwhere n stands for the minimum integer that is larger thann. According to our attack strategy, for eachn-bits model, we should get 2n averaged power traces and each trace is averaged byh original power traces. Obviously, the method should be operated for 8/n times.According to (9), (10), (11), and (12), we estimate the necessary number of the power traces to reach a 90% success rate for the basic attack method in Section 3 and an improved version in Section 4, shown in Tables 1 and 2, respectively. The 1-bit model only has two possible results, so improved method makes no sense for it. It is obvious that, in theory, 4-bit model collision attack needs the least number of traces with high efficiency, which will be verified later in experiments.Table 1
The necessary number of original attacks to reach 90% success rate.
n-bits 1 2 3 4 5 6 7 8 Number 288 160 168 128 192 256 512 256Table 2
The necessary number of improved attacks to reach 90% success rate.
n-bits 1 2 3 4 5 6 7 8 Number No 128 120 96 140 256 256 256Furthermore, the practical experiments have been carried out to find how many bits are best for the proposed multiple-bits model. Figure6 shows the necessary number of power traces to reach a 90% success rate for the original approach presented in Section 3 (denoted as MBDD), while Figure 7 shows the he necessary number of power traces for the improved version proposed in Section 4 (denoted as MBDD-ET). As can be seen in Figures 6 and 7, it is verified that 4-bit model (in black) is the best choice when operating the proposed attack strategy.Figure 6
Necessary number of traces for MBDD to reach 90% success rate.Figure 7
Necessary number of traces for MBDD-ET to reach 90% success rate.


## 5.3. Experiments and Results

The attack method and the improved method with error-tolerant mechanism have been performed successfully in practice against a hardware design with an 8-bit data path of AES, where 16 S-boxes are sequentially operated in every round operation. The target AES is implemented on a Xilinx SPARTAN-6 FPGA of a SAKURA-G circuit board. An Agilent MSO-X 9104A oscilloscope is employed to collect original power traces. In our case, each power trace obtained contains about 32365 points.For a better understanding, operation onk1m and k2m corresponding to S-box 1 and S-box 2 is taken as an example to present the process of double distance voting detection. Without loss of generality, k1m and k2m are fixed as(13)k1m=11012,k2m=01102,Δk1,2m=10112.Two corresponding sets of subtraces are denoted as t-1m_j1j1=015 and t-2m_j2j2=015. Figure 4 shows square of difference between each subtrace t-1m_j1 of t-1m_j1j1=015 and the trace set t-2m_j1j1=015 with 16 traces. Figures 8(a)–8(p) are like 16 decision making units in Figure 3 corresponding to j1 ranging from 0 to 15. The accumulation of all points’ square of difference between two subtraces is the value of Euclidean Distance.Figure 8
Square of difference between each subtrace in sett-1mj1j1=015 and all subtraces in set t-2mj1j1=015.We take Figure8(a) as an example to describe its meaning. Figure 8(a) shows the result of (t-1,lm_0-t-2,lm_j2)2 for each point l ranging from 1 to 32365 and each value of j2 ranging from 0 to 15. The black curve represents the square of difference between each point of t-1,lm_0and t-2,lm_0⊕Δk1,2m, which are two traces corresponding to a collision in theory. However, square of differences between t-1,lm_0 and other traces in the trace set t-2m_j1j1=015 is marked by grey curves. If the black curve is lower than any other grey curves, the decision making unit will generate the right candidate. An initial and rough conclusion can be drawn that when in situations like Figure 8(a), whose black curve is close to zero, two traces corresponding to a collision may have the lowest distance, meaning that the corresponding decision making unit generates the right candidate, but in some exceptional situations such as Figure 8(p), whose black curve is higher than some grey curves, collision cannot be assured by minimum Euclidean Distance and the unit generates the wrong candidate. Therefore, voting detection works to determine the final value of Δk1,2m. As is shown in Figure 9, (1011)2 occurs the maximum times, and voting detection chooses it to be the final result.Figure 9
Result of the voting stage.


## 5.4. Comparison

In this section, we compare our improved attack version denoted as MBDD with correlation-enhanced collision attack [15], bitwise collision attack [19], and LDPC method with Euclidean Distance detection [16] denoted as CECA, BCA, and LDPC, respectively. Comparisons are done from three aspects, which are relation between success rate and necessary number of traces, relation between success rate and online time, and relation between offline time and online time. Each compared method was performed 1000 times for calculating an actual success rate.In this section,tave is used for indicating the total time that the oscilloscope spends on capturing and averaging one power trace in real time, and ts is for indicating the time that the oscilloscope spends on acquiring and saving one trace. Taking Agilent MSO-X 9104A oscilloscope that we use for acquiring power traces as an example, ts is about 50 times of tave. The number of power traces used to obtain one averaged power trace in oscilloscope is denoted asq, and the number of saved averaged power traces isn. Therefore, the online time denoted as tol can be written as (14)tol=nqtave+ts=n0.02q+1ts.And we fix q=6 for this experiment, so(15)tol=1.12nts.Figure10 presents the relations between success rate and number of traces. As can be seen from Figure 10, LDPC has a better performance. To get a high given success rate, LDPC needs less number of traces. However, in Figure 11, the success rate is as a function of the total online time rather than the number of original power traces. As is mentioned above, we can decrease the online time due to the fact that the time an oscilloscope spends on averaging one trace is much less than saving one trace. It is obvious in Figure 11 that the performance of MBDD with error-tolerant mechanism got a promotion under this setting. Due to the fact that the 4-bit model of MBDD can find all 120 relations among 16 key bytes with 32 averaged power traces, the fact that the oscilloscope spends less time on averaging traces does a favor for MBDD to have a higher success rate with the same online time. Meanwhile, it seems that LDPC method does not have a remarkable promotion as MBDD with the help of averaging traces. The reason may be that the collision detection method of LDPC will need more averaged traces to detect all collisions occurring among 16 key bytes, even if traces are far from being noisy. However, the results of Figures 10 and 11 can reflect that LDPC is more tolerant to noise because the performance of LDPC in a noisy setting is almost the same as that in a less noisy setting.Figure 10
Relations between success rate and number of traces.Figure 11
Relations between success rate and online time.Finally, we show the relation between offline time and online time for LDPC and MBDD. The offline time, which reflects the computational complexity, was estimated by MATLAB. As is shown in Figure12, LDPC is more costly in terms of computation time than MMBD. However, the increased time overhead is slight. For LDPC, the offline time decreases as the online time increases, which indicates that the number of iterations for LDPC decoding decreases. For MBDD, the offline time increases as the online time increases, and it quickly converges to a certain value.Figure 12
Relations between success rate and online time.From these comparisons, it can be confirmed that LDPC with soft decision decoding has less trace overhead but more computation time overhead than MBDD, which can be seen as a kind of hard decision decoding procedure. In addition, the necessary number of traces for our method is 90% less than CECA and 96% less than BCA.


## 6. Conclusion

In this paper, we proposed a basic multiple-bits side-channel collision attack framework based on double distance voting detection. Then an improved version with modified double detection as well as error-tolerant and mechanism is presented. The 4-bit model is proven to be the optimal choice for the novel attack strategy in both theory and practice. Practical attack experiments are performed successfully on a hardware implementation of AES on SAKURA-G circuit board with Xilinx SPARTAN-6. Results show that our detection method performs steadily in noisy environment. We compare our methods with other attacking methods; our method needs less computation time but more traces than LDPC method, and to reach 90% success rate, the necessary number of traces for our method is 90% less than CECA and 96% less than BCA. The novel framework proposed in this paper can be utilized in other cryptographic symmetric algorithms.



---

*Source: 2483619-2018-06-05.xml*