# Cold Boot Attacks on the Supersingular Isogeny Key Encapsulation (SIKE) Mechanism
## 5 Evaluation of Our Key-Recovery Algorithm
### Performance and Success Rates of Our Key-Recovery Algorithm  
This section reports success rates of our key-recovery algorithm. We first note that in this setting the attacker procures a noisy version ch of \(\text{sk}_{3}\) via a cold boot attack, as stated in Section 4.1, and so our key-recovery algorithm tries to find a full key candidate for \(\text{sk}_{3}\) from the noisy version. In order to compute estimates for success rates of our key-recovery algorithm, we analyze the following scenarios. For a given set of instance parameters, we calculate the success rate for our key-recovery algorithm with NOKEA if it is set to (1) enumerate all the possible full key candidates; (2) enumerate an interval with roughly \(2^{30}\) full key candidates; (3) enumerate an interval with roughly \(2^{40}\) full key candidates; (4) enumerate an interval with roughly \(2^{50}\) full key candidates. In this context, by instance parameters we mean setting the array P, the array M, \(w\) (normally 8), \(\alpha\), \(\beta\), together with the selected SIKE parameters. Note that given the noisy version ch and the instance parameters, our key-recovery algorithm creates the lists \(L_{\text{Bj}}\) at the end of step 4, then these are passed to NOKEA at the beginning of the step 5. Here is where we exploit several features of this algorithm in order to compute estimates for the success rates without actually running an enumeration with NOKEA. In particular, we exploit the fact that NOKEA can enumerate full key candidates of which total scores belong to a given interval in order from the highest to the lowest total score and that many scores of block candidates for a given block are repeated [11; 36; 44]. In particular, once the lists \(L_{\text{Bj}}\) are created, our tweaked NOKEA creates factorized lists, one per list \(L_{\text{Bj}}\), that contain entries of the form \((score,count)\) where \(score\) represents a score and \(count\) is the number of block candidates having \(score\) as score in the corresponding list \(L_{\text{Bj}}\). These factorized lists are passed to an alternative version of OKEA, where \(count\) is seen as a candidate value, and it generates another factorized list \(L\) with entries of the same form \((score,count)\), which is sorted by score in descending order, i.e., from the highest to the lowest score. An entry \((score,count)\) may be interpreted as there are \(count\) full key candidates of which total score is equal to \(score\). To calculate estimates for success rates, we run our tweaked key-recovery algorithm with all required parameters a fixed number of times (100 times) and then compute the corresponding success rate. Specifically, at each trial the SIKE key generation algorithm is run to obtain \((\mathfrak{s},\text{sk}_{3},\text{pk}_{3})\) according to the selected set of SIKE parameters, and then \(\text{sk}_{3}\) is perturbed as per \(\alpha\) and \(\beta\) and then our tweaked key-recovery algorithm is called by passing the noisy version ch, the instance parameters and the original key as parameters. It then runs until generating the lists \(L_{\text{Bj}}\) and, at such point, checks that each block of the original key is found in the corresponding list \(L_{\text{Bj}}\). If so, it means that a complete enumeration, carried out by NOKEA, would not fail in finding the secret key (it would fail otherwise). On the condition that the complete enumeration will not fail, the tweaked NOKEA is run to create the factorized list \(L\), which is used to determine if the original key may be found by the instance of NOKEA if it enumerates a range having roughly \(2^{30}\) or \(2^{40}\) or \(2^{50}\) full key candidates. In particular, say, we want to determine if the original key can be found via enumerating a range with approximately \(2^{a}\) full key candidates, \(a\in\{30,40,50\}\), then the algorithm finds an entry at index \(e\) in \(L\) such that \(e\) is the smallest integer satisfying \(2^{a}<\sum_{k=0}^{e}L[k]count\).