Detecting man-in-the-middle attacks during initial generation of shared secrets is a major challenge that arises in many communication platforms offering end-to-end encrypted messaging, audio calls or video calls. Given the inherent ad-hoc nature of many of these extremely-popular platforms, out-of-band authenticated key-exchange protocols are becoming widely deployed in the user-to-user setting: Protocols that enable two users to establish shared secrets, while detecting man-in-the-middle attacks via an external channel through which users can manually authenticate one short value (e.g., two users who recognize each other’s voice can compare a short value).
We initiate the study of out-of-band authentication in the group setting, and establish a tight tradeoff between the length of the out-of-band authenticated value (which is a crucial bottleneck given that the out-of-band channel is of low bandwidth) and the probability that a man-in-the-middle attack is undetected. We present both computationally-secure and statistically-secure protocols together with matching lower bounds. Moreover, instantiating our computationally-secure protocol in the random-oracle model yields an efficient and practically-relevant protocol.
In addition, we consider two important extensions of this model. In the first, we put forward the notion of immediate key delivery, requiring that even if some users participate in the protocol but do not complete it (e.g., due to losing data connectivity), then the remaining users should still agree on a shared secret. We present a protocol with an optimal-length out-of-band value, which is inspired by techniques that have been developed in the context of fair string sampling in order to minimize the effect of adversarial aborts. Our second extension is relevant already in the user-to-user setting, and considers the plausible behavior of “lazy users” who only compare parts of the values presented to them (rather than their entirety). We show that some protocols, including the one used by WhatsApp and Signal, become completely insecure in this scenario, and then we present protocols that retain the best possible security in this setting.
This talk is based on joint works with Moni Naor and Gil Segev.