# Key Bit-Dependent Side-Channel Attacks on Protected Binary Scalar Multiplication +
## 4 Methods  
### Key Bit-Dependent Attack Framework  
In this paper, we consider binary scalar multiplication algorithms that are resistant against SPA and DPA. In particular, we targeted algorithms based on regular algorithms protected by intermediate data randomization. Therefore, we suppose that an attacker is obliged to use a single trace rather than numerous traces. In addition, we assumed that the attacker could distinguish the iterative structure in the traces of regular algorithms. We categorized the attack framework in four steps as follows. Note that we did not consider side-channel atomicity algorithms that are SPA-resistant since it is impossible to distinguish the starting point of iterative loop operations.  
* Preprocessing The attacker can divide trace \(T\) into \(\lambda\) subtraces, \(O_{i}\), corresponding to each iteration (\(0\leq i\leq\lambda-1\)). As shown in Figure 6, trace \(T\) is described as a series of \(\lambda\) sub-races as \[T=\{O_{\lambda-1}\ ||O_{\lambda-2}\ ||\cdots||O_{0}\}\] since \(\lambda\) iterative operations are performed when the secret scalar is \(\lambda\)-bit, we divide trace \(T\) into \(\lambda\) subtraces and align them.
* Select Points of Interest (PoS) If the attacker can use the same device as the target and acquire a trace with a known key, it is easy to find PoIs. The attacker can calculate the sum of squared pairwise t-differences (SOST) [26] of the subtraces classified based on the properties described in Sections 3.1.1 and 3.1.2. Then, the PoIs are the points that have high SOST values. SOST is calculated as follows: \[SOST=\left(\frac{\frac{m_{G_{1}}-m_{G_{2}}}{\sqrt{\frac{c_{G_{1}}^{2}}{c_{G_{1} }}+\frac{c_{G_{2}}^{2}}{c_{G_{2}}}}}}{\frac{m_{G_{1}}}{m_{G_{2}}}+\frac{c_{G_ {2}}}{m_{G_{2}}}}\right)^{2}\] (1) where \(m\) denotes the mean, \(\sigma\) is standard deviation, and \(n\) is the number of elements. If it is not possible to use the same device, the attacker must know how the target algorithm is implemented to find PoIs. Moreover, the key bit identification phase section should be recognized in the trace. In general, since the \(d_{i}\) value must be decided in advance before each loop operation, the target phase is positioned near the beginning of each subtrace \(O_{i}\). We represent \(p_{i}\) as PoIs of each subtrace \(O_{i}\) (\(0\leq i\leq\lambda-1\)).
* Classify into Two Groups and Extract Secret Scalar Bits The attacker can separate \(p_{i}\) into two groups, \(G_{0}\) and \(G_{1}\), applying SPA-VI or a clustering algorithm (e.g., k-means, fuzzy k-means, or EM algorithm [27; 28]). Because the most significant bit is always 1, the attacker can configure \(d_{\lambda-1}\) as 1 and find the respective scalar bit \(d_{i}\) based on the power model and properties described in Sections 3.1.1 and 3.1.2. For instance, when power consumption complies with the HD model, the attacker can recover secret scalar bits \(d_{i}\) as follows. It is possible to assume that the group that contains \(p_{\lambda-1}\) indicates that leakage is nonzero, if \(d_{i}\) is at first initialized as zero. Consequently, if \(p_{i}\) is contained in the same group that contains \(p_{\lambda-1}\), \(d_{i}\) is one; otherwise, \(d_{i}\) is zero (\(0\leq i<\lambda-1\)). Similarly, when power consumption complies with the HW model, the group that includes \(p_{\lambda-1}\) indicates that leakage is non-zero, and the other group indicate that leakage is zero. Consequently, if \(p_{i}\) is contained in the same group that contains \(p_{\lambda-1}\), then \(d_{i}\) is one; otherwise, \(d_{i}\) is zero (\(0\leq i<\lambda-1\)).