Melhorando o ataque de reação contra o QC-MDPC McEliece (2017)
- Autores:
- Autor USP: PAIVA, THALES ARECO BANDIERA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assuntos: COMPUTABILIDADE E COMPLEXIDADE; CRIPTOLOGIA
- Palavras-chave do autor: Ataque de reação; Criptografia pós-quântica; Post-quantum cryptography; QC-MDPC; QC-MDPC; Reaction attack
- Agências de fomento:
- Idioma: Português
- Resumo: O QC-MDPC McEliece foi considerado um dos mais promissores esquemas criptográficos de chave pública que oferecem segurança contra ataques por computadores quânticos. O tamanho das chaves públicas do QC-MDPC McEliece é competitivo com o das chaves do RSA, e o esquema tem uma redução de segurança aparentemente forte. Por três anos, o esquema não sofreu ataques críticos, até que na Asiacrypt de 2016 Guo, Johansson, e Stankovski mostraram um ataque de reação contra o QC-MDPC McEliece que explora um aspecto não considerado em sua redução de segurança: a probabilidade de o algoritmo de decriptação falhar é menor quando a chave secreta e o vetor usado para encriptar a mensagem compartilham certas propriedades, chamadas de espectros. Dessa forma, um atacante pode, ao detectar falhas de decriptação, obter informação sobre o espectro, que será usada para reconstruir a chave secreta. Guo et al. apresentaram um algoritmo para a reconstrução da chave a partir do espectro recuperado, para o qual é possível apontar três problemas. O primeiro é que seu algoritmo não é eficiente quando o espectro da chave não foi recuperado quase completamente, o que resulta em o atacante ter que enviar um grande número de testes de decriptação à portadora da chave secreta. O segundo problema é que o desempenho de seu algoritmo não escala bem para níveis de segurança mais altos. O terceiro e último problema é que, por ser baseado numa busca em profundidade, seu algoritmo não pode ser paralelizadotrivialmente. Para aumentar a eficiência do ataque, dois novos algoritmos de reconstrução são propostos neste trabalho. Estes algoritmos são mais eficientes, usam menos informação sobre a chave secreta, e podem ser paralelizados trivialmente. O primeiro algoritmo é probabilístico e tem complexidade assintótica ligeiramente melhor do que a do original. Entretanto, o desempenho do algoritmo probabilístico piora rapidamente, embora mais lentamente do que o algoritmo de Guo et al., conforme a quantidade de informação sobre o espectro diminui. O segundo algoritmo explora uma relação linear entre os blocos da chave secreta. Este é mais eficiente, tanto assintoticamente quanto na prática, que os dois outros algoritmos, e é eficiente mesmo com 50% menos informação sobre o espectro do que o necessário para o algoritmo original. Isso permite que o atacante encontre a chave secreta fazendo apenas em torno de 20% do número de testes necessários pelo algoritmo de Guo\'s et al., considerando-se o nível de segurança de 80 bits. O desempenho de ambos os algoritmos são analisados e comparados com o do algoritmo original, e as análises são feitas tanto para a complexidade teórica quanto para o desempenho na prática, considerando a implementação dos algoritmos em linguagem C
- Imprenta:
- Data da defesa: 11.12.2017
-
ABNT
PAIVA, Thales Areco Bandiera. Melhorando o ataque de reação contra o QC-MDPC McEliece. 2017. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2017. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07012018-212020/. Acesso em: 23 abr. 2024. -
APA
Paiva, T. A. B. (2017). Melhorando o ataque de reação contra o QC-MDPC McEliece (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07012018-212020/ -
NLM
Paiva TAB. Melhorando o ataque de reação contra o QC-MDPC McEliece [Internet]. 2017 ;[citado 2024 abr. 23 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07012018-212020/ -
Vancouver
Paiva TAB. Melhorando o ataque de reação contra o QC-MDPC McEliece [Internet]. 2017 ;[citado 2024 abr. 23 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-07012018-212020/ - Attacking and defending post-quantum cryptography candidates
- Faster constant-time decoder for MDPC codes and applications to BIKE KEM
- Cryptanalysis of the binary permuted kernel problem
- Robust covert channels based on DRAM power consumption
- A timing attack on the HQC encryption scheme
- BGP anomalies classification using features based on AS relationship graphs
Como citar
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
