Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How do I prove the following MACs are insecure?


                                            1                                                                                   2

share|improve this question
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. – Maeher Feb 21 '14 at 13:37
This looks a lot like homework, so I've only given a hint. – figlesquidge 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?
share|improve this answer
Good spot @Maeher :) – figlesquidge Feb 21 '14 at 15:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.