MACs for stream ciphers

Providing data origin authentication and data integrity guarantees for stream ciphers is particularly important due to the fact that bit manipulations in additive stream-ciphers may directly result in predictable modifications of the underlying plaintext (e.g., Example 9.83). While iterated hash functions process message data a block at a tune (§9.3.1), MACs designed for use with stream ciphers process messages either one bit or one symbol (block) at a time, and those which may be implemented using linear feedback shift registers (LFSRs) are desirable for reasons of efficiency.

One such MAC technique, Algorithm 9.72 below, is based on cyclic redundancy codes (cf. Example 9.80). In this case, the polynomial division may be implemented using an LFSR. The following definition is of use in what follows.

  • 9.71 Definition A (b, m) hash-family H is a collection of hash functions mapping Ь-bit messages to m-bit hash-values. A (b, m) hash-family is s-balanced if for all messages В Ф 0 and all m-bit hash-values c, probh{h(B) = c)) < e, where the probability is over all randomly selected functions k e B.
  • 9.72 Algorithm CRC-based MAC

INPUT: b-bit message B shared key (see below) between MAC source and verifier. OUTPUT: m-bit MAC-value on В (e.g., m = 64).

  • 1. Notation. Associate В = Вь~... BB0 with the polynomial B(x) = Xa=o BiX1-
  • 2. Selection of MAC key.
  • (a) Select a random binary irreducible polynomial p(x) of degree m. (This represents randomly drawing a function h from a (b, m) hash-family.)
  • (b) Select a random m-bit one-time key k (to be used as a one-time pad).

The secret MAC key consists of p(x) and k, both of which must be shared a priori between the MAC originator and verifier.

  • 3. Compute h(B) = cocf(B(x) ■ x"‘ mod p(x)), the m-bit string of coefficients from the degree m - 1 remainder polynomial after dividing B(x) ■ xm by p{x).
  • 4. The ?n-bit MAC-value for В is: h(B)®k.
  • 9.73 Fact (security' of CRC-based MAC) For any values band m > 1, the hash-family resulting from Algorithm 9.72 is e-balanced for e = (b + m)/(2'"_1), and the probability of MAC forgery is at most e.
  • 9.74 Remark (polynomial reuse) The hash function h in Algorithm 9.72 is determined by the irreducible polynomial p(x). In practice, p(x) may be re-used for different messages (e.g., within a session), but for each message a new random key к should be used.
< Prev   CONTENTS   Source   Next >