While preparing for a crypto exam there is a task we don't really understand:


Let $E_K$ be a permutation $\{0,1\}^b \rightarrow \{0,1\}^b$ defined by a blockcipher with the key $K$. Let $M = (M_1,...,M_n) \in *(\{0,1\}^b)^n$ be an nb-bit message.

We interpret the output of $E_K$ as an integer $E_K(\cdot) \in \mathbb{Z}_{2^b}$ and define the MAC as the following:

enter image description here

// ungerade means odd, gerade means even

we should now provide an attack which is always successful. The restriction is that we are not allowed to perform a CPA. So we search for the a pair $(M',A')$ with $A' = MAC_K(M')$

Our problem is the restriction. So we don't know whether we are allowed to change the calculation or function in any way (furthermore would such an operation make the task way too easy).

  • $\begingroup$ Could you not just swap any even block with another even block or any odd block with another odd block? $\endgroup$ – Maarten Bodewes Sep 19 '15 at 0:09
  • $\begingroup$ Well that was something we also thought about, but as it says "No chosen Plaintext". So wouldn't switching blocks within the Plaintext not be a CPA? $\endgroup$ – hGen Sep 19 '15 at 7:43
  • $\begingroup$ I don't get this. If you cannot change the message at all then then attacks on a MAC - except replay attacks on the protocol - don't make sense, right? $\endgroup$ – Maarten Bodewes Sep 19 '15 at 10:27
  • $\begingroup$ I guess the focus lies on the fact that we are not allowed to choose other plaintexts. The solution you gave before seems to be right as we are not choosing new plaintexts but just modifying the given one in a man in the middle like way. $\endgroup$ – hGen Sep 19 '15 at 10:32
  • 1
    $\begingroup$ Hint: what happens if you compute the MAC of a message that consists of two equal blocks? $\endgroup$ – poncho Sep 19 '15 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.