In 2012, the Tor project expressed the need to upgrade Tor’s onion encryption scheme to protect against tagging attacks and thereby strengthen its end-to-end integrity protection. The only concrete candidate replacement, backed by formal albeit partial security proofs is Tor proposal 261, which processes each encryption layer by a strongly secure, yet relatively expensive tweakable wide-block cipher. We identify the functionality and security desiderata for Tor’s onion encryption, and propose an alternative onion encryption scheme, called Counter Galois Onion ( \(\textsf{CGO}\) ), that follows a minimalistic, modular design and includes several improvements over proposal 261. \(\textsf{CGO}\) ’s underlying primitive is an updatable tweakable split-domain cipher accompanied with a new security notion, that augments the recently introduced rugged pseudorandom permutation. Thus, we relax the security compared to a tweakable wide-block cipher, allowing for more efficient designs. We show that our security notion for updatable tweakable split-domain ciphers successfully hybridizes, which allows us to argue informally that \(\textsf{CGO}\) meets the full security requirements. Finally, we suggest a concrete instantiation for the updatable tweakable split-domain cipher, called \(\mathsf {UIV+}\) , prove its security, and benchmark our full \(\textsf{CGO}\) scheme against Tor’s existing onion encryption scheme, demonstrating a clear performance gain at the proxy and at exit and entry routers, at the expense of a mild slowdown at intermediate routers.