# Is it possible to know the key if we have the original value and the hash using HmacSHA1?

I was wondering if it were possible to know the key if you already know the original value and the hashed result.

For example, let's say :

```````\$value` = helloworld
`\$hmac_key` = 0123456789
``````

With only `\$value` and `\$result`, is it possible to retrieve `\$hmac_key` ?

In simple basic math, it's quite obvious, but with HmacSHA1, is it also possible?

-
You certainly can't recover the key parameter of HMAC if you know the message and the result. But you question is a bit vague, so I don't know what you're doing, and why. You talk about a salt(as opposed to key), but you assume that it should be secret, which is an unusual combination. – CodesInChaos May 9 '12 at 11:51
I updated my question to be more precise. But I think you answered it in the comment ;) If so, two options : you put your comment as an answer and I accept it or I can also delete this question. You choose :) – Cyril N. May 9 '12 at 11:55

It is not possible to get the key given this information. Otherwise, you'd have a pretty serious security problem. Many "full-strength" cryptography(and hashing) algorithms have the proper that knowing input-output pairs does not bring attackers closer to figuring out the key. This is sometimes called "key wear", based on your key being worn down with use and becoming less secure.

-

It is not possible to recover the key ... assuming the key has sufficient entropy.

Here's what the attacker can do. If the attacker has a guess at the key, the attacker can check whether his guess is correct. This means that if the attacker can narrow down the list of possibilities for the key to a short enough list, the attacker can simply try all possibilities in that list and see which one is correct, and the attacker will eventually discover the correct value of the key. This attack strategy is known as brute-force search, or exhaustive keysearch. It turns out that this is essentially the only attack an attacker can do; with SHA1-HMAC, an attacker can't do any better than this attack strategy.

So, your job as defender is to make sure that the number of possibilities for the key is large enough that brute-force search will be unsuccessful. Ideally, there would be at least 2128 possibilities for the key, all equally likely. For instance, you might generate the key by reading 128 bits from `/dev/urandom`. If that is how you select the key, then there will be no way for an attacker to recover the key.

On the other hand, if you do a lousy job as defender of picking the key, then it might be possible for an attacker to recover the key. For instance, suppose you decide your key will be a random 4-digit number. Well, then there are only 10,000 possibilities for the key, so an attacker can try them all and identify which one is correct. The trial-and-error process will take only milliseconds -- so if that's how you picked your key, things would be totally insecure, and the attacker would be able to recover the key. If you pick a random 10-digit number as your key, then there are 1010 possible values of the key, which is still not enough: an attacker could try all of those possible value in mere hours. So, don't do that. Or, if you use someone's telephone number or SSN as the key, then again it will be possible for an attacker to recover the key (simply by trying all possibilities). So, don't do that, either.

In short: choose your key using 128 bits of crypto-strength randomness. Then, it will not be possible for an attacker to recover the key.

-

In general, you try to keep the original secure, and the salt is stored in a less secure way, in general inside some database table along with the username, or something like that. You're asking the opposite of what generally happens.

So, assuming that salt is stored somewhere, and nobody had access to it, it's as "hard to find" as the original would be in the usual way.

When people say to "use a salt do prevent pre-computed tables", the salt have two purposes: making your password "bigger", so that it won't be in a covered pre-computade table range, and preventing that two users with the same password end up with the same hash.

If you have a piece of it secrect (the original piece) and another one that could be disclosed (the salt piece), you'll be making the attacker go with brute-force, since the known piece (salt) will be appended to every try.

What happens when you disclose the original piece and keep the salt very secret is that you're simply reversing the names: the original is the one known, and the salt is the secret one. So, all observations about the hardness to find the original when you know the salt still applies.

-
I'm sorry you wrote your entire answer based on my wrongly said word "salt". I was meaning "key". I updated my post. As a sorry I upvoted your answer since it's still quite interesting. – Cyril N. May 9 '12 at 11:59

A good Message Authentication Code algorithm should be resistant to forgeries: imagine that the Bad Guy has access to a box which computes HMAC/SHA-1 over inputs that he chooses and provides; internally, the box uses a secret key. The goal of the attacker is to build a pair (m,h) where h is a correct MAC for message m, without using m as an input to the box. If you prefer, the attacker feeds N inputs to the box and tries to end with N+1 valid MAC values. Key recovery would be even worse (if the attacker recovers the key, then he can produce as many (m,h) pairs that he wishes to).

If the MAC output has length n bits, and the attacker can succeed by sending less than 2n-1 queries to the box and spending less than 2n-1 MAC invocations worth of CPU, then the MAC algorithm is declared "broken" (at least in an academic way). Currently, HMAC/SHA-1 is NOT broken (even academically), and since its output is n = 160 bits, and a CPU effort of 2159 is totally out of reach of mankind, we can say that nobody can produce forgeries on HMAC/SHA-1, let alone recover the key, given input/output pairs (even if the attacker gets to choose the input values in these pairs).

The above assumes that the key is itself taken from a set of possible keys of size at least 2n. If you use a key with less than n bits, then the attacker can just try random sequences of n bits until a match is found. That's the generic exhaustive search attack. If the key has length at least 80 bits or so, this is not feasible with today's technology (with a 128-bit key, you have a very substantial security margin). Then again, this assumes that the set of possible keys is really that large, i.e. that you used a cryptographically strong PRNG to generate the key -- see @D.W.'s answer for details.

-