Why is a HMAC using a 32bit tag not prone to birthday attacks? 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.
"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.