8
$\begingroup$

The HMAC Construction is defined as:

Hash( (Key XOR opad) || Hash((Key XOR ipad) || Message) )

This was designed because a simpler construction such as:

Hash(Key || Message)

Is vulnerable to a length extension attack (but not for all hashes, a notable exception is SHA-3).

The questions are, what about cases where the message:

  1. Is of a known, fixed length, and would be rejected if having any other length than the expected one (CBC-MAC, for instance, is secure for a fixed length message, but not for a variable-length one).
  2. Is prepended with fixed-sized length indicator at very the beginning of the message (i.e. the extended message would be Fixed-Sized Length indicator||Message and the hash would be: Hash(Key||Fixed-Sized Length indicator||Message)).
  3. The same scheme as the previous one but where the length indicator is only included within the hash.

(these may be completely different cases so consider them separately).

Note that for (3) an alternative configuration Hash(Fixed-Sized Length indicator||Key||Message) would guarantee that the length indicator is included in the first block of the hash - I mean, even for a huge key that is larger than the hash function block length. The length indicator would probably not need to be any more than 64bits of size (as most [older] hashes are limited to a maximum message size of 2^64 - 1 bits anyway). This makes it very hard to imagine how can it be insecure? But I'm not a cryptographer, I guess.

$\endgroup$
  • 2
    $\begingroup$ crypto.stackexchange.com/q/1186/991 $\;$ $\endgroup$ – user991 May 17 '15 at 9:40
  • $\begingroup$ Thanks, this seem to address the second part of the question (though the referenced papers seem to go a bit beyond my ability to understand at the moment), but what about the simpler case when the length is fixed and known in advance? $\endgroup$ – Anon2000 May 17 '15 at 11:50
  • $\begingroup$ Re-reading it I'm not sure it exactly addresses the second question, as I meant that the length is also included within the body of the message itself, not just the hash (Interestingly I didn't even consider the idea of only including it in the hash, though that might have been my next question if the answer for current one was positive though :) ). $\endgroup$ – Anon2000 May 17 '15 at 12:10
  • $\begingroup$ The only difference between your description of 2 and what I linked to is that you're considering a fixed-size length indicator. $\;$ $\endgroup$ – user991 May 17 '15 at 12:28
  • 1
    $\begingroup$ I don't think there's any difference between 2 and 3, the length field actually part of the sent message is redundant, as the length of the message already must be a property of the message itself. For a given hash and fixed length key and message, H(k, m) may be secure as a MAC, and for some (e.g. SHA3) the message can be variable length, and for some the third construction may be safe, but with HMAC you have some VERY strong properties with fairly weak requirements on the underlying hash. $\endgroup$ – Steve Peltz May 17 '15 at 19:12
6
$\begingroup$

In summary: Yes, HMAC is the way to go for construction of a MAC from an arbitrary concrete iterated hash. We have no constructive argument of security of the MAC constructs in the question; we even have a concrete attack when using some otherwise apparently fine hashes.


I consider a hash constructed by iterating a compression function $F$ as $s_{i+1}=F(s_i,m_i)$ with $s_i$ of $h$ bits (also the size of the MAC), message blocks $m_i$ of size $b$, perhaps with Merkle-Dåmgard strengthening (this matches MD5, SHA-1, SHA-2, but not Keccak/SHA-3); I also assume Key is of fixed size, enters $m_0$, and the third construct is Hash(Fixed-Sized Length indicator||Key||Message).

Under the assumption that $F$ is an ideal PRF, the three constructs in the question appear to be secure, but perhaps to some sub-optimal degree. The best general attack (that is, valid irrespective of the details of the iterated function) that I see is to obtain the hash of messages of equal size (at least $\max(2b,h)+b$), with the beginning of the message random and the last message block fixed, until a collision is found between distinct $m_0$ and $m_1$ (which requires $\mathcal O(2^{h/2})$ MACs); then obtain the MAC of $\widetilde{m_0}$ with the last bit toggled; that MAC will stands a good chance to also be valid for the similarly modified $\widetilde{m_1}$. That's a valid attack against the MAC. It works because the collision between the MACs for $m_0$ and $m_1$ stands a good chance to have occurred before the last block, and in that case $\widetilde{m_0}$ and $\widetilde{m_1}$ will necessarily collide too.

The above generic attack does apply to HMAC (and CBC-MAC, and any iterated MAC with a single pass). However, HMAC (contrary to the other constructs) comes with security arguments that there is no asymptotically better attack, and even arguments valid with relatively weak assumptions on the iterated function; see Mihir Bellare: New Proofs for NMAC and HMAC: Security without Collision-Resistance, with extended abstract in proceeding of Crypto 2006.

The security arguments of HMAC, and the fact that the key enters both at the start and the end of the computation (which in turn insures, in the above attack, that the attacker does not get to know the colliding value), gives us a security margin. I'm reasonably confident that HMAC-MD5 won't be practically broken (excluding attacks on implementations such as DPA or injected faults) for some years, but I'm not so confident for MACs constructed from MD5 as in the question. Addition: there's a lot of truth in the saying: better safe than sorry.

As an illustration of the superiority of HMAC, we can make an iterated hash such that the three constructs are weak, but HMAC remains strong. An example is SHA-256 modified by removing the 8 additions modulo $2^{32}$ in the 4th (last) step of a round (making that $H_0^{(i)}=a$, .., $H_7^{(i)}=h$). If there's an attack against the collision-resistance, or (first or second) preimage resistance of that modified SHA-256, I fail to see it (update: on second thought, the best I see is a preimage attack similar to this, with cost about $2^{128}$ rather than $2^{256}$ for full SHA-256). However, in the constructs of the question, from a single message/MAC pair, it becomes easy to compute the MAC for any message of the same length differing in blocks after the first (notice that for known blocks and output, it is possible to walk back the hash states). [Addition following strongly critical comment: A key point of my reasoning is that the security argument of HMAC seems to apply when using that modified SHA-256; I'll concede a gap if it irreparably does not; or if since there's a widely accepted definition of security of a hash that this modified SHA-256 fails (quantitatively at least), but SHA-256 pass (notice that SHA-256, contrary to Keccak/SHA-3, trivialy fails widely accepted definitions of security due to the length-extension property)].

$\endgroup$
  • 1
    $\begingroup$ I think for (3) he meant that the hash would be H(k, l, m), NOT (H(k, m), l) (with fixed length k, l). $\endgroup$ – Steve Peltz May 17 '15 at 19:16
  • $\begingroup$ @fgrieu: Thanks for the comprehensive answer, bit I did mean in (3) that the length is included in the hash, e.g. one of H(K,L,M), H(L,K,M) or even H(K,M,L) (which would allow on-line, streaming calculation of the hash - the others require the length to be known beforehand). As a non-expert, I'm getting the sense from both you and @StevePeltz that HMAC was is valued for more reasons than being immune to length extension attacks. However since I'm a practical person (a developer basically), it would be useful to me to know for example how essential is it for SHA-1/2/3 for example? $\endgroup$ – Anon2000 May 17 '15 at 19:43
  • 1
    $\begingroup$ @Anon2000: for your need of a fast MAC, have you considered Siphash? $\endgroup$ – fgrieu May 17 '15 at 20:22
  • 1
    $\begingroup$ I fail to see how arbitrary collisions and derived collisions have any relevance for a MAC function. You break a MAC function by constructing an altered message and a MAC-value that match the altered message and the key combined, I see nothing in your post indicating that the suggested construction should be weak in that regard. $\endgroup$ – aaaaaaaaaaaa Jun 15 '15 at 21:06
  • 2
    $\begingroup$ @fgrieu Still -1, your collision part is irrelevant bollocks. All you have proven is that "broken sha2" is broken. Maybe it will still make a secure MAC in the HMAC construction, I tend to believe so, but you don't have any proof for that. As for the headline question, you deliver the wrong answer, if you can't touch HASH, you can't touch HASH(length || key || message) as a MAC function. HMAC was made in a time when people didn't trust hash functions, that is the only reason for its existence. $\endgroup$ – aaaaaaaaaaaa Jun 16 '15 at 5:20
5
$\begingroup$

I'm going to agree with @fgrieu's marvelous post above in a back-handed way.

My answer is: No, you don't have to use an HMAC. Do it anyway.

As you noted, some hashes, sush as SHA-3 (especially in its Keccak form), Skein (which I was a team member on), and others will work just fine. In the case of Skein, there is a one-pass Skein-MAC that has a proof of security interestingly done by Mihir Bellare (also a Skein team member), who did the HMAC proof that @fgrieu cited above.

Furthermore, there is an HMAC criticism that I and a few others (including Niels Ferguson, another Skein team member) have made that is that HMAC essentially assumes a working hash function. HMAC protects against a number of breakages of hash functions, including Merkle-Dåmgard length extension attacks, but we don't know how good it is with a hash function with whatever sorts of weaknesses. I don't think we have any idea, for example, how good HMAC-MD5 or HMAC-MD4 is, despite the horrid breaks in each of them. (MD5 is readily broken with a computer; MD4 is readily broken with pencil-and-paper.) You can see that criticism above in @fgrieu's remark about assuming that F is an ideal PRF. What if F is known to be a non-ideal PRF with a whole set of flaws? How good is HMAC then?

You've described a bunch of constructions that are very likely to work just fine with the sort of hash function one is likely to see in the real world, like SHA-1, SHA-256, SHA-512, and SHA-512/z that are still known to have weaknesses. Even better would be a hash of Key-Length || Key || Message-Length || Message.

But do an HMAC anyway, unless you have a need for the one-pass MAC that you can get from Skein or Keccak/SHA-3. As an example of need, the protocol ZRTP allows either a SHA-1 HMAC or a Skein-MAC (again in full disclosure, I'm a co-author of this protocol and perpetrator of this use). The reason is that if you're doing the HMAC, then the majority of the compute time of the protocol is spent in the HMAC. Despite this, it's merely an option with a fallback to the HMAC always being there.

The reason you want to do an HMAC is a meta-principle I've learned in doing crypto: don't do anything that stupid people think is stupid. Think of this as a corollary of the maxim, "never argue with an idiot, people may not be able to tell the difference." That's snarky and pejorative, so let's also call it the Elvis Costello Detective principle, "Don't get cute." So let's look at it from a real-world perspective.

I think that your construct is just fine in any real-world case. But what if we are wrong? Unless someone who is as well-respected in protocol proofs as Mihir Bellare is going to do a proof for this, then we always are behind the you-have-no-proof eight-ball, and it's a fair cop! Even if you point out that these security proofs has their own set of assumptions and are of questionable worth (especially after the Paterson et al. SSH break -- which is another whole discussion), the fact is that there's a proof for HMAC and not for yours (unless you're using a known-good-MAC hash like Skein or Keccak).

I can think of some ways to break that construct through the use of stupid coding. (Here's a hand wave: make the counter be a fixed-length binary counter, as opposed to the ASCII string of the actual length. Wrap the counter so the colliding message has the same length mod 2^n (e.g. 1 vs 257 for a one-byte counter or 65537 for a two-byte counter) and then go on for a length-extension attack.) This is massively face-palmingly broken, but it wouldn't be the first time someone made a massively face-palminingly broken coding error. In fact, such things happen every day.

I have come to believe that an important property of good crypto is being understandable. The advantage that HMAC has over constructs like an improved keyed hash is that the person reading your protocol can say, "oh, it's an HMAC" and move on, rather than having to read all the details and remember under which circumstances those improvements work. Moreover, if you use something nonstandard, people will complain. Those complaints won't go away. Even after you've written a zillion blog posts about how what you did was just fine, people will still complain. Whereas if you use an HMAC, they won't. The cost of the lack of complaints is a mere second call to the hash function. If that mere second call is actually a large cost (like with ZRTP), then there are one-pass systems with proofs of security you can use!

The ultimate problem with what you're suggesting is that you're getting cute. HMAC exists to address known problems with keyed hashes. It has a proof of security that shows that it meets that goal. It has a history of being useful in the field. Even the legitimate criticism of that proof and use-history doesn't bolster the way you're getting cute, and even though I think your cuteness is secure enough, I know I don't have anything other than licking my finger and sticking it in the wind to back me up.

So to sum up, no, you don't have to use an HMAC. Do it anyway.

$\endgroup$
  • $\begingroup$ Hi, I'm just a person who's moderately new to cryptography, but takes it very seriously (I'm developing a database system that heavily relies on MACs to authenticate requests, and supports end-to-end encryption). But I guess that to the contrary to what you describe, I'm also the sort of person who'd see "it's an HMAC" and ask, "but why do I need it, really"? and go ahead and make invent my own construct just to see what people think about it.. $\endgroup$ – Anon2000 May 19 '15 at 23:50
  • $\begingroup$ I might sound "cute" (or just "annoying" for some people I guess) because I'm willing to ask really silly questions and embarrass myself with stupid blunders. None of what I speculate about here would (probably) be used in practice, this is all purely for a learning experience. $\endgroup$ – Anon2000 May 19 '15 at 23:51
  • $\begingroup$ I have not really studied HMACs in terms of theory but from the overwhelming responses here I'm starting to understand how they improve the protection against length extensions attacks and help with collision resistance of the hash function. I think maybe it's time for me to go and actually study them more carefully though, but it's not completely "mandatory" I guess.. maybe at some point in the future.. $\endgroup$ – Anon2000 May 19 '15 at 23:56
  • $\begingroup$ The methods I described were not only the ones I was interested in, for example, what about E(H(Data))? (with a block cipher of a block size equal or larger than the hash size) - turns out it is secure but more vulnerable to collision (but not pre-image I think) attacks. What about E(H(Key||Data))? (no idea). How about using a smaller-than-hash block cipher in CBC mode for the previous two cases? (up to double the size of the encryption block it may still be secure for tampering?). I'm not sure why you find this "cute"? these is extremely interesting questions! $\endgroup$ – Anon2000 May 20 '15 at 6:43
  • $\begingroup$ It's good to question constructs. However, you should not take that further and implement it in a production database system. If you are really certain, ask here, then write a scientific paper. If no attack is found you are famous and you would be able to use that fame to monitize your DB. If you cannot get yourself to create the scientific paper then don't put it into production. $\endgroup$ – Maarten Bodewes May 20 '15 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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