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

<p>A standard way to justify and analyze a design decisions like this is via the <em>random oracle model (ROM) methodology</em>.  <a href="http://portal.acm.org/citation.cfm?doid=168588.168596" rel="nofollow">Bellare and Rogaway (CCS'93)</a> 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.</p>

<p>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</p>

<p>$F_K(x) = SHA1(x||K)$,</p>

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

<p>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.</p>

<p>(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.)</p>

CC BY-SA 2.5
2010-10-13T17:54:21.913Z
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 http://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.
Sadeq Dousti
CC BY-SA 2.5
2010-10-13T18:38:05.057Z
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
CC BY-SA 2.5
2010-10-13T18:41:57.290Z
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.
Sadeq Dousti
CC BY-SA 2.5
2010-10-14T05:51:23.190Z
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
CC BY-SA 2.5
2010-10-14T12:14:34.903Z
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
CC BY-SA 2.5
2010-10-13T17:21:39.157Z
2010-10-13T17:21:39.157Z
David Cash
<p>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, </p>

<blockquote>
  <p>Is function $f_i(\cdot)=HMAC(\cdot, k_i)$ a MAC?</p>
</blockquote>

<p>The answer is yes. I don't have a formal proof, yet the following reasoning seems just fine (see also <a href="https://cstheory.stackexchange.com/q/17/873">this topic</a>): 
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.</p>

CC BY-SA 2.5
2010-10-13T18:40:14.733Z
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
CC BY-SA 2.5
2010-10-13T18:45:19.810Z
@David: AFAIK, no such proof can be given unless we resort to hash functions whose outputs are uniformly distributed (i.e. Random Oracles).
Sadeq Dousti
CC BY-SA 2.5
2010-10-13T19:32:05.540Z
Or hash functions with PRF-type properties.  :)
David Cash
CC BY-SA 2.5
2010-10-13T20:23:33.953Z
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.
Sadeq Dousti
CC BY-SA 2.5
2010-10-13T13:51:46.573Z
2010-10-13T13:51:46.573Z
2017-04-13T12:32:28.167Z
Sadeq Dousti
<p>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$:</p>

<p>$y = HMAC_{salt}(x) = SHA1(\mbox{  }SHA1(salt) + SHA1(x) \mbox{  } )$</p>

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

<p>$y = HMAC_{salt}(x) = SHA1(\mbox{  }perm(SHA1(salt),SHA1(x))\mbox{  })$</p>

CC BY-SA 2.5
2010-10-14T00:24:31.037Z
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
CC BY-SA 2.5
2010-10-14T14:21:44.470Z
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
CC BY-SA 2.5
2010-10-13T18:34:44.153Z
2010-10-13T18:34:44.153Z
luis.espinal
<p>In a system that uses HMAC for a number of different applications, it is important to use different keys for different applications.  Suppose:</p>

<ol>
<li>there is just a single random string available (50 bytes long, in this case) </li>
<li>we are using HMAC-SHA1 </li>
<li>we will shorten keys longer than the blocksize using SHA1 (as per RFC 2104)</li>
</ol>

<p>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?</p>

<p>Thanks.</p>

CC BY-SA 2.5
2010-10-13T14:34:25.047Z
Could you explain what HMAC is?
Jeffε
CC BY-SA 2.5
2010-10-13T15:47:16.140Z
@JeffE: HMAC is a cryptographic construct used in generating MACs (Message Authentication Codes) using hash functions. More info is provided here: http://en.wikipedia.org/wiki/HMAC
Sadeq Dousti
CC BY-SA 2.5
2010-10-13T18:14:33.097Z
I would prefer to do the following: SHA1(SHA1(appname)+SHA1(secret))
luis.espinal
<cr.crypto-security>
Creating HMAC keys using a fixed prefix and a random string
spookylukey
# Creating HMAC keys using a fixed prefix and a random string

(Asked by: username_0 on 2010-10-13)

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.

**Tags:** cr.crypto-security
> **Comments:**
> **username_1**: Could you explain what HMAC is?  
> **username_2**: @JeffE: HMAC is a cryptographic construct used in generating MACs (Message Authentication Codes) using hash functions. More info is provided here: http://en.wikipedia.org/wiki/HMAC  
> **username_3**: I would prefer to do the following: SHA1(SHA1(appname)+SHA1(secret))  

---

## 3 answers

### Answer by username_4 on 2010-10-13. Score: 2 | Accepted answer

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)](http://portal.acm.org/citation.cfm?doid=168588.168596) 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.)

> **Comments:**
> **username_2**: 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 http://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.  
> **username_4**: 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?  
> **username_2**: 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.  
> **username_4**: 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.  
> **username_0**: 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!  

---

### Answer by username_2 on 2010-10-13. Score: 4

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](https://cstheory.stackexchange.com/q/17/873)):
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.

> **Comments:**
> **username_4**: 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.  
> **username_2**: @David: AFAIK, no such proof can be given unless we resort to hash functions whose outputs are uniformly distributed (i.e. Random Oracles).  
> **username_4**: Or hash functions with PRF-type properties.  :)  
> **username_2**: 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.  

---

### Answer by username_3 on 2010-10-13. Score: 2

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

> **Comments:**
> **username_0**: 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.  
> **username_3**: 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.)  

---

