How Quantum Computing Will Change Browser Encryption

In 2015, The NSA’s Information Assurance Directorate issued guidance to postpone moving from RSA cryptography to elliptic curve cryptography (ECC) if they hadn’t already done so. The guidance stated:

For those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum-resistant algorithm transition.

The timing of the announcement was curious. Many in the crypto community wondered if there had been a quantum computing breakthrough significant enough to warrant the NSA’s concern. Since then, the crypto community has been trying to prepare for the transition to “quantum-resistant" algorithms — that is, algorithms that are secure against an attack by a quantum computer. Let’s look at some of the likely candidates for those algorithms and how they’ll be fitted into the Transport Layer Security (TLS) protocol that we all use today with HTTPS. But first, a bit of explanation.

If the day ever comes when a real, working, large-scale quantum computer can be built, then the era after that moment will become known as the “post-quantum” era. Encryption algorithms used in the "post-quantum" era should be puzzles that are not easily solved by quantum computers.

What’s the Current Quantum Computing Exposure?
Cryptographers currently believe that asymmetric encryption algorithms are vulnerable to quantum computing. Unfortunately, these include all the ones we use for TLS protocol handshakes!

Interestingly, a 2017 paper, Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms, by Martin Roetteler, Michael Naehrig, Krysta M. Svore, and Kristin Lauter, appears to confirm suspicions that ECC will fall to quantum computing before RSA does. That may have been another factor in the NSA’s announcement.

Symmetric algorithms (used by bulk encryption) are thought to be safe from quantum computing by merely doubling their key sizes, for example, using the advanced encryption standard AES-256 instead of AES-128.

How Post-Quantum Computing Will Affect TLS
So, what’s the problem that quantum computing introduces? Before we look at that, let’s start with the good news, which is that record processing in a quantum computing world will be exactly the same. That’s because the symmetric encryption ciphers (like AES) and hash message authentication code  (HMAC) hashing algorithms (like SHA) are thought to be mostly resistant to quantum computing, requiring only a doubling of key size to be resistant until the end of time. According to the NSA’s Information Assurance Directorate, "The AES-256 and SHA-384 algorithms are symmetric, and believed to be safe from attack by a large quantum computer."

F5 Labs’ own research shows that 75% of TLS hosts on the Internet already prefer AES-256, so we’re practically there already—at least for the record processing!

That leaves just the asymmetric encryption functions that need to be replaced: RSA, DSA, DH and their ECC variants, ECDSA and ECDH. Those are only used during the initial handshake phase of the TLS protocol, which for many clients is only done once per site, once per day, because of session reuse. That’s pretty good news when you think about it!

So, we don’t have to replace all of TLS, just shoe-horn in a new asymmetric handshake cipher. But which one will we use?

NIST Projected Timeline for Choosing Post-Quantum Algorithms
The National Institute of Standards and Technology (NIST) has issued a timeline by which they would like to see a post-quantum algorithm ready to replace the existing asymmetric algorithms. At the time of this writing (summer of 2017), we’re currently in the submissions phase, with deadlines for submissions at the end of November, followed by submitters’ presentations in early 2018. A three- to five-year analysys will follow when NIST will report findings, and one or two workshops will be scheduled. Finally, two years after that, draft standards may be read.

In 2009 two NIST researchers, Ray A. Perlner and David A. Cooper, published a white paper examining the (then) likely post-quantum algorithm candidates. They included the chart below showing some of the algorithms’ comparative metrics against non-post-quantum algorithms (RSA, DSA, DH, ECC).

Since that paper was published, new algorithms have found currency in the community. You quickly find that none are perfect!

Current Candidates for Post-Quantum Asymmetric Encryption Algorithms
Several candidates are already being discussed, all of which have chosen key sizes that achieve the 128-bit level of security necessary to be quantum-safe: NTRUEncrypt, McEliece with Goppa codes, and Ring Learning with Errors. One promising algorithm is Supersingular Isogeny Diffie-Hellman (SIDH).

SIDH uses the smallest key sizes of the candidates (3K public keys), can support forward secrecy, and is free of patents. However, SIDH is not perfect; some researchers have already been poking holes at it and have come up with some pretty disturbing attacks, which can be mitigated against, but  add a whole new rash of complications.

Related and Relevant IETF Projects
The IETF TLS working group has already started design work to fit a post-quantum algorithm into TLS. At the 93^rd IETF in 2015, William Whyte proposed a hybrid handshake. Like Google’s CECPQ1, Whyte’s proposal uses a classical key exchange for half of the key, and a post-quantum key exchange for the other half. The two halves are then combined into a key derivation function to get the final master key, from which the rest of the session key data is derived.

If it seems unlikely that any of these algorithms will make an ideal candiate, well, that’s okay. Many people in the crypto community are skeptical that a large-scale quantum computer is even possible. But if it really does become a thing, we’ll be (sort of) ready for post-quantum in pretty short order, at least from a protocol point of view.

Get the latest application threat intelligence from F5 Labs.