It seems like quantum computing is the core fusion of the tech industry: it’s always only a few years away, but that status hasn’t really changed for the past decade. However, since Google announced their “quantum supremacy” achievement back in 2019 and more recent news from IBM building a quantum computer with more than 400 qbits there are chances it won’t take very long indeed before quantum computing becomes the next big thing. For the cybersecurity industry that’s a big challenge, as some of the cryptography we use today will become obsolete. On the other hand, companies claiming to commercialize quantum safe cryptography – also called post quantum cryptography – have been springing up everywhere. And this development has been fueled by the announcement by NIST to start standardizing quantum-resistant public-key cryptographic algorithms.
We have covered quantum cryptography in the past, but we still wanted to know what the current status of development is and whether we need to worry about obsolete cryptography any time soon. We therefore spoke with someone who should be familiar with the latest trends in that area.
Matthew Campagna is a Sr. Principal Engineer & Cryptographer for Amazon Web Services Inc.’s. He oversees the design and analysis of cryptographic solutions across AWS. He is a member of the ETSI Security Algorithms Group Experts (SAGE), and Chairman of ETSI TC CYBER’s Quantum Safe Cryptography group.
Cyber Protection Magazine: As an introduction to the topic: What is quantum safe cryptography? And what is the TC QSC at ETSI working on?
Matthew Campagna: Quantum-Safe Cryptography or Post-Quantum Cryptography, refers to the development of cryptographic algorithms that run on classical computers that are not known to be vulnerable to a large-scale quantum computer, or a cryptographically-significant quantum computer.
ETSI TC CYBER QSC is working on standards and recommendations on the adoption of quantum-safe cryptography, or Technical Specifications and Technical Recommendations in the ETSI nomenclature.
We are updating an existing standard on quantum-safe hybrid key establishment. This specifies how to do a classical key exchange, like Elliptic Curve Diffie Hellman, with a quantum-safe scheme, in a manner that ensures the resulting key is as strong as its strongest component. We are updating it to reflect the most recent announcement from NIST’s Post-Quantum Cryptography Standardization Process.
We are also working on a series of recommendations around the adoption of quantum-safe cryptographic schemes, and the effect of quantum computing on symmetric key algorithms and various assumptions we make in our existing security proofs.
Cyber Protection Magazine: Today, there are different encryption algorithms used for different purposes. From a technological point of view, how does QSC differ from today’s cryptography? And why are symmetric encryptions apparently less at risk of being broken compared to asymmetric encryption algorithms.
Matthew Campagna: We can separate out two sets of cryptographic algorithms, symmetric cryptography, which uses a single secret key (typically shared between two parties), and asymmetric cryptography that uses a key pair (one private, and one public). A primary use-case for symmetric cryptography is data encryption and message authentication. We use asymmetric cryptography for key establishment between two parties and digital signatures. Key establishment results in a secret key shared between the parties that can be used for data encryption or message authentication.
QSC is primarily focused on new families of asymmetric algorithms for digital signatures and key establishment.
Most of the algorithms we use today are parametrized by a security level. If you want 128 bits of security, that means it should take on the order of 2^128 operations to break the security of the scheme using the best-known attack. So, if want 128 bits of security with the Advanced Encryption Standard (AES) we would use a 128-bit key. AES also supports 256-bit security using a 256-bit key. Similarly, we work backwards from a security level to a parameter size for asymmetric schemes like elliptic curve cryptography or RSA.
With quantum computing, the best-known attack on these asymmetric schemes is Shor’s algorithm, which effectively reduces the security of these schemes to the point they are considered broken against such an adversary.
By comparison, the best-known attack on a quantum computer for symmetric schemes is Grover’s algorithm, which reduces the security by a square root. That means if we want to obtain 128-bit security we could just extend the key size to 256-bit keys, and still maintain 128 bits of security against a quantum adversary.
The primary focus of quantum-safe cryptography today is to replace the asymmetric cryptographic algorithms with new quantum-resistant algorithms.
Cyber Protection Magazine: In 2019, Google announced that they have been able to built the first “real” quantum computer. Will we see quantum computer breaking current encryptions anytime soon?
Matthew Campagna: The current state-of-art in quantum-computing (roughly low 100s qubits) is a long-ways away from being a cryptographically relevant quantum computer (10s of millions of qubits). There are a lot of unresolved engineering hurdles to overcome. Quantum-computing is valuable when it can be used as general programmable computer that can perform computations that classical computing systems cannot efficiently run. There are a lot of valuable computations that a moderate size quantum computer can execute. A moderate scale quantum computer, and the value it can deliver, will appear before a large-scale quantum computer capable of breaking the asymmetric cryptography we use today.
Soon is a relative term to how long we expect the security of a cryptographic scheme to hold. If we need to authenticate a transaction, that happens in the moment, now, for instance, where we can be fairly certain that no large-scale quantum computer exists. You can’t go back in time with a quantum computer to circumvent what happened in the past. However, if I want my communication with my lawyer to be confidential, I might need that to stay confidential for 30 years. If a large-scale quantum computer can break that cryptosystem in the next 30 years, I could lose that confidentiality.
Cyber Protection Magazine: What will the implications on current cybersecurity technologies be, once quantum computers effectively render current cryptography solutions useless?
Matthew Campagna: There are two main concerns to the cybersecurity systems we use today:
The first is the long-lived requirement of confidentiality. Suppose we want our data to remain confidential for 30 years. Then we need to protect that data with algorithms and keys that we believe will be secure for the 30 years. If we look out 30 years, the probability of a large-scale quantum computer becomes a greater threat than we might accept for any classical vulnerability on our cryptographic algorithms. This means we need to start the work to replace the asymmetric schemes we use today to establish keys.
The second relates to our ability to upgrade the systems we deploy. Many security models rely on “burning in” a public key root of trust, to verify software upgrades. That is a key that is written to read-only-memory. Other models include devices that connect periodically to a network, and can go 5, 10 or even 20 years before they have the opportunity to connect to a network. Both of these use cases require shipping a device with a long-lived root of trust for digital signatures. Again, the threat of a large-scale quantum computer during this time period warrants considering an alternate, or quantum-resistant signature scheme.
Cyber Protection Magazine: ETSI is an organization that develops technological standards – so is NIST, and NIST has recently announced 4 finalist algorithms that might be used as a standard for quantum safe cryptography in the future. Is ETSI working together with NIST, and if so, how?
Matthew Campagna: ETSI loosely works with NIST through liaison statements, which is how one Working Group at ETSI communicates with other Standards Development Organizations or other ETSI Working Groups. However, many members of the QSC Technical Committee are also participants in the NIST PQC Standardization Process. The overall goal of its members is to align our work to the NIST process. For instance, our standard for Quantum-Safe Hybrid Key Establishment is being refined to align with the NIST algorithm selection for standardization.
Cyber Protection Magazine: From the last interview with your predecessor, we learned that cryptographic agility is key in preparing for the age of quantum computers. However, in many software solutions, this is not easily done and/or requires a huge number of computers and solutions to be updated. Will the industry be able to switch to cryptographic agility gradually or will we see hectic efforts once quantum computers are here, similar to what happened with the Y2K topic?
Matthew Campagna: It will be more similar to the transition from RSA cryptography to Elliptic Curve Cryptography. This was not a hectic transition, but it was slow. Systems, especially small ecosystems, requiring higher security levels and assurance transitioned first. I expect to see the adoption of QSC happen in phases. First, adopting quantum-safe hybrid key establishment to address applications with long-lived confidentiality concerns. Then the distribution of long-lived new quantum-safe roots of trust. At some point in the future, when we no longer believe the classical asymmetric schemes are providing value, we will transition to use only the quantum-safe schemes. This will take a decade. It would not be prudent to go faster. We are still analyzing these algorithms. Once standardized, we need to validate implementations for correctness, and harden them against errors and side-channel vulnerabilities.
It’s clear during this transition, crypto agility will be required, and we continue to emphasize the importance of agility in the design of systems and protocols.
Cyber Protection Magazine: How can companies protect data in the age of quantum computing? Do options for implementing quantum safe cryptography already exist and how can companies implement those?
Matthew Campagna: There are a few pq algorithms, like stateful Hash-Based Signature schemes that are standardized and widely accepted today. These tend to be unwieldy for other reasons, like state-management, performance, or bandwidth. The NIST PQC process will (hopefully) arrive at a more usable set of pq algorithms to replace the asymmetric schemes we are using today. It is too soon to rely solely on these schemes, they are still being analyzed, and may require changes that would break interoperability before they are standardized.
Companies can test these proposed algorithms in the protocols they are using today. There are many ways to do this today without sacrificing the existing security of how these protocols secure data. In particular, Amazon’s s2n-tls, includes post-quantum hybrid TLS, which combines the NIST selected Kyber, a Key Encapsulation Mechanism (KEM), with elliptic curve Diffie-Hellman (ECDH) in such a way that both schemes would need to be broken to break the security of the TLS handshake. There are a number of other implementations of post-quantum hybrid protocols at places like the Open Quantum Safe at the University of Waterloo. The ETSI TS on Hybrid Quantum Safe Key Establishment includes an open source implementation that can be downloaded from ETSI Forge (https://forge.etsi.org/rep/cyber/103744_QHKEX/tree/master).
Cyber Protection Magazine: Where do you see trends for the future, i.e. future interests of the members of the ETSI QSC group, especially once a standard has been finalized and agreed upon?
Matthew Campagna: Much of our initial work was focused on contributing to the NIST process by analyzing the candidates in the earlier rounds. Our current work is focused on how to adopt these emerging standards, like our recommendation on Migration to Quantum Safe Cryptography for the Intelligent Transport Systems, on Deployment Considerations for Hybrid Schemes, and our standard for Hybrid Quantum-Safe Key Establishment.
The working group will continue to develop recommendations and standards for adopting quantum safe cryptography for use cases important to our members and that are not addressed in other Standards Development Organizations (SDOs).
Cyber Protection Magazine: As blockchain cryptography (currently) is not quantum safe – what would the impact be, taking Bitcoin as an example. To phrase the question a bit provocative: will all my bitcoin be worthless once quantum computing is there?
Matthew Campagna: Bitcoin uses the elliptic curve digital signature algorithm (ECDSA) to sign transactions. That means to protect those funds, they would have to transition to a new post-quantum signature scheme before a large-scale quantum computer is available. There is time to transition to a pq-scheme without the loss of funds. This will take some careful planning and engineering. For instance, Bitcoin also uses BIP32, an algorithm that relies on the structure of elliptic curves to enable a Hierarchical Deterministic (HD) wallets. This algorithm is highly dependent on the underlying mathematical structure of elliptic curve cryptography. So, in addition to replacing ECDSA as a signature scheme, the new post-quantum scheme will also need to provide additional functionality the community enjoys today.