NPRFs and their application to Message Layer Security

Chris Brzuska, Jan Winkelmann


Noise, Signal and TLS 1.3 use key derivation functions (KDF) and pseudorandom functions (PRF) to combine key material to obtain a secure key whenever at least one of the input keys is secure. Security analyses of the aforementioned protocols either analyze the protocol in the random oracle model or, if only two keys are combined at a time, assume that in the KDF/PRF, the role of the key and the message are interchangeable. Thus, protocols typically rely on the ad hoc assumption of a dual KDF or a dual PRF (DPRF).
To combine more than two secrets, state-of-the-art protocols apply the DPRF multiple times sequentially, each time evaluating it on one new secret as well as piping in the result of the previous DPRF call. The resulting number of sequential DPRF evaluations is thus linear in the number of keys to be combined.
We propose n-pseudorandom functions (NPRFs) as a new primitive which combines an arbitrary number of keys. We provide a security model for our multi-instance, multi-key primitive. We then provide a practical construction of NPRFs which is parallelizable and, in each of the parallel branches (one for each secret), requires only 1 PRF evaluation, independently of the number of keys to be combined. It is based on the standard assumption that HMAC is a PRF.
We compare the security of our NPRF construction with the aforementioned piping construction under collision attacks, i.e., colliding key values, colliding key names and colliding context values. By adding one or two more PRF evaluations in each of the parallel branches, we improve the security of our basic NPRF to be on the same or higher level of collision-resistance than the aforementioned piping construction. These extended constructions additionally assume that salted HMAC is a collision-resistant hash-function.
As a case study, we explore key derivation in the current draft of the Message Layer Security (MLS) IETF standard, and provide justification for pull request 337 which is a change to the current draft of the MLS standard that we suggest, based on our NPRF construction.


Additional Material

Return to Chris Brzuska's Homepage

Last update: 2020-07-26