Why is a HMAC using a 32bit tag not prone to birthday attacks?

I have read that it has something to do with the fact a birthday attack isn't really possible if the output size is not large enough. But then that asks the question of at what size does it become valid and a practical attack can be carried out?

If it isn't prone to birthday attack then what would be the probability of guessing a valid tag value for something as weak as a 32 bits in length?

Probability of a single hash collision$$\frac{1}{2^{32}}$$

However the birthday paradox mathematically suggests that this probability should be n^32/2...

Or am I missing something here?

Update: The goal of the attack is just guess what the tag might be.

  • 1
    $\begingroup$ What would be the attacker's goal be? In the most permissive attack model for a MAC, the attacker has an oracle that can compute tags for an arbitrary number of messages of his choosing, and he is then challenged to produce any valid message+tag pair where he hasn't asked the oracle about that particular message yet. Finding a tag collision doesn't seem to help him with this task at all. $\endgroup$ – Henning Makholm Nov 17 '16 at 15:59
  • $\begingroup$ The attackers goal is to correctly guess what the computed tag would be. It's simply asking what is the probability that an adversary could guess a random value from a 32bit tag and be correct. $\endgroup$ – NoDirection Nov 17 '16 at 16:21
  • $\begingroup$ x @NoDirection, but what is the "birthday attack" you're speaking about? As far as I'm aware, "birthday" in crypto-ish contexts is about collissions. $\endgroup$ – Henning Makholm Nov 17 '16 at 16:23
  • $\begingroup$ @HenningMakholm see here - youtube.com/watch?v=ZZovSCFZffM $\endgroup$ – NoDirection Nov 17 '16 at 16:33
  • $\begingroup$ Yes its about collisions, the question is what is the probability of having one of the those collisions. $\endgroup$ – NoDirection Nov 17 '16 at 16:34

"Birthday attacks" relate to the mathematical phenomenon colloquially known as the birthday problem, which states that if you generate random value in a space of size $N$, you expect to hit your first collision, i.e. generating a value that you already generated previously, after having produced about $\sqrt{N}$ values. This can lead to actual attacks in some contexts. It so happens that the normal usage context of HMAC is not one of these contexts.

HMAC is about checked integrity: it is a keyed function that is computed over a given message. In the most generic model, the attacker is allowed to submit $n$ messages $m_i$ of his own choice, and obtain the corresponding HMAC value $h_i$; and his goal is to achieve a forgery, i.e. a new message $m$ distinct from all submitted $m_i$, and the corresponding HMAC value $h$.

HMAC being what it is, it operates as a random oracle: from the point of view of the attacker, every time he submits a new message $m_i$, the obtained HMAC value $h_i$ is indistinguishable from a newly generated random value. Thus, when considering an as yet unsubmitted message $m$, the attacker's chances at predicting the HMAC value are essentially $1/2^r$, where $r$ is the length (in bits) of the HMAC output. In your case, $r = 32$, so anytime the attacker tries to predict the HMAC output for a message, then either he already submitted that exact message, and thus he can predict with probability $1$, or he did not submit that exact message previously, so his prediction will be true with probability $2^{-32}$ only.

The birthday problem, here, says that once the attacker has observed (or submitted) more than about $2^{16}$ messages, he can expect collisions, i.e. two distinct messages that map to the same HMAC value. But this does not change anything for the attacker, in that he still has no clue about what will be the next HMAC value for any given (new) message.

In fact, one can say that the birthday problem really incarnates how much collisions do not help the attacker. If you imagine a MAC system that takes care never to produce the same MAC value as previously (e.g. by remembering all produced MAC values in a database), then, message after message, the space of remaining possible MAC values get thinner. Ultimately, with such a system, once $2^{32}-1$ message+MAC have been obtained, the attacker could predict the next MAC value with probability $1$, since that would be the only MAC value not produced yet. But HMAC is not such a system, and will produce collisions just like it was a random source, thereby not incurring this "thinning space" effect.


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.