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

Is this MAC secure:

To authenticate a message $m=m_1||\ldots||m_l$ where $m_i \in \{0,1\}^{n/2}$, choose $r \leftarrow \{0,1\}^n$ at random, compute $$t:=F_k(r)\oplus F_k(\langle 1\rangle || m_1) \oplus \ldots \oplus F_k(\langle l\rangle ||m_l)$$

(where $\langle i \rangle$ is $\frac{n}{2}$ bit encoding of the integer $i$) and send $\langle r, t\rangle$. $F$ is a pseudorandom function.

The question comes from "Introduction to Modern Cryptography" (4.4c) where it is asked to prove that it is insecure, however I'm not sure it is. Here is my intuition (I understand that it is very weak):

The problem comes from the fact that $\langle i \rangle$ is $n/2$ bit encoded. Therefore there is only negligible chance that any r will be of form: $\langle i \rangle || m$ where $i$ is of polynomial size. If this was only $\log n$ bit encoded then we can do something.

So each message xor $F_k(\langle 1\rangle || m_1) \oplus \ldots \oplus F_k(\langle l\rangle ||m_l)$ is XORed with $F_k(r)$ which is basically a random bit string (since $F$ is PRF) that has negligible chance of occuring twice. Therefore each tag is independent from each other.

I tried to prove that it is secure by simulating what would happen if it was breakable, but i was unable to prove that any fraudulent tag would have a unique $F_k(\langle i \rangle || m_i)$ that we haven't sent already during the simulation.

share|improve this question
I don't understand how that would work. Could you develop your argument? – gregorias Nov 23 '13 at 15:57
I was aware of those. Attacks presented there are not applicable here, since there's ordering added to message text preventing simple swapping of message chunks. Also we can't enlarge the message with something of 0 XOR value since every tag we get from oracle is a result of XOR with unknown random number $F_k(r)$, where $r$ is arbitrary. – gregorias Nov 23 '13 at 16:28
Could they be just referring to the fact that for every way of padding messages whose length is not $\hspace{.44 in}$ a multiple of $n$ to strings whose length is a multiple of $n$, the resulting algorithm will be insecure? $\hspace{.6 in}$ – Ricky Demer Nov 23 '13 at 21:49
up vote 5 down vote accepted

$\langle \langle 1\rangle || m_1, 0^n \rangle$ is a valid tag on $m = m_1$

share|improve this answer

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.