 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 32j, 1 < j < 10°; secret 64-bit MAC key Z = Z..Z, 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: X ^ J (mod 232 - 1)ф J (mod 232 - 2)

Y [.Kr° (mod 232 - 1)фР (mod 232 - 2)](1 + P)2 (mod 232 - 2)

V <- J (mod 232 - 1)ф J (mod 232 - 2)

W «- K7 (mod 232 - 1)фЯ7 (mod 232 - 2)

S <- J8 (mod 232 - 1)®J8 (mod 232 - 2)

T <- I(,J (mod 232 - 1 )фЯ9 (mod 232 - 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... xt denote the resulting augmented segment of 32-bit blocks. (The final 2 blocks of the segment thus involve key-derived secrets.)
• 3. Block processing. Pr ocess each 32-bit block x, (for i from 1 to t) as follows,

r <- (» p 1), U <— (ифИ7)

tx «- (Hx®xi) xx (((Я2фхх) + U) OR A) AND C) t2 <- (H2®xi) x2 {{(Нгфхг) + U) OR В) AND D)

Hi iti, H2 t2

where x, denotes special multiplication mod 232 - i as noted above (г = 1 or 2); “+” is addition mod 232; 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 232 - 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 K0, K, and K2 as follows: for i from 0 to 2, Ki <- MD5(/c || Ui || k).
• (c) Partition each of K0 and K into four 32-bit substrings К, [г], 0 < i < 3.
• 3. K0 replaces the four 32-bit IV’s of MD5 (i.e., h, = А'о[г]).
• 4. Кi [г] is added mod 232 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:

k2 || k2 e T01| k2 ® Ti || k2 e t2.

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 U0, Uy U2 are defined: •  In ISO 8731-2, a well-defined but unconventional definition of multiplication mod 232 — 2 is specified, pro
•  In ISO 8731-2, a well-defined but unconventional definition of multiplication mod 232 — 2 is specified, pro
•  In ISO 8731-2, a well-defined but unconventional definition of multiplication mod 232 — 2 is specified, pro
•  ducing 32-bit results which in some cases are 232 — 1 or 232 — 2; for tins reason, specifying e g., J3 here may
•  be ambiguous; the standard should be consulted for exact details.
•  be ambiguous; the standard should be consulted for exact details.