# Cold Boot Attacks on the Supersingular Isogeny Key Encapsulation (SIKE) Mechanism
## 4 Key Recovery
### Our Key-Recovery Algorithm  
Throughout this section we give a detailed account of our key-recovery strategy, taking into consideration the notation introduced in Section 2.3.5 and the review of SIKE's reference implementation. Let \(\mathtt{ch}=b_{0}b_{1}b_{2}\ldots b_{\mathrm{W}}\) be \(W\) bit string that represents the noisy version of the secret key encoding \(\mathtt{sk}_{3}\). Note that the value for \(W\) depends on the SIKE parameters on which SIKE is configured. In particular, \(W=8\cdot\mathtt{sk}_{3}\) (see the fourth column of Table 1). We denote \(w\) as the size in bits of a chunk (it is set to 8), and so \(\mathtt{ch}\) can be written as a sequence of \(\mathcal{N}=W/w\) chunks  
\[\mathtt{ch}=\mathtt{ch}^{0}||\mathtt{ch}^{1}||\ldots||\mathtt{ch}^{N-1}\]  
with \(\mathtt{ch}^{i}=b_{i:w}b_{i:w+1}\ldots b_{i:w+(w-1)}\). We define a block \(\mathtt{B}_{m}^{k}=\mathtt{ch}^{k}||\mathtt{ch}^{k+1}||\cdots||\mathtt{ch}^{k +m-1}\) as a sequence of consecutive chunks, where \(0\leq k\leq k+m-1<\mathcal{N}\) and \(m\) is the number of chunks in the block. We can now rewrite \(\mathtt{ch}\) as a concatenation of \(n_{b}\) blocks, namely  
\[\mathtt{ch}=\mathtt{B}_{m_{0}}^{0}||\mathtt{B}_{m_{1}}^{m_{0}}||\ldots|| \mathtt{B}_{m_{m_{0}-1}}^{m_{0}+m_{1}+m_{2}+\ldots+m_{n_{b}-2}}\]  
with \(\sum_{i=0}^{n_{b}-1}m_{i}=\mathcal{N}\). Now we are ready to present our key-recovery algorithm. \begin{table}
\begin{tabular}{c c c c c c} \hline Name & \(\lfloor\mathtt{log_{2}}3^{\mathtt{s_{5}}}\rfloor\) & MASK & \(\mathtt{N_{sk_{3}}}\) & e2 & e3 \\ \hline SIKEp434 & 218 & Ox01 & 28 & 216 & 137 \\ \hline SIKEp503 & 253 & OxOF & 32 & 250 & 159 \\ \hline SIKEp610 & 305 & OxFF & 38 & 305 & 192 \\ \hline SIKEp751 & 379 & Ox03 & 48 & 372 & 239 \\ \hline \end{tabular}
\end{table} 
Table 1: Relevant constants from Supersingular Isogeny Key Encapsulation (SIKE) parameters. 1. Set the array \(\mathtt{P}=\left[m_{0},m_{1},m_{2},\ldots,m_{n_{b}-1}\right]\) with \(\sum_{j=0}^{n_{b}-1}m_{j}=\mathcal{N}\). Each \(m_{j}\) is the number of chunks in the block \(\mathtt{B}_{m_{j}}^{m_{0}+m_{1}+\ldots+m_{j-1}}\). 2. Set the array \(\mathtt{M}=\left[M_{0},M_{1},M_{2},\ldots,M_{n_{b}-1}\right]\). Each \(M_{j}\) is the number of high-scoring candidates to generate for the block \(\mathtt{B}_{m_{j}}^{m_{0}+m_{1}+\ldots+m_{j-1}}\). 3. By making use of Equation (1), our algorithm computes the log-likelihood scores for all possible candidate values for each chunk \(\mathtt{ch}^{i}\), with \(0\leq i<\mathcal{N}\). Note that, in the SIKE setting, all candidate values are in the set \(\{0,1,2,\ldots 255\}\), except for the last chunk, where all candidate values are in the set \(\{0,1,2,\ldots,2^{n_{s}}-1\}\) with \(n_{s}\) being the number of ones of the binary string Params.MASK. Each tuple \((score,value)\) generated for a particular chunk \(\mathtt{ch}^{i}\) is inserted into the list \(L_{\mathtt{ch}^{i}}\), and this is finally inserted in the corresponding index \(i\) of the main list \(L\). 4. For each block \(\mathtt{B}_{m_{j}}^{m_{0}+m_{1}+\ldots+m_{j-1}}\), with \(0\leq j<n_{b}\) and \(m_{-1}=0\), then the lists stored in \(L\) at indexes \(m_{0}+m_{1}+\ldots+m_{j-1}+k\) for \(0\leq k<m_{j}\) are given as parameters to an optimal key enumeration algorithm, which we denote as OKEA, to produce the list \(L_{\mathtt{B}^{j}}\) that contains the \(M_{j}\) candidates with the highest scores for the block \(\mathtt{B}_{m_{j}}^{m_{0}+m_{1}+\ldots+m_{j-1}}\). 5. All lists \(L_{\mathtt{B}^{j}}\) are given as parameters to an instance of a key enumeration algorithm (KEA). This instance regards each \(L_{\mathtt{B}^{j}}\) as a list of suitable candidates for the corresponding block \(\mathtt{B}_{m_{j}}^{m_{0}+m_{1}+\ldots+m_{j-1}}\) and outputs high-scoring full key candidates for the target secret key encoding. Upon generating a full key candidate \(c\), our algorithm passes it as input to a testing function (Test in our case) to verify whether the full key candidate \(c\) is a valid secret key or not.