%!TEX root = slides.tex

% \section{Introdução}

% \subsection{Motivação}


\begin{frame}[fragile]{Melhorando o ataque de reação contra o QC-MDPC McEliece}

    \textbf{QC-MDPC McEliece} \\
    \begin{itemize}
        \item Esquema de encriptação de chave pública elaborado em 2013
        \item Variante do esquema de McEliece com chaves compactas
        \item QC-MDPC $=$ \emph{quasi-cyclic moderate density parity-check}
        \item Até 2016, era considerado um esquema pós-quântico
    \end{itemize}
    \textbf{Ataque de reação} \\
    \begin{itemize}
        \item Obtém informação através da decifrabilidade de textos cifrados
        \item Usa a informação obtida para reconstruir a chave
        \item No caso de um esquema seguro contra ataques
                de texto cifrado escolhido (IND-CCA),
                só são permitidos textos cifrados aleatórios como desafios
    \end{itemize}
    \textbf{Melhorando o ataque}
    \begin{itemize}
        \item Duas propostas de algoritmos para a reconstrução de chave
    \end{itemize}

\end{frame}

\begin{frame}[fragile]{Motivação}

    \textbf{Por que esquemas criptográficos com códigos corretores de erros?} \\
    \begin{itemize}
        \item Esquemas baseados em códigos usam um problema supostamente difícil até
        para computadores quânticos
        \item Algoritmos quânticos ameaçam RSA~\cite{rsa1978rsa} e Curvas Elípticas~\cite{shor1997poly}
        \item Outros esquemas supostamente pós-quânticos são baseados em:
            \begin{itemize}
                \item Reticulados
                \item Hashes
                \item Equações quadráticas multivariadas
                \item Isogenias de curvas elípticas
            \end{itemize}
        \item Esquema de McEliece é o principal dos baseados em códigos
    \end{itemize}

\end{frame}


\begin{frame}[fragile]{Criptografia com Códigos Corretores}

    \textbf{Esquema de McEliece} \cite{mceliece1978} \\
    \begin{itemize}
        \item Encriptação e Decriptação mais eficientes que RSA e CE \cite{bernstein2013mcbits}
        \item Baseado no problema \cNP-difícil da decodificação~\cite{berlekamp1978inherent} \\
        (talvez dê uma falsa sensação de segurança?)
        \item Principal problema é que usa \textbf{chaves públicas muito grandes}
    \end{itemize}

    \begin{table}[H]
    \centering
    % \caption{Tamanhos das chaves públicas para alguns esquemas~\cite{bernstein2013mcbits}}
    \label{tab:mcbits}
    \begin{tabular}{@{}cccc@{}}
    \toprule
    \multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Nível de segurança\\ aproximado\end{tabular}} & \multicolumn{3}{c}{\begin{tabular}[c]{@{}c@{}}Tamanho da chave pública~\cite{bernstein2013mcbits}\\ (Bytes)\end{tabular}} \\ \cmidrule(l){2-4}
                                        & Curvas Elípticas                 & RSA                               & McEliece                \\ \midrule
    80  &  20  &  128   &  65006  \\
    128 &  32  &  384   &  261702  \\
    256 &  64  &  1920  &  1046739 \\ \bottomrule
    \end{tabular}
    \end{table}


\end{frame}


\begin{frame}[fragile]{Variantes do esquema de McEliece}

    \begin{itemize}
        \item  O original usa códigos de {Goppa binários e irredutíveis}~\cite{goppa1970new, berlekamp1973goppa}

        \item Vários códigos propostos para chaves
        compactas~\cite{gaborit2005shorter,berger2009reducing,misoczki2009compact,
        shokrollahi2000using}

        \item A maioria foi quebrada pouco depois de sua publicação~\cite{otmani2010cryptanalysis, faugere2010algebraic,faugere2016structural}

        \item Até 2016 a variante \textbf{QC-MDPC}~\cite{misoczki2013mdpc} era a mais
            promissora~\cite{augot16initial}
    \end{itemize}

    \begin{table}[H]
        \centering
        \caption{Parâmetros sugeridos para cada nível de segurança~\cite{misoczki2013mdpc}}
        \label{tab:param_sugerido}
        \begin{tabular}{@{}ccccccc@{}}
        \toprule
        Segurança & $n_0$ & $n$   & $r$   & $w$ & $t$ & \begin{tabular}[c]{@{}c@{}}Tamanho da chave\\ (Bytes)\end{tabular} \\ \midrule
        80        & 2     & 9602  & 4801  & 90  & 84  & 601             \\
        128       & 2     & 19714 & 9857  & 142 & 134 & 1233             \\
        256       & 2     & 65542 & 32771 & 274 & 264 & 4097            \\ \bottomrule
        \end{tabular}
    \end{table}

\end{frame}

\begin{frame}[fragile]{Códigos QC-MDPC}
    \[
        \mat{H} = \left[ \mat{H}_0 | \mat{H}_1 \right],
            \text{ onde $\mat{H}_0$ e $\mat{H}_1$ são cíclicas e esparsas }
    \]
    \begin{figure}[htpb]
      \includegraphics[width=10cm,height=2.5cm] {figuras/qcmdpc_checkmat.pdf}
      % \label{fig:qcmdpc}
      % \caption{Matriz de paridade de código QC-MDPC com dois blocos e $w = 6$.}
    \end{figure}
    \only<1>{
        \[
            \mat{G} = \left[ \quad \mat{I} \quad | \quad (\mat{H}_1^{-1} \mat{H}_0)^{T} \, \right] \text{ é sistemática e densa }
        \]
    }
    \only<2>{
        \[
            \mat{G} = \left[ \quad \mat{I} \quad | \quad (\textcolor{red}{\mat{H}_1^{-1} \mat{H}_0})^{T} \, \right] \text{ é sistemática e densa }
        \]
    }
    \begin{figure}[htpb]
      \includegraphics[width=10cm,height=2.5cm] {figuras/qcmdpc_genmat.pdf}
      % \caption{Matriz geradora de código QC-MDPC com dois blocos.}
      % \label{fig:qcmdpc_gen}
    \end{figure}
\end{frame}


\begin{frame}[fragile]{QC-MDPC McEliece}

    \begin{itemize}
        \item \textbf{Chave privada}
        \begin{itemize}
            \item É a matriz de paridade $\mat{H} = \left[ \mat{H}_0 | \mat{H}_1 \right]$
                de um código QC-MDPC
            \item Basta guardar as primeiras linhas de $\mat{H}_0$ e $\mat{H}_1$ denotadas por  $\vec{h}_0$ e $\vec{h}_1$
        \end{itemize}

        \item \textbf{Chave pública}:
            \begin{itemize}
                \item Matriz geradora densa $\mat{G}$
                \item Basta guardar a primeira linha $\vec{g}$ do bloco cíclico $\mat{G}$
                \item $t$, o número de erros que o código corrige com alta probabilidade
            \end{itemize}

        \item \textbf{Encriptação} de uma mensagem $\vec{m}$:
            \begin{itemize}
                \item Escolha aleatoriamente um vetor de erro $\vec{e}$ binário de peso $t$
                \item Devolva $\vec{c} = \vec{m}\mat{G} + \vec{e}$
            \end{itemize}

        \item \textbf{Decriptação} de um texto encriptado $\vec{c}$
            \begin{itemize}
                \item Seja $\Psi$ um algoritmo de decodificação para códigos QC-MDPC
                \item Corrija os erros de $\vec{c}$ obtendo $\vec{c}' = \vec{m} \mat{G} = \Psi(\vec{c})$
                \item Se $\Psi(\vec{c})$ falhar, peça para o remetente encriptar com outro erro
                \item Resolva o sistema linear sobredeterminado e obtenha $\vec{m}$
            \end{itemize}
    \end{itemize}

\end{frame}



\begin{frame}[fragile]{Ataque contra o QC-MDPC McEliece~\cite{guo2016key}}

    \begin{itemize}
        \item A probabilidade de o decodificador falhar é menor se $\vec{e}$ e $\mat{H}$ compartilham
                certas propriedades
        \item A cada sucesso ou falha de decodificação a atacante obtém informação sobre $\mat{H}$
        \item A atacante pode obter grande quantidade de informação sobre $\mat{H}$ com um número suficiente
        de desafios de decodificação
        \item Com informação suficiente, a matriz secreta $\mat{H}$ pode ser reconstruída
    \end{itemize}
    \textbf{Mas que informação é possível obter através de testes de decodificação?}

\end{frame}


\begin{frame}[fragile]{Espectro}

    Definição de espectro de um vetor binário

    \begin{itemize}
        \item O espectro de um vetor $\vec{v}$, denotado por $\sigma(\vec{v})$, é o
        conjunto de menores distâncias cíclicas entre posições não-nulas de $\vec{v}$
        \item Um exemplo
        \begin{itemize}
            \item Seja $\vec{v} = [\,0\,1\,1\,0\,0\,0\,0\,0\,1\,]$ \\
            \item Então $\sigma(\vec{v}) = \{ 1, 2, 3 \}$
        \end{itemize}
    \end{itemize}


    Tome um texto encriptado $\vec{c} = \vec{m} \mat{G} + [ \vec{e}_0 | \vec{e}_1 ]$

    \begin{itemize}
        \item Guo et al. mostraram que a probabilidade de $\Psi(\vec{c})$ falhar é menor quanto maiores
        os tamanhos dos conjuntos
        \[
            \sigma(\vec{e}_0) \cap \sigma(\vec{h}_0) \text{ e }
             \sigma(\vec{e}_1) \cap \sigma(\vec{h}_1)
        \]
        \item O ataque de reação recupera os espectros dos vetores
        $\vec{h}_0$ e $\vec{h}_1$
    \end{itemize}

\end{frame}


\begin{frame}[fragile]{Reconstrução de $\vec{h}_0$ a partir de seu espectro}

    \begin{itemize}
        \item Tome $\hz = [0\,1\,1\,0\,0\,0\,1\,0\,0]$, então $\sigma(\hz) = \{1, 4\}$
        \item Suponha que não sabemos $\hz$ mas temos as seguintes informações parciais:
        \begin{itemize}
            \item $\hz$ tem 3 entradas não nulas
            \item $\hz$ tem tamanho $r = 9$
            \item $D_0 = \{2\}$ é um conjunto de distâncias fora de $\sigma(\hz)$
            \item $s_0 = 1$ é uma distância pertencente a $\sigma(\hz)$
        \end{itemize}
    \end{itemize}

    \centering
    \begin{tikzpicture}

    \only<1>{

        \matrix (A) [matrix of nodes, ampersand replacement=\&,
             row sep=10*\pgflinewidth, column sep=-\pgflinewidth,
             nodes={draw,minimum size=10mm,anchor=center}] {

                ? \& ? \& ? \& ? \& ? \& ? \& ? \& ? \& ?\\
        };
    }
    \only<2>{

        \matrix (A) [matrix of nodes, ampersand replacement=\&,
             row sep=10*\pgflinewidth, column sep=-\pgflinewidth,
             nodes={draw,minimum size=10mm,anchor=center}] {

                \textbf{1} \& \textbf{1} \& ? \& ? \& ? \& ? \& ? \& ? \& ?\\
        };
    }
    \only<3>{

        \matrix (A) [matrix of nodes, ampersand replacement=\&,
             row sep=10*\pgflinewidth, column sep=-\pgflinewidth,
             nodes={draw,minimum size=10mm,anchor=center}] {

                1 \& 1 \& \textbf{0} \& \textbf{0} \& ? \& ? \& ? \& \textbf{0} \& \textbf{0}\\
        };
    }

    \only<4>{

        \matrix (A) [matrix of nodes, ampersand replacement=\&,
             row sep=10*\pgflinewidth, column sep=-\pgflinewidth,
             nodes={draw,minimum size=10mm,anchor=center}] {

                1 \& 1 \& {0} \& {0} \& \color{red}{\textbf{1}} \&
                \color{red}{\textbf{0}} \&
                \color{red}{\textbf{0}} \& {0} \& {0}\\
        };
    }


    \only<5>{

        \matrix (A) [matrix of nodes, ampersand replacement=\&,
             row sep=10*\pgflinewidth, column sep=-\pgflinewidth,
             nodes={draw,minimum size=10mm,anchor=center}] {

                1 \& 1 \& {0} \& {0} \& \color{green}{\textbf{0}} \&
                \color{green}{\textbf{1}} \&
                \color{green}{\textbf{0}} \& {0} \& {0}\\
        };
    }
    \only<6>{

        \matrix (A) [matrix of nodes, ampersand replacement=\&,
             row sep=10*\pgflinewidth, column sep=-\pgflinewidth,
             nodes={draw,minimum size=5mm,anchor=center}] {

                1 \& 1 \& {0} \& {0} \& \color{green}{\textbf{0}} \&
                \color{green}{\textbf{1}} \&
                \color{green}{\textbf{0}} \& {0} \& {0}\\
        };
        \node [ right=2cm of A, draw] (z){$\{1, 2\}$}
          child {node [draw] (a) {$\{1, 2, 5\}$}}
          child {node [draw,fill=green] (j) {$\{1, 2, 6\}$}}
          child {node [draw] (k) {$\{1, 2, 7\}$}
         };
    }

\end{tikzpicture}

\end{frame}

\begin{frame}[fragile]{Reconstrução de $\vec{h}_0$ a partir de seu espectro}

    \begin{itemize}
        \item Guo et al. só fazem testes para o nível de segurança de 80 bits
        e considerando que $D_0$ contém todas as distâncias fora do espectro

        \item Seu algoritmo tem tempo médio de execução de 144s

        \item O argumento para o desempenho do algoritmo é que ramos ruins da
        árvore de busca são podados relativamente cedo

        \item Pode ser difícil paralelizar a busca em profundidade

        \item O desempenho do algoritmo pode ser muito ruim para níveis de segurança mais
        altos


    \end{itemize}
    \begin{table}[ht]
    \centering
    % \caption{Desempenho estimado do algoritmo de reconstrução de chave}
    \label{tab:guo_time}
    \begin{tabular}{@{}ccccc@{}}
    \toprule
    \begin{tabular}[c]{@{}c@{}}Nível de segurança \\ $\lambda$\end{tabular} & Número médio de caminhos  & \begin{tabular}[c]{@{}c@{}}Extrapolação\\ para o tempo\\ médio de execução\end{tabular} \\ \midrule
    80                                                                        & $2^{25.45}/2$                                                                 & 144s~\cite{Guo2016Youtube}                                                                             \\
    128                                                                      & $2^{39.72}/2$                                                                 & $\sim$ 32 dias                                                                   \\
    256                                                                     & $2^{61.95}/2$                                                                 & $\sim$ 422930 anos                                                              \\ \bottomrule
    \end{tabular}
    \end{table}


\end{frame}

\begin{frame}[fragile]{Como classificar distâncias em $\sigma(\vec{h}_0)$ e $\sigma(\vec{h}_1)$}
    \begin{itemize}
        \item Estimar as taxas de falha de decodificação para cada distância
        \item As taxas de falha são usadas para classificar as distâncias
        \item É construído um conjunto $D_0$ com distâncias fora do espectro
        \item $D_0$ \textbf{não pode} conter distâncias dentro do espectro
    \end{itemize}

    \begin{figure}[htpb]
      \includegraphics[width=\textwidth] {figuras/exemplo_d_exclusao.pdf}
      % \caption{Matriz geradora de código QC-MDPC com dois blocos.}
      % \label{fig:qcmdpc_gen}
    \end{figure}
\end{frame}


\begin{frame}[fragile]{Como o número de testes de decodificação afeta $\max |D_0|$}
    \begin{itemize}
        \item O algoritmo de Guo et al. precisa de em torno de 200M de testes
        \item Testes de decodificação são caros pois envolvem comunicação com o decodificador
        \item Determinar o número de testes para um ataque bem sucedido é importante
                para estimar a vida útil de uma chave secreta
    \end{itemize}

    \begin{figure}[htpb]
      \includegraphics[width=0.75\textwidth] {figuras/d_sep_obtida_100M_200cods.pdf}
      % \caption{Testes de decodificação}
      % \label{fig:qcmdpc_gen}
    \end{figure}

    \scriptsize{As simulações foram realizadas com o auxílio dos recursos de HPC disponibilizados
    pela Superintendência de Tecnologia da Informação da Universidade de São Paulo.}
\end{frame}


\begin{frame}[fragile]{Nosso objetivo}
    Propor novos algoritmos de reconstrução de chave que:
    \begin{itemize}
        \item Sejam mais eficientes do que o de Guo et al.
        \item Consigam lidar com menores tamanhos de $|D_0|$
    \end{itemize}

\end{frame}


\begin{frame}[fragile]{Algoritmo probabilístico de reconstrução}
    \begin{itemize}
        \item Similar ao algoritmo de Guo et al. mas escolhe aleatoriamente onde colocar `1's
        \item A cada iteração, percorre um caminho aleatório na árvore de busca da raiz até uma de suas folhas
        \item Encontrar a chave se reduz a poucas escolhas certas no começo de cada iteração
        \item Evita que o algoritmo de reconstrução fique preso em ramos ruins da árvore de busca
        \item Principal problema é não ser eficiente nos níveis de segurança mais altos do que 80
        quando $|D_0|$ não é muito grande
    \end{itemize}
\end{frame}


\begin{frame}[fragile]{Algoritmo probabilístico de reconstrução}
    O algoritmo probabilístico percorre, em média, bem menos caminhos do que o de Guo et al.
    \begin{figure}[htpb]
      \includegraphics[width=\textwidth] {figuras/comp_prob_com_guo.pdf}
      % \caption{Matriz geradora de código QC-MDPC com dois blocos.}
      % \label{fig:qcmdpc_gen}
    \end{figure}
\end{frame}

\begin{frame}[fragile]{Desempenho do algoritmo  probabilístico}
    \begin{itemize}
        \item O algoritmo é mais eficiente que o algoritmo de Guo et al. em todos
             os tamanhos realistas de $|D_0|$
        \item Ele é paralelizável trivialmente
    \end{itemize}
    \begin{table}[h]
    \centering
    % \caption{O desempenho do algoritmo de reconstrução para diferentes níveis de segurança}
    \label{tab:attack_performance}
    \begin{tabular}{@{}cccc@{}}
    \toprule
    \begin{tabular}[c]{@{}c@{}}Nível de segurança \\ $\lambda$\end{tabular} &  \begin{tabular}[c]{@{}c@{}}$|D_0|$ \\  normalizado\end{tabular} & \begin{tabular}[c]{@{}c@{}}Tempo médio \\ de execução\end{tabular} \\ \midrule
    80                                                                  &  $62.92 \%$                                                                           & \textbf{142s}                                                         \\
    128                                                                 & $77.27 \%$                                                                           & \textbf{165s}                                                       \\
    256                                                                 &  $89.45 \%$                                                                         & \textbf{251s}                                                   \\ \bottomrule
    \end{tabular}
    \end{table}
    Considerando o algoritmo executado em 16 cores de um processador Intel Xeon E7-2870 @ 2.40GHz
\end{frame}

\begin{frame}[fragile]{Algoritmo probabilístico de reconstrução}
    \begin{itemize}
        \item $|D_0| = 1000$ é suficiente para que o algoritmo funcione eficientemente
        \item Basta que $|D_0|$ ou $|D_1|$ sejam $\geq 1000$
    \end{itemize}
    \begin{figure}[htpb]
      \includegraphics[width=\textwidth] {figuras/hist_ataque_prob.pdf}
      % \caption{Matriz geradora de código QC-MDPC com dois blocos.}
      % \label{fig:qcmdpc_gen}
    \end{figure}
\end{frame}


\begin{frame}[fragile]{Algoritmo iterativo de reconstrução}
    \begin{itemize}
        \item Explora a relação linear
            $\ho \mat{B} = \hz$,
        onde $\mat{B} = \mat{H}_1^{-1} \mat{H}_0$ é pública

        \item Usa testes de decodificação para obter conjuntos $D_0$ e $D_1$,
        que contêm distâncias fora dos espectros de \hz e \ho

        \item Usa $s_0$ e $s_1$, que são distâncias nos espectros de \hz e \ho
        \item Usando $s_0$ e $D_0$, encontram-se posições de entradas nulas de uma rotação de $\hz$
        \item Usando $s_1$ e $D_1$, encontram-se posições de entradas nulas de uma rotação de $\ho$
        \item Com um número suficiente de posições nulas conhecidas, pode-se obter o vetor
              $\vec{h}_1$ através da resolução de um sistema linear homogêneo

    \end{itemize}
\end{frame}


\begin{frame}[fragile]{Desempenho do algoritmo iterativo}
    \begin{itemize}
        \item O algoritmo pode falhar em encontrar a chave
        \item Sejam $z_0$ e $z_1$ o número de posições nulas conhecidas em \hz e \ho,
            a probabilidade de falha é $\approx 2^{z_0 + z_1 - r}$
    \end{itemize}
    Considerando uma probabilidade de falhar de $2^{-20}$ para 99\% dos códigos,
    o desempenho do algoritmo é
    \begin{table}[h]
    \centering
    % \caption{O desempenho do algoritmo de reconstrução para diferentes níveis de segurança}
    \label{tab:attack_performance}
    \begin{tabular}{@{}cccc@{}}
    \toprule
    \begin{tabular}[c]{@{}c@{}}Nível de segurança \\ $\lambda$\end{tabular} & \begin{tabular}[c]{@{}c@{}}Tempo médio\\ por iteração\end{tabular} & \begin{tabular}[c]{@{}c@{}}$|D_0| = |D_1|$ \\  normalizados\end{tabular} & \begin{tabular}[c]{@{}c@{}}Tempo médio \\ de execução\end{tabular} \\ \midrule
    80                                                                  & 0.0169s                                                              & $45.63 \%$                                                                           & \textbf{41s}                                                         \\
    128                                                                 & 0.1710s                                                              & $49.58 \%$                                                                           & \textbf{14m3s}                                                       \\
    256                                                                 & 3.4179s                                                              & $52.34 \%$                                                                         & \textbf{15h33m24s}                                                   \\ \bottomrule
    \end{tabular}
    \end{table}
    Considerando um processador i7 870 Lynnfield @ 2.93GHz.
    As operações de álgebra linear foram feitas usando a biblioteca M4RI~\cite{M4RI}
\end{frame}

\begin{frame}[fragile]{Número necessário de testes de decodificação}
    \begin{figure}[htpb]
      \includegraphics[width=\textwidth] {figuras/hist_ataque_kernel.pdf}
      % \caption{Matriz geradora de código QC-MDPC com dois blocos.}
      % \label{fig:qcmdpc_gen}
    \end{figure}
\end{frame}

\begin{frame}[fragile]{Conclusão}
    \begin{itemize}
        \item Ambos os algoritmos usam menos informação e são mais eficientes do que
                o de Guo et al.

        \item O algoritmo probabilístico sofre os mesmos problemas de escalamento  que o de Guo et al.
        \item O algoritmo iterativo é muito mais robusto em relação à quantidade de informação
        \item Os dois algoritmos foram analisados tanto teoricamente quanto na prática, com
        implementações em C
    \end{itemize}

\end{frame}


\begin{frame}[fragile]{Conclusão}
    \begin{itemize}

        \item O algoritmo probabilístico pode ser mais eficiente que o iterativo quando o $D_0$
                está quase completo
        \item O número necessário de decodificações para ambos os algoritmos é similar
                para o nível de segurança de 80 bits
        \item Mas é esperado que o algoritmo iterativo precise de menos decodificações do
                que o probabilístico em níveis de segurança mais altos

        \item O algoritmo iterativo foi submetido à revista Transactions on Fundamentals of Electronics,
        Communications and Computer Sciences do IEICE
    \end{itemize}

\end{frame}


\begin{frame}[fragile]{Trabalhos futuros}
    \begin{itemize}
        \item Considerar variantes dos algoritmos para tratar de casos em que
        há informação limitada sobre os espectros (chave tem vida útil)
        \item Combinar o algoritmos probabilístico com o iterativo usando heurísticas
        \item Melhorar o algoritmo de estimação do espectro para escolher conjuntos de desafios (aleatórios)
              com maior probabilidade de falha de decodificação
        \item Verificar como o ataque afeta o MDPC-McEliece
        \item Estender a análise do número necessário de decodificações  para níveis de segurança mais altos
        e outros decodificadores
        \item Proteger o esquema encontrando decodificadores que falham com probabilidade independente
            do espectro do código

    \end{itemize}
\end{frame}
