Rechercher
Fermer ce champ de recherche.

Vous êtes victime d’un incident de sécurité ? Contactez notre CERT

04/06/2024

Blog technique

Why you should not put all your eggs in the same basket | Part 3

Lucile Razé & Gabriel Departout

Why you should not put all your eggs in the same basket.

A series about post-quantum cryptography

Part III: Hybridization’s DIY Tutorial

Welcome to the last part of this blog series about hybridization. In the first part here, we introduced why using quantum computer can threaten classical cryptography. In the second blog post, we presented a practical solution to the quantum threat, namely hybridization. This blog post will be more technical than the previous ones, we recommend you to read them before get into this one. The goal here is to give you the main methods to build hybrid KEM, PKE and digital signatures properly. These combiners come from the scientific literature, so they have been peer reviewed. For each primitive, we are going to give its target security and two viable combiners.

Key encapsulation mechanism combiners

Security

As depicted in the previous blog post, a KEM is an asymmetric cryptographic primitive used to exchange a secret key between two parties. Let’s consider K = ( KeyGen , Encaps , Decaps ) a KEM as defined in the second blog post, how can we be sure that K is secure? And what does it mean to be secure for a KEM?

A KEM is said to be secure if an attacker A cannot distinguish the real secret key shared using K from a random one in a reasonable time (less than 2256 classical elementary operations and less than 2128 quantum elementary operations). To do so, the imaginary attacker A can do queries to a decapsulation oracle: a black box that returns the key corresponding to the input ciphertext. If A does not succeed, the KEM achieve Key Indistinguishability under Chosen Ciphertext Attack (IND-CCA) security.

One can define a weaker variant of this security where the attacker does not have access to a decapsulation oracle (but he can still use Encaps because the only material needed is the public key, which is public): this is the IND-CPA security (Chosen Plaintext Attack). Notice that if the KEM is IND-CCA secure then it is also IND-CPA secure.

XOR combiner for KEM

After having generated a key pair with KeyGen and establish a shared secret k, it seems logical to throw away the key pair generated, we call them ephemeral keys. When using ephemeral keys, IND-CPA security is enough for your KEM (NIST, 2016). Here we are going to present a KEM combiner that preserves IND-CPA security. But first, let’s define a hybrid KEM.

Let K1 and K2 be two KEM and their associated functions KeyGeni, Encapsi and Decapsi. We define the hybrid KEM K and its associated functions as follow:

Where combined pki and ski are resp. the public and the private keys of the scheme Ki , W is a combiner who takes as input the two secret keys k1 and k2 established with each KEM and the combined ciphertext c = c1 || c2  and output the combined shared secret k. Now we can define our first combiner. We can define the hybrid KEM XOR ( K1 , K2 ) and its combiner by

W ( k1 , k2 , c ) = kk2

Figure 1- XOR combiner.

If K1 or K2 is IND-CPA secure, then XOR ( K1 , K2 ) is IND-CPA secure. The XOR combiner is a very simple and robust way to hybrid KEM when using an ephemeral key pair. You can for instance combine KYBER-1024 with DH-KEM (the KEM version of the Diffie-Hellman protocol) using the  combiner to get an IND-CPA hybrid KEM (because both underlying KEM are IND-CPA).

CatKDF combiner

Now a combiner for the IND-CCA security. We define the hybrid KEM CatKDF ( K1 , K2 )  and its combiner by:

W ( k1 , k2 , c ) = KDF ( k ||  k2 )

Figure 2- CatKDF combiner.

where KDF is a secure key derivation function (like HKDF for instance). If K1 or K2 is IND-CCA secure, then CatKDF ( K1 , K2 ) is IND-CCA secure. Note that the parameters of the KDF function must take into account the combined ciphertext  in its process. For instance, in HMAC-based KDF function (IETF, 2010), one need a salt to derive the secret, this salt could use the ciphertext as the random seed. Otherwise, one can attack the IND-CCA security of the hybrid KEM under certain assumptions about the malleability of K1 or K2 (assumptions that El-Gamal satisfies). The CatKDF combiner has been selected for the hybrid key exchange in TLS 1.3 (Gueron, 2024).

Public key encryption combiner

OW-CPA security

As depicted in the first blog post, a PKE is an asymmetric cryptographic primitive E = ( KeyGen , Encrypt , Decrypt ). We will see later how one can build a secure KEM based on a PKE. But first we need to introduce the security notion of One-Wayness under Chosen Plaintext Attack (OW-CPA). The idea is simple: can an attacker recover the plaintext from the ciphertext in a reasonable time? If not, the PKE is said OW-CPA secure. Every PKE must be at least OW-CPA secure (otherwise we strongly advise you not to use it).

XOR combiner for PKE

Let E1 and E2 be two PKE and their associated functions KeyGeniEncrypti , and Decrypti .We define the hybrid PKE XOR ( E1 , E2 ) as follow:

Where m1 is a random message picked from the messages space M.

Figure 3- XOR combiner for PKE.

If E1 or E2 is OW-CPA secure, then the PKE XOR ( E1 , E2 ) is OW-CPA secure.

FO transforms

This is quite nice already but remember: KEM is the new trend. Here is the plan, from our two PKE E1 and E2 OW-CPA secure, we managed to get a hybrid PKE E OW-CPA secure thanks to the XOR combiner for PKE described previously. Now we want an IND-CCA KEM. In (Kiltz, 2017), one can find what we call the Fujisaka-Okamoto transforms. These transformations, when combined properly, allow you to build an IND-CCA KEM from an OW-CPA PKE. This is exactly what we need. Here we present you the final construction which is a KEM K ( E1 , E2 ) .

Where H is a secure hash function (it has the role of a pseudo-random function. In the end, K ( E1 , E2 )  is IND-CCA secure if E1 or E2 is OW-CPA secure. This method is less documented in the literature, one can get more information here (Kiltz, 2017). Indeed, all the implementations proposed for the post-quantum schemes of the NIST competition are for the KEM and not for the underlying PKE. That may be the reason the first method is preferred.

Signatures combiners

EUF-CMA security

Last but not least, we have digital signatures. As a reminder, a signature is an asymmetric primitive S = ( KeyGen , Sign , Verif )  used to authenticate the party associated to a key pair. A signature scheme is secure if it’s impossible for an attacker A to forge a valid signature σ for a message m chosen by A in a reasonable time, even if A can query a signing oracle (a blackbox that signs an input message, but not m, it would be too easy). This is called the Existential Unforgeability under Chosen Message Attack (EUF-CMA) security.

CAT combiner for signatures

Let S1 and S2 be two signature schemes and their associated functions KeyGeni , Signi and Verifi , as defined in the second blog post. We define the hybrid signature CAT ( S1 , S2 ) as follow:

Figure 4- CAT combiner.

If S1 or S2 is EUF-CMA secure, then the hybrid signature CAT ( S1 , S2 ) is EUF-CMA secure. You can for instance combine FALCON-1024 and ECDSA using the CAT combiner to get a EUF-CMA hybrid signature, because both underlying schemes are EUF-CMA.

The CAT combiner is simple, maybe too simple. Let’s imagine the following scenario: Alice wants to sign a document m for Bob. Bob accepts hybrid signatures combining ECDSA and Dilithium, but in a transition context he may also accept only ECDSA signatures. Let σ be the hybrid signature σDSA || σDltm of m sent to Bob. Consider Eve, who spies on the channel between Alice and Bob and can modify the content of packets before retransmitting them. When Eve sees σ passing by, she can extract σDSA , which is a valid signature for m , and only retransmits it to Bob. This means that the signature Bob receives is not post-quantum, which was not Alice’s original intention. Indeed, using a quantum computer, Eve could alter m while keeping σDSA  valid. The next combiner we propose counter this downgrading attack.

Strong Nesting combiner

Let S1 and S2 be two signature schemes and their associated functions KeyGeni , Signi and Verifi . We define the hybrid signature StrNest ( S1 , S2 ) as follow:

Figure 5- Str-nest combiner.

If S1 or S2 is EUF-CMA secure, then the hybrid signature StrNest ( S1 , S2 ) is EUF-CMA secure. One can notice that you can still extract the valid signature S1 from the combined signature σ . That’s why we recommend S1 to be the post-quantum scheme, to assure at least the post-quantum security in the case of a downgrading attack.

What you should remember

In this blog series, we first depicted the consequences of the upcoming of the quantum computers for cryptography.

Hybridization seems to be the perfect solution to the tricky choice between choosing a post-quantum scheme that we cannot trust yet, or choosing a classic scheme we know well but that will probably be broken in one or two decades.

Just do not rush into standalone post-quantum protection for the moment, think hybridization. The ITSEF of AMOSSYS will be ready to advise you and assess products that use post-quantum cryptography by 2025. You can always come to say hello.

References

Gueron, D. S. (2024). Hybrid key exchange in TLS 1.3. IETF. https://www.ietf.org/archive/id/draft-ietf-tls-hybrid-design-09.html

IETF. (2010). HMAC-based Extract-and-Expand Key Derivation Function (HKDF). https://datatracker.ietf.org/doc/html/rfc5869

Kiltz, D. H. (2017). A Modular Analysis of the Fujisaki-Okamoto Transformation. https://eprint.iacr.org/2017/604

NIST. (2016). Call For Proposal. https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

Voir les derniers articles de notre Blog technique

4 juin 2024
A series about post-quantum cryptography: Part II: Hybridization
4 juin 2024
A serie about post-quantum cryptography: Part I: A Post-Quantum World
28 mai 2024
Cet article présente et expérimente AWARE (Attacks in Windows Architectures REvealed), un outil défensif capable d'interroger un système Windows et de construire un graphe dirigé mettant en évidence les chemins d'attaque furtifs.
28 mai 2024
Cet article présente la première proposition du format CAPG, qui est une méthode de représentation d'une vulnérabilité CVE, d'une exploitation correspondante et des positions d'attaque associées.
11 avril 2024
M&NTIS Platform est une solution SaaS destinée au test d'efficacité de produits de défense (AV, EDR, sondes réseau/NDR, SIEM, XDR, ...) et d'architectures de supervision. Une nouvelle version majeure de la plateforme vient de sortir.
25 mars 2024
Through this article, we propose a way to find LPE in Windows applications, by using SysInternals tools. What and how to look at? How to exploit in an easy and quick way?
31 janvier 2024
During the inter-CESTI challenge organized by ANSSI, many vulnerabilities were included to test our abilities to find them and, if possible, to exploit them. In this article, we explore one vulnerability that we found during the original challenge, and explainhow we exploited it: can we find a secret key from a singlesignature?
4 décembre 2023
Find here the crypto and reverse challenges that our teams created for the European Cyber Week pre-qualification and qualification tests of CTF, a recognized cybersecurity event that took place in Rennes from November 21 to 23, 2023.
29 mars 2023
On the 24th of January, AMOSSYS and Malizen put together a Blue Team CTF, for the SupSec seminar organized by Inria. In this blog post, we explain how we, at AMOSSYS, generated the dataset used in this challenge.
20 décembre 2022
Find here the crypto and web challenges that our teams created for the European Cyber Week pre-qualification tests of CTF, a recognized cybersecurity event that took place in Rennes from November 15 to 17, 2022.