Tail-MAC broken

From: Bartosz Zoltak (X_at_vmpcfunction.com;)
Date: 10/28/04 

Date: Thu, 28 Oct 2004 22:01:31 +0200

The Tail-MAC scheme which I proposed some time ago for the VMPC stream
cipher is broken.

(http://www.vmpcfunction.com/vmpcmac.htm)

The main loop of the scheme went like this:
-----------------------------------
   1. s=P[s+P[n]]
   2. Ciphertext[m] = Plaintext[m] XOR P[P[P[s]]+1]
(** steps 1 and 2 come from VMPC stream cipher **)

   3.1. x4 = x4 + x3
   3.2. x3 = x3 + x2
   3.3. x2 = x2 + x1
   3.4. x1 = P[ x1 + s + Ciphertext[m] ]

   4.1. XOR T[g] with x1
   4.2. XOR T[g+1] with x2
   4.3. XOR T[g+2] with x3
   4.4. XOR T[g+3] with x4
(** steps 3.X, 4.X is the main part of the Tail-MAC **)

   5. Swap P[n] with P[s]
   6.1. g=(g+4) mod 32
   6.2. n=(n+1) mod 256
   6.3. m=m+1

7. Post-Processing: Repeat steps 1 - 6.3 for a zeros-filled plaintext
32 times.
8. MAC = HASH(T)
-----------------------------------

The main attack finds collisions in T. It asumes appending one byte to
the cipherptext message and relies on the fact that the
post-processing phase (step 7) and the encryption phase of the MAC
algorithm (steps 3.1 - 3.4) are equivalent (they generate the same
output from a given input) and from the fact that the probability that
x1,x2,x3,x4 will not change T in the last step of processing the
one-byte-longer-message is 2^-32.

The other problem with the Tail-MAC is that if for a new message x1
grows by 128 (or any other integer D=256/integer), then the
propagation of changes of the variables x1,x2,x3,x4 is awfully limited
due to their linearity (only the addition operation x(n)=x(n)+x(n-1)).
As a result in even numbers of overlapping loops the x variables do
not change at all since the addition is modulo 256 (128+128 mod
256=0). This significantly limits the number of elements of T which
are affected by the change of the one (or more) bytes of the message.

This way if anybody was using the Tail-MAC scheme in any applications,
he should keep in mind that the chances of forging the message are
roughly speaking as large as 1 / 2 000 000 000 on average, which is by
far unacceptably high.

-----------------------

There is however a proposition of fixing these problems - a new
scheme called rather not originally "VMPC-MAC".
There are two modifications from Tail-MAC to VMPC-MAC:

1* The 3.X step is modified into x(n) = P[ x(n) + x(n-1) ] - the P
permutation is there to currupt the linearity of x(n) + x(n-1)

2* The consecutive steps of the post-processing phase are not
equivalent to the encryption phase. The 3.X step of the
post-processing phase is modified into
x(n) = P[ x(n) + x(n-1) + R] where R runs from 1 to 24.

Also the VMPC-MAC is no longer a general proposition, it is dedicated
only to the VMPC stream cipher - it is too high of an art for me to
design a general scheme.

The VMPC-MAC scheme is described in detail at my website, at
http://www.vmpcfunction.com/vmpcmac.htm

The links to PDF/PS/DVI papers on that website fetch a TEMPORARY
version of the new VMPC-MAC paper. It is there not because it is good
but because the old Tail-MAC paper had to go.

The final version of the VMPC-MAC paper will be uploaded at the
website around 20 November.

If anybody would like to share any comments on the new (or the old)
scheme, I will be very glad to hear.

A general lesson I learned from my Tail-MAC experience is - don't go
for extra speed and simplicity of the scheme **by all force**.
Security is much worse to lack than speed.

 --
Bartosz Zoltak
http://www.vmpcfunction.com
X@vmpcfunction.com; X=bzoltak