Paper 2022/065

Practical (Post-Quantum) Key Combiners from One-Wayness and Applications to TLS

Nimrod Aviram, Benjamin Dowling, Ilan Komargodski, Kenneth G. Paterson, Eyal Ronen, and Eylon Yogev

Abstract

The task of combining cryptographic keys, some of which may be maliciously formed, into one key, which is (pseudo)random is a central task in cryptographic systems. For example, it is a crucial component in the widely used TLS and Signal protocols. From an analytical standpoint, current security proofs model such key combiners as dual-PRFs -- a function which is a PRF when keyed by either of its two inputs -- guaranteeing pseudo-randomness if one of the keys is compromised or even maliciously chosen by an adversary. However, in practice, protocols mostly use HKDF as a key combiner, despite the fact that HKDF was never proven to be a dual-PRF. Security proofs for these protocols usually work around this issue either by simply assuming HKDF to be a dual-PRF anyway, or by assuming ideal models (e.g. modelling underlying hash functions as random oracles). We identify several deployed protocols and upcoming standards where this is the case. Unfortunately, such heuristic approaches to security tend not to withstand the test of time, often leading to deployed systems that eventually become completely insecure. In this work, we narrow the gap between theory and practice for key combiners. In particular, we give a construction of a dual-PRF that can be used as a drop-in replacement for current heuristic key combiners in a range of protocols. Our construction follows a theoretical construction by Bellare and Lysyanskaya, and is based on concrete hardness assumptions, phrased in the spirit of one-wayness. Therefore, our construction provides security unless extremely strong attacks against the underlying cryptographic hash function are discovered. Moreover, since these assumptions are considered post-quantum secure, our construction can safely be used in new hybrid protocols. From a practical perspective, our dual-PRF construction is highly efficient, adding only a few microseconds in computation time compared to currently used (heuristic) approaches. We believe that our approach exemplifies a perfect middle-ground for practically efficient constructions that are supported by realistic hardness assumptions.