How do I prove the following MACs are insecure?


                                            1                                                                                   2

  • 3
    $\begingroup$ Well, to show that they are not secure, you have to present an adversary that is able to forge them. For the first one, think about how, given a message and a tag, you can find another message for which the same tag will verify. For the second one, think about how you might be able to compute a tag for a longer message without knowing the key. $\endgroup$ – Maeher Feb 21 '14 at 13:37
  • $\begingroup$ This looks a lot like homework, so I've only given a hint. $\endgroup$ – Cryptographeur Feb 21 '14 at 13:50

The following was originally written as an edit to the question, but I'm going to put it here instead because I think formalizing the schemes might well provide you with enough of a hint for you to solve this question yourself:

Let $f(k,m)$ be a pseudo-random function, taking as inputs a key and a message, and outputing a value of the same length as the key (eg AES-128).

Why are the following MACs not sure?

  1. [ref] $\tau = c_i \oplus c_2 \dots \oplus c_n$, where $c_i=f(k,m_i)$.

  2. [ref] $c_0=k$, $c_i=f(c_{i-1},m_i)$ for $i=1,\dots,m$ and $\tau=c_n$

To prove something insecure, we provide an explicit adversary. That is, we provide a method for doing what the security model says we shouldn't be able to.

In this case, that means we need are allowed to ask the system to provide us with the tag on some messages $\mathcal{M}=\{M_1,M_2,\dots\}$. Then, we create a valid tag for some message $M'\notin\mathcal{M}$.

So, a more direct hint: If you have the MAC of message $M=(m_1,\dots,m_n)$, can you construct...

  1. Another message with the same tag?
  2. A longer message who's tag you can calculate?
  • $\begingroup$ Good spot @Maeher :) $\endgroup$ – Cryptographeur Feb 21 '14 at 15:33

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.