Tor introduces Counter Galois Onion encryption to thwart traffic attacks

The Tor Project has announced a significant upgrade to the cryptographic core of its network, retiring the aging “tor1” relay encryption algorithm and introducing a modern replacement named Counter Galois Onion (CGO).

This move strengthens Tor’s defenses against a class of attacks that could compromise user anonymity and lays the groundwork for further cryptographic improvements.

The new encryption scheme is the result of years of research and collaboration between Tor developers and cryptographers Jean Paul Degabriele, Alessandro Melloni, Jean-Pierre Münch, and Martijn Stam. It directly addresses critical weaknesses in the old tor1 system, chief among them, malleability, a vulnerability that enabled so-called tagging attacks.

Tor’s core function is to anonymize internet traffic by routing it through a series of relays (known as a circuit), each decrypting a layer of encryption, a process inspired by onion routing. The encryption used between these relays, called relay encryption, has long relied on a scheme involving AES-128 in counter mode (CTR) with a 4-byte digest for integrity checks.

While functional, this system, now called tor1, had several design shortcomings:

• Malleability leading to tagging attacks: Without built-in authentication at each relay, an attacker could tamper with encrypted data mid-transit and observe the results downstream. This could allow correlation of traffic and the deanonymization of users.
• Weak forward secrecy: Encryption keys were reused for the entire lifespan of a circuit, which could last minutes, or even days. If a key was compromised, all past traffic on that circuit could potentially be decrypted.
• Inadequate message authentication: The tor1 algorithm used a 4-byte SHA-1 digest, an uncomfortably short and outdated integrity check that could theoretically be forged with brute-force efforts.

These issues are particularly troubling in modern threat environments, where well-funded adversaries can afford sophisticated active attacks. While mitigations like circuit path diversity and client-side failure detection have helped, the underlying cryptography needed a revamp.

Introducing Counter Galois Onion

The CGO encryption design is based on a new class of cryptographic constructions called Rugged Pseudorandom Permutations (RPRP). Specifically, it uses a construction called UIV+, which offers strong malleability resistance during encryption and operates efficiently even under the performance constraints of Tor relays.

Here’s how CGO improves on the tor1 scheme:

• Resistant to tagging attacks: CGO treats each cell (a fixed-size encrypted message between relays) as a single cryptographic block. Any tampering with the encrypted cell renders it completely unreadable. Furthermore, CGO links each message to the one before it using chained authentication tags, making undetected modification impossible.
• Forward secrecy by design: Keys and nonces are updated with every cell, ensuring that once a message is sent, the keys used to encrypt it are irreversibly discarded. Even if a key is compromised later, it can’t be used to decrypt earlier messages.
• Stronger authentication: CGO replaces the old 4-byte SHA-1 digest with a modern 16-byte authentication tag, significantly improving integrity verification and resistance to forgery.

By encrypting and authenticating the entire message using a wide-block cipher model, CGO avoids the pitfalls of earlier remailer-inspired designs that required one authenticator per layer, a strategy that consumed excessive bandwidth. CGO manages to stay efficient while delivering modern cryptographic assurances.

The Tor Project is a nonprofit organization dedicated to enabling anonymous communication on the internet, widely used by privacy advocates, journalists, and those under oppressive regimes. The relay encryption algorithm sits at the heart of Tor’s circuit model, and changing it involves both deep cryptographic work and complex engineering across multiple implementations.

The new CGO algorithm has been implemented in Arti, Tor’s Rust-based next-generation client and relay software, and in the legacy C Tor implementation to ensure compatibility with existing infrastructure. Some parts of the transition, like CGO negotiation for onion services, are expected to remain exclusive to Arti due to the complexity of integrating them into the older C codebase.

The CGO deployment is currently underway. In Arti, it’s marked experimental for now, but will soon be enabled by default as remaining performance and integration issues are addressed.