New results on HMAC

| Comments (4) |
One of the basic primitives used in communications security protocols is called a Message Authentication Code (MAC). What we want is a function MAC that takes a secret key k and a message m and produces a characteristic fixed-length output X. I.e.,
X = MAC(k, m)

The way that you use a MAC is that you and I share a secret key and when we want to send messages around we attach the MAC value of the message using that key. Anyone who doesn't have that key can't generate matching MAC/message pairs and so can't forge messages that appear to be from one of us. MACs are used all over cryptographic protocols because they're an efficient way of providing an integrity check.

In order for a MAC to be useful, we would like it to have (at least) the following properties, listed roughly in order of descending strength (note that we assume the attacker doesn't have the key).

  1. Given a set of MAC values X it's infeasible to construct a new (m,X) pair. (If that there's any dependence on the key at all, this looks pretty easy to meet).
  2. Given a set of (m, X) pairs, it's infeasible to recover k.
  3. Given a set of (m, X) pairs, it's infeasible to construct a new (m, X) pair.
  4. Given a set of (m, X) pairs, it's infeasible to construct a message m' that produces any of the known X values.

Because a MAC takes an arbitrary input and produces a fixed-length output which is supposed to be hard to forge, it sort of feels like a hash function, except that it's got a key. It's very natural to try to use hash functions to construct MACs and indeed many of these functions went under the name "keyed hash". It turns out that many of the obvious constructions have problems and eventually one particular hash-based construction called HMAC came to dominate the space, largely based on the fact that it came with proofs of its security—assuming you made certain assumptions about the hashes it was based on. HMAC is used more or less everywhere these days.

That was all fine before Wang et al. started successfully attacking MD5 and SHA-1 (not too out of date roundup here and update here). These attacks called into question the assumptions underlying the original HMAC proofs. Mihir Bellare produced new proofs of security with weaker assumptions.

Unfortunately, those assumptions don't seem to actually obtain to MD5 and SHA-1 in the face of the current attacks, as shown by a new paper by Contini and Yin. They demonstrate attacks on HMAC-MD4, HMAC-MD5, HMAC-SHA-0 and reduced-round HMAC-SHA-1 which lead to recovery of the key (a violation of property 2) and forgery of MACs (a violation of property 3).

That said, this is currently a don't panic situation, for a number of reasons. First, mounting the attack requires a very large number of (m,X) pairs: 247 for MD5 and 284 for SHA-0. If we assume that SHA-1 is stronger than SHA-0, then this tells us something about the strength of SHA-1. So, it requires one of the endpoints being able to do a truly enormous amount of computation. This isn't something you wouldn't notice on your SSL/TLS or SSH server, and since you seem to need those pairs for each key, it's a lot more traffic than you'd normally protected under a single key, and it's not clear how you'd force the server to compute the pairs for you. Second, it seems to still require a lot of computation (order 245 operations with MD5) in order to actually forge a MAC. I haven't studied the Contini and Wang paper that carefully, but I'd guess that the cost would be higher with SHA-1.

The bottom line, then, is that this doesn't appear to be a practical threat to current protocols (that's what the authors say too). But it's definitely an interesting result and should make you glad that people are working on transitioning away from MD5 and SHA-1.

UPDATE: "attack" -> "attach" (thanks to "that guy")

4 Comments

In "attack the MAC" do you mean "attach the MAC"?

Yeah, and don't worry about a thing, because we should be all done transitioning away by 2015 or maybe 2025 at the latest. Well, mostly done anyway.

s/obtain/pertain/

TLS messages have a 64-bit sequence number, and sequence number wrapping is not permitted, so the attack on HMAC-SHA0, at least, doesn't apply to TLS (although it obviously wouldn't be feasible in any event).

Way back when TLS was first being specified, I recommended that the sequence number be shortened to 32 bits, as a matter of basic cryptographic hygiene. I was, of course, ignored.

Leave a comment