Google publishes plans for post-quantum cryptography

Secure email firm Tuta has also upgraded its systems to be quantum-proof

Google has published a threat model for the arrival of quantum computers that can crack commonly used cryptosystems such as RSA and ECC.

"If we do not encrypt our data with a quantum-secure algorithm right now, an attacker who is able to store current communication will be able to decrypt it in as soon as a decade," Google security researchers write in a blog post.

They quote research by the Global Risk Institute that assigns a probability of 17%-31% to a quantum computer being able to crack RSA-2048 in 24 hours.

In 2022, the US National Institute of Standards and Technology (NIST) announced four candidates to be standardised as recommended public key post-quantum cryptography (PQC) algorithms. These algorithms are recommended to replace asymmetric cryptosystems based on elliptic curves and prime factorisation which are theoretically vulnerable to quantum computers, as these devices can effectively guess a huge number of possibilities at once.

Organisations are now starting to replace or augment vulnerable systems with quantum-proof alternatives, but this is not always straightforward.

For Google, the main motivation in adopting PQC now is to prevent "store-now-decrypt-later" attacks, where an attacker stores encrypted data now and decrypts it once quantum computers become available.

It is prioritising quantum threat mitigation based on feasibility of the attack, level of store-now-decrypt-later risk, use cases requiring long-lived public keys, and need for research on redesigning systems for PQC.

The most urgent threat from store-now-decrypt-later attacks is data in transit protected with vulnerable algorythms like TLS and SSH. Firmware signatures and software signatures will also need to move to PQC soon, the Google researchers say.

Public key infrastructure (PKI) and tokens (such as JSON Web Tokens) face performance challenges with PQC due to larger key and signature sizes. These will require more research.

In most cases Google will use NIST-recommended quantum-safe algorithms for key agreement (e.g. CRYSTALS-Kyber) and digital signatures (e.g. Dilithium, SPHINCS+) in a hybrid mode with classical algorithms for now.

Among the systems and protocols that will need to be upgraded are TLS, SSH, Signal, Google's authentication protocol ALTS, firmware signatures, hardware security modules, tokens used for stateless authentication and other products using asymmetric encryption, such as PGP S/MIME and HPKE.

Nation-states are the most likely threat actors to develop cryptographically-relevant quantum computers first, Google says.

"They will most likely try to deploy the quantum computer in a deniable fashion, in order to avoid tipping off adversaries of their capabilities. Nation states are most likely to target the Cloud deployments of other nation state customers, and may target political dissidents and other targets for surveillance."

Tuta is also upgrading to post-quantum cryptography

Encrypted email service Tuta (formerly Tutanota) is also upgrading its services to use PQC.

In a blog post the German company also said it is concerned by the risk of store-now-decrypt-later attacks. Like Google it is adopting a hybrid approach to beef up its existing algorithms.

Tuta is launching TutaCrypt, a PQC protocol that secures emails by combining quantum-safe algorithms (CRYSTALS-Kyber) with traditional algorithms (AES, ECDH). TutaCrypt uses post-quantum algorithms for key exchange.

It will be implemented by default for all new accounts, and rolled out to existing customers over time, the company says.

In the future it plans to further improve the TutaCrypt protocol by implementing the full PQMail protocol for Perfect Forward Secrecy and Future Secrecy. The company also intends to have the protocol formally verified.

Tuta says it is following the advice of NIST as well as renowned cryptography experts such as Vadim Lyubashevsky: "If you really have sensitive data, do it now, migrate yourself."

Computing's recent research found that just 5% of UK organisations polled are looking to upgrade their cryptosystems to PQC.