Design, diffusion, and cryptanalysis of symmetric primitive

Abstract

Nessa tese de doutorado, novas técnicas de criptografia, criptoanálise e de desenvolvimento de algoritmos são estudadas e propostas. Resumidamente, os seguintes resultados são alcançados: • Uma técnica denominada Análise de Difusão Contínua (CDA) é proposta. Utilizandose essa técnica é possível se estudar, desenvolver e comparar algoritmos criptográficos. Com CDA é possível generalizar tais algoritmos a partir da transformação dos bits discretos em probabilidades, de tal forma que o algoritmo é generalizado em uma função matemática contínua. A partir disso, propõe-se três novas métricas de difusão a serem utilizadas nesse novo espaço contínuo, a saber: o Fator de Avalanche Contínuo (CAF), a Métrica de Neutralidade Contínua (CNM), e o Fator de Difusão (DF). Além disso, mostra-se que essas métricas de difusão podem ser utilizadas para avaliar e comparar algoritmos criptográficos. Em particular, o Fator de Difusão pode ser usado para comparar a difusão sem a necessidade de se reduzir o número de rodadas dos algoritmos criptográficos, algo inédito até então na área de criptografia. • Um novo método para avaliar a segurança de algoritmos criptográficos em relação à criptoanálise diferencial, denominado ColoreD, é proposto. Com o ColoreD, ao invés de se considerar apenas diferenças binárias (“pretas e brancas”), passa a ser possível o uso de diferenças contínuas. Isso é possível a partir do uso das generalizações contínuas que permitem que se considere diferenças menores do que 1 bit. Adicionalmente, com o método ColoreD, propõe-se novas ferramentas tais como a Criptoanálise Diferencial Contínua (CDC). Esta ferramenta viabiliza a implementação de ataques de recuperação de chave sem a necessidade de redução do número de rodadas para algoritmos complexos. Para demonstrar a utilidade dessa proposta, utiliza-se o ferramental ColoreD para estudar e comparar os algoritmos AES e PRESENT, duas cifras de bloco bastante conhecidas. Tal análise, leva a conclusão de que o algoritmo AES é mais seguro do que o PRESENT quando se considera a criptoanálise diferencial. Em particular, demonstra-se que o algoritmo PRESENT necessitaria de ao menos 37 rounds para atingir a mesma margem de segurança do AES. Finalmente, aplicando-se o CDC, é proposto um ataque capaz de recuperar chave desses algoritmos, a partir do uso de suas generalizações contínuas e de pares de entradas com diferenças bem pequenas. • Novas técnicas de criptoanálise contra algoritmos do tipo ARX são propostas. Primeiramente, uma nova forma de se gerar aproximações lineares é apresentada. Com tal técnica, demonstra-se ser possível encontrar aproximações lineares mais eficientes em cifras tipo ARX. Com tal técnica, propõe-se as primeiras aproximações lineares explicitamente derivadas para 3 e 4 rounds da cifra de fluxo ChaCha. Como consequência, novos ataques contra o ChaCha são apresentados, sendo possível reduzir a complexidade dos ataques para 2 51 e 2 224 bits de complexidade, contra 6 e 7 rodadas da cifra ChaCha, respectivamente. Adicionalmente, propõe-se uma nova técnica denominada Expansões Lineares Bidirecionais (BLE), capaz de aumentar a eficácia de distinguishers do tipo linear-diferencial. Usando a BLE, apresenta-se os primeiros distinguishers da literatura alcançando 7 e 8 rounds do algoritmo Salsa20 com complexidades de 2 108.98 e 2 215.62, respectivamente. Finalmente, demonstra-se que usando os novos diferenciais obtidos via BLE, é possível melhorar ataques de recuperação de chave do tipo Probabilistic Neutral Bits (PNB) contra 7 e 8 rodadas do algoritmo Salsa20, obtendo complexidades de 2 122.63 e 2 219.56, respectivamente. • Novas cifras de fluxo são propostas. Primeiramente, demonstra-se que é possível aplicar uma alteração bastante simples no algoritmo ChaCha, apenas pela alteração dos parâmetros de rotações na função de quarto de round (QRF), tornando o ChaCha mais seguro contra todos os ataques conhecidos sem perda de performance. De fato, com tais mudanças, deixa de ser possível quebrar 7 rounds do ChaCha, restando apenas ataques contra 6 rounds. Na sequência, a cifra Forró é proposta. Demonstra-se que o algoritmo Forró é capaz de atingir segurança maior do que a do ChaCha mesmo aplicando uma menor quantidade de operações matemáticas. Assim, conclui-se que 5 rounds do Forró é tão seguro quanto 7 rounds do ChaCha e que o algoritmo Forró é mais eficiente quando implementado em diversos tipos de processadores.