# Message authentication codes construction

I was reading the paper $[1]$ and came across the scheme that I show below. While I understand the scheme well, I don't understand why they prepend a 0 to the block containing $r$ and a 1 to all other blocks. What is achieved by this? They never explain why they do it. Here is the scheme as presented in the paper:

$[1]$Bellare, Mihir, Roch Guérin, and Phillip Rogaway. "XOR MACs: New methods for message authentication using finite pseudorandom functions." Advances in Cryptology—CRYPT0’95 (1995): 15-28.

-
Thank you for editing! – user4399 Nov 29 '12 at 0:49
Please don't cross-post – CodesInChaos Nov 29 '12 at 13:19

The short answer is: They prepend bits in that way because the scheme is not secure without them. While they might not explain it in English, their proof makes it clear where they use it.

Let us construct an attack against the scheme that does not prepend a bit to the blocks. The same idea will work against a version of the scheme that prepends the same bit to every block. In this version of the scheme, a tag for a single-block message $M\in\{0,1\}^{32}$ is $(r,z)$, where $$z = F_a(r)\oplus F_a(\langle1\rangle\| M).$$ Our attack will obtain about $2^{32}$ tags for an arbitrary single-block message $M$, stopping if it ever gets a tag $(r,z)$ such that the upper $32$ bits of $r$ are equal to $\langle1\rangle\in\{0,1\}^{32}$ and lower $32$ bits are not equal to $M$. When it finds such a tag $(r,z)$, let $s\neq M$ denote the lower $32$ bits of that $r$. The adversary outputs a forgery on the message $M' = s$ with tag $(r',z')$ defined by $$r' = \langle 1\rangle\| M \quad \text{ and } \quad z' =z$$ This tag will verify with message $M'$ because $$z' = z= F_a(r)\oplus F_a(\langle 1 \rangle\|M)= F_a(r')\oplus F_z(\langle 1 \rangle\| M'),$$ where the second equality uses the fact that our $r$ is equal to $\langle 1\rangle\| s = \langle 1\rangle\| M'$ (it switches the order of the arguments to $\oplus$). Moreover, our adversary never queries the message $M'$ and one can verify that it will get the needed $r$ with good probability in about $2^{32}$ tries, so it will win the security game.

The intuition is that prepending the bits prevents this sort of thing from happening. Specifically, this adversary found a way to force the verification algorithm to treat a previously used $r$ as a message, which can't happen with their domain separation strategy.

-

I'm guessing the idea is domain separation : if $F_a$ is a secure PRF then $G^0_a(x)=F_a(0.x)$ and $G^1_a(x)=F_a(1.x)$ are two "independant" PRF. What they're doing here is basically using 2 different PRF for the randomness and the message.

If that protection wasn't there you could use an attacker supplied $r$ to cancel out blocks and then with a pair $(r,F_a(r))$ you could forge tags. I haven't figured out how you could get that pair but it may be that the designers thought it would be giving too much freedom to the attacker.

-

It's a way of padding, so that the final chunk of data is always a multiple of the block size.

The reason why the pattern is 1 bit followed by 0 bits is to be able to find out exactly where the actual message ends and where the padding begins after you decrypt it: The message ends exactly before the first '1' bit when starting from the end of the message and going backwards. This padding method is frequently referred to as "ISO padding" (since it's described in ISO/IEC 9797-1 as padding method 2).

There are other ways to pad things, but this is relatively easy to implement and understand and that makes it frequently used. For more on padding check out http://en.wikipedia.org/wiki/Padding_(cryptography)

Update:

So now to explain: The reason is that they want the "string" they pass into Fa to be 64-bits long; r is exactly 63-bits by choice; M[i] is 32 bits, and i is at most 31 bits (also by definition), making their concatenation also 63 bits. So they need to pad with something to ensure that it's always 64-bits long.

As to why they do a 0 for the first block r and 1 for everything else (instead of say 1 and 0), after a very cursory reading of their paper I don't see any particular reason; it seems like an arbitrary choice. This doesn't mean that the padding itself is arbitrary. It serves a very important purpose, which they describe in their paper and it needs to be distinguishable from every other possible block.

-
I wasn't referring to the padding. In the scheme itself, they have z=F_a(0.r) XOR F_a(1. <1>.M[1]) XOR F_a(1.<2>.M[2])... – user4399 Nov 29 '12 at 1:00
Oops. My bad. I'll update my answer, but it may take me a few minutes - at work, so can't devote all my time to StackOverflow! – Nik Bougalis Nov 29 '12 at 1:04
Thank you!! :-) – user4399 Nov 29 '12 at 1:06
Thanks, but I don't think it's arbitrary. They purposely make the data only 63 bits so that they can prepend the bit. My intuition is that a forgery is possible if r can look like one of the message blocks and they therefore differentiate r from the message blocks with the first bit. The issue is, I don't see how a polynomial time adversary would forge even without this bit. – user4399 Nov 29 '12 at 1:49
I didn't mean arbitrary in the sense of "let's put random values", I meant that they arbitrarily chose to use 0 for r and 1 for the other blocks, and they could have just as easily chosen 1 and 0 respectively. Clearly they want the block with the seed to never match any of the blocks of data. The reasoning for this is explained on the section titled "SECURITY" on the beginning of Page 4 of their paper at cs.ucdavis.edu/research/tech-reports/1995/CSE-95-18.pdf – Nik Bougalis Nov 29 '12 at 1:57