# Cold Boot Attacks on the Supersingular Isogeny Key Encapsulation (SIKE) Mechanism
## 2 Background
### Previous Work
#### 2.3.5 General Strategy to Key Recovery  
According to the work by [PERSON] [11; 27], we can deal with the key-recovery problem in the cold boot attack setting via key enumeration algorithms. Let \(\text{ch}=b_{0}b_{1}b_{2}\ldots b_{N}\) denote a \(W\) bit string with the noisy bits of the secret key encoding. Note that \(\text{ch}\) may be written as a sequence of \(\mathcal{N}=W/w\) chunks, with each chunk being a \(w\) bit-string, i.e., \(\text{ch}=\text{ch}^{0}||\text{ch}^{1}||\ldots||\text{ch}^{N-1}\) with \(\text{ch}^{i}=b_{i:w}b_{i:w+1}\ldots b_{i:w+(w-1)}\). On the condition that we have access to a suitable key-recovery algorithm, we can generate full key candidates \(\text{c}\) for the original secret key encoding. Based on [PERSON]'s theorem, the probability of \(\text{c}\) being the right full key candidate given the noisy version \(\text{ch}\) is given by \(\text{P}(\text{c}|\text{ch})=\frac{\text{P}(\text{ch}|\text{c})\text{P}( \text{c})}{\text{P}(\text{ch})}\). Therefore, \(\text{c}\) should be chosen so as to maximize this probability, according to the maximum likelihood estimation method. Note that both \(\text{P}(\text{ch})\) and \(\text{P}(\text{c})\) are constants, with the former independent of \(\text{c}\), and that \(\text{P}(\text{ch}|\text{c})=(1-\alpha)^{n_{00}}\alpha^{n_{01}}\beta^{n_{10}}( 1-\beta)^{n_{11}}\), where \(n_{00}\) counts the positions in which both \(\text{c}\) and \(\text{ch}\) contain a 0 bit, \(n_{01}\) counts the positions in which \(\text{c}\) contains a 0 bit and \(\text{ch}\) contains a 1 bit, etc. Hence our optimization problem reduces to find the candidate \(\text{c}\) to maximize this probability \(\text{P}(\text{ch}|\text{c})\). Note that this problem can be stated equivalently as choosing \(\text{c}\) that maximizes the log of these probabilities \(\log(\text{P}(\text{ch}|\text{c}))=n_{00}\log(1-\alpha)+n_{01}\log\alpha+n_{1 0}\log\beta+n_{11}\log(1-\beta)\). Therefore, each candidate can be assigned a score, namely \(S(\text{c},\text{ch}):=\log(\text{P}(\text{ch}|\text{c}))\). If we now assume that the full key candidates \(\text{c}\) may be written as a sequence of chunks as for \(\text{ch}\), i.e., \(\text{c}=\text{c}^{0}||\text{c}^{1}||\ldots||\text{c}^{N-1}\), with \(\text{c}^{i}\) being a sequence of \(w\) bits, then we may also assign a score to each of the at most \(2^{w}\) values for a chunk candidate \(\text{c}^{i}\). \[S\big{(}\text{c}^{i},\text{ch}^{i}\big{)}=n_{00}^{i}\log(1-\alpha)+n_{01}^{i} \log\alpha+n_{10}^{i}\log\beta+n_{11}^{i}\log(1-\beta) \tag{1}\]  
where the \(n_{ab}^{i}\) values count occurrences of bits across the \(i_{th}\) chunks, \(\text{c}^{i},\text{ch}^{i}\). Because of \(S(\text{c},\text{ch})=\sum_{i=0}^{N-1}S\big{(}\text{c}^{i},\text{ch}^{i}\big{)}\), \(\mathcal{N}\) lists of chunk candidates, containing up to \(2^{w}\) entries, may be created. More concretely, each list contains at most \(2^{w}\) 2-tuples of the form \((score,value)\), where the first component \(score\) is a real number (candidate score) and the second component \(value\) is a \(w\)-bit string (candidate value). Now note that the original key-recovery problem reduces to an enumeration problem that consists in traversing the lists of chunk candidates to produce full key candidates \(\text{c}\) of which total scores are obtained by summation. Fortunately for us, the enumeration problem has been previously studied in the side-channel analysis literature [12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27], and there are many algorithms that may be useful for our key-recovery setting, in particular those producing full key candidates sorted in descending order based on the score component. More formally, let \(L^{i}=\big{[}\text{c}^{i}_{0},\text{c}^{i}_{2},\ldots,\text{c}^{i}_{m_{i}-1} \big{]}\) be a list of chunk candidates for chunk \(\text{ch}^{i}\), with \(0<m_{i}\leq 2^{w}\) and \(\text{c}^{i}_{j}=\big{(}score^{i}_{j},value^{i}_{j}\big{)}\).