Message Authentication - Codes: The Guide to Secrecy from Ancient to Modern Times - page 251

the upper layer (authentication protocol) ensuring that the receiver can verify
the authenticity of the message.
Although there is no hierarchy written in stone as to the bottom layer func-
tions for authentication, the following is generally accepted by the cryptographic
community.

Types of Authentication Functions
1. Hash functions, where a publically known cryptographic hash function is
the authenticator.

2. Message authentication codes (MAC)s, where a publicly known MAC of the
message coupled with a secret key, outputs a fixed-length value, which is
the authenticator.

3. Message encryption, wherein the ciphertext is the authenticator itself.

We are going to devote the balance of this section to the first of these, and
cover MACs in Section 7.2. Section 7.3 will be a description of the third and a
comparison of the three. The concluding Section 7.4 will deal with authentica-
tion applications.

Hash functions
We had a brief introduction to hash functions and message digests on pages
170 and 171, where we learned that a ( cryptographic ) hash function is a one-
way function that is a computationally e:cient function mapping bitstrings of
arbitrary length to bitstrings of fixed length. The hash value (or message digest )
is then a:xed to the message by the sender, and the message is authenticated
by the receiver, who recomputes the message digest. As noted on page 171,
the message digest is a “fingerprint” of sorts, and this is the purpose of the
hash function: to authenticate the data by fingerprinting it. Moreover, as noted
on page 171, it is desirable for the cryptographic hash function to be strongly
collision resistant . The reason for this latter requirement is to guard against a
class of attacks for which we have prepared the reader on page 130, when we
discussed the meet-in-the-middle attack.

The Birthday Attack
We are given a hash function H : S → T , with | T | = n and | S | >n , so there

is at least one collision. (If | S |≥ 2 n , there are at least n collisions. In fact, it can

be shown that when , there exists a probabilistic algorithm that

finds a collision for h with probability bigger than 1 / 2 (see [159, Fact 9.33]).)
We now look at how to find such collisions. First, we describe the analogue of
the above that gives this attack its name.
The Birthday Paradox : Suppose there are n> 1 balls in a container
numbered from 1 to n inclusive. Also, let us assume that m> 1 balls are drawn
one at a time, listed, and replaced each time (where m<n ). What is the
probability that one of the balls is drawn at least twice?

∞ > | S |≥ 2 | T |