Derivation of many (Key, IV) pairs from random 128 nonces and one secret 512 master key

Question

The ext4 encryption system encrypt files with aes-256-xts. Each file uses two unique keys which are derived from a 512 bit master key and a per-file 128 bit nonce randomly generated when the file is created (see the design doc).

In order to derive two 256 bit keys for each file, the 512 bit master key is encrypted with AES-128-ECB using the 128 nonce as a key.

One disadvantage noted in the design doc is that if the file keys are leaked then the attacker can retrieve the master key by decrypting the file keys with the nonce.

My question is : why not use a one-way KDF to derive the per-file keys instead ? I would have derived the keys using something like :

key1||key2 = hmac_sha512(master_key, nonce)

Is there any downsides with this approach ?

Answer 1

Do we get to assume that the master key is uniformly selected? The goal of a KDF, as the HKDF paper defines it, is this:

Its goal is to take a source of initial keying material, usually containing some good amount of randomness, but not distributed uniformly or for which an attacker has some partial knowledge, and derive from it one or more cryptographically strong secret keys. We associate the notion of “cryptographically strong” keys with that of pseudorandom keys, namely, indistinguishable by feasible computation from a random uniform string of the same length.

If the master key is selected uniformly at random, then the full HKDF extract-and-expand paradigm is not needed; all we need is the expand phase, which can be realized by a PRF with an uniform key.

Given the PRF security of HMAC-SHA512 your use of it looks appropriate then, but possibly overkill because:

• HMAC supports variable input lengths, but this application has fixed input and output sizes;
• The application is already using AES, so bringing in HMAC requires an extra primitive.

So perhaps simpler would be to just:

1. Use a shorter, 256-bit master key directly as the AES key;
2. Given a file's random nonce, derive the file key as fk = fk[1] || fk[2] || fk[3] || fk[4], where:

• fk[0] = random_nonce;
• fk[i] = AESENC(master_key, fk[i-1]).

This is equivalent to encrypting all-zero plaintexts in OFB or CBC mode with random IVs, so attacks against this approach should reduce to attacks against those modes. So for example if some file keys are leaked as you suggest, that's a known-plaintext attack scenario.

As a real-life example, the current AES-GCM-SIV draft (draft-irtf-cfrg-gcmsiv-02) uses a variant of this to derive its encryption and authentication subkeys (section 4):

if len(key-generating-key) == 16 {
  record-authentication-key = AES128(key = key-generating-key, input = nonce)
  record-encryption-key = AES128(key = key-generating-key,
                                 input = record-authentication-key)
} else if len(key-generating-key) == 32 {
  record-authentication-key = AES256(key = key-generating-key, input = nonce)
  second-half = AES256(key = key-generating-key, input = record-authentication-key)
  first-half = AES256(key = key-generating-key, input = second-half)
  record-encryption-key = concatenate(first-half, second-half)
}