KeyForge: Non-Attributable Email from Forward-Forgeable Signatures

Email breaches are commonplace, and they expose a wealth of personal, business, and political data whose release may have devastating consequences. Such damage is compounded by email's strong attributability: today, any attacker who gains access to your email can easily prove to others that the stolen messages are authentic, a property arising from a necessary anti-spam/anti-spoofing protocol called DKIM. This greatly increases attackers' capacity to do harm by selling the stolen information to third parties, blackmail, or publicly releasing intimate or sensitive messages -all with built-in cryptographic proof of authenticity. This paper introduces non-attributable email, which guarantees that a wide class of adversaries are unable to convince discerning third parties of the authenticity of stolen emails. We formally define non-attributability, and present two system proposals -KeyForge and Time-Forge -that provably achieve non-attributability while maintaining the important spam/spoofing protections currently provided by DKIM. Finally, we implement both and evaluate their speed and bandwidth performance overhead. We demonstrate the practicality of KeyForge, which achieves reasonable verification overhead while signing faster and requiring 42% less bandwidth per message than DKIM's RSA-2048. different approaches to building a new type of signature scheme that we introduce: forward-forgeable signatures (FFS). Forward-forgeable signatures. An FFS is a digital signature scheme equipped with a method to selectively disclose signature-invalidating "expiry information" for past signatures without similarly damaging the public key for future signatures. Succinctness of FFS is a measure of efficiency of disclosure. We present two constructions of FFS, which are the key building blocks of KeyForge and TimeForge respectively. FFS may be of independent interest as a signature primitive for other applications. KeyForge. Our first proposal, KeyForge ( §5.1), achieves delayed universal forgeability by publishing signing keys after a delay ∆. KeyForge relies on an FFS based on hierarchical identity-based signatures (HIBS), which achieves logarithmic succinctness. As a result, KeyForge can efficiently distribute forging keys with minimal bandwidth. TimeForge. Our second protocol, TimeForge ( §5.2), assumes a publicly verifiable timekeeper (PVTK) model in which a trusted timekeeper periodically issues publicly verifiable timestamps. In a nutshell, the idea of TimeForge is to substitute each signature on a message m at time t with a succinct zero-knowledge proof of the statement S(m) ∨ T (t + ∆), where: S(m) denotes knowledge of a valid signature by the sender on m and T (t + ∆) denotes knowledge of a valid timestamp for a time later than t + ∆. Including T (t + ∆) ensures delayed universal forgeability, while R(m) ensures immediate recipient forgeability. TimeForge can be described as a forward-forgeable signature scheme in the PVTK model. KeyForge + /TimeForge + . The enhanced protocols ( §5.4) consist of the respective base protocols with the following modifications: (1) an additional protocol, called forge-on-request, that allows parties to request forged emails addressed only to the requester herself under limited circumstances; and (2) for multiple-recipient emails, a new signature is produced for each recipient domain (unlike the base protocols and DKIM, which produce one signature per outgoing email). Among our protocols, KeyForge is the most efficient and would necessitate the least change to existing infrastructure. KeyForge + and TimeForge + are alternative approaches showing the feasibility of addressing stronger threat models though at significant overhead (in fact, certain overhead is unavoidable in the stronger threat model; see §3). TimeForge could become more practical with advances in the fast-moving area of non-interactive proofs. Summary of our Contributions. 1. We define non-attributability in store-and-forward email systems, and propose two system designs -KeyForge ( §5.1), and TimeForge ( §5.2) -that achieve this goal. 2. We implement KeyForge and TimeForge and evaluate their signing, verification, and bandwidth costs, and show that KeyForge has acceptable bandwidth and processing overhead for practical deployment ( §6). 3. We provide formal definitions for email non-attributability and prove that our constructions realize them. 4. Of independent interest, we give provably secure constructions of a new cryptographic primitive, succinct forward-forgeable signatures (FFS)in both the standard and PVTK models ( §4.3, §5.2).