Post Quantum Cryptography

https://access.redhat.com/blogs/766093/posts/3031361?sc_cid=7016000000127ECAAY

The SSL/TLS protocol uses RSA, Diffie-Hellman (DH) or Elliptic Curve Diffie-Hellman (ECDH) primitives for the key exchange algorithm.

RSA is based on the fact that when given a product of two large prime numbers, factorizing the product (which is the public key) is computationally intensive, but a quantum computer could efficiently solve this problem using Shor’s algorithm. Similarly, DH and ECDH key exchanges could all be broken very easily using sufficiently large quantum computers.

For symmetric ciphers, the story is slightly different. It has been proven that applying Grover’s algorithm the strength of symmetric key lengths are effectively halved: AES-256 would have the same security against an attack using Grover’s algorithm that AES-128 has against classical brute-force search. Hashes are also affected in the same way symmetric algorithms are.

Therefore, we need new algorithms which are more resistant to quantum computations. This article introduces you to 5 proposals, which are under study.

204 Comments

  1. Tomi Engdahl says:

    https://blog.cloudflare.com/kemtls-post-quantum-tls-without-signatures

    The Transport Layer Security protocol (TLS), which secures most Internet connections, has mainly been a protocol consisting of a key exchange authenticated by digital signatures used to encrypt data at transport[1]. Even though it has undergone major changes since 1994, when SSL 1.0 was introduced by Netscape, its main mechanism has remained the same. The key exchange was first based on RSA, and later on traditional Diffie-Hellman (DH) and Elliptic-curve Diffie-Hellman (ECDH). The signatures used for authentication have almost always been RSA-based, though in recent years other kinds of signatures have been adopted, mainly ECDSA and Ed25519. This recent change to elliptic curve cryptography in both at the key exchange and at the signature level has resulted in considerable speed and bandwidth benefits in comparison to traditional Diffie-Hellman and RSA.

    TLS is the main protocol that protects the connections we use everyday. It’s everywhere: we use it when we buy products online, when we register for a newsletter — when we access any kind of website, IoT device, API for mobile apps and more, really. But with the imminent threat of the arrival of quantum computers (a threat that seems to be getting closer and closer), we need to reconsider the future of TLS once again. A wide-scale post-quantum experiment was carried out by Cloudflare and Google: two post-quantum key exchanges were integrated into our TLS stack and deployed at our edge servers as well as in Chrome Canary clients. The goal of that experiment was to evaluate the performance and feasibility of deployment of two post-quantum key exchanges in TLS.

    NIST post-quantum standardization process use mathematical objects that are larger than the ones used for elliptic curves, traditional Diffie-Hellman, or RSA. As a result, the overall size of public keys, signatures and key exchange material is much bigger than those from elliptic curves, Diffie-Hellman, or RSA.

    How can we solve this problem? How can we use post-quantum algorithms as part of the TLS handshake without making the material too big to be transmitted? In this blogpost, we will introduce a new mechanism for making this happen.

    TLS 1.3 was introduced in August 2018, and it brought many security and performance improvements (notably, having only one round-trip to complete the handshake). But TLS 1.3 is designed for a world with classical computers, and some of its functionality will be broken by quantum computers when they do arrive.

    We can estimate the impact of such a replacement on network traffic by simply looking at the sum of the cryptographic objects that are transmitted during the handshake. A typical TLS 1.3 handshake using elliptic curve X25519 and RSA-2048 would transmit 1,376 bytes, which would correspond to the public keys for key exchange, the certificate, the signature of the handshake, and the certificate chain. If we were to replace X25519 by the post-quantum KEM Kyber512 and RSA by the post-quantum signature Dilithium II, two of the more efficient proposals, the size transmitted data would increase to 10,036 bytes[4]. The increase is mostly due to the size of the post-quantum signature algorithm.

    KEMTLS, therefore, achieves the same goals as TLS 1.3 (authentication, confidentiality and integrity) in the face of quantum computers. But there’s one small difference compared to the TLS 1.3 handshake. KEMTLS allows the client to send encrypted application data in the second client-to-server TLS message flow when client authentication is not required, and in the third client-to-server TLS message flow when mutual authentication is required. Note that with TLS 1.3, the server is able to send encrypted and authenticated application data in its first response message (although, in most uses of TLS 1.3, this feature is not actually used). With KEMTLS, when client authentication is not required, the client is able to send its first encrypted application data after the same number of handshake round trips as in TLS 1.3.

    Cloudflare and KEMTLS: the implementation

    As part of our effort to show that TLS can be completely post-quantum safe, we implemented the full KEMTLS handshake in Golang’s TLS 1.3 suite.

    Reply
  2. Tomi Engdahl says:

    Kvanttisalaus vaatii jo ensimmäisiä toimia
    https://www.uusiteknologia.fi/2024/06/06/kvanttisalaus-vaatii-jo-ensimmaisia-toimia/

    Suomalaisen kriittisen verkko- ja muun infrastruktuurin toimijoista vasta murto-osa on varautunut kvanttitietokoneiden tulevaisuuden kykyyn murtaa salaukset tietoliikenteestä. Tämä ilmenee tutkimuskeskus VTT:n Huoltovarmuuskeskukselle tekemästä selvityksestä, jonka oheen on tehty myös alan yrityksille tietopaketti ja tiekartta tarvittavista muutoksista salausalgoritmeihin ja kriittiseen tiedonsiirtoon.

    Kvanttitietokoneiden arvioidaan saavuttavan 5–15 vuoden kuluttua kyvyn murtaa tietoliikenteen salaukset. Vaikka aikaa näyttäisi olevan, siirtymistä uudenlaiseen salaukseen ei ole VTT:n selvityksen mukaan syytä lykätä. Maailmantilanne on myös muuttunut. Vihamieliset valtiot ja kyberrikolliset voivat jo nyt tallentaa kannaltaan kiinnostavien organisaatioiden tietoliikennettä odottamaan aikaa, jolloin salaukset voidaan purkaa. Kvanttikoneiden kehitys voi myös edetä ennakoitua nopeammin.

    Selvityksen yhteyteen VTT ja Huoltovarmuuskeskus ovat laatineet kvanttiturvallisiin algoritmeihin siirtymisestä ohjeistavan varautumistiekartan, joka näyttää miten ja missä järjestyksessä kannattaa edetä, jos toimii kriittisen infrastruktuurien alalla. Siirtymä kvanttiturvalliseen salaukseen täytyy suunnitella ja sen toteuttamiseen täytyy varata resursseja. Tiekartan alkupuoleen kuuluu myös avainhenkilöstön koulutus ymmärtämään, miksi ja miten siirtyä kvanttiturvallisiin algoritmeihin.

    VTT:n selvityksen mukaan Yhdysvalloissa ja Britanniassa suositellaan, että siirrytään kerralla. Euroopassa Ranskassa ja Saksassa halutaan käyttää hybridimenetelmiä, jotka kuitenkin hidastavat toimintoja. Ne ovat myös mutkikkaampia, jolloin virheiden riski on suurempi. Suomessa valmius on selvästi jäljessä naapurimaista. Koko Eurooppa taas laahaa Yhdysvaltojen ja muiden englanninkielisten maiden perässä.

    Kriittisen infrastruktuurin haasteena on myös se, että uudet kvanttiturvalliset algoritmit vaativat nykyistä salausta enemmän muistia ja suorituskykyä.

    Reply
  3. Tomi Engdahl says:

    Quantinuum inches closer to fault-tolerant quantum with a 56 qubit machine
    This one only produces errors 65 percent of the time. Woo-hoo!
    https://www.theregister.com/2024/06/07/quantinuum_new_computer/

    Reply

Leave a Comment

Your email address will not be published. Required fields are marked *

*

*