How come “short” (eg 80 bit) MACs are regarded to be safe? I‘ve got two questions:


Why are much shorter output lengths of, e.g 80 bits, sufficient for MACs ?
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.