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.
This version contains an illustrated discussion of the suggested change to the current draft of the MLS standard. See bottom of page 4 until the middle of page 11. Minor revision compared to 2020/06/09, mostly corrected typos.
This version contains an illustrated discussion of the suggested change to the current draft of the MLS standard. See bottom of page 4 until the middle of page 11.
This document contains a discussion and comparison of different MLS Key Schedule proposals.
Return to Chris Brzuska's Homepage
Last update: 2020-07-26