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. / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-07012018-212020 |
| Date | 11 December 2017 |
| Creators | Thales Areco Bandiera Paiva |
| Contributors | Routo Terada, Denise Hideko Goya, Marcos Antonio Simplicio Junior |
| Publisher | Universidade de São Paulo, Ciência da Computação, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0032 seconds