# Derive a key from public data using a secret master key

Users in my system will be given a device that contains a 128-bit AES user key. The user key will be derived from 64 bits of public data related to the user, which is unique but very predictable (i.e. a sequential user ID value). The value of the user key must be kept secret from the users. I assume users are fully aware that the user ID is used in the key derivation and that they know its value. A centrally controlled "master" AES key will be used to derive the user key in each device. Users will have no access to this key.

I've been asked to design the derivation scheme. The goal is to ensure the user has no hope of determining their key based on the 64-bits of public data.

My current plan for this derivation is to concatenate a "context" byte to the user ID and then encrypt it with the master key, using ECB-mode and PKCS #7 padding and use the result as the user key.

Does this simplistic derivation scheme meet my design goal? Without knowledge of the master key, I can't fathom how users could infer anything about the user key from the public data. However the simplicity of my design worries me.

I have encountered key derivation schemes, such as RFC 5869 that might be appropriate. I would be much happier using a peer-reviewed method rather than designing my own if someone can point at a suitable standard.

-
Not sure what you mean by "brute force attack is plausible" in the context of HKDF. Your scheme and HKDF seem to aim at the same context, where you have a strong master key. –  CodesInChaos Jul 31 '13 at 7:58
@CodesInChaos Sorry, I confused one RFC with another in my mind. My comments were probably more applicable to key derivation schemes such as those in PKCS #5. –  Duncan Jul 31 '13 at 8:01
is your message longer than one block? –  CodesInChaos Jul 31 '13 at 8:03
@CodesInChaos I've been told it's 64 bits, so that's comfortably smaller than 16 bytes. –  Duncan Jul 31 '13 at 8:06
NIST has also published an AES based variant of HKDF. Might want to look for that one. But personally I prefer hashes for key derivation in most situations. –  CodesInChaos Jul 31 '13 at 8:07

I'd still go with HKDF. Since you already have a good uniform master key, you can skip the extraction step.

So HKDF simply becomes HMAC-SHA-2(masterKey, info+\x01) I'd start info with a string identifying your use, and add the user specific information after that.

Your system should be secure as well as long as you only produce a single block of output. Essentially the user specific info serves as an IV for a mode similar to AES-CTR.

NIST Special Publication 800-56C - Recommendation for Key Derivation through Extraction-then-Expansion defines a scheme similar to AES, but it's probably unnecessarily complicated for your scenario.

-
If you encrypt a unique block with AES you get a unique output, and key recovery is hard. So I don't see a problem with your scheme as long as you only encrypt a single block. –  CodesInChaos Jul 31 '13 at 8:06
Your comments suggests you don't realize that the security of his scheme up to the birthday bound $\hspace{.1 in}$ follows from the block cipher being a weak PRP. $\:$ –  Ricky Demer Jul 31 '13 at 8:43
@RickyDemer The OP won't derive 2^60 keys, so that doesn't matter. For reasonably sized outputs AES-CTR is indistinguishable from random data. And even if you'd go above the birthday bound, it'd most likely stay secure despite indistinguishably breaking down. So I wouldn't worry about the birthday bound. –  CodesInChaos Jul 31 '13 at 9:01

Ideal:
Start with an empty list; whenever given a new input, generate a random element
of $\:\{0,\hspace{-0.04 in}1\hspace{-0.02 in}\}^{128}\:$,$\:$ and output it and add the pair of that input and that output to the list;
whenever given an previously seen input (as determined by looking at the list),
give the same output as was previously given for that input.

Hybrid_I :
Start with an empty list; whenever given a new input, repeatedly generate random
elements of $\:\{0,\hspace{-0.04 in}1\hspace{-0.02 in}\}^{128}\:$ until obtaining one that was not previously given as output,
and output that element; whenever given a previously seen input (as determined
by looking at the list), give the same output as was previously given for that input.

Hybrid_R_(pad) is the composition of Hybrid_I with $\:$pad$\:$.

Choose a random key $r$, and then act as $\: x\mapsto \operatorname{AES}(r,\hspace{-0.01 in}x) \:\:$.

(Obviously, the hybrids only make sense for up to $2^{128}$ queries,
and Real(pad) only makes sense if $\:\operatorname{Range}(\hspace{.01 in}\text{pad}) \subseteq \{0,\hspace{-0.04 in}1\hspace{-0.02 in}\}^{128} \;$.)

As long as Hybrid_I makes sense, the difference between Ideal and Hybrid_I only matters
when the randomly chosen elements of $\:\{0,\hspace{-0.04 in}1\hspace{-0.02 in}\}^{128}\:$ repeat. $\;\;$ (See birthday attack.)

The probability of that happening with at most $q$ queries is at most $\:\frac{\binom{q}{2}}{2^{128}}\:$ (see binomial coefficient).

For all $q$, $\;\;$ if $\:0< q\:$ then $\:\frac{\binom{q}{2}}{2^{128}} < \frac{q^{\hspace{.01 in}2}}{2^{129}}\:\:$.

Since Hybrid_I is symmetric with respect to its inputs,
Hybrid_R_(pad) will behave identically to Hybrid_I whenever $\:$pad$\:$ is injective and Hybrid_I makes sense.

For any oracle adversary $\mathcal{A}$ for distinguishing Real(pad) from Ideal, consider the
oracle adversary $\mathcal{B}$ that applies $\:$pad$\:$ to $\mathcal{A}$'s oracle queries before sending them to the oracle,
forwards the oracle's responses to $\mathcal{A}$, and outputs the same bit as $\mathcal{A}$.
If $\: q\leq 2^{128} \:$ and $\:$pad$\:$ is injective and $\:\operatorname{Range}(\hspace{.01 in}\text{pad}) \subseteq \{0,\hspace{-0.04 in}1\hspace{-0.02 in}\}^{128}\:$,
then such a $\mathcal{B}$ uses no decryption and at most $q$ encryption queries to
distinguish AES from a random permutation by an amount that is at most $\:\frac{\binom{q}{2}}{2^{128}}\:$ less than
the amount by which such an $\mathcal{A}$ distinguishes Real(pad) from Ideal.

Therefore, $\:$ if $\: q\leq 2^{128} \:$ and $\:$pad$\:$ is injective and $\:\operatorname{Range}(\hspace{.01 in}\text{pad}) \subseteq \{0,\hspace{-0.04 in}1\hspace{-0.02 in}\}^{128}\:$, $\;$ then
the previous paragraph gives a constructive reduction from an adversary generating at most $q$ keys
that distinguishes Real(pad) from Ideal by $\:\epsilon+\frac{\binom{q}{2}}{2^{128}}\:$ to an adversary making no decryption queries
and at most $q$ encryption queries that distinguishes AES from a random permutation by at least $\hspace{.01 in}\epsilon$,
whose only additional computation is at most $q$ evaluations of $\:$pad$\:$.

As mentioned by CodesInChaos, even if $\:\frac{\binom{q}{2}}{2^{128}}\:$ is large, there's no known
way to take advantage of the distinctness relation between the keys.

-