1
$\begingroup$

How do I prove the following MACs are insecure?

          

                                            1                                                                                   2

$\endgroup$
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, 2014 at 13:37
  • $\begingroup$ This looks a lot like homework, so I've only given a hint. $\endgroup$ Feb 21, 2014 at 13:50

1 Answer 1

4
$\begingroup$

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?
$\endgroup$
1
  • $\begingroup$ Good spot @Maeher :) $\endgroup$ Feb 21, 2014 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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