## 2 Background
### Previous Work
#### 2.3.5 General Approach to Key Recovery  
The author of [5; 17] noted that there is a general strategy to key recovery in the cold boot attack setting. We here follow the description in [17] to give an account of this general strategy. Let \(\texttt{ns}=b_{0}b_{1}b_{2}\ldots b_{W}\) be the noisy version of the encoding of the secret key and let us assume that \(\texttt{ns}\) can be represented as a concatenation of \(\mathcal{N}=W/w\) chunks, where each chunk is a sequence of \(w\) bits. That is, \(\texttt{ns}=\texttt{ns}^{0}||\texttt{ns}^{1}||\ldots||\texttt{ns}^{\mathcal{N }-1}\) with \(\texttt{ns}^{i}=b_{i:w}b_{i:w+1}\ldots b_{i:w+(w-1)}\). Additionally, let us assume there exists a key recovery algorithm that generates complete candidates \(\texttt{c}\) for the encoding of the secret key and that these complete candidates \(\texttt{c}\) can also be represented by concatenations of chunks in the same way, i.e., \(\texttt{c}=\texttt{c}^{0}||\texttt{c}^{1}||\ldots||\texttt{c}^{\mathcal{N}-1}\) with \(\texttt{c}^{i}\) being a sequence of \(w\) bits. Given the bit-flip probabilities \(\alpha\), \(\beta\), let us define \(\textbf{P}(\texttt{c}|\texttt{ns})\) to be the probability of \(c\) being the correct encoding of the secret key given the noisy version of the secret key. Hence, \(\textbf{P}(\texttt{c}|\texttt{ns})=\frac{\textbf{P}(\texttt{ns}|\texttt{c}) \textbf{P}(\texttt{c})}{\textbf{P}(\texttt{ns})}\). According to the maximum likelihood estimation method, \(\texttt{c}\) should be chosen as the value that maximises \(\textbf{P}(\texttt{c}|\texttt{ns})\). Since \(\textbf{P}(\texttt{ns})\) and \(\textbf{P}(\texttt{c})\) can be seen as constants, then \(\texttt{c}\) should be chosen as the value that maximises \(\textbf{P}(\texttt{ns}|\texttt{c})=(1-\alpha)^{n_{00}}\alpha^{n_{01}}\beta^{n_{1 0}}(1-\beta)^{n_{11}}\), where \(n_{00}\) denotes the number of positions where both \(\texttt{c}\) and \(\texttt{ns}\) contain a 0 bit, \(n_{01}\) denotes the number of positions where \(\texttt{c}\) contains a 0 bit, \(\texttt{ns}\) contains a 1 bit, etc. Equivalently, \(\texttt{c}\) may be chosen as the value that maximises the log of these probabilities, i.e., \(\log(\textbf{P}(\texttt{ns}|\texttt{c}))=n_{00}\log(1-\alpha)+n_{01}\log\alpha+n _{10}\log\beta+n_{11}\log(1-\beta)\). Consequently, we can give a score to a given candidate \(\texttt{c}\), i.e., \(S(\texttt{c},\texttt{ns}):=\log(\textbf{P}(\texttt{ns}|\texttt{c}))\). Let us further assume that each of the at most \(2^{w}\) candidate values for chunk \(c^{i}(0\leq i<W/w)\) can be enumerated; then, its own score also can be calculated as  
\[S(c^{i},\texttt{ns}^{i})=n^{i}_{00}\log(1-\alpha)+n^{i}_{01}\log\alpha+n^{i}_{10} \log\beta+n^{i}_{11}\log(1-\beta) \tag{1}\]  
where the \(n^{i}_{\lambda p}\) values count occurrences of bits across the \(i\)th chunks, \(c^{i},\texttt{ns}^{i}\), resulting in \(S(c,\texttt{ns})=\sum_{i=0}^{N-1}S(c^{i},\texttt{ns}^{i})\). As a result, we may obtain \(\mathcal{N}\) lists of chunk candidates, where each list contains up to \(2^{w}\) entries and a chunk candidate is defined as a 2-tuple of the form \((score,value)\) such that the first component \(score\) is a real number (candidate score) and the second component \(value\) is an array of \(w\)-bit strings (candidate value). From the previous observation, it follows that the problem of key recovery becomes that of developing efficient algorithmic techniques to construct full key candidates \(c\) with high accumulated scores calculated by summation, by travelling across the lists of chunk candidates while merging chunk candidates \(c^{i}\)[17]. This problem has already been extensively studied in the side-channel analysis literature [17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32], and there is a great variety of different algorithms able to solve the problem.