C-Onion: A secure and efficient onion encryption scheme with subtle improvements

Tor is the most widely used anonymity network and employs onion encryption for anonymous communication. However, the onion encryption scheme currently deployed in Tor is vulnerable to tagging attacks. In response, Tor is actively seeking a replacement that is both secure and efficient. Several alternatives — proposals 261, 295, and 308 — have been proposed to address this issue. Although these designs leverage advanced cryptographic techniques, none of them achieves both strong security and good performance. This situation arises from a partial neglect of security foundations of onion encryption, thereby highlighting the need for a new design. In this paper, we propose C-Onion, a new onion encryption scheme that is secure, efficient, and deployable in the Tor setting. C-Onion refines proposals 295 and 308. More importantly, C-Onion is built upon a comprehensive, onion-layer-centric security model and adopts the Encrypt-then-MAC paradigm to ensure strong security guarantees. It removes the outermost onion layer to boost performance without sacrificing security. Furthermore, by fine-tuning the tweak encoding in the underlying GCM-RUP variant, C-Onion achieves tighter security bounds than proposals 295 and 308. We formally prove the security of C-Onion and implement an academic prototype. In single-threaded benchmarks using AES-NI and PCLMULQDQ instructions, C-Onion reduces both encryption and decryption time by at least 30% in a typical 3-hop Tor circuit.