In response to the threat of a future, large-scale, quantum computer, the American National Institute of Standards and Technology (NIST) initiated a competition for designs of quantum-resistant cryptographic primitives. In 2022, the lattice-based Module-Learning With Errors (M-LWE) scheme Kyber emerged as the winner to be standardized. The standardization procedure and development of secure implementations call for thorough evaluation and research. One of the main threats to implementations of cryptographic algorithms today is Side-Channel Analysis (SCA), which is the topic of this thesis. Previous work has presented successful power-based attacks on implementations of lattice cryptography protected by masking and even masking combined with shuffling. Shuffling makes SCA harder as the order of independent instructions is randomized, reducing the correlation between operations and power consumption. This randomization is commonly implemented by shuffling the order of the indexes used to iterate over a loop, using the modern Fisher-Yates algorithm. This work describes a new attack that defeats the shuffling countermeasure by first attacking the generation of the index permutation itself. The attack first recovers the positions of the first and last indexes, 0 and 255, and then rotates the encrypted messages using a ciphertext malleability applicable to many ring-based LWE schemes to shift two bits into the known positions from which they can be recovered. This procedure is repeated to recover full messages in 128 rotations. The attack is tested and evaluated on masked and shuffled implementations of Kyber as well as Saber, another similar finalist of the NIST competition which is based on the Module-Learning With Rounding (M-LWR) problem. Compared to the previous attack on masked and shuffled Saber, which required 61,680 traces, the 4,608 needed for this attack demonstrates a 13-fold improvement. / Som svar på hotet från en framtida, storskalig kvantdator initierade amerikanska National Institute of Standards and Technology (NIST) en tävling för design av kvantsäker kryptografi. Den gitter-baserade Module-Learning With Errors algoritmen Kyber valdes 2022 till vinnare och därmed till att standardiseras. Standardiseringsprocessen och utvecklingen av säkra implementationer manar till utvärderingar och forskning. Ett av de primära hoten mot implementationer av kryptografiska algoritmer är sidokanalsanalys, vilket är fokus i detta arbete. Tidigare attacker har genom effektanalys demonsterat lyckade attacker på implementationer av gitter-baserade algoritmer skyddade genom maskering samt maskering och slumpad ordning av operationer. Slumpad ordning av oberoende operationer gör sidokanalsanalys svårare då korrelationen till effektförbrukningen minskar. Denna slumpordning brukar vanligtiv implementeras genom att slumpmässigt permutera, med den moderna implementationen av Fisher-Yates, de index som används i en kodslinga. I detta arbete presenteras en ny attack som till först extraherar positionen av det första och det sista indexen, 0 och 255, innan de två motsvarande meddelandebitarna extraheras. Bitarna i meddelandet roteras till de kända positionerna med en metod för skiffertextmanipulation som är vanlig bland ring-baserade LWE-designer. Denna process upprepas 128 gånger för att få fram hela meddelandet. Attacken has testats och utvärderats på implementationer, skyddade genom maskering kombinerad med slumpad operationsordning, av både Kyber och en liknande NIST-finalist, Saber. Jämfört med den tidigare attacken på Saber med samma skyddsåtgärder minskar den nya metoden det antal mätningar som krävs från 61,608 till 4,608, vilket motsvarar en 13-falding förbättring.

A criptografia de chave pública sem certificado (certificateless) é uma alternativa ao modelo convencional de criptografia assimétrica, pois a autenticação da chave pública ocorre implicitamente durante a execução dos protocolos, sem a necessidade de gerenciamento e distribuição de certificados digitais. Potencialmente reduz custos computacionais e o nível de segurança alcançado é maior quando comparado ao modelo baseado em identidade. Nesta tese de doutorado, modelos formais de segurança para acordo de chave com autenticação sem certificado são aprimorados visando dois objetivos paralelos: (1) aumentar o nível de confiança que usuários podem depositar na autoridade geradora de chaves secretas parciais e (2) viabilizar protocolos que sejam eficientes computacionalmente e com propriedades de segurança relevantes, dentre as quais se inclui resistência a ataques de adversários que têm total controle do canal de comunicação e que podem substituir chaves públicas de usuários por valores arbitrários. Para atestar que as melhorias efetuadas são praticáveis e possibilitam que os objetivos sejam alcançados, novos protocolos são propostos para o caso que envolve dois participantes na comunicação. Os protocolos são provados seguros, usando-se técnica de redução de problemas computacionais. / Certificateless public key cryptography is an alternative model to traditional asymmetric key cryptography, because the public key authentication occurs implicitly during a protocol run, with no need of digital certificates management and distribution. It has the potential to reduce computing costs, and it allows a higher security level than the one in the identity-based model. In this PhD thesis, formal security models for certificateless authenticated key agreement are improved with two independent objectives: (1) to increase the trust level for the partial secret key generating authority on which users rely, and (2) to enable computationally efficient protocols, with significant security properties, such as resistance against attacks from adversaries with full control of the communication channel, and from adversaries who are able to replace users\' public keys by any chosen value. In order to demonstrate that these improvements made are feasible and achieve the objectives, new protocols are proposed in the two-party case. These protocols are proved secure by using reduction techniques for provable security.

Le premier protocole cryptographique basé sur les codes correcteurs d'erreurs a été proposé en 1978 par Robert McEliece. La cryptographie basée sur les codes est dite post-quantique car il n'existe pas à l'heure actuelle d'algorithme capable d'attaquer ce type de protocoles en temps polynomial, même en utilisant un ordinateur quantique, contrairement aux protocoles basés sur des problèmes de théorie des nombres. Toutefois, la sécurité du cryptosystème de McEliece ne repose pas uniquement sur des problèmes mathématiques. L'implantation, logicielle ou matérielle, a également un rôle très important pour sa sécurité et l'étude de celle-ci face aux attaques par canaux auxiliaires/cachés n'a débuté qu'en 2008. Des améliorations sont encore possibles. Dans cette thèse, nous proposons de nouvelles attaques sur le déchiffrement du cryptosystème de McEliece, utilisé avec les codes de Goppa classiques, ainsi que des contre-mesures correspondantes. Les attaques proposées sont des analyses de temps d'exécution ou de consommation d'énergie. Les contre-mesures associées reposent sur des propriétés mathématiques et algorithmiques. Nous montrons qu'il est essentiel de sécuriser l'algorithme de déchiffrement en le considérant dans son ensemble et non pas seulement étape par étape / The first cryptographic protocol based on error-correcting codes was proposed in 1978 by Robert McEliece. Cryptography based on codes is called post-quantum because until now, no algorithm able to attack this kind of protocols in polynomial time, even using a quantum computer, has been proposed. This is in contrast with protocols based on number theory problems like factorization of large numbers, for which efficient Shor's algorithm can be used on quantum computers. Nevertheless, the McEliece cryptosystem security is based not only on mathematical problems. Implementation (in software or hardware) is also very important for its security. Study of side-channel attacks against the McEliece cryptosystem have begun in 2008. Improvements can still be done. In this thesis, we propose new attacks against decryption in the McEliece cryptosystem, used with classical Goppa codes, including corresponding countermeasures. Proposed attacks are based on evaluation of execution time of the algorithm or its power consumption analysis. Associate countermeasures are based on mathematical and algorithmic properties of the underlying algorithm. We show that it is necessary to secure the decryption algorithm by considering it as a whole and not only step by step

A criptografia de chave pública sem certificado (certificateless) é uma alternativa ao modelo convencional de criptografia assimétrica, pois a autenticação da chave pública ocorre implicitamente durante a execução dos protocolos, sem a necessidade de gerenciamento e distribuição de certificados digitais. Potencialmente reduz custos computacionais e o nível de segurança alcançado é maior quando comparado ao modelo baseado em identidade. Nesta tese de doutorado, modelos formais de segurança para acordo de chave com autenticação sem certificado são aprimorados visando dois objetivos paralelos: (1) aumentar o nível de confiança que usuários podem depositar na autoridade geradora de chaves secretas parciais e (2) viabilizar protocolos que sejam eficientes computacionalmente e com propriedades de segurança relevantes, dentre as quais se inclui resistência a ataques de adversários que têm total controle do canal de comunicação e que podem substituir chaves públicas de usuários por valores arbitrários. Para atestar que as melhorias efetuadas são praticáveis e possibilitam que os objetivos sejam alcançados, novos protocolos são propostos para o caso que envolve dois participantes na comunicação. Os protocolos são provados seguros, usando-se técnica de redução de problemas computacionais. / Certificateless public key cryptography is an alternative model to traditional asymmetric key cryptography, because the public key authentication occurs implicitly during a protocol run, with no need of digital certificates management and distribution. It has the potential to reduce computing costs, and it allows a higher security level than the one in the identity-based model. In this PhD thesis, formal security models for certificateless authenticated key agreement are improved with two independent objectives: (1) to increase the trust level for the partial secret key generating authority on which users rely, and (2) to enable computationally efficient protocols, with significant security properties, such as resistance against attacks from adversaries with full control of the communication channel, and from adversaries who are able to replace users\' public keys by any chosen value. In order to demonstrate that these improvements made are feasible and achieve the objectives, new protocols are proposed in the two-party case. These protocols are proved secure by using reduction techniques for provable security.

Indiana University-Purdue University Indianapolis (IUPUI) / Blömmer, Otto, and Seifert presented a fault attack on elliptic curve scalar multiplication called the Sign Change Attack, which causes a fault that changes the sign of the accumulation point. As the use of a sign bit for an extended integer is highly unlikely, this appears to be a highly selective manipulation of the key stream. In this thesis we describe two plausible fault attacks on a smart card implementation of elliptic curve cryptography. King and Wang designed a new attack called counter fault attack by attacking the scalar multiple of discrete-log cryptosystem. They then successfully generalize this approach to a family of attacks. By implementing King and Wang's scheme on RSA, we successfully attacked RSA keys for a variety of sizes. Further, we generalized the attack model to an attack on any implementation that uses NAF and wNAF key.