Securing tomorrow today: Why Google now protects its internal communications from quantum threats

Editor's note: The ISE Crypto PQC working group is comprised of Google Senior Cryptography Engineers Stefan Kölbl, Rafael Misoczki, and Sophie Schmieg.

When you visit a website and the URL starts with HTTPS, you’re relying on a secure public key cryptographic protocol to shield the information you share with the site from casual eavesdroppers. Public key cryptography underpins most secure communication protocols, including those we use internally at Google as part of our mission to protect our assets and our users’ data against threats. Our own internal encryption-in-transit protocol, Application Layer Transport Security (ALTS), uses public key cryptography algorithms to ensure that Google’s internal infrastructure components talk to each other with the assurance that the communication is authenticated and encrypted. 

Widely-deployed and vetted public key cryptography algorithms (such as RSA and Elliptic Curve Cryptography) are efficient and secure against today’s adversaries. However, as Google Cloud CISO Phil Venables wrote in July, we expect large-scale quantum computers to completely break these algorithms in the future. The cryptographic community already has developed several alternatives to these algorithms, commonly referred to as post-quantum cryptography (PQC), that we expect will be able to resist quantum computer-driven attacks. We’re excited to announce that Google Cloud has already enabled one of the algorithms on our internal ALTS protocol today.

Why we chose NTRU-HRSS internally

With the PQC standards by the National Institute of Standards and Technology (NIST) still pending, rolling out quantum-resistant cryptography can currently only happen on an ephemeral basis, where the exchanged data is used once and never needed anymore. Google’s internal encryption in transit protocol, ALTS, is an ideal candidate for such a rollout since we control all endpoints using this protocol and can switch to a different algorithm with relative ease if NIST adopts different standards. Controlling all the endpoints can give us the confidence of defeating store-now-decrypt-later attacks without worrying about having to maintain a non-standard solution.

Deploying new cryptography is risky because it has not been field-tested. In fact, several of the candidates in the NIST process suffered devastating attacks that did not even require a quantum computer. We avoided a scenario where our attempt to secure our infrastructure against a theoretical computing architecture renders it defenseless against a laptop recovering private keys over a weekend by adding the post-quantum algorithm as an additional layer. This tactic helps ensure that the security properties of our currently-deployed vetted and tested cryptography are still in place.

Note that we do not need to address signature algorithms yet. An adversary who can forge a signature in the future will not affect past sessions of the protocol. For now, we only need to address "store now, decrypt later" attacks, as these can affect our data today. Since signature algorithm threats are not immediate, we were able to simplify the vetting process in two ways: 

We only had to add PQC for the key agreement parts of the protocol.

It allowed us to only change parts which rely on ephemeral keys. For authenticity we still rely on classic cryptography, which likely will only be affected when a large-scale quantum computer exists.

Among the more promising quantum-resistant choices, NIST has favored lattice-based algorithms, with NIST recently announcing the selection of Kyber to become the first NIST-approved post-quantum cryptography key encapsulation mechanism (KEM). Kyber has high performance (it has a more balanced latency cost when considering operations than alternative lattice-based counterparts), but still lacks some clarification from NIST about its Intellectual Property status (see the third round status report by NIST). 

From the same realm of lattice-based KEMs, there’s the NTRU-HRSS KEM algorithm. This is a direct descendant of the well-known, time-vetted NTRU scheme proposed back in 1996, and it is considered by many experts as one of the more conservative choices among the structured, efficient lattice-based schemes. Given its high performance and maturity, we have selected this scheme to protect our internal communication channels using the ALTS protocol.

The post-quantum cryptography migration brings unique challenges in scale, scope, and technical complexity which have not been attempted before in the industry, and therefore require additional care. That’s why we are deploying NTRU-HRSS in ALTS using the hybrid approach. By hybrid we mean combining two schemes into a single mechanism in such a way that an adversary interested in breaking the mechanism needs to break both underlying schemes. Our choice for this setup was: NTRU-HRSS and X25519, thus matching the insightful choice of our Google Chrome 2018’s CECPQ2 experiment and allowing us to reuse BoringSSL’s CECPQ2 implementation.

Protecting ALTS against quantum-capable adversaries is a huge step forward in Google’s mission to protect our assets and users’ data against current and future threats. We continue to actively participate in the Post-Quantum Cryptography standardization efforts: Googlers co-authored one of the signature schemes selected for standardization (SPHINCS+), and two proposals currently considered by NIST in the fourth round of their PQC KEM competition (BIKE and Classic McEliece). We may re-evaluate our algorithmic choices when Kyber’s IP status is clarified, and when these fourth round selected standards are published.

^{The ISE Crypto PQC working group would like to acknowledge the contributions of Vlad Vysotsky and Dexiang Wang, software engineers on the ALTS team, and Adam Langley, principal cryptography engineer on BoringSSL.}