International Association
for Cryptologic Research

Key derivation functions (KDFs) are integral to many cryptographic protocols. Their functionality is to turn raw key material, such as a Diffie-Hellman secret, into a strong cryptographic key that is indistinguishable from random. This guarantee was formalized by Krawczyk together with the seminal introduction of HKDF (CRYPTO 2010), in a model where the KDF only takes a single key material input. Modern protocol designs, however, regularly need to combine multiple secrets, possibly even from different sources, with the guarantee that the derived key is secure as long as at least one of the inputs is good. This is particularly relevant in settings like hybrid key exchange for quantum-safe migration. Krawczyk's KDF formalism does not capture this goal, and there has been surprisingly little work on the security considerations for KDFs since then. In this work, we thus revisit the syntax and security model for KDFs to treat multiple, possibly correlated inputs. Our syntax is assertive: We do away with salts, which are needed in theory to extract from arbitrary sources in the standard model, but in practice, they are almost never used (or even available) and sometimes even misused, as we argue. We use our new model to analyze real-world multi-input KDFs---in Signal's X3DH protocol, ETSI's TS 103-744 standard, and MLS' combiner for pre-shared keys---as well as new constructions we introduce for specialized settings---e.g., a purely blockcipher-based one. We further discuss the importance of collision resistance for KDFs and finally apply our multi-input KDF model to show how hybrid KEM key exchange can be analyzed from a KDF perspective.

Key derivation functions (KDFs) are integral to many cryptographic protocols, turning raw (e.g., Diffie-Hellman) key material into strong cryptographic keys. Traditionally KDFs are designed and analyzed, for settings where they take a single key material input. Modern protocol designs, however, regularly need to combine multiple secrets (e.g., in hybrid key exchange for quantum-safe migration) with the guarantee that the derived key is secure as long as at least one of the inputs is good. Complex applications, especially in the setting where keys are user-managed, may even require threshold versions of KDFs. In this talk, we present lessons learned from analyzing such real-world proposals for multi-input KDFs. We first discuss combiner KDFs (aka key combiners), studying the designs in Signal's X3DH protocol, ETSI's TS 103-744 standard for hybrid key exchange, and MLS' combiner for pre-shared keys. Notably, the ETSI standard, widely recognized and recommended for use, for example by the German Federal Agency for IT Security, misuses the underlying HKDF salt input in a way that makes it insecure in its general form. We take the opportunity to revisit the syntax and security model for KDFs (mainly due to Krawczyk's HKDF paper, CRYPTO 2010) to give results on multiple-input KDFs. Taking an assertive stand on syntax, we do away with salts, which are needed in theory to extract from arbitrary sources in the standard model, but in practice, are almost never used (or even available) and sometimes even misused, as we saw. We then turn to the novel threshold primitive, which emerged as part of the multi-factor KDF (MFKDF) design (Nair and Song, USENIX 2023). We show how a naive implementation (such as the one proposed in MFKDF) leaves the scheme open to devastating cryptographic attacks and discuss ways forward.

The Fast IDentity Online (FIDO) Alliance has developed the widely adopted FIDO2 protocol suite that allows for passwordless online authentication. Cryptographic keys stored on a user’s device (e.g. their smartphone) are used as credentials to authenticate to services by performing a challenge-response protocol. Yet, this approach leaves users unable to access their accounts in case their authenticator is lost. The device manufacturer Yubico thus proposed a FIDO2-compliant mech- anism that allows to easily create backup authenticators. Frymann et al. (CCS 2020) have first analyzed the cryptographic core of this pro- posal by introducing the new primitive of Asynchronous Remote Key Generation (ARKG) and accompanying security definitions. Later works instantiated ARKG both from classical and post-quantum assumptions (ACNS 2023, EuroS&P 2023). As we will point out in this paper, the security definitions put forward and used in these papers do not adequately capture the desired security requirements in FIDO2-based authentication and recovery. This issue was also identified in independent and concurrent work by Stebila and Wilson (AsiaCCS 2024), who proposed a new framework for the analy- sis of account recovery mechanisms, along with a secure post-quantum instantiation from KEMs and key-blinding signature schemes. In this work, we propose alternative security definitions for the primitive ARKG when used inside an account recovery mechanism in FIDO2. We give a secure instantiation from KEMs and standard signature schemes, which may in particular provide post-quantum security. Our solution strikes a middle ground between the compact, but (for this particular use case) inadequate security notions put forward by Frymann et al., and the secure, but more involved and highly tailored model introduced by Stebila and Wilson.