Today, we’re celebrating one year of quantum-safe encryption in Tuta, and we couldn’t be prouder of what we’ve accomplished. Read more on our initial launch and why we need post-quantum cryptography already now.

Milestone in post-quantum security

From the moment we introduced TutaCrypt on March 11, 2024, every new Tuta user has been protected by default with our quantum-resistant encryption. Just this week, we took another major step: enabling TutaCrypt for all older single-user accounts. As these users log in, they get updated to the new encryption protocol immediately. At the moment of writing this blog post, 50% of Tuta users are using the new TutaCrypt protocol.

50% of Tuta users have already been upgraded to TutaCrypt.

Are you using quantum-safe encryption already? If not, sign in to your Tuta account or register for the first time, and you’ll be upgraded to TutaCrypt right away!

Smooth rollout

Deploying quantum-safe encryption and scaling it for millions of Tuta users had to be handled carefully. When updating the encryption keys, the Tuta client generates fresh random keys for use with the new algorithms. This happens right after login as the user password is needed to re-encrypt the new keys for later use of the hybrid TutaCrypt protocol. We call the protocol hybrid because it combines classical algorithms (x25519) with quantum-resistant algorithms (Kyber, which has recently been standardized as ML-KEM) in a way that ensures security as long as at least one of the algorithms remains unscathed. At the same time we also updated our security parameters for symmetric encryption replacing AES-128 with the quantum-resistant AES-256 variant.

During this process, we had to make sure that the new encryption protocol worked flawlessly for sending and receiving emails and encrypting these with other Tuta users also on the new protocol (quantum-safe), and at the same time be backward-compatible, so the encryption also needs to work with Tuta users who still use the old, traditional encryption protocol based on RSA-2048.

Despite the complexity, our rollout has been remarkably smooth and bug-free. The rollout for single-user accounts was a major success. Given how many changes we made at the core of the Tuta protocol, the rollout was smooth and without any major issues. This is a testament to the meticulous quality assurance (QA) efforts of our team.

With the success of single-user account transitions, we’ve already released the implementation to migrate multi-user accounts. We’re now waiting for all clients to update to a compatible version before we begin a gradual rollout - just as we did with single-user accounts. By taking time when rolling out the new encryption protocol, we are able to monitor and address any potential issues proactively.

We have been holding back the migration of accounts with multiple admin users until now, as it came with some additional challenges. We have designed a rollout mechanism that ensures no admin or regular users ever loses access to their data. At the same time no fresh quantum-safe admin or user keys are ever shared over a non-quantum-safe channel with other admins or users. Therefore, as soon as the rotation is done, even a quantum adversary that recorded the rotation, cannot gain access anymore.

Protecting against downgrade attacks

Having introduced quantum-resistant cryptography as the first email provider worldwide, we also understand the need for backward compatibility. Tuta still supports RSA for updated accounts and will keep doing so in case users need to access old existing data, that is still encrypted with RSA and was not yet decrypted. In addition, we have rolled out some mitigations to protect against potential downgrade attacks that will prevent the usage of weaker ciphers or at least alert users if this should be happening.

Advancing cryptographic research

To ensure that TutaCrypt meets the highest security standards, we’ve been working closely with the Bergische Universität Wuppertal, IT Security and Cryptography department. Together, we’ve modeled TutaCrypt as a One-Pass Key Exchange, aiming for a formal proof of indistinguishability from random under chosen ciphertext attacks (IND-CCA2). This proof is still in progress, but we’re optimistic about reaching this milestone in the coming months.

Additionally, since the release of TutaCrypt, Kyber has been standardized as ML-KEM, requiring adjustments on our side to ensure compatibility with updated cryptographic libraries. While making these changes, we also addressed side-channel attack vulnerabilities found in certain Kyber implementations by updating our encryption libraries. We know of no case where such a side-channel attack was deployed against a Tuta user nor do we think that such an exploit could have gone unnoticed as it would have been extremely noisy, for instance by requiring lots of TutaCrypt runs when trying to exploit this over the network. In addition, thanks to our hybrid protocol approach (combining traditional and post-quantum algorithms), Tuta remained secure throughout, as the traditional, proven algorithms also protect all user data in Tuta.

What’s next?

We are now focusing on manual key verification to enhance authentication security, particularly under the Harvest Now, Decrypt Later (HNDL) threat model. This will further protect users against machine-in-the-middle (MITM) attacks, where an attacker would compromise the server and provide the user with falsified encryption keys trying to listen in on a conversation or impersonating another user. TutaCrypt allows defending against such attacks when carried out by a non-quantum adversary, but it can only reliably do so if the encryption keys are verified.

As we look back on this past year, we’re proud of how far we’ve come. But this is just the beginning. Our mission remains the same: to provide the world’s most secure communication platform that keeps all your data private! We make sure that no one - neither malicious attackers nor governments - can access your data.

Thank you for trusting Tuta with your private data.

Here’s to another year of implementing best-in-class cryptography! 🚀

The Tuta Team meets cryptography experts from the University of Wuppertal.