Tell me more ×
IT Security Stack Exchange is a question and answer site for IT security professionals. It's 100% free, no registration required.
up vote 2 down vote favorite

An HMAC is basically a "keyed hash". Only the correct message and the correct key will produce a particular hash digest efficiently.

Conceptually speaking, the same can be said for a salted hash; only the correct message and the same salt value will produce a particular hash value efficiently. In fact, the HMAC algorithm is little more than a nested, salted hash, where the salts prepended to the message for each of the two nested hashes is based on a simple derivation of the key.

If a true salt, therefore, were kept secret as a key (or equivalently, if a shared secret symmetric key were used as a salt), it stands to reason that any cryptographic hash primitive would become an effective MAC.

So, I guess two questions naturally follow. First, is that assumption correct? Second, if so, what does the HMAC algorithm get you over the incorporated hash primitive, other than reducing computation speed by half and adding one order of magnitude to the brute-force complexity of finding a preimage message using a constant key (or vice-versa)?

share|improve this question
The problem is you didn't specify how you combine key and message before hashing. Different combinations have different security properties. For example Hash(k||m) is insecure with SHA-2(length extension attack) but secure with SHA-3, Hash(m||k) suffers from collision attacks,... – CodesInChaos Jan 22 at 20:14
Oh and the HMAC overhead is one compression function call, not a factor of two. – CodesInChaos Jan 22 at 20:16
What about k xor m or combinations of xor and concat? – KeithS Jan 22 at 20:24
You'd need to look at each of them individually and the prove the security. HMAC has a security proof, that shows that it's secure if the hash function has certain properties. If you xor k into the beginning of the message that suffers from length extensions(assuming SHA-2). If you use other combinations, it might or might not be secure. | If you want to get rid of the overhead, just use SHA-3 or a SHA-3 finalist. – CodesInChaos Jan 22 at 20:26

1 Answer

up vote 6 down vote accepted

If the hash function is a Random Oracle then hashing the concatenation of the key (your "secret salt") and the message is indeed a perfect MAC (I say "key" because if a salt is a secret piece of data then it matches the definition of a key; let's use the proper name).

Unfortunately, random oracles do not really exist... instead, we are stuck with hash functions which we know are not random oracles, and we must get along with their quirks. In particular, the hash function from the Merkle–Damgård persuasion (which includes MD5, SHA-1, SHA-256 and SHA-512) suffer from the length extension attack, which does not contradict the basic properties which are expected from a secure hash function (resistance to preimages, second preimages and collisions), but means that the simple MAC constructions tend to fail horribly.

... Which is precisely why HMAC was invented: with its double-nested hash invocation, it copes with the non-random-oracleness of MD hash functions. We do not do the two hash invocations for the fun of it, but because they are necessary for achieving proper security. Let me stress the important point: designing a MAC algorithm is not as easy as it may seem; you cannot slap a hash function and a key together and hope for the best. Details, as usual, matter.

If you need Performance with a big 'P', the kind which would not be fulfilled by HMAC, then:

  1. You have very fast networks, or very slow CPU.
  2. There are faster MAC constructions which are not based on existing hash function.
  3. You will be better served with an authenticated encryption mode, assuming you also encrypt the data which is MACed (this is the most common scenario).
share|improve this answer
This is exactly the explanation I needed. I did not know about the possibility of length extension attacks. CodesInChaos mentioned that the SHA-3 finalists, none of which use MD-based construction, may be a secure way to use H(K||M) as a MAC. Can you expand on this? Are there any proofs for these algorithms? – KeithS Jan 22 at 20:37
We don't have proof that hash functions can really exist; all we have are candidates. The SHA-3 candidates were designed to avoid the length extension attack (it was part of the design criteria), but usage as MAC has not been thoroughly investigated yet. The SHA-3 winner (Keccak) uses a so-called "sponge construction" which is amenable to some proofiness, so you can build a MAC which would be as secure as the hash function itself (not a proof that the MAC is secure, but a proof that if the MAC is broken, so is the hash function). – Thomas Pornin Jan 22 at 20:47
OK, and the fact that Keccak won the SHA-3 competition, meaning it withstood some pretty heavy peer review, is evidence that it is at least not fundamentally broken (I realize that every hash function that was or is a recommended universal standard has been demonstrated to be at least theoretically if not practically vulnerable). – KeithS Jan 22 at 21:00
Assuming a perfect entropy pool, of course.... Good post/explanation. – grauwulf Jan 22 at 21:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.