Treat Randomness with Care: Breaking and Provably Fixing Anonymity of Tor Proposal 295

Tor proposal 295, currently the only open proposal for onion encryption, emerged from a work presented at CRYPTO 2017 and has garnered significant attention from the Tor team for its strong security and efficiency base. However, upon closer examination, it is evident that the design of proposal 295 exhibits a critical flaw—namely, the randomness within the intermediate onion layers is incomplete. This incompleteness renders proposal 295 non-compliant with the Tor-specific anonymity notion known as CircuitHiding, introduced at EUROCRYPT 2018. In this paper, we highlight this anonymity flaw that trivially breaks the CircuitHiding notion. We propose a lightweight fix and rigorously prove the security of the corrected design. To our knowledge, this paper provides the first formal treatment of proposal 295, contributing to Tor’s cryptographic infrastructure. Given that onion encryption has gained prominence as a critical tool for privacy-preserving Internet of Things (IoT) applications, a thorough analysis of its anonymity property is crucial for securing these applications.