# Single Trace Analysis against HyMES by Exploitation of Joint Distributions of Leakages
## 2 Related Works
### Code-Based Cryptography
#### 2.2.1 McEliece Cryptosystem
\(HW(e)\leq t\)
3: Return \(c=m\times G_{sys}+e\)
```
**Algorithm 4** HyMES : Encryption
```
0:\(c\), \(K_{sec}=(g(z),L_{sec})\)
0: Message \(M\)
1: Compute the syndrome \(S_{c}=(H\hat{P})c^{T}\)
2: Obtain a \(k\)-bit \(\hat{m}=m\times S\times G\times P=mG_{sys}=m(I_{k}\mid Q)=(m\mid mQ)\) from \(S_{c}\) using decoding algorithm \(D_{Goppa}(c)\)
3: Obtain \(m\) from the top \(k\)-bit of \(\hat{m}\). 4: Represent the \(m\) as a message \(M\)
5: return \(M\)
```
**Algorithm 5** HyMES : Decryption

In step 3 of Algorithm 4, it is not necessary to multiply the identity matrix \(I_{k}\) for matrix multiplication with \(m\) and \(G_{sys}\), so the encryption speed of HyMES is faster than that of the Classical McEliece. ### Side-Channel Analysis by Exploiting Joint Distributions of Leakages

The side-channel analysis is an attack which exploits any weakness that occurs during the execution of a cryptographic algorithm. The first side-channel analysis using power consumptionwas proposed by [PERSON] et al. in Reference [11]. Later, [PERSON] proposed the template attack in Reference [16], and then [PERSON] proposed a collision attack in Reference [17]. Since then, various side-channel attacks have proposed for various algorithms. Regarding code-based cryptography, [PERSON] et al. proposed SPA on the decoding process of the Classical McEliece in 2010 [9]. The proposed method used the leakage obtained when multiplying a matrix \(P^{-1}\) before calculating the syndrome during decryption. However, since HyMES does not multiply \(P^{-1}\) before calculating the syndrome in the decryption process, the method proposed in [9] cannot be used. Therefore, we analyzed HyMES by exploiting the joint distributions of leakages. In this section, we describe in detail the analysis exploiting the joint distributions of leakages. In 2014, [PERSON] proposed a method of determining the secret key of AES by using the joint distributions [13]. They exploited the joint distributions of the input and output of the S-box, which is a nonlinear function of AES. Since this distribution depends on the key value, an attacker can identify the secret key under the assumption that the value of the plaintext pair is unknown. The attack procedure proposed by [PERSON] is described in Algorithm 6. The function \(g\) takes \(k\) and \(a\) as arguments and outputs \(b\). The function \(\phi\) outputs the input's Hamming weight. In Reference [13], the function \(g\) is selected as the AES S-box. In this example, the attack is described based on the S-box used in the first round SubBytes of AES. ```
0:\((a_{i},b_{i}),\ i=0,...,M-1\)
0:key
1:\(g:K\times A\to B,\ N=|K|,\ S(g,k),\ S_{d}\in\{0,...,n\}\times\{0,...,m\}\)
2:for\(k\in K\)\(\leftarrow\) computation of theoretical joint distributions
3:\(S(g,k)\gets 0\)
4:for\(a\in A\)
5:\(S(g,k)(\phi(a),\phi(g(a,k)))\gets S(g,k)(\phi(a),\phi(g(a,k))+\frac{1}{|A|}\)
6:end
7:end
8:\(S_{d}\gets 0\)
9:for\(i=0:M-1\)\(\leftarrow\) computation of estimated joint distribution
10:\(S_{d}(a_{i},b_{i})\gets S_{d}(a_{i},b_{i})+\frac{1}{M}\)
11:end
12:\(key\gets 0\)
13:for\(k\in K\)\(\leftarrow\) compare theoretical distribution and estimated distribution
14:if\(d(S(g,k),S_{d})<d(S(g,key),S_{d})\)
15:\(key\gets k\)
16:end
17:end
18:return key
```
**Algorithm 6** Side channel analysis using joint distributions

First, steps 2-7 of Algorithm 6 are the processes involved in making the theoretical joint distributions table, which uses the Hamming weight values of random variables, plaintext \(a\), and S-box output \(b\). This process is performed for key \(k^{\prime}=0\)-255 with a 1-byte size. The \(S(g,k)\) is the theoretical joint distribution table of \(\phi(a)\) and \(\phi(b)\) when the key is \(k\) for function \(g\). The size of \(S(g,k)\) is \(9\times 9\), since the range of possible Hamming weights for \(a\) and \(b\) is 0-8. Next, steps 9-11 are the processes of constructing the estimated joint distribution table using \((a_{i},b_{i})\) pairs, which are the estimated Hamming weight values of \(a\) and \(b\).