Creating HMAC keys using a fixed prefix and a random string

Question

In a system that uses HMAC for a number of different applications, it is important to use different keys for different applications. Suppose:

1. there is just a single random string available (50 bytes long, in this case)
2. we are using HMAC-SHA1
3. we will shorten keys longer than the blocksize using SHA1 (as per RFC 2104)

Is it safe to generate unique keys by prefixing the application name to the secret, so that the key for application 1 ends up as SHA1("application1" + secret) and the key for application 2 ends up as SHA1("application2" + secret)? The strings "application1" and "application2" are not kept secret. Or does this open up significant weaknesses compared to using completely different secret keys for each application?

Thanks.

Answer 1

Your idea sounds reasonable, at least in theory (and that's what we do here, right? :)

A standard way to justify and analyze a design decisions like this is via the random oracle model (ROM) methodology. Bellare and Rogaway (CCS'93) gave a nice description of ROM analysis, and are generally credited with suggesting that it be applied in practical cryptography. In the ROM, one pretends that the function SHA1(.) is a truly random function that is available to everyone through an oracle. Of course, this is never true in reality because SHA1(.) is defined by a publicly-known algorithm. Nevertheless, ROM analysis seems to be an excellent tool for verifying that protocols and algorithms do not have certain structural weaknesses of the sort you should be worried about.

Usage of the ROM is sometimes regarded as a heuristic that theoretically results in a security weakness. In your situation, you could alternatively justify your design by assuming that the keyed function $F$, defined by

$F_K(x) = SHA1(x||K)$,

is a secure pseudorandom function. Now, this is an assumption that has a reasonable shot at being true, unlike the situation with pretending that SHA1 is a ROM.

Either way, we are searching for some way to justify that each of the HMAC keys you generate will look uniformly random and independent to an adversary. After that step, we could give a standard reductionist/"provable security" analysis of HMAC composed with your key derivation step.

(I'm ignoring issues with input/output lengths not fitting together, and so on. To do this right in a product you'd have to be much more careful about all of this than I have been. Lower-level errors can mess everything up.)

Answer 2

Let's put it more formally first. Let $s$, $t$ be strings known to the adversary, and $k$ be a secret key. Let $k_1$ and $k_2$ be the keys obtained as $k_1 = H(s|k)$ and $k_2 = H(t|k)$ respectively, where $H(\cdot)$ is a collision-resistant hash function, and $|$ denotes the concatenation. The question is,

Is function $f_i(\cdot)=HMAC(\cdot, k_i)$ a MAC?

The answer is yes. I don't have a formal proof, yet the following reasoning seems just fine (see also this topic): Given $s$ and $t$, and keeping $k$ secret, the adversary will be unable to deduce $k_1$ or $k_2$ with non-negligible probability. Lacking access to $k_i$, the key to HMAC, function $f_i$ will indeed act as a MAC.

Answer 3

One could think that the appname prefix is a salt (but not necessarily a nonce). By the principle of confusion, I would, at the very least, do the following to generate the HMAC $y$ out of both the salt and $x$:

$y = HMAC_{salt}(x) = SHA1(\mbox{ }SHA1(salt) + SHA1(x) \mbox{ } )$

Better yet, if I had in my possession a permutation function $z = perm(x_1,x_2)$, and if it is desirable and cost effective, I would use it (instead of concatenation) to increase diffusion:

$y = HMAC_{salt}(x) = SHA1(\mbox{ }perm(SHA1(salt),SHA1(x))\mbox{ })$