# How come “short” (eg 80 bit) MACs are regarded to be safe?

I‘ve got two questions:

1. Why are much shorter output lengths of, e.g 80 bits, sufficient for MACs ?

2. Assume a message $x$ that is sent in clear together with its MAC over the channel: $(x,MAC_k(x))$. What does Oscar have to do to attack this system?

I think I can answer the first question: it’s because of the Birthday Paradox But for the second, I don´t know how to start. It’s not given how the MAC is calculated. I could do a secret pre- or suffix attack ?

But for the second, I don´t know how to start.

I won't give you the answer (this is homework; you won't learn as much if I just give you the answer); I will give you hints.

It’s not given how the MAC is calculated.

No, but for this question, we assume that the attacker knows what the MAC is; he just doesn't know the key. We also assume that he knows the correct MAC for a number of different messages (actually, we assume that the attacker can ask for a MAC for messages of his choosing; that ability won't help you in this attack).

What does that mean? Well, it means that, for the purpose of this question, we treat the MAC as a black box; the attacker can (to his heart's content, up to the limits of the computational resources he has on hand) generate keys and messages and compute what the MAC would be for that key.

So, with those capabilities, our attacker's job is to get a (message, MAC) pair accepted, for a message he hasn't seen (he's not allowed to submit one of the (message, MAC) pairs he's already been given). How can he do that?

Hint: there are two basic ways the attacker can proceed; one involves his use of the black box, and one does not.

• Do you mean maybe Brute Force the keys ? – userkir Jul 29 '16 at 18:05
• @userkir: this is indeed one possible attack (the one that uses the black box); if the attacker finds a key that correctly computes the MAC for the messages he knows the MAC to, then that's likely to be the correct one; he can then easily compute the MAC for any other message. – poncho Jul 29 '16 at 18:30
• But what is the second one ? You sad he can't change any Messages, so a Man in the middle Attack is not possible ?! – userkir Jul 29 '16 at 18:55
• @userkir: I said "he can't change any Messages"??? I'm not sure where you think I implied that... As for "[the attacker is] not allowed to submit one of the (message, MAC) pairs he's been given", that's just one of the rules of the game; if he finds a MAC for any other message, he wins... – poncho Jul 29 '16 at 23:44
• @userkir: you're going in the wrong direction; the second attack doesn't worry about the key at all. Hint: it becomes easier if you make the tag shorter... – poncho Jul 30 '16 at 22:41