Articles > Google Tests Post-Quantum Crypto
Quantum computing will pose a grave threat to the encryption algorithms now protecting everything from online banking and e-commerce to email and instant messaging. That's because today's algorithms are largely geared toward making the calculation of the decryption keys for scrambled messages so computationally intensive that the task is effectively impossible. Quantum computers, however, will likely one day make such calculations much more efficient, thus threatening the security of any bit of information that has ever been encrypted.
While quantum computers are in their infancy, Google has taken a first step toward adapting to the post-quantum cryptography world by launching a two-year experiment that incorporates into its Chrome browser a modified version of a key exchange algorithm called Ring Learning with Errors (Ring-LWE) that's been implemented for OpenSSL. Google's approach is based on a scheme known as "New Hope" that researchers note is designed to provide "post-quantum security for TLS."
OpenSSL is the general purpose cryptography library that provides an open source implementation of the Secure Sockets Layer (SSL) and Transport Layer Security (TLS) protocols, which are used to secure internet communications.
In theory, this new approach will be resistant to key calculation by quantum computers that haven't even been built yet. The tests will be carried out over the next couple of years for a small fraction of connections between Google's domains and people using its Canary version of Chrome, which the company uses to test new features. Users can see if it's in use if they see phrase "CEPQ1_ECDSA" in Chrome's security panel.
This is a Test
Security experts say that knowledge about quantum-computing-related crypto risks isn't new, but note that there's been a recent surge in enthusiasm for solving the problem. "Although people such as me have been talking about the threat to public key cryptography from quantum computers for years, and the alternatives that could be used, it seems that when Google announced that they were experimenting with a post-quantum crypto scheme in Chrome, it caught people's imagination," says Alan Woodward, a computer science professor at the University of Surrey who also serves as a cybersecurity consultant for the EU's law enforcement intelligence agency, known as Europol, in a blog post. "Perhaps this marks the beginning of post-quantum crypto entering the mainstream?"
Interesting that Google plumping for New Hope crypto as their post quantum scheme https://t.co/6yrEvf2wcV
— Alan Woodward (@ProfWoodward) July 8, 2016
Google, meanwhile, cautions that its Chrome test qualifies as bleeding-edge experimentation and says that it may not prove to be secure. Because of that, Google will continue to employ the widely used elliptic curve cryptography key-exchange algorithm in Chrome. "The post-quantum algorithm might turn out to be breakable even with today's computers, in which case the elliptic-curve algorithm will still provide the best security that today's technology can offer," writes Matt Braithwaite, a Google software engineer. "Alternatively, if the post-quantum algorithm turns out to be secure then it'll protect the connection even against a future, quantum computer."
Seeking Future-Proof HTTPS Security
Most web services are secured using "https," which means the service is using a digital certificate that enables SSL or its successor, TLS. Those certificates use either RSA or ECC keys. ECC keys are shorter but provide the same strength as their equivalent but longer RSA keys, reducing overhead. Although efforts have been underway to increase the length of keys used to secure SSL/TLS transactions, encryption experts predict that such upgrades won't be secure forever.
As noted, current public key cryptography schemes are designed to make it computationally impractical to calculate the decryption keys. The RSA algorithm, for example, creates a public key that is the product of two very large prime numbers. Factoring an RSA public key would, in theory, be much faster using quantum computers. Conventional computers use binary values consisting of a 0 or a 1. Quantum computers use quantum bits - qubits - which are units that can be either a 0 or a 1 at the same time depending on when the state is measured, allowing for much faster parallel calculations.
Quantum Computing is Coming, NSA Warns
The era of quantum computing isn't quite here yet, but there are commercial offerings from companies such as D-Wave. The worry is that once technologists master qubits, trouble will quickly ensue. Those worries were fueled in part by the National Security Agency, which warned in August 2015 that today's algorithms won't hold up against quantum computing.
"Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, which has made it clear that elliptic curve cryptography is not the long-term solution many once hoped it would be," according to the NSA's Information Assurance Directorate. "Thus, we have been obligated to update our strategy."
The agency is investigating various post-quantum crypto strategies, and it notes in a related CNSA Suite and Quantum Computing FAQ released in January that it could take two decades for a new alternative to be deployed across national security systems.
Historical Data at Risk
Once quantum computers can be practically applied to cryptographic systems, any encrypted content ever created - from yesterday, back to the birth of the commercial web in the early 1990s - could be at risk of being cracked. "This means that even encrypted information sitting in a database for 25 years, for example, will be subject to discovery by those with access to quantum computing platforms," according to a "Quantum-Safe Cryptography and Security" white paper published in 2014 by the European Telecommunications Standards Institute. "Without quantum-safe encryption, everything that has been transmitted, or will ever be transmitted, over a network is vulnerable to eavesdropping and public disclosure."
Many security experts suspect that intelligence agencies such the NSA and Britain's GCHQ have been collecting enormous volumes of encrypted Web traffic, waiting for the day when decrypting it becomes feasible. That's why Google's experiment is important. If it proves to be effective, it means that communications could be safer from quantum computing advances - at least for a while.
Surrey University's Woodward, meanwhile, recommends that anyone who has a hand in crypto systems come up to speed on both New Hope as well as Google's implementation. "All of this detail is freely available - although often spread around on the web - and I would encourage those involved in public key cryptography to start to look at it as it is coming to an infrastructure near you in the very near future."