Cryptology ePrint Archive: Report 2022/065

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

Nimrod Aviram and Benjamin Dowling and Ilan Komargodski and Kenneth G. Paterson and 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.

Category / Keywords: HKDF; Key Combiners; Hybrid Key Exchange

Date: received 18 Jan 2022, last revised 25 Feb 2022

Contact author: nimrod aviram at gmail com, b dowling at sheffield ac uk, ilank at cs huji ac il, kenny paterson at inf ethz ch, eyal ronen at cs tau ac il, eylony at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20220225:161618 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]