Efficient implementation of cryptography hash functions : SHA-3 and QUARK

Orientador: Julio César López HernándezDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: As funções de resumo criptográfico são primitivas de extrema importância, pois são necessárias para a construção de inúmeros protocolos de segurança. Em 2007, o Instituto Nacional de Padrões e Tecnologias americano (NIST) iniciou um concurso público para escolher um novo padrão de funções de resumo criptográfico, conhecido por SHA-3; tal concurso teve fim em 2012, tendo como vencedor o algoritmo Keccak. A família SHA-3 tende a ser usada em larga escala nos próximos anos e é importante desenvolver implementações eficientes e seguras destas funções; uma estratégia que pode ser usada é aproveitar conjuntos avançados de instruções vetoriais. Os processadores de propósito geral estão expandindo cada vez mais seus conjuntos de instruções; em 2013, a microarquitetura Haswell da Intel trouxe consigo o conjunto de instruções vetoriais AVX2, que expandiu as instruções de aritmética inteira nos registradores de 128 e 256 bits. Um dos objetivos gerais desta dissertação foi prover técnicas que viabilizem o uso eficiente dos conjuntos de instruções vetoriais na implementação do algoritmo SHA-3; este estudo culminou em um conjunto de implementações eficientes que usam registradores de 128 e 256 bits para calcular um, dois ou quatro valores de resumo concorrentemente, permitindo uma aceleração de 1,89 e 2,57 vezes na computação de dois e quatro valores de resumo, respectivamente. Adicionalmente, também foram estudadas funções de resumo criptográfico para dispositivos com recursos limitados; tais dispositivos estão ganhando cada vez mais mercado, sendo usados principalmente para a Internet das Coisas (IoT). A maioria dos algoritmos criptográficos desenvolvidos para esses dispositivos foram projetados para serem implementados em hardware; do ponto de vista de implementação em software, esses algoritmos apresentam desafios para realizar uma implementação eficiente e segura. O QUARK é um algoritmo que foi projetado neste contexto; ele é uma família de funções de resumo que possui um bom desempenho em hardware, mas não possui implementações em software eficientes para processadores de 32 bits. Neste contexto, foram realizadas otimizações algorítmicas e de implementação no QUARK que permitiram acelerar sua execução na plataforma Intel Galileo, atingindo um ganho de desempenho de aproximadamente 15 vezes quando comparado com a implementação de referênciaAbstract: Cryptographic hash functions are extremely important primitives, as they are necessary for the construction of several cryptographic protocols. In 2007, the National Institute of Standards and Technology (NIST) started a competition to select the new version of the SHA algorithm family, called SHA-3; this competition ended in 2012, having Keccak as the winner. The SHA-3 family is expected to be used on a large scale in the coming years, so it is important to have fast and secure implementations of these functions; a strategy that can be used is to take advantage of the advanced instruction sets. General purpose processors are increasingly expanding their instruction sets; in 2013 the Intel's microarchitecture, Haswell, brought the set of vector instructions AVX2 that expanded the integer arithmetic instructions in the registers of 128 and 256 bits. One of the general goals of this work was to provide techniques that facilitate the efficient use of sets of vector instructions in implementing the SHA-3 algorithm; this study culminated in a set of efficient implementations that use registers of 128 and 256 bits to calculate one, two or four hash values concurrently, allowing to compute two and four hash values 1.89 and 2.57 times faster, respectively. Additionally, cryptographic hash functions for resource-constrained devices were also studied; such devices are being used widely, mainly for the Internet of Things (IoT). Most of the cryptographic algorithms developed for these devices were designed to be implemented in hardware; from the point of view of software implementation, those algorithms present challenges to achieve a fast and secure implementation. QUARK is a family of lightweight hash functions that was designed for hardware implementation. In this work, we propose some algorithmic optimizations to obtain a fast software implementation of QUARK on the Intel Galileo platform, achieving a speedup of 15 times compared to the reference implementationMestradoCiência da ComputaçãoMestre em Ciência da Computação301566/2014-3CNPQCAPE