%!TEX root = paper.tex

\section{Timing Attack Against HQC}
\label{sec:attack}


In the decryption algorithm, the decoder $\Psi$ is
used to correct the errors in the word
\[
  \vec{c}' = \vec{m} \mat{G} + \vec{x} \cdot \vec{r}_2 + \vec{r}_1 \cdot \vec{y} + \vec{e},
\]
where the attacker knows every element, except for the secret key consisting of $\vec{x}$ and
$\vec{y}$. For the original instantiation, where $\mathcal{C}$ is the tensor product of
a BCH code and a repetition code, the decoder $\Psi$ consists of a sequence of two operations:
first apply a repetition code decoder $\Psi_2$, and then apply the BCH code decoder $\Psi_1$.
That is $\Psi(\vec{c}') = \Psi_1(\Psi_2(\vec{c}'))$.

The timing attack is based on the fact the BCH decoder implemented by Aguilar-Melchor et al.~\cite{melchor2018hamming}
is not constant-time, and is slower when there are more errors to be corrected.
In other words, the decryption time leaks the number of errors that the repetition code (RC) decoder
$\Psi_2$ was not able to correct.

Figure~\ref{fig:time_vs_bch_error_weight} shows the essentially linear relation between
the decryption time and the number of errors corrected by the BCH decoder.
We emphasize that the time considered is for complete decryption, not only the BCH decoding step.
The weight distribution is centered between 9 and 10, thus error weights larger than 22
are rare (around 1\%).


\begin{figure}[ht!]
  \centering
  \includegraphics[width=\textwidth]{figures/information_leakage/time_vs_bch_error_weight_sm.pdf}
  \caption{The average decryption time for different weights of the errors corrected
  by the BCH decoder, considering 10 million decryption operations.}
  \label{fig:time_vs_bch_error_weight}
\end{figure}


Let $\vec{e}'$ be the error vector that $\Psi_2$ will try to correct, that is
$\vec{e}' = \vec{x} \cdot \vec{r}_2 + \vec{r}_1 \cdot \vec{y} + \vec{e}$.
We note that it is useful to consider
Guo's et al.~\cite{guo2016key} observation, used in their attack
on QC-MDPC, that the weight of the product of two binary sparse vectors
$\vec{a} \cdot \vec{b}$ is lower when the spectrums of $\vec{a}$ and $\vec{b}$ share more entries.
However, this observation is not sufficient to enable us to accurately distinguish between distances in and out
of the spectrum, because we are not just interested in the weight
of $\vec{e}'$, but mainly in the probability that it has enough non-null entries
in the same repetition blocks to cause $\Psi_2$ to leave decoding errors.

When the number of RC decoding errors for $\Psi_2(\vec{m}\mat{G} + \vec{e}')$
is high, it means that $\vec{e}'$ has a lot of non-null entries that are at a distance
lower than the repetition block size $n_2$.
Therefore, if we understand how $\vec{r}_1$ and $\vec{y}$
influence the number of entries lower than $n_2$ in $\sigma \left( \vec{r}_1 \cdot \vec{y} \right)$,
we can use our knowledge on $\vec{r}_1$ together with the decryption time to obtain
information on $\vy$.\footnote{This sentence remains valid if we substitute $\vy$ and $\vec{r}_1$ by $\vx$ and $\vec{r}_2$,
respectively.}

We make three observations that relate the spectrum of $\vec{e}'$ to the spectrums of $\rone$ and $\vy$,
(alternatively $\rtwo$ and $\vx$).
These are presented in the next section based on empirical data, and their mathematical nature
is explained in Section~\ref{sec:analysis_spectrums}.

The timing attack then consists of two parts. In the first part, called the spectrum recovery,
the attacker sends Alice a great number of ciphertexts and records the decryption times for each one.
This step runs until it is gathered sufficient information on the spectrums of \vy (or \vx)
for him to build a large set $D$ of distances outside the spectrum, and to obtain a distance
$s \in \sy$ (respectively, \sx).
In the second part, the set $D$ and distance $s$ are passed to the key reconstruction algorithm.

It is important to notice that the the attacker needs only to recover one of $\vx$ or $\vy$, because
he can use the linear relation $\vec{s} = \vx + \vy \cdot \vec{h}$ to easily recover one from the other.

In the next sections, the two parts are presented in detail.

\subsection{Spectrum Recovery}
\label{sec:spectrum_recovery}

This is the part where timing information is used. Let Alice
be the target secret key holder.
The attacker sends Alice valid ciphertexts, and records the time she takes to decrypt each challenge.
Since the attacker generated all ciphertexts, then, for each one of them, he knows $\vec{r}_1$ and $\vec{r}_2$.
The idea is that the attacker iteratively builds
two arrays, $\vec{T}_\vec{x}$ and $\vec{T}_\vec{y}$, such that
$\vec{T}_\vec{x}[d]$ ($\vec{T}_\vec{y}[d]$) is the average of the decryption time when $d$ is in the spectrum of $\vec{r}_2$
(resp. $\vec{r}_1$).

The algorithm for spectrum recovery is given as Algorithm~\ref{alg:spec_recovery}.
Notice that we are not choosing the vectors $\vec{r}_1$, $\vec{r}_2$, which are
assumed to be random. Therefore CCA2 conversions~\cite{hofheinz2017modular}
do not protect the scheme against this attack.


\begin{algorithm}[ht]
  \KwData{The HQC public parameters and Alice's public key \\
    \myinput{$\mathcal{T}$ returns the target's decryption time for the challenge passed as argument }
    \myinput{$M$ number of decoding challenges}
  }
  \KwResult{$\vec{T}_\vec{x}, \vec{T}_\vec{y}$ average decryption time for candidate distances
  in $\sigma(\vx)$ and $\sigma(\vy)$, respectively}
  \Begin{
    $\vec{a}_y,\vec{b}_y, \vec{a}_x, \vec{b}_x \gets $
      zero-initialized arrays with $\lfloor n/2 \rfloor$ entries each \\

    \For{each decoding trial $i = 1, 2, \ldots, M$} {
      $\vec{m} \gets $ a random message in $\Fb^k$ \\
      $\vec{c} \gets $ encryption of $\vec{m}$ using vectors
        $ \vec{r}_1 $ and $ \vec{r}_2$ randomly chosen\\

      $t = \mathcal{T}(\vec{c})$ \\

      \For{each distance $d$ in $\sigma(\vec{r}_1)$} {
        $\vec{a}_y[d] \gets \vec{a}_y[d] + t$ \\
          $\vec{b}_y[d] \gets \vec{b}_y[d] + 1$ \\
        }
      \For{each distance $d$ in $\sigma(\vec{r}_2)$}{
        $\vec{a}_x[d] \gets \vec{a}_x[d] + t$ \\
        $\vec{b}_x[d] \gets \vec{b}_x[d] + 1$ \\
      }
    }
    $\vec{T}_\vec{x}, \vec{T}_\vec{y} \gets $ zero-initialized array with $\lfloor n/2 \rfloor$ positions \\
    \For{each distance $d$ in $\{ 1, 2, \ldots, \lfloor n/2 \rfloor \}$ }{
      $\vec{T}_\vec{x}[d] \gets \vec{a}_x[d]/\vec{b}_x[d]$ \\
      $\vec{T}_\vec{y}[d] \gets \vec{a}_y[d]/\vec{b}_y[d]$ \\
    }
  \Return{$\vec{T}_\vec{x}$ and $\vec{T}_\vec{y}$}
  }
  \caption{Estimating the decryption time for each possible distance in $\sx$ and $\sy$}
  \label{alg:spec_recovery}
\end{algorithm}

To maximize the information obtained from each decryption timing, the proposed spectrum recovery procedure
targets $\sx$ and $\sy$ simultaneously. This is interesting for the attacker since it may be the case
that, after a number of challenges, the output $\vec{T}_\vec{x}$ does not have sufficient information on \vx for it to
be reconstructed, but $\vec{T}_\vec{y}$ is sufficient to recover $\vy$.

Figure~\ref{fig:decryption_time_vs_spectrum} shows the output of the spectrum recovery algorithm $\Ty$ for $M = 1$ billion decryption
challenges. On the left of the figure, we see that distances lower than $n_2$ have a significantly higher average decryption time.
The figure shows that, in general, distances inside the spectrum of $\vec{y}$ appears to have lower average decryption time.
However, there is no clear line to classify a distance $d$ as inside or outside \sy, based
only on $\Ty[d]$, since this value appears to also depend on the neighbors of $d$.

Figure~\ref{fig:decryption_time_vs_spectrum_density} shows another interval of the same data, but with one vertical line
for each distance in the spectrum. This enables us to see that regions where there are more distances inside the spectrum
appear to have higher average decryption time.

\begin{figure}[htb!]
  \centering
  \includegraphics[width=\textwidth]{figures/timing_attack/decryption_time_vs_spectrum_sm.pdf}
  \caption{The average decryption time $\Ty[d]$ for each distance $d$ that
  can occur in $\vec{r}_1$, for $M = 1$ billion.}
  \label{fig:decryption_time_vs_spectrum}
\end{figure}

\begin{figure}[htb!]
  \centering
  \includegraphics[width=\textwidth]{figures/timing_attack/decryption_time_vs_spectrum_density_sm.pdf}
  \caption{A closer look at the behavior of $\Ty[d]$ for each distance $d$. The gray vertical lines represent distances inside
   $\sigma(\vec{y})$.}
  \label{fig:decryption_time_vs_spectrum_density}
\end{figure}

Summarizing the analysis of the figures, we make the following three informal observations that allow us to distinguish between
distances inside and outside the spectrums.
\begin{enumerate}
  \item When $d$ decreases from $d = n_2 - 1$ to $d = 1$, the value of $\Ty[d]$ increases, getting
    significantly higher than the rest of the values in $\Ty$.
  \item When $d \in \sy$, the value of $\Ty[d]$ is lower than the average in the neighborhood of $d$.
  \item When $d$ has a large number of neighbors in $\sy$, the value of $\Ty[d]$ tends to be higher.
\end{enumerate}
The reasons why we observe such behavior are analyzed in detail in section~\ref{sec:analysis_spectrums}.

Similarly to the GJS algorithm (Algorithm~\ref{alg:rec_h0}),
our key reconstruction algorithm for the next part of the attack works with two inputs:
a set $D$ of distances outside the spectrum, and a distance $s$ inside the spectrum.
Figure~\ref{fig:decryption_time_vs_spectrum} suggests that, when a sufficiently large number of
decryption challenges are timed, it is easy to get a distance inside the spectrum
with high probability by just taking the distance $s$ such that $\Ty[s]$ is the minimum value in the array. However, it is not
trivial to find a sufficiently large set $D$ from $\Ty$. For this, we propose a routine called
$\textsc{BuildD}$, which is describe next.

\subsubsection{\textsc{BuildD}: Building the Set of Distances not in $\sy$ from $\Ty$.}
We propose to use the following simple algorithm,  that takes as input a value $\mu$ and the
decryption times estimation $\Ty$, and outputs $\mu$
distances which it classifies as out of \sy.
The idea is to select the $\mu$ values of $d$ such that $\Ty[d]$ are among the highest of their
corresponding neighborhood.

Let $\eta$ be some small positive integer for which the probability
that $\{ d, d + 1, \ldots, d + \eta - 1 \} \subset \sy$ is negligible for all values of $d$.
The value $\eta$ will be the size of the neighborhood, which must contain at least one distance outside the spectrum.
This value can be estimated by generating $N$ random vectors, then computing the
minimum value $\eta$ for which $\eta$ consecutive distances always contain at least one distance not in the vectors
corresponding spectrums. For the Basic-I parameters, we obtained $\eta = 11$ for $N = 10000$.

For each $d$, we compute the difference between \Ty[d] and the highest value
of \Ty in the window
$\{ d - \lfloor \eta/2 \rfloor, \ldots, d + \lceil \eta/2 \rceil - 1 \}$. If
the window contains invalid distances, we just truncate it to exclude them.
In other words
\[
  \rho(d) = \left( \max_{i \in W_d} \Ty[i] \right) - \Ty[d],
\]
where $W_d$ is the intersection between $\left\{ d - \lfloor \eta/2 \rfloor, \ldots, d + \lceil \eta/2 \rceil - 1 \right\}$
and the set of possible distances.
The algorithm sorts the possible distances with respect to $\rho(d)$, and returns the $\mu$ values of $d$ such that
$\rho(d)$ are the lowest ones.

Let $\textsc{BuildD}(\Ty, \mu)$ be the output of the algorithm just described for the given inputs.
Since the key reconstruction only works if $D$ is a large set of distances not in the spectrum,
it is natural to define the quality of the input \Ty as
\[
  \qual(\Ty) = \max \left\{ \mu : \textsc{BuildD}(\Ty, \mu) \cap \sy = \emptyset \right\}.
\]

Figure~\ref{fig:clustering_procedure} helps us visualize why this algorithm works.
For $M = 1$ billion decryptions, it is easy to see that the distances between $\Ty[d]$
and $\max_{i \in W_d} \Ty[i]$ should be smaller
when $d$ is not in the spectrum of $\vy$.
However, it is not clear yet how many decryptions
are necessary for the algorithm to be able to build sufficiently large sets $D$, that is,
to obtain high values for $\qual(\Ty)$.
This is considered in the experimental analysis in Section~\ref{sec:number_of_decryption_timings}.

\begin{figure}[htb!]
  \centering
  \includegraphics[width=\textwidth]{figures/timing_attack/clustering_procedure_sm.pdf}
  \caption{Illustration of the values $\max_{i \in W_d} \Ty[i]$ for each distance $d$, considering
  windows of size $\eta = 11$, after $M = 1$ billion decryptions.}
  \label{fig:clustering_procedure}
\end{figure}

\subsection{Reconstructing $\vec{y}$ from partial information on its spectrum}

We propose the key reconstruction algorithm given as Algorithm~\ref{alg:randomized_reconstruction},
which is a simple randomized extension of Guo's et al. algorithm.
Instead of performing a depth-first search for the key, at each level of the search tree,
the algorithm chooses the next node at random.

\SetKwRepeat{Do}{do}{while}

\begin{algorithm}[!h]
  \KwData{The HQC public parameters and Alice's public key\\
    \myinput{$s$ a distance inside $\sigma(\vy)$}\\
    \myinput{$D$ a set of distances which are not in $\sigma(\vy)$}\\
  }
  \KwResult{$V$ the support of a rotation of $\vy$}
  \Begin{
    \Do{Both $V$ and $\mirror(V)$ are not the support of a rotation of $\vy$}{
        $V \gets \{0, s\}$ \\
        $\Gamma_2 \gets \left\{ i \in \{ 1, \ldots, \lfloor n/2 \rfloor \} - V : \dist_n(i, v) \notin D
                \text{ for all } v \in V \right\}$ \\
        $\ell \gets 2$ \\
        \While{$|V| < w$ and $|\Gamma_\ell| > 0$}{
            $p \gets $ a random element from $\Gamma_\ell$ \\
            $V \gets V \cup \{ p \}$ \\
            $\Gamma_{\ell + 1} \gets \left\{ i \in \Gamma_\ell : \dist_n(i, v) \notin D
                \text{ for all } v \in V \right\}$ \\
            $\ell \gets \ell + 1$ \\
        }

    }
    \If {$V$ is the support of a shift of $\vy$}{ \label{line:shady}
      \Return{$V$}
    }
    \ElseIf {$\mirror(V)$ is the support of a shift of $\vy$}{ \label{line:mirror_test}
      \Return{$\mirror(V)$}
    }
  }
  \caption{Randomized key reconstruction algorithm}
  \label{alg:randomized_reconstruction}
\end{algorithm}

We give a brief description of the algorithm.
Parameters $s$, which must be a distance inside the spectrum of $\vy$,
and $D$, which is a set of distances outside the spectrum of $\vy$,
are obtained in the first part of the attack.
At each iteration, the algorithm starts with the set
$V = \{ 0, s \}$ and tries to complete it with
$w - 2$ indexes.
To complete the support $V$, the algorithm chooses at random an index inside the
auxiliary set $\Gamma_\ell$, which contains, for each level $l$,
the possible positions to complete the support. That is,
$\Gamma_\ell$ consists of all the elements from $\{0, \ldots, n - 1\}$ which are not in $V$,
and whose circular distance to any index in $V$ is not in $D$.

Notice that it is easy to perform the tests in lines~\ref{line:shady} and~\ref{line:mirror_test} without
knowing the secret key. Let $\bar{\vy}$ be the vector with support $V$ found in the algorithm's main loop.
Consider all possible cyclic shifts of $\bar{\vy}$, denoted by
$\vy^0, \ldots, \vy^{n - 1}$.
To test if $\bar{\vy}$ is a shift of $\vy$, we look for a shift $\vy^i$
such that the weight of the vector $\bar{\vec{x}} = \vec{s} + \vy^i \cdot \vec{h}$
is $\weight(\bar{\vec{x}}) = w$. If we find one, then  $\bar{\vy}$ is
a shift of $\vy$ (high probability), or we have found an equivalent secret key for the given public
key (\vec{h}, \vec{s}). If we do not find one, then we start a new iteration.

The complexity of the algorithm is analyzed in Section~\ref{sec:analysis_randomized_key_reconstruction_algorithm},
while its practical performance is shown in Section~\ref{sec:performance_key_reconstruction}.

