In the wake of recent revelations of mass government surveillance, secure messaging protocols have come under renewed scrutiny. A widespread weakness of existing solutions is the lack of strong deniability properties that allow users to plausibly deny sending messages or participating in conversations if the security of their communications is later compromised. Deniable authenticated key exchanges (DAKEs), the cryptographic protocols responsible for providing deniability in secure messaging applications, cannot currently provide all desirable properties simultaneously. We introduce two new DAKEs with provable security and deniability properties in the Generalized Universal Composability framework. Our primary contribution is the introduction of Spawn, the first non-interactive DAKE that offers forward secrecy and achieves deniability against both offline and online judges; Spawn can be used to improve the deniability properties of the popular TextSecure secure messaging application. We also introduce an interactive dual-receiver cryptosystem that can improve the performance of the only existing interactive DAKE with competitive security properties. To encourage adoption, we implement and evaluate the performance of our schemes while relying solely on standard-model assumptions.
In the wake of recent revelations of mass government surveillance, secure messaging protocols have come under renewed scrutiny. A widespread weakness of existing solutions is the lack of strong deniability properties that allow users to plausibly deny sending messages or participating in conversations if the security of their communications is later compromised. Deniable authenticated key exchanges (DAKEs), the cryptographic protocols responsible for providing deniability in secure messaging applications, cannot currently provide all desirable properties simultaneously. We introduce two new DAKEs with provable security and deniability properties in the Generalized Universal Composability framework. Our primary contribution is the introduction of Spawn, the first non-interactive DAKE that offers forward secrecy and achieves deniability against both offline and online judges; Spawn can be used to improve the deniability properties of the popular TextSecure secure messaging application. We also introduce an interactive dual-receiver cryptosystem that can improve the performance of the only existing interactive DAKE with competitive security properties. To encourage adoption, we implement and evaluate the performance of our schemes while relying solely on standard-model assumptions.
Abstract A deniable authenticated key exchange (DAKE) protocol establishes a secure channel without producing cryptographic evidence of communication. A DAKE offersstrong deniabilityif transcripts provide no evidence even if long-term key material is compromised (offline deniability) and no outsider can obtain evidence even when interactively colluding with an insider (online deniability). Unfortunately, existing strongly deniable DAKEs have not been adopted by secure messaging tools due to security and deployability weaknesses. In this work, we propose three new strongly deniable key exchange protocols—DAKEZ, ZDH, and XZDH—that are designed to be used in modern secure messaging applications while eliminating the weaknesses of previous approaches. DAKEZ offers strong deniability in synchronous network environments, while ZDH and XZDH can be used to construct asynchronous secure messaging systems with offline and partial online deniability. DAKEZ and XZDH provide forward secrecy against active adversaries, and all three protocols can provide forward secrecy against future quantum adversaries while remaining classically secure if attacks against quantum-resistant cryptosystems are found. We seek to reduce barriers to adoption by describing our protocols from a practitioner’s perspective, including complete algebraic specifications, cryptographic primitive recommendations, and prototype implementations. We evaluate concrete instantiations of our DAKEs and show that they are the most efficient strongly deniable schemes; with all of our classical security guarantees, our exchanges require only 1 ms of CPU time on a typical desktop computer and at most 464 bytes of data transmission. Our constructions are nearly as efficient as key exchanges with weaker deniability, such as the ones used by the popular OTR and Signal protocols.
We introduce the first deniable attribute-based key exchange (DABKE) framework that is resilient to impersonation attacks. We define the formal security models for DABKE framework, and propose a generic compiler that converts any attribute-based key exchanges into deniable ones. We prove that it can achieve session key security and user privacy in the standard model, and strong deniability in the simulation-based paradigm. In particular, the proposed generic compiler ensures: 1) a dishonest user cannot impersonate other user’s session participation in conversations since implicit authentication is used among authorized users; 2) an authorized user can plausibly deny his/her participation after secure conversations with others; 3) the strongest form of deniability is achieved using one-round communication between two authorized users.
Key-exchange, in particular Diffie-Hellman key-exchange (DHKE), is among the core cryptographic mechanisms for ensuring network security. For key-exchange over the Internet, both security and privacy are desired. In this paper, we develop a family of privacy-preserving authenticated DHKE protocols named deniable Internet key-exchange (DIKE), both in the traditional PKI setting and in the identity-based setting. The newly developed DIKE protocols are of conceptual clarity and practical (online) efficiency. They provide useful privacy protection to both protocol participants, and add novelty and new value to the IKE standard. To the best of our knowledge, our protocols are the first provably secure DHKE protocols that additionally enjoy all the following privacy protection advantages: 1) forward deniability, actually concurrent non-malleable statistical zero-knowledge, for both protocol participants simultaneously; 2) the session transcript and session-key can be generated merely from DH-exponents (together with some public values), which thus cannot be traced to the pair of protocol participants; and 3) exchanged messages do not bear peer's identity, and do not explicitly bear player role information.
Secure messaging protocols have come to take a central role in modern, internet-based communication.Besides the common notions of confidentiality and authentication, many protocols also aim to provide a form of deniability.A deniable protocol enables parties to plausibly deny certain claims about their communication to a third party, the Judge.For example, participation deniability allows communicating parties to claim that any evidence of communication happening could have been fabricated by some other party.This can be especially useful when dealing for example with oppressive regimes that want to punish communication to international press.Therefore, in this thesis, we formalize one form of deniability, participation deniability, for two-party secure messaging protocols.We consider both an offline setting, in which the Judge only has access to evidence of a past conversation, and an online setting, where the Judge can directly observe and influence the conversation.In addition, the possibility for one or both parties to have their state leaked is taken into account.We investigate the relations between our varying notions of deniability and prove the impossibility of a protocol both providing full online deniability and authentication.Afterwards, we analyse the Signal protocol within this context.To circumvent the aforementioned impossibility, we introduce a relaxed version of our online model and continue to show that the Signal protocol can achieve this notion of online deniability.i
We propose two public-key schemes to achieve deniable authentication for the Internet Key Exchange (IKE). Authentication in security had is the essential factor in the key establishment over Internet. The Deniable Internet key exchange protocol gives more value to the IKE standard. Our schemes can in some situations be more efficient than existing IKE protocols as well as having stronger deniability properties. Key-exchange, in particular Diffie–Hellman key exchange (DHKE), is among the core cryptographic mechanisms for ensuring network security. For key-exchange over the Internet, both security and privacy are desired. In this paper, we develop a family of privacy-preserving authenticated DHKE protocols named deniable Internet key-exchange (DIKE), both in the traditional PKI setting and in the identity-based setting. The newly developed DIKE protocols are of conceptual clarity and practical (online) efficiency. They provide useful privacy protection to both protocol participants, and add novelty and new value to the IKE standard.
Although the objective of secure communication can be achieved by using cryptographic tools, the undeniability that results from cryptographic properties may create a potential threat to the sender of the message. Unfortunately, most existing deniable protocols only provide 1-out-of-2 deniability. When both parties (the sender and the receiver) are allowed to deny generating the message, a dispute might occur between these two parties. The 1-out-of-2 deniable protocol can result in an unfair resolution of the dispute. Therefore, we propose a new model of deniability, called 1-out-of-∞ deniability, that can provide full deniability. The 1-out-of-∞ deniability protocol allows the originator of the message to deny that he or she generated the message, since there are an infinite number of possible message generators; at the same time, all transmitted messages can be protected and authenticated between the sender and the intended receiver. Our design can be implemented by using any public-key cryptography technique. We also analyze the correctness of the proposed protocols based on logical rules, and two practical examples are given to illustrate our design.