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.
213 Comments
Tomi Engdahl says:
https://www.microsoft.com/en-us/research/project/post-quantum-tls/
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.
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ä.
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/
Tomi Engdahl says:
SSH:n kvanttiturvalliselle NQX-salausratkaisulle kansallinen huipputason turvaluokitus
Anna Helakallio16.7.202407:41SALAUSTURVALLISUUSTIETOTURVATULEVAISUUDEN TEKNIIKAT
Uusi turvaluokitus kestää kolme vuotta
https://www.tivi.fi/uutiset/sshn-kvanttiturvalliselle-nqx-salausratkaisulle-kansallinen-huipputason-turvaluokitus/f00fcbd3-49b8-403b-b4c1-135d2911e7e7
Tomi Engdahl says:
NIST Announces Post-Quantum Cryptography Standards Three security standards are ready for use, with a fourth on the way
https://spectrum.ieee.org/post-quantum-cryptography-2668949802
Today, almost all data on the Internet, including bank transactions, medical records, and secure chats, is protected with an encryption scheme called RSA (named after its creators Rivest, Shamir, and Adleman). This scheme is based on a simple fact—it is virtually impossible to calculate the prime factors of a large number in a reasonable amount of time, even on the world’s most powerful supercomputer. Unfortunately, large quantum computers, if and when they are built, would find this task a breeze, thus undermining the security of the entire Internet.
Luckily, quantum computers are only better than classical ones at a select class of problems, and there are plenty of encryption schemes where quantum computers don’t offer any advantage. Today, the U.S. National Institute of Standards and Technology (NIST) announced the standardization of three post-quantum cryptography encryption schemes. With these standards in hand, NIST is encouraging computer system administrators to begin transitioning to post-quantum security as soon as possible.
“Now our task is to replace the protocol in every device, which is not an easy task.”
—Lily Chen, NIST
“Today, public key cryptography is used everywhere in every device,” Chen says. “Now our task is to replace the protocol in every device, which is not an easy task.”
Why we need post-quantum cryptography now
Most experts believe large-scale quantum computers won’t be built for at least another decade. So why is NIST worried about this now? There are two main reasons.
First, many devices that use RSA security, like cars and some IoT devices, are expected to remain in use for at least a decade. So they need to be equipped with quantum-safe cryptography before they are released into the field.
Second, a nefarious individual could potentially download and store encrypted data today, and decrypt it once a large enough quantum computer comes online. This concept is called “harvest now, decrypt later“ and by its nature, it poses a threat to sensitive data now, even if that data can only be cracked in the future.
Security experts in various industries are starting to take the threat of quantum computersseriously, says Joost Renes, principal security architect and cryptographer at NXP Semiconductors. “Back in 2017, 2018, people would ask ‘What’s a quantum computer?’” Renes says. “Now, they’re asking ‘When will the PQC standards come out and which one should we implement?’”
NIST announced a public competition for the best PQC algorithm back in 2016. They received a whopping 82 submissions from teams in 25 different countries. Since then, NIST has gone through 4 elimination rounds, finally whittling the pool down to four algorithms in 2022.
These four winning algorithms had intense-sounding names: CRYSTALS-Kyber, CRYSTALS-Dilithium, Sphincs+, and FALCON. Sadly, the names did not survive standardization: The algorithms are now known as Federal Information Processing Standard (FIPS) 203 through 206. FIPS 203, 204, and 205 are the focus of today’s announcement from NIST. FIPS 206, the algorithm previously known as FALCON, is expected to be standardized in late 2024.
Two out of the three schemes already standardized by NIST, FIPS 203 and FIPS 204 (as well as the upcoming FIPS 206), are based on another hard problem, called lattice cryptography. Lattice cryptography rests on the tricky problem of finding the lowest common multiple among a set of numbers. Usually, this is implemented in many dimensions, or on a lattice, where the least common multiple is a vector.
The third standardized scheme, FIPS 205, is based on hash functions
central problem at the heart of all cryptography schemes: There is no proof that any of the math problems the schemes are based on are actually “hard.” The only proof, even for the standard RSA algorithms, is that people have been trying to break the encryption for a long time, and have all failed.
NIST’s announcement is exciting, but the work of transitioning all devices to the new standards has only just begun. It is going to take time, and money, to fully protect the world from the threat of future quantum computers.
“We’ve spent 18 months on the transition and spent about half a million dollars on it,” says Marty of LGT Financial Services. “We have a few instances of [PQC], but for a full transition, I couldn’t give you a number, but there’s a lot to do.”
Tomi Engdahl says:
Announcing Approval of Three Federal Information Processing Standards (FIPS) for Post-Quantum Cryptography
August 13, 2024
https://csrc.nist.gov/News/2024/postquantum-cryptography-fips-approved
The Secretary of Commerce has approved three Federal Information Processing Standards (FIPS) for post-quantum cryptography:
FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard
FIPS 204, Module-Lattice-Based Digital Signature Standard
FIPS 205, Stateless Hash-Based Digital Signature Standard
These standards specify key establishment and digital signature schemes that are designed to resist future attacks by quantum computers, which threaten the security of current standards. The three algorithms specified in these standards are each derived from different submissions to the NIST Post-Quantum Cryptography Standardization Project.
FIPS 203 specifies a cryptographic scheme called the Module-Lattice-Based Key-Encapsulation Mechanism Standard, which is derived from the CRYSTALS-KYBER submission.
FIPS 204 and 205 each specify digital signature schemes, which are used to detect unauthorized modifications to data and to authenticate the identity of the signatory. FIPS 204 specifies the Module-Lattice-Based Digital Signature Standard, which is derived from CRYSTALS-Dilithium submission. FIPS 205 specifies the Stateless Hash-Based Digital Signature Standard, which is derived from the SPHINCS+ submission.
Tomi Engdahl says:
Frederic Lardinois / TechCrunch:
The US NIST publishes its first three post-quantum cryptography standards; IBM’s director of research thinks quantum will hit an inflection point around 2030 — It’ll still be a while before quantum computers become powerful enough to do anything useful, but it’s increasingly likely …
The first post-quantum cryptography standards are here
https://techcrunch.com/2024/08/13/the-first-post-quantum-cryptography-standards-are-here/?guccounter=1&guce_referrer=aHR0cHM6Ly93d3cudGVjaG1lbWUuY29tLw&guce_referrer_sig=AQAAAJMZevVzp3QppLycVFq9mC8mKfDsE6GEexiHjfz1qpzSoosAyNScqQo4kwG2bTBQLDtqSbwsVloEnNt8XJzMPJ4l1cKFKNvfm-fM-QiEy7ze3m4wE8xysv1KWMznO3_y2Oqauulp13ARgChyYx3dmqGG4FLZp9WOBJznI31uGyS6
It’ll still be a while before quantum computers become powerful enough to do anything useful, but it’s increasingly likely that we will see full-scale, error-corrected quantum computers become operational within the next five to 10 years. That’ll be great for scientists trying to solve hard computational problems in chemistry and material science, but also for those trying to break the most common encryption schemes used today. That’s because the mathematics of the RSA algorithm that, for example, keep the internet connection to your bank safe, are almost impossible to break with even the most powerful traditional computer. It would take decades to find the right key. But these same encryption algorithms are almost trivially easy for a quantum computer to break.
“Then the question is, from that point on, how many years until you have systems capable of [breaking RSA]? That’s open for debate, but suffice to say, we’re now in the window where you’re starting to say: all right, so somewhere between the end of the decade and 2035 the latest — in that window — that is going to be possible. You’re not violating laws of physics and so on,” he explained.
One excuse for this, he said, is that there weren’t any standards yet, which is why the new standards announced Tuesday are so important (and the process for getting to a standard, it’s worth noting, started in 2016).
Even though many CISOs are aware of the problem, Gil said, the urgency to do something about it is low. That’s also because for the longest time, quantum computing became one of those technologies that, like fusion reactors, was always five years out from becoming a reality. After a decade or two of that, it became somewhat of a running joke. “That’s one uncertainty that people put on the table,” Gil said. “The second one is: OK, in addition to that, what is it that we should do? Is there clarity in the community that these are the right implementations? Those two things are factors, and everybody’s busy. Everybody has limited budgets, so they say: ‘Let’s move that to the right. Let’s punt it.’ The task of institutions and society to migrate from current protocols to the new protocol is going to take, conservatively, decades. It’s a massive undertaking.”
It’s now up to the industry to start implementing these new algorithms. “The math was difficult to create, the substitution ought not to be difficult,” Gil said about the challenge ahead, but he also acknowledged that that’s easier said than done.
Indeed, a lot of businesses may not even have a full inventory of where they are using cryptography today. Gil suggested that what’s needed here is something akin to a “cryptographic bill of materials,” similar to the software bill of materials (SBOM) that most development teams now generate to ensure that they know which packages and libraries they use in building their software.
Like with so many things quantum, it feels like now is a good time to prepare for its arrival — be that learning how to program these machines or how to safeguard your data from them. And, as always, you have about five years to get ready.
Tomi Engdahl says:
https://etn.fi/index.php/13-news/16483-nyt-ne-ovat-valmiit-salausstandardit-kestaevaet-kvanttikonehyoekkaeykset
Tomi Engdahl says:
Race to develop quantum-resistant encryption intensifies: https://ie.social/Njw2d
Breakthrough quantum algorithm can break advanced data encryption
https://interestingengineering.com/science/quantum-algorithm-mit-crack-advanced-encryption?utm_source=facebook&utm_medium=article_image
The widely-used RSA encryption system relies on the difficulty of factoring extremely large numbers, a task that classical computers cannot accomplish in a reasonable timeframe.
Tomi Engdahl says:
https://etn.fi/index.php/13-news/16543-suomalaistekniikka-tuo-laitteisiin-kvanttiturvallisen-kaeynnistyksen
Kryptografiaratkaisuja kehittävä suomalainen Xiphera on esitellyt uusimman tuotteensa, joka tuo kvanttiturvallisen todennuksen käynnistyskuville ja laiteohjelmistopäivityksille. Tuote on nimeltään nQrux Secure Bootin, ja se tulee osaksi yhtiön nQrux Hardware Trust Engines -perhettä.
Tomi Engdahl says:
Meta warns of looming ‘quantum apocalypse’ for modern encryption, cryptography standards
Meta said that protecting asymmetric cryptography used by blockchains is the company’s top priority related to quantum computing.
https://cryptoslate.com/meta-warns-of-looming-quantum-apocalypse-for-modern-encryption-cryptography-standards/
Tomi Engdahl says:
‘Unbreakable’ quantum communication closer to reality thanks to new, exceptionally bright photons
https://www.livescience.com/technology/communications/unbreakable-quantum-communication-closer-to-reality-thanks-to-new-exceptionally-bright-photons
Scientists build a new light source for quantum communications by combining existing technologies together to create a stronger and more robust quantum signal.