# Single Trace Analysis against HyMES by Exploitation of Joint Distributions of Leakages
## 2 Related Works
### Code-Based Cryptography
#### 2.2.1 McEliece Cryptosystem
Finally, steps 13-18 are the processes for obtaining the similarity between the estimated distribution and the theoretical distribution. The guessed key is the one with the highest similarity to the real key. In order to construct the estimated joint distribution table, the Hamming weight values of the plaintext \(a\) and the output \(b\) are estimated from the collected power consumption traces. Although the Hamming weight values should be accurately estimated for the performance of the attack, it is very difficult to accurately guess the Hamming weight values due to the noise signal. In 2017, an improved method was proposed that use a maximum likelihood method that reflects the influence of noise as a probability [18]. An attack using the joint distributions of leakages is possible because the joint distribution depends on the key value, which occurs because the AES S-box is sufficiently non-linear. The attack using the joint distribution has only been investigated in symmetric key cryptography. ## 3 Single Trace Analysis Against Hymes

In this section, we propose for the first time a side-channel attack on HyMES exploiting the joint distributions of the leakages. First, we present an outline of the proposed attack. Then, we describe the two steps used to recover the secret key \((g(z),L_{sec})\). ### Outline of the Proposed Attack

Our attack targets the leakage obtained during the computation of \(H\hat{P}\). Note that \(H\hat{P}\) is required for syndrome operation \(S_{\mathcal{E}}=(H\hat{P})c^{T}\) in step 1 of Algorithm 5. The implementation of HyMES proposed in Reference [6] includes the process of calculating the column vectors \(h_{i}\) of \(H\hat{P}\) in the key generation algorithm. The implementation precomputes the values \(h_{i},\ i=0,...,n-1\) and stores the result as a secret key. Since these values are required to compute the syndrome, they can also be directly calculated in the decryption process if they are not precomputed. Therefore, without loss of generality, we may assume that the \(h_{i}\) is calculated in the same way as described in Algorithm 7. Algorithm 7 computes the \(H\hat{P}\) using the secret key \(L_{sec}\) which is substituted with the permutation matrix \(\hat{P}\). The \(h_{i}\) with length \(mt\)-bit can be expressed as a polynomial of degree \(t-1\) degree polynomial over \(GF[2^{m}]\), as shown in Equation (5). \[h_{i}=h_{i}[t-1]z^{t-1}+h_{i}[t-2]z^{t-2}+...+h_{i}[0]. \tag{5}\]
```
0:\(g(z)=z^{t}+g_{t-1}z^{t-1}+...+g_{O},\ L_{sec}=\{\alpha_{0},...,\alpha_{n-1}\},\ n=2^{m}\)
0: the column vectors \(h_{i},\ i=0,...,n-1\) of \(H\hat{P}\)
1:for\(i=0:n-1\)
2:\(h_{i}[t-1]\gets 1\)
3:for\(j=t-2:0\)
4:\(h_{i}[j]\gets g_{j+1}\oplus(\alpha_{i}\times h_{i}[j+1])\)
5:end
6:\(a\gets g_{0}\oplus(\alpha_{i}\times h_{i}[0])\)
7:for\(j=0:t-1\)
8:\(h_{i}[j]\gets h_{i}[j]/a\)
9:end
10:end
11:return\(h_{i},\ i=0,...,n-1\)
```
**Algorithm 7** HyMES Implementation : Computation of \(H\hat{P}\)[6]

To recover the secret key \((g(z),L_{sec})\), the proposed attack is divided into two stages. The first stage of the attack identifies the Goppa polynomial \(g(z)\) based on the joint distributions of leakages. The second stage finds the remaining secret key \(L_{sec}\) through the horizontal correlation analysis by using \(g(z)\) obtained in the first stage. In Sections 3.2 and 3.3, we explain how to determine \(g(z)\) and \(L_{sec}\), respectively. ### Recovering \(g(z)\)

The multiplication and division involved in Algorithm 7 are computed over the field \(GF(2^{m})\). In general, the multiplication and division on \(GF(2^{m})\) are implemented using the exponentiation-table and the log-table for the purpose of speed efficiency. For the root \(\alpha\) of the primitive polynomial \(p(x)\) that constitutes \(GF(2^{m})\), the exponentiation-table takes the positive integer \(i\) as input and returns \(\alpha^{i}\). The log-table is constructed to return \(i\) by taking the element \(\alpha^{i}\) of \(GF(2^{m})\) as an input.