# Creating HMAC keys using a fixed prefix and a random string

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.

• Could you explain what HMAC is? – Jeffε Oct 13 '10 at 14:34
• @JeffE: HMAC is a cryptographic construct used in generating MACs (Message Authentication Codes) using hash functions. More info is provided here: en.wikipedia.org/wiki/HMAC – M.S. Dousti Oct 13 '10 at 15:47
• I would prefer to do the following: SHA1(SHA1(appname)+SHA1(secret)) – luis.espinal Oct 13 '10 at 18:14

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

• David, you cannot easily extend the ROM to the real world. For instance, "extension attacks" are non-issue against RO-based hash functions, while they may be applied to Merkle-Damgard based hash functions (see en.wikipedia.org/wiki/Merkle-Damgard_construction). This gap between theory & practice made theorist think about other ways of formalizing properties of hash functions, and they succeeded to some extend. The bottom-line is that, even if you want to speak about theory, you do not have to resort to ROM; and whatever is proven in ROM does not often hold in practice. – M.S. Dousti Oct 13 '10 at 17:54
• Arguing that extension attacks invalidate ROM proofs is weak. Fine, we make sure we never put the secret at the beginning of the hashed message. What else goes wrong? – David Cash Oct 13 '10 at 18:38
• There are tone of arguments on the provable consequences of ROM security in the standard model. I was just pointing to one. I does not intend to say that your result is wrong, I just wanted to mention that one must be extremely cautious when extending ROM results to the real world. – M.S. Dousti Oct 13 '10 at 18:41
• One must be extremely cautious when extending any provable-security result to the real world. The ROM is no different from other techniques in this respect. – David Cash Oct 14 '10 at 5:51
• I actually feel unqualified to judge which was the best answer, so sorry if anyone would dispute this one being "accepted", but this one helped me the most. Many thanks! – spookylukey Oct 14 '10 at 12:14

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.

• It is not enough that the adversary "lack access to $k_i$." We must argue that $k_1,\ldots,k_n$ are all computationally indistinguishable from uniform and independent keys in order for HMAC security to apply. – David Cash Oct 13 '10 at 18:40
• @David: AFAIK, no such proof can be given unless we resort to hash functions whose outputs are uniformly distributed (i.e. Random Oracles). – M.S. Dousti Oct 13 '10 at 18:45
• Or hash functions with PRF-type properties. :) – David Cash Oct 13 '10 at 19:32
• One more thing: Here, I think we do not need anything other than collision resistance. If I'm right, computationally indistinguishable is not required at all. – M.S. Dousti Oct 13 '10 at 20:23

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

• SHA1("known string") == "another known string", leaving the first option equal to SHA1("different salt" + SHA1(x)), which seems less secure to me - since SHA1(x) has only 20 bytes of entropy, which is less than x, which has at least 50 bytes in my application. – spookylukey Oct 14 '10 at 0:24
• If the first option is equal to SHA1("different salt"+ SHA1(x)) then they are equally as insecure. You do bring a good point that SHA1 only has 20 bytes of entropy which I completely forgot,and which invalidates my previous suggestions... mod up for you:) However, there is something ungainly about using the plain salt as is. If instead of feeding the concatenation of the salt and the message, you could feed a permutation and expansion of both salt and message, that would increase the search space (just in case the attacker knows the application name a-priori.) – luis.espinal Oct 14 '10 at 14:21