# Customized MACs

Two algorithms designed for the specific purpose of message authentication are discussed in this section: MAA and MD5-MAC.

Message Authenticator Algorithm (MAA)

The Message Authenticator Algorithm (MAA), dating from 1983, is a customized MAC algorithm for 32-bit machines, involving 32-bit operations throughout. It is specified as Algorithm 9.68 and illustrated in Figure 9.7. The main loop consists of two parallel interdependent streams of computation. Messages are processed in 4-byte blocks using 8 bytes of chaining variable. The execution tune (excluding key expansion) is proportional to message length; as a rough guideline, MAA is twice as slow as MD4.

9.68 Algorithm Message Authenticator Algorithm (MAA)

INPUT: data *x* of bitlength 32*j,* 1 < *j <* 10°; secret 64-bit MAC key *Z = Z[1]..Z[8], *OUTPUT: 32-bit MAC on *x.*

- 1.
*Message-independent key expansion.*Expand key*Z*to six 32-bit quantities*X, Y, V*,*W, S, T (X. Y*are initial values;*V. W*are main loop variables;*S, T*are appended to the message) as follows. - 1.1 First replace any bytes 0x00 or Oxff in
*Z*as follows. Pf- 0; for*i*from 1 to 8 (P 2P; if*Z[i} =*0x00 or Oxff then (P <- P + 1;*Zi] Z[i]*OR P)). - 1.2 Let
*J*and*К*be the first 4 bytes and last 4 bytes of*Z*, and compute:^{[1]}*X ^ J*(mod 2^{[1]}^{32}- 1)ф J^{[1]}(mod 2^{32}- 2)

*Y* [.*K ^{r}°* (mod 2

^{32}- 1)фР

^{[4]}(mod 2

^{32}- 2)](1 + P)

^{2}(mod 2

^{32}- 2)

*V* <- J^{[5]} (mod 2^{32} - 1)ф J^{[5]} (mod 2^{32} - 2)

*W* «- *K ^{7}* (mod 2

^{32}- 1)фЯ

^{7}(mod 2

^{32}- 2)

*S <-* J^{8} (mod 2^{32} - 1)®J^{8} (mod 2^{32} - 2)

*T <- I( ^{,J}* (mod 2

^{32}- 1 )фЯ

^{9}(mod 2

^{32}- 2)

- 1.3 Process the 3 resulting pairs
*(X, Y), (V. W),*(S,*T)*to remove any bytes 0x00, Oxff as for*Z*earlier. Define the AND-OR constants:*A*= 0x02040801,*В*= 0x00804021,*C*= 0xbfef7fdf,*D =*0x7dfefbff. - 2.
*Initialization and preprocessing.*Initialize the rotating vector:*v <- V,*and the chaining variables:*Hi <- X,*#_{2}«-*Y.*Append the key-derived blocks 5,*T*to*x,*and let*xi*...*x*denote the resulting augmented segment of 32-bit blocks. (The final 2 blocks of the segment thus involve key-derived secrets.)_{t} - 3.
*Block processing.*Pr ocess each 32-bit block x, (for*i*from 1 to*t)*as follows,

r <- (» p 1), *U <—* (ифИ^{7})

*t _{x}* «-

*(H*xx (((Я

_{x}®xi)_{2}фхх) +

*U)*OR

*A)*AND

*C) t*<-

_{2}*(H*x2

_{2}®xi)*{{(Нгфхг)*+

*U)*OR

*В)*AND

*D)*

* Hi i*—

**ti, H**_{2}t_{2}where x, denotes special multiplication mod 2^{32} - *i* as noted above (г = 1 or 2); “+” is addition mod 2^{32}; and “<-> 1” denotes rotation left one bit. (Each combined AND-OR operation on a 32-bit quantity sets 4 bits to 1, and 4 to 0, precluding 0- multipliers.)

4. *Completion.* The resulting MAC is: Я = ЯхфЯ_{2}.

**Figure 9.7: ***The Message Authenticator Algorithm (МАЛ).*

Since the relatively complex key expansion stage is independent of the message, a onetime computation suffices for a fixed key. The mixing of various operations (arithmetic mod 2^{32} - *i,* for *i =* 0,1 and 2; XOR; and nonlinear AND-OR computations) is intended to strengthen the algorithm against arithmetic cryptanalytic attacks.

MD5-MAC

A more conservative approach (cf. Example 9.66) to building a MAC from an MDC is to arrange that the MAC compression function itself depend on *k,* implying the secret key be involved in all intervening iterations; this provides additional protection in the case that weaknesses of the underlying hash function become known. Algorithm 9.69 is such a technique, constructed using MD5. It provides performance close to that of MD5 (5-20% slower in software).

9.69 Algorithm MD5-MAC

INPUT: bitstring *x* of arbitrary bitlength 6 > 0; key *к* of bitlength < 128.

OUTPUT: 64-bit MAC-value of *x.*

MD5-MAC is obtained from MD5 (Algorithm 9.51) by the following changes.

- 1.
*Constants.*The constants*U,*and*T,*are as defined in Example 9.70. - 2.
*Key expansion.* - (a) If
*к*is shorter than 128 bits, concatenate*к*to itself a sufficient number of times, and redefine*к*to be the leftmost 128 bits. - (b) Let MD5 denote MD5 with both padding and appended length omitted. Expand
*к*into three 16-byte subkeys*K*and_{0}, K,*K*as follows: for_{2}*i*from 0 to 2,*Ki*<- MD5(/c ||*Ui*||*k).* - (c) Partition each of
*K*and_{0}*K*into four 32-bit substrings*К,*[г], 0 <*i <*3. - 3.
*K*replaces the four 32-bit_{0}*IV’s*of MD5 (i.e.,*h,*= А'о[г]). - 4.
*Кi*[г] is added mod 2^{32}to each constant y[j] used in Round*i*of MD5. - 5.
*K**‘2*is used to construct the following 512-bit block, which is appended to the padded input*x*subsequent to the regular padding and length block as defined by MD5:

k_{2} || k_{2} e T_{0}1| k_{2} ® *Ti* || k_{2} e t_{2}.

6. The MAC-value is the leftmost 64 bits of the 128-bit output from hashing this padded and extended input string using MD5 with the above modifications.

9.70 Example (*MD5-MAC constants/test vectors*) The 16-byte constants *T,* and three test vectors (ж, MD5-MAC(x)) for key *к =* 00112233445566778899aabbccddeef f are given below. (The *T,* themselves are derived using MD5 on pre-defined constants.) With subscripts in *Ti* taken mod 3, the 96-byte constants *U _{0}, U_{y} U2* are defined:

- [1] In ISO 8731-2, a well-defined but unconventional definition of multiplication mod 232 — 2 is specified, pro
- [2] In ISO 8731-2, a well-defined but unconventional definition of multiplication mod 232 — 2 is specified, pro
- [3] In ISO 8731-2, a well-defined but unconventional definition of multiplication mod 232 — 2 is specified, pro
- [4] ducing 32-bit results which in some cases are 232 — 1 or 232 — 2; for tins reason, specifying e g., J3 here may
- [5] be ambiguous; the standard should be consulted for exact details.
- [6] be ambiguous; the standard should be consulted for exact details.