• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
10.11606/D.45.2018.tde-07012018-212020
Documento
Autor
Nombre completo
Thales Areco Bandiera Paiva
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2017
Director
Tribunal
Terada, Routo (Presidente)
Goya, Denise Hideko
Simplicio Junior, Marcos Antonio
Título en portugués
Melhorando o ataque de reação contra o QC-MDPC McEliece
Palabras clave en portugués
Ataque de reação
Criptografia pós-quântica
QC-MDPC
Resumen en portugués
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 paralelizado trivialmente. 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.
Título en inglés
Improving the efficiency of the reaction attack on the QC-MDPC McEliece
Palabras clave en inglés
Post-quantum cryptography
QC-MDPC
Reaction attack
Resumen en inglés
The QC-MDPC McEliece scheme was considered one of the most promising public key encryption schemes for efficient post-quantum secure encryption. As a variant of the McEliece scheme, it is based on the syndrome decoding problem, an NP-hard problem from Coding Theory. The key sizes are competitive with the ones of the widely used RSA cryptosystem, and it came with an apparently strong security reduction. For three years, the scheme has not suffered major threats, until the end of 2016, when Guo, Johansson, and Stankovski presented at Asiacrypt a reaction attack on the QC-MDPC that exploits one aspect that was not considered in the security reduction: the probability of a decoding failure to occur is lower when the secret key and the error used for encryption share certain properties, which they called spectrums. By detecting decoding failures, the attacker can obtain information on the spectrum of the secret key and then use this information to reconstruct the key. Guo et al. presented an algorithm for key reconstruction for which we can point three weaknesses. The first one is that it cannot deal efficiently with partial information on the spectrum of the secret key, resulting in the attacker having to send a great number of decoding trials. The second one is that it does not scale well for higher security levels. The third one is that the algorithm, which is based on a depth-first search, cannot be trivially parallelized. To improve the efficiency of the attack, we propose two different key reconstruction algorithms that are more efficient, use less information on the secret key, and can be trivially parallelized. The first algorithm, which is a simple probabilistic extension of Guo's et al. algorithm, is more efficient and runs increasingly faster, for higher security levels, than the original one. However, for security levels higher than 80 bits, the probabilistic algorithm cannot run efficiently without too much information on the spectrum of the secret key, even though it needs less information than the original algorithm. The second algorithm is based on a linear relation between the blocks of the secret key. It can run efficiently with around 50% less information than needed by Guo's et al. key reconstruction algorithm. This makes it possible for an attacker to recover the secret key sending approximately 20% of the of the number of decoding trials needed by Guo's et al. algorithm, for the security level of 80 bits. The performance of each presented algorithm is analyzed and compared with that of the original one. The analysis are made theoretically, considering a probabilistic analysis of the algorithms, and in practice, considering the corresponding implementations in C language.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
diss_ThalesPaiva.pdf (1,000.16 Kbytes)
Fecha de Publicación
2018-02-19
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2020. Todos los derechos reservados.