Tuta Launches Post Quantum Cryptography For Email

We are excited to announce that with this release we are enabling quantum-safe encryption by default for all new Tuta Mail accounts. We are now replacing the classic asymmetric cryptography (RSA-2048) with our quantum-safe hybrid encryption protocol called TutaCrypt: It combines a post-quantum Key Encapsulation Mechanism (CRYSTALS-Kyber) and an Elliptic-Curve-Diffie-Hellmann key exchange (x25519).

If you want to be among the first to use quantum-resistant encryption for your emails, sign up now for Tuta Mail now!

Arne Möhle, CEO of Tuta Mail comments: "With TutaCrypt we are revolutionizing the security of email. For the first time, people can now send and receive emails that are encrypted so strongly that not even quantum computers will be able to break the encryption and decipher the messages. At Tuta, we see ourselves as pioneers in secure communication. Back in 2014, we published Tutanota, the first automatically encrypted email service. Today, ten years later and ten million users more, we are delighted to be paving the way for quantum-safe emails! We want to help as many people as possible communicate easily and securely - now and in the future. With the release of TutaCrypt in Tuta Mail, we have now reached another milestone to future-proof the security of online communication."

When Tutanota (now Tuta Mail) launched in March 2014, it was the first end-to-end encrypted email provider enabling people to easily encrypt emails to anyone in the world. Over the years, we have continuously strengthened the level of security in Tuta Mail by upgrading our algorithms from AES 128 to AES 256, which already makes all encryption at rest quantum-safe. We also upgraded our password based key derivation function from bcrypt to Argon2 as Argon2 is the most secure hashing function to protect passwords and derive encryption keys.

Challenge for securing emails

While quantum-resistant encryption at rest can be easily achieved with AES 256, the challenge for email is its use of asymmetric encryption. New post-quantum algorithms for asymmetric encryption and public key cryptography are needed, and the NIST has already chosen CRYSTALS-KYBER for standardization as ML-KEM (key establishment) and CRYSTALS-Dilithium as ML-DSA (digital signatures).

We've re-built the Tuta cryptographic protocol from the ground up and are now upgrading our encryption using quantum-resistant algorithms together with conventional algorithms (Kyber in combination with AES 256 and ECDH x25519 in a hybrid protocol) for our asymmetric public key encryption of emails, but also for calendar sharing, sharing of contact lists and future file sharing services. The latter service, post-quantum secure drive and file sharing, is already being worked on in parallel together with the University Wuppertal in a research project funded by the German government.

How to enable quantum-safe encryption

New Tuta users do not have to take any action but update to the latest version of the Tuta apps for post-quantum algorithms to protect their emails, calendars and contacts. The new protocol will slowly be rolled out to all existing Tuta users as well.

This new generation of encryption future-proofs all data stored in Tuta and also protects from the concept of "Harvest now, decrypt later". Attackers wanting to get their hands on the encrypted data of Tuta emails now need to break both, the new post-quantum algorithms as well as classical AES/ECC cryptography.

This is a major leap forward in email security and we are proud to be leading the way towards a more private digital future.

The complete protocol specification is available on our website: TutaCrypt

As Tuta Mail is an open source project you can also have a look at the implementation of the protocol at our GitHub repository.

Security properties

Leading cryptography experts as well as the US government recommend a cybersecurity strategy that updates to quantum-safe encryption algorithms already now.

Following this state-of-the-art approach, we at Tuta now protect all data against attackers that collect encrypted messages now to decrypt them once a large-scale universal quantum computer is available. This attacker model is called "Harvest Now, Decrypt Later". As we do not consider an active quantum adversary that is able to tamper and break messages during a protocol run we do not need authentication and integrity for the post-quantum scenario. As threats evolve and quantum computers might become available we plan to improve our current protocol accordingly.

TutaCrypt provides the following security properties:

• Confidentiality (classical and post-quantum): Only the intended recipients (and the sender) are able to access the content of a TutaCrypt encrypted message.

• Integrity (classical): A TutaCrypt encrypted message cannot be modified after its encryption by the sender without detection upon decryption by the recipient.

• Authenticity (classical): Recipients get a cryptographic guarantee that any TutaCrypt encrypted message was sent by its acclaimed sender.

Cryptographic building blocks

Prior to releasing TutaCrypt, your secure mail client was generating an RSA key pair upon registration. With the release of TutaCrypt, we are now generating two key pairs:

• One Elliptic Curve key pair with curve X25519 used for an Elliptic Curve Diffie-Hellman Key Exchange (ECDH)
• And one Kyber-1024 key pair used for key encapsulation.

The private keys are stored encrypted on our German-based servers (with a key derived from the user's password) so that they can be used on any of device of the user. New Tuta Mail accounts will from now on only have TutaCrypt key pairs and no RSA key pair, which is explained on our encryption page with details on how we encrypt and secure the users' keys on our German-based servers for best data protection.

For quantum-safe and authenticated symmetric encryption TutaCrypt uses AES-256 in CBC mode with HMAC-SHA-256.

Long-term AES-256 keys are used to encrypt data stored on the server which are derived from the user's password using Argon2.

Symmetric encryption keys are derived using HKDF-SHA-256.

How does it work?

TutaCrypt combines the aforementioned algorithms in order to exchange a cryptographic key which is used to encrypt and decrypt the message, including mail body, subject and attachments.

The protocol derives two shared secrets using ECDH between the sender's identity key (IKA), an ephemeral key (EKA) generated by the sender and the recipient's identity key (IKB).

These two secrets (DHI and DHE) are used as input to the key derivation function together with a third shared secret that is obtained from a Kyber key encapsulation (SSPQ). The derived key encrypts and decrypts the message key.

The shared secret calculation of TutaCrypt.

Gradual roll-out to all Tuta users

With the release of TutaCrypt, all newly generated encryption keys of new Tuta Mail accounts will be generated with quantum-safe algorithms.

In a second step of TutaCrypt, we are now working on a mechanism to rotate the different keys used in our application. Once this feature becomes available for public release, we will start to roll out post-quantum secure encryption to all ten million existing users as well.

Further plans

TutaCrypt is a major improvement to Tuta's cryptography. We are happy to be the first email provider that encrypts their users' data with quantum-safe encryption. It proves that complex and strong cryptography can be made available for everybody. But we plan to go even further.

We have explained which security properties the protocol currently has. However, we are aware that there are some limitations regarding authentication, in particular in the case that long-term identity keys are compromised.

Our partners in the PQDrive project at the University of Wuppertal have not found any security problems with the TutaCrypt protocol and suggested that we do a formal verification. We plan to have the protocol formally reviewed and verified in the near future.

We are in the process of improving the protocol together with the University of Wuppertal and in the long term we aim to implement the full PQMail protocol to achieve Perfect Forward Secrecy and Future Secrecy as additional security properties.

All of this is necessary to provide best security. We are enabling TutaCrypt already now for all of our customers so they can benefit from the increased level of security with post-quantum cryptography. As one of the next steps, we will also add key verification so that TutaCrypt will also provide cryptographically guaranteed authentication.

Why We Need Post-Quantum Cryptography NOW

Quantum-resistant or post-quantum cryptography is our best bet against attacks from future quantum computers to increase security, data privacy and data protection.

The rise of quantum computers brings great advantages to our online world, but also great risks to our security and privacy. As the quantum revolution inches closer, the introduction of robust post-quantum cryptography becomes paramount: The new algorithms must be implemented now to safeguard our data from future attacks by quantum computers. In this post we explain the purpose of post quantum cryptography, how post-quantum encryption works and why we need quantum-resistant cryptography already today - and not once the era of quantum computers has started.

The Internet as we know it depends on encryption: confidential communication, secure emails, financial transactions, critical infrastructure - all of these are at risk if encryption can be broken. Today all sorts of players heavily invest in developing quantum computers - for manifold reasons.

These computers promise to bring great advantages to information technology, particularly in combination with artificial intelligence (AI). But quantum computers can also be turned into unprecedented surveillance machines and threaten our cybersecurity: The race is on between quantum computers and post-quantum cryptography!

Quantum computers threaten encryption

Quantum computing and quantum-resistant cryptography will change information technology in a way that we have never seen before.

Past research has yielded various quantum algorithms to efficiently solve different problems that are considered too difficult today. Due to that ability quantum computing will bring great enhancements in different areas of information technology.

They do, however, also pose a serious threat to encryption as the asymmetric cryptosystems that are widely used today (RSA, ECC, (EC)DSA and (EC)DH), rely on variants of only two hard mathematical problems that, unfortunately, quantum computing is able to solve significantly faster: the integer factorization problem and the discrete logarithm problem.

With Shor's algorithm (1994) running on a universal quantum computer both problems become solvable in polynomial time.

Is Elliptic Curve Cryptography quantum resistant?

This means that the respective cryptosystems relying on RSA and ECC can actually be broken.

Popular cryptographic algorithms such as Elliptic Curve Cryptography (ECC) is not quantum-resistant and can be easily broken by quantum computing. It's important to note that ECC as well as PGP encryption based on AES and RSA will be obsoleted in the coming years when NIST's post-quantum cryptography competition has been completed. At best these traditional algorithms will be used in hybrid protocols, combined with quantum secure algorithms.

How much time it will take for an attacker to break RSA and ECC encryption depends on the capacity of the quantum computer. According to a study by the German Federal Office for Information Security (BSI) about 1 million physical qubits are needed to break 2048-bit RSA in 100 days and about 1 billion qubits to break it within an hour. Advances in algorithm design will further reduce these numbers.

The race for quantum-safe solutions

"This means that quantum computers have the potential to eventually break most secure communications on the planet," says cryptographer Rafael Misoczki. The race is on to create new ways to protect data and communications to combat the threat posed by large scale universal quantum computers.

For instance, US federal agencies like the FBI and NSA are already required to adopt post-quantum security, and the private sector is being advised to follow. This requirement is part of the National Cybersecurity Strategy released by the Biden administration in March 2023. It is obvious that policymakers have already understood the cybersecurity threat of quantum computers to confidential and secret communication online.

When will quantum computing become a reality?

To date, no practical quantum computer has been developed. However, quantum computing is a very active research field and fast progress has been made in the past, particularly in most recent years.

Advances in quantum computing are announced regularly by big companies such as IBM, Google and Intel. These computers, however, operate on only about 50 -70 physical qubits. According to the mentioned BSI study, a quantum computer capable of breaking today's cryptosystems will not become a reality in the short term.

However, the revelations of Edward Snowden made it obvious that encrypted data is stored by different actors already today. It is high time to ensure that these actors will not be able to decrypt it years in the future, when large scale universal quantum computers will have been build.

In addition, quantum computing is no longer a distant possibility, but already a reality. The Riken research institute in Japan has announced it will make the country’s first domestically built quantum computer available online for several businesses and academic institutions. Riken plans to connect this quantum computer prototype to the world’s second-fastest supercomputer, Fugaku, by 2025, in order to expand its real-world use cases, including research related to materials and pharmaceuticals.

This is not an isolated development, but part of what looks like a quantum computing “arms race”. According to Japan's Science and Technology Agency, over the past three decades China has registered the most patents worldwide for quantum computing, approximately 2,700, followed by the U.S. with roughly 2,200 and Japan with 885.

It’s clear that the world is on the verge of a technological revolution with the emergence of quantum computers, which promises unprecedented processing power and the ability to solve complex problems that classical computers cannot.

While this is exciting, it will also pose a threat to current encryption protocols, which could be easily broken by quantum computers, leaving sensitive information exposed to attackers. This is why the U.S. National Cybersecurity Strategy is calling for the transition to post-quantum cryptography, which uses algorithms that are resistant to attacks from quantum computers. The strategy recognizes the need to prepare for the future and ensure that encryption protocols remain secure in the face of evolving threats.

While the possibility of a quantum computer successfully breaking current end-to-end encryption protocols is not expected to become a reality in the immediate future, it is important to work on preventing this type of threat as soon as possible, because efficient solutions take time to develop.

How quantum computers work

Ordinary computers store data as 1s and 0s. Whereas quantum computers use qubits to store data. Each qubit is in a superposition of 1 and 0. Measurements project one of these states with certain possibility. This possibility is changed by the quantum algorithm. Because each qubit represents two states at once, the total number of states doubles with each added qubit.

Thus, one quibit is two possible numbers, two qubits is four possible numbers, three qubits is eight possible numbers. Since the coronavirus pandemic, we all understand exponential numbers. We can get an idea of how powerful a quantum computer with, let's say 100 qubits, could be. A quantum machine with 300 qubits, for instance, could represent more values than there are atoms in the observable universe.

About 20 years ago, researchers in Japan pioneered superconducting qubits: They cooled certain metals to extremely low temperatures to reach a stable working environment for quantum computers.

This method was so promising that it triggered research projects at Google, IBM, and Intel.

The actual quantum computers do not look like ordinary computers at all. Instead, these are large cylinders of metal and twisted wires, which are dropped into large refrigerators. Researchers send information to the machine and receive calculations in return, just like with ordinary computers.

IBM even lets external researchers buy computing power on their Q System One. This enables researchers around the world to use a quantum computer without ever seeing or touching one for real.

Their inherent parallelization of computation on all states simultaneously will enable these powerful computing machines to break currently unbreakable encryption.

Why we need encryption

Encryption is all around us when we use the Internet. It is an integral part for any digital process that needs confidentiality: communication, finance, commerce, critical infrastructure, health care and many more areas of our daily life are protected with strong encryption. When the cryptographic algorithms used in these processes become breakable due to the development of large scale universal quantum computers, attackers with access to such computers can threaten many aspects of our every-day life.

The Internet as we know it only works with unbreakable encryption. Now is the time to prepare for the quantum revolution with the introduction of post-quantum cryptography.

What is post quantum cryptography?

Quantum-resistant encryption can protect your data from the looking threat of quantum computers.

Post-quantum cryptography describes cryptographic algorithms running on conventional computers but relying on mathematical problems that are believed to be too hard for conventional and quantum computers to break them. As long as there is no efficient quantum algorithm that solves exactly these problems more efficiently, we can assume that they cannot be broken by quantum computers.

In response to the quantum threat, the global cybersecurity community is actively engaged in a race to develop post-quantum cryptographic algorithms. These algorithms are designed to withstand attacks from both classical and quantum computers, ensuring the longevity of secure communication.

In 2016, the U.S. National Institute for Standards and Technology (NIST) initialized a process to standardize such quantum-safe algorithms. The final result of this NIST post quantum cryptography standard is being awaited eagerly by the crypto community. The process is currently in the fourth - and almost final - phase of evaluating standard algorithms for post-quantum secure encryption, with the first four quantum-resistant cryptographic algorithms - CRYSTALS-Kyber for encryption and CRYSTALS-Dilithium, FALCON and SPHINCS+ for digital signatures - already being announced.

Getting ready for the quantum computing revolution

Developing and deploying post-quantum cryptography is quite urgent. Even though quantum computers capable of breaking the cryptosystems we use today might not become reality in short term, experience has shown that rolling out new cryptographic standards takes a lot of time. New algorithms have to be evaluated carefully, their security has to be proven by intensive cryptanalysis and efficient implementations have to be found. For instance, even though Elliptic Curve Cryptography was first proposed in the late 1980s, it has only been adapted for mass usage some years ago.

Harvest now, decrypt later

Sauron's eye will be able to see everything once quantum computers can decrypt your communication.

Deployment of post-quantum cryptography should happen as soon as possible - not only to be prepared when large scale universal quantum computers become a reality but also to protect the data currently encrypted with standard algorithms from being decrypted in the future. The difference between the current cryptography and post-quantum cryptography is that the new quantum resistant algorithms will be able to fend off attacks from quantum computers - while data encrypted with currently used algorithms will not have the power to resist such attacks.

The threat here is called the harvest now, decrypt later strategy: Data that travels the internet is being collected now, for instance by secret services such as the NSA or other five eye countries, for later decryption.

This threat makes it obvious that waiting whether - or when - quantum computers will be released is no longer an option.

What's the purpose of it all?

The purpose of of post quantum cryptography is to make sure the encrypted data stay secure in the future. As the US government and the NIST have explained: all data encrypted with standard algorithms fall short of achieving this new level of security requirement and post quantum cryptography algorithms must be implemented now. Fortunately, some data can be secured with post-quantum encryption relatively easy as AES 256 (symmetric encryption) is already considered quantum resistant.

This means that any data that is stored on your computer or on a company's system like documents and files can be easily secured with the proven algorithm AES 256.

The challenge of asymmetric encryption

It gets more tricky though when you want to encrypt data asymmetrically in a quantum-resistant manner, for instance for encrypted file sharing or for sending and receiving encrypted emails. New post-quantum algorithms for asymmetric encryption and public key cryptography are being researched and tested as you read this.

Many different companies have already started to experiment with quantum resistant asymmetric cryptography in their applications. Similar to recent post-quantum updates by Signal and Apple, we at Tuta Mail are pioneering at using quantum-resistant algorithms together with conventional algorithms (Kyber and Dilithium in combination with AES 256 and RSA 2048 in a hybrid protocol) for our asymmetric public key encryption of emails, but also for calendar sharing, sharing of contact lists and future file sharing services.

In doing so we are following the advice of NIST, the US government as well as renowned cryptography experts such as Lyubashevsky: "If you really have sensitive data, do it now, migrate yourself."

Hybrid protocol to achieve maximum security

As quantum resistant algorithms are fairly new and their security has not been sufficiently proven, we cannot just replace current cryptographic algorithms with them. It might still happen that somebody comes up with an attack running on a conventional or a quantum computer that breaks the quantum-safe algorithm that have been chosen. A hybrid approach is a core requirement as the new algorithms have not been tested in battle yet. Even if the mathematical conclusion that makes these algorithms quantum safe is correct, there could be mistakes in the implementation which can undermine the security.

Therefore, post quantum cryptography algorithms and conventional algorithms have to be combined in a hybrid approach. This is the approach used by all quantum-resistant updates, being is done by Signal, Apple, or Tuta.

As quantum computers are about to become a reality, we must be one step ahead with post quantum cryptography to keep all data secure - now and in the future!

If you want to be among the first to use quantum-resistant encryption for your emails, sign up now for Tuta Mail!