Tor is switching to the Counter Galois Onion encryption algorithm

Tor (The Onion Router) is switching its encryption algorithm to help boost security and privacy. The change is being introduced to protect users against certain types of attack, and sees the browser adopting a new “research-backed new design” called Counter Galois Onion.

The algorithm that is being updated is the one used to encrypt user data as it travel across a circuit via multiple relays. In making the switch, Tor concedes that its previous encryption design “looks funny”, hence the need to replace it.

In a blog post about the changes, Tor highlights some of the problems with the previous encryption algorithm – pointing out that it does not even have a name, so it is retrospectively referred to as tor1! Three particular issues stand out, the first being tagging attacks:

Tagging attacks enable an active adversary to trace traffic by modifying it in one place on the network, and observing predictable changes in another. Even when tagging attacks don't succeed immediately, their side effects can give the attacker more and more opportunities to retry.

The second issue is described as “forward secrecy begins when a circuit closes”:

This attack and the one after it are much less severe than the tagging attack above; we mention them for the sake of completeness.

In many modern online protocols, including messaging apps like Signal, the keys used to decrypt a message are destroyed as soon as the message is decrypted, so that nobody can steal them and use them later on. But Tor's old encryption algorithm (tor1) doesn't provide this property: the same AES keys are used for the entire life of the circuit. That means that if a key was stolen while the circuit was still alive, all previous traffic on the circuit could be decrypted.

The third and final issue that Tor highlights with tor1 is its use of a 4-byte authenticator:

The use of a mere 4-byte digest means that there's a one-in-4-billion chance to forge a cell undetected.

That isn't a very good attack in practice: if the attacker doesn't get lucky with their guess, then their invalid message causes the circuit to fail, and they can't try again unless the client builds another circuit through them. The same pathbias mechanisms that help resist tagging attacks also help here, but it would be better not to need them.

The change is not completely in place, but is described as being “underway”:

We've implemented the cryptography for Arti, the Rust Tor implementation. We've also implemented it in C, since it won't do us any good unless relays support it too, and the Arti relay project is still a work in progress.

In order to build this implementation, we've had to refactor a lot of code to revise its existing assumptions: for example, we've had to revise all the places where we assumed anything about the layout of a relay cell, or where we assumed that there was only one way to do relay encryption. These changes will help us with any other changes to relay cell formatting and encryption in the future.

Our next steps are:

• Enable CGO by default in Arti. (It's currently marked as experimental because of some of its dependencies.)
• Implement CGO negotiation for onion services. (This feature is likely to be be Arti-only, due to its complexity.)
• Tune the performance for modern CPUs. (The CGO authors got impressively good results for their optimized implementation, but some of the tricks they used will be pretty hard to deliver in the C Tor implementation without big refactoring. Fortunately, there are some low-hanging fruit in optimizing what we have today.)

For much more detail about the changes, what they mean, and why they are being introduced, take a look at Tor’s announcement here.