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

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 ?

• This looks much better to me. Not sure why they did it that way, it seems ridiculous. Sometimes these choices are motivated by e.g. hardware support for AES but for nothing else (especially in embedded systems), but it does not seem to be the case here. Is this already in production or still in development? – Thomas Jan 14 '17 at 11:39
• It's been merged in for some time now, but the only big user of ext4 encryption that I know of is android 7 and they seem to be using a different key derivation mechanism (source.android.com/security/encryption/…) – rca Jan 14 '17 at 22:13
• While you're at it, you could use an actual KDF (key derivation function) such as HKDF (which uses HMAC underneath), or maybe one based on a block cipher (so you need only one primitive). Counter mode KDF comes to mind in NIST SP 800-108. By the way, I think that the downside that's already mentioned would be enough to not use the scheme - imagine the nonce being predictable or the RNG being predictable just once. Ugh. – Maarten Bodewes Jan 16 '17 at 1:33
• They're using a non-secret nonce as the AES key? Isn't that super fishy? Ciphers are normally evaluated under models like CPA or CCA where the key is secret and the messages aren't; this scenario is the other way around! – Luis Casillas Jan 17 '17 at 1:58
• That's what I understood of it. I'm quite surprised myself so I welcome anyone willing to confirm this. Here is the code for those interested. key derivation – rca Jan 17 '17 at 7:19

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)
}

• The master key is indeed random so the AES-GCM-SIV method looks good. – rca Jan 17 '17 at 16:58