Towards Leakage-Resilient Ratcheted Key Exchange

Ratcheted key exchange captures the heart of modern se- cure messaging, wherein protocol participants continuously update their secret material to protect against full state exposure through forward security (protecting past secrets and messages) and post-compromise se- curity (recovering from compromise). However, many practical attacks only provide the adversary with partial information about the secret state of a given party, an attack vector that has been extensively studied under the umbrella of leakage resilience. Existing models of ratcheted key exchange or messaging therefore provide less-than-optimal guaran- tees under partial leakage due to inherent limitations in security under full state exposure that are exacerbated by relaxations in security made by many practical protocols for performance reasons. In this work, we initiate the study of leakage-resilient ratcheted key ex- change that provides typical guarantees under full state exposure and additional guarantees under partial state exposure between ratchets of the protocol. We consider unidirectional ratcheted key exchange (URKE) where one party acts as the sender and the other as receiver. Start- ing from the notions of Balli et al. introduced at ASIACRYPT 2020, we formalise a key indistinguishability game under randomness manip- ulation and bounded leakage (KIND), which in particular enables the adversary to continually leak a bounded amount of the sender’s state between honest send calls. We construct a corresponding protocol from a key-updatable key encapsulation mechanism (kuKEM) and a leakage- resilient one-time MAC. By instantiating this MAC in the random oracle model (ROM), results from Balli et al. imply that in the ROM, kuKEM and KIND-secure URKE are equally powerful, i.e., can be built from each other. As a second step, given the strong limitations that key indistin- guishability imposes on the adversary, we formalise a one-wayness game that also permits leakage on the receiver. We then propose a correspond- ing construction from leakage-resilient kuKEM, which we introduce, and a leakage-resilient one-time MAC. Furthermore, we show that leakage- resilient kuKEM and one-way-secure URKE can be built from each other in the ROM, highlighting the increased cost that strong one-way secu- rity entails. Our work opens exciting directions for developing practical, leakage-resilient messaging protocols.