Analysis of the BIKE post-quantum cryptographic protocols and the Legendre pseudorandom function

Dusan Kostic
EPFL, 2020
Thèse EPFL

Résumé

The field of post-quantum cryptography studies cryptographic systems that are secure against an adversary in possession of a quantum computer. In 2017, the National Institute of Standards and Technology (NIST) initiated a process to standardize quantum-resistant public-key cryptographic algorithms (NIST PQC Project). In this thesis we analyze the performance and security of the Bit-Flipping Key Encapsulation Mechanism (BIKE) -- one of the candidates in the NIST PQC project which advanced to the second round of the standardization process. BIKE is a code-based cryptographic system featuring three different variants of the protocol. In the first round of the NIST PQC project BIKE offered security only against chosen-plaintext attacks (CPA). In the second round, BIKE introduced three new variants that are claimed to be secure also against chosen-ciphertext attacks (CCA). Firstly, we build a secure implementation of the CCA protocol and show that its performance characteristics are only negligibly worse than the CPA variant. In the key decapsulation phase of the protocol BIKE uses a decoding algorithm which fails with some probability, called the Decoding Failure Rate (DFR). We analyze the DFR of two decoders used in BIKE, Back-Flip and Black-Gray, and propose a new decoder, called Black-Gray-Flip, that achieves the same DFR as the two previously used decoders while being almost twice as fast. Finally, we propose an algorithm for inversion of binary polynomials in a polynomial ring used in BIKE-2, the second variant of BIKE. Our implementation of the inversion significantly outperforms previously used algorithms. With this and the fact that the bandwidth requirement for BIKE-2 is the smallest among the three variants, BIKE-2 is positioned as the preferable variant of BIKE. The second part of this thesis studies the Legendre pseudorandom function (PRF) which is proposed to be used in the context of blockchains. We present a new algorithm for cryptanalysis of the Legendre PRF. The complexity of our algorithm is lower than the previous best known algorithm. Moreover, we show the results of breaking three Legendre PRF challenges posed by the Ethereum foundation. The most difficult challenge that we solved set the new record which is not broken so far.

Official source

https://infoscience.epfl.ch/record/281361?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Dusan Kostic
EPFL, 2020
Thèse EPFL

Résumé

Official source

https://infoscience.epfl.ch/record/281361?ln=fr

À propos de ce résultat

Concepts associés (15)

Concepts associés

Chargement

Publications associées (15)

Chargement

Afficher plus

Publications associées

Chargement

Publications associées (15)

Bringing Theory Closer to Practice in Post-quantum and Leakage-resilient Cryptography

Alexandre Raphaël Duc

Modern cryptography pushed forward the need of having provable security. Whereas ancient cryptography was only relying on heuristic assumptions and the secrecy of the designs, nowadays researchers try to make the security of schemes to rely on mathematical problems which are believed hard to solve. When doing these proofs, the capabilities of potential adversaries are modeled formally. For instance, the black-box model assumes that an adversary does not learn anything from the inner-state of a construction. While this assumption makes sense in some practical scenarios, it was shown that one can sometimes learn some information by other means, e.g., by timing how long the computation take. In this thesis, we focus on two different areas of cryptography. In both parts, we take first a theoretical point of view to obtain a result. We try then to adapt our results so that they are easily usable for implementers and for researchers working in practical cryptography. In the first part of this thesis, we take a look at post-quantum cryptography, i.e., at cryptographic primitives that are believed secure even in the case (reasonably big) quantum computers are built. We introduce HELEN, a new public-key cryptosystem based on the hardness of the learning from parity with noise problem (LPN). To make our results more concrete, we suggest some practical instances which make the system easily implementable. As stated above, the design of cryptographic primitives usually relies on some well-studied hard problems. However, to suggest concrete parameters for these primitives, one needs to know the precise complexity of algorithms solving the underlying hard problem. In this thesis, we focus on two recent hard-problems that became very popular in post-quantum cryptography: the learning with error (LWE) and the learning with rounding problem (LWR). We introduce a new algorithm that solves both problems and provide a careful complexity analysis so that these problems can be used to construct practical cryptographic primitives. In the second part, we look at leakage-resilient cryptography which studies adversaries able to get some side-channel information from a cryptographic primitive. In the past, two main disjoint models were considered. The first one, the threshold probing model, assumes that the adversary can put a limited number of probes in a circuit. He then learns all the values going through these probes. This model was used mostly by theoreticians as it allows very elegant and convenient proofs. The second model, the noisy-leakage model, assumes that every component of the circuit leaks but that the observed signal is noisy. Typically, some Gaussian noise is added to it. According to experiments, this model depicts closely the real behaviour of circuits. Hence, this model is cherished by the practical cryptographic community. In this thesis, we show that making a proof in the first model implies a proof in the second model which unifies the two models and reconciles both communities. We then look at this result with a more practical point-of-view. We show how it can help in the process of evaluating the security of a chip based solely on the more standard mutual information metric.

EPFL2015

Chargement

Post-quantum cryptography is a branch of cryptography which deals with cryptographic algorithms whose hardness assumptions are not based on problems known to be solvable by a quantum computer, such as the RSA problem, factoring or discrete logarithms.This thesis treats two such algorithms and provides theoretical and practical attacks against them.The first protocol is the generalised Legendre pseudorandom function - a random bit generator computed as the Legendre symbol of the evaluation of a secret polynomial at an element of a finite field. We introduce a new point of view on the protocol by analysing the action of the group of Möbius transformations on the set of secret keys (secret polynomials).We provide a key extraction attack by creating a table which is cubic in the number of the function queries, an improvement over the previous algorithms which only provided a quadratic yield. Furthermore we provide an ever stronger attack for a new set of particularly weak keys.The second protocol that we cover is SIKE - supersingular isogeny key encapsulation.In 2017 the American National Institute of Standards and Technology (NIST) opened a call for standardisation of post-quantum cryptographic algorithms. One of the candidates, currently listed as an alternative key encapsulation candidate in the third round of the standardisation process, is SIKE.We provide three practical side-channel attacks on the 32-bit ARM Cortex-M4 implementation of SIKE.The first attack targets the elliptic curve scalar multiplication, implemented as a three-point ladder in SIKE. The lack of coordinate randomisation is observed, and used to attack the ladder by means of a differential power analysis algorithm.This allows us to extract the full secret key of the target party with only one power trace.The second attack assumes coordinate randomisation is implemented and provides a zero-value attack - the target party is forced to compute the field element zero, which cannot be protected by randomisation. In particular we target both the three-point ladder and isogeny computation in two separate attacks by providing maliciously generated public keys made of elliptic curve points of irregular order.We show that an order-checking countermeasure is effective, but comes at a price of 10% computational overhead. Furthermore we show how to modify the implementation so that it can be protected from all zero-value attacks, i.e., a zero-value is never computed during the execution of the algorithm.Finally, the last attack targets a point swapping procedure which is a subroutine of the three-point ladder. The attack successfully extracts the full secret key with only one power trace even if the implementation is protected with coordinate randomisation or order-checking. We provide an effective countermeasure --- an improved point swapping algorithm which protects the implementation from our attack.

EPFL2022

Chargement

Misuse Attacks on Post-quantum Cryptosystems

Ciprian Baetu, Fatma Betül Durak, Loïs Evan Huguenin-Dumittan, Abdullah Talayhan, Serge Vaudenay

Many post-quantum cryptosystems which have been proposed in the National Institute of Standards and Technology (NISI) standardization process follow the same meta-algorithm, but in different algebras or different encoding methods. They usually propose two constructions, one being weaker and the other requiring a random oracle. We focus on the weak version of nine submissions to NISI. Submitters claim no security when the secret key is used several times. In this paper, we analyze how easy it is to run a key recovery under multiple key reuse. We mount a classical key recovery under plaintext checking attacks (i.e., with a plaintext checking oracle saying if a given ciphertext decrypts well to a given plaintext) and a quantum key recovery under chosen ciphertext attacks. In the latter case, we assume quantum access to the decryption oracle.

SPRINGER INTERNATIONAL PUBLISHING AG2019

Chargement

Afficher plus

Bringing Theory Closer to Practice in Post-quantum and Leakage-resilient Cryptography

Alexandre Raphaël Duc

EPFL2015

EPFL2022