Root finding techniques in binary finite fields

Abstract

Com a disseminação da Internet, a comunicação entre pessoas e o acesso a informação se tornou instantâneo. O principal mecanismo que garante essa comunicação de forma segura e privada é a criptografia. Atualmente, os protocolos criptográficos utilizados para realizar a troca de mensagens segura são baseados em problemas matemáticos que podem ser considerados inseguros com o avanço da computação quântica. A fim de criar novos padrões de criptografia, o Instituto de Padrões e Tecnologia (NIST), abriu um processo de padronização de esquemas que sejam seguros contra ataques clássicos e quânticos. Como consequência, a implementação desses novos esquemas precisa ser realizada de forma com que não seja possível realizar um ataque de efeito colateral. Este trabalho apresenta um ataque a um esquema criptográfico baseado em códigos de correção de erro submetido ao NIST, o BIGQUAKE. Este esquema é baseado no clássico trabalho de McEliece, e em sua fase de decodificação, durante o algoritmo de Paterson, os autores do BIGQUAKE não utilizam um método constante. Adicionalmente, contramedidas a esse ataque são apresentadas, comparadas e avaliadas para que seja possível construir um esquema seguro.

Abstract: In the last few years, post-quantum cryptography has received much attention. National Institute Standards and Technology (NIST) is running a competition to select some post-quantum schemes as standard. As a consequence, implementations of post-quantum schemes have become important and with them side-channel attacks. In this work, we show a timing attack on a code-based scheme which was submitted to the NIST competition. This timing attack recovers secret information because of a timing variance in finding roots in a polynomial. We present five algorithms to find roots that are protected against timing exploitation.