Classification and framework
At the highest level, hash functions may be split into two classes: unkeyed hash functions, whose specification dictates a single input parameter (a message); and keyed hash functions, whose specification dictates two distinct inputs, a message and a secret key. To facilitate discussion, a hash function is informally defined as follows.
- 9.1 Definition A hash function (in the unrestricted sense) is a function h which has, as a minimum, the following two properties:
- 1. compression — h maps an input x of arbitrary finite bitlength, to an output h(x) of fixed bitlength n.
- 2. ease of computation — given h and an input x, h(x) is easy to compute.
As defined here, hash function implies an unkeyed hash function. On occasion when discussion is at a generic level, this term is abused somewhat to mean both unkeyed and keyed hash functions; hopefully ambiguity is limited by context.
For actual use, a more goal-oriented classification of hash functions (beyond keyed vs. unkeyed) is necessary, based on further properties they provide and reflecting requirements of specific applications. Of the numerous categories in such a functional classification, two types of hash functions are considered in detail in this chapter:
1. modification detection codes (MDCs)
Also known as manipulation detection codes, and less commonly as message integrity> codes (MICs), the purpose of an MDC is (informally) to provide a representative image or hash of a message, satisfying additional properties as refined below. The end goal is to facilitate, in conjunction with additional mechanisms (see §9.6.4), data integrity assurances as required by specific applications. MDCs are a subclass of unkeyed hash functions, and themselves may be further classified; the specific classes of MDCs of primary focus in this chapter are (cf. Definitions 9.3 and 9.4):
- (i) one-way hash functions (OWHFs): for these, finding an input which hashes to a pre-specified hash-value is difficult;
- (ii) collision resistant hash functions (CRHFs): for these, finding any two inputs having the same hash-value is difficult.
- 2. message authentication codes (MACs)
The purpose of a MAC is (informally) to facilitate, without the use of any additional mechanisms, assurances regarding both the source of a message and its integrity (see §9.6.3). MACs have two functionally distinct parameters, a message input and a secret key; they are a subclass of keyed hash functions (cf. Definition 9.7).
Figure 9.1 illustrates this simplified classification. Additional applications of unkeyed hash functions are noted in §9.2.6. Additional applications of keyed hash functions include use in challenge-response identification protocols for computing responses which are a function of both a secret key and a challenge message; and for key confirmation (Definition 12.7). Distinction should be made between a MAC algorithm, and the use of an MDC with a secret key included as part of its message input (see §9.5.2).
It is generally assumed that the algorithmic specification of a hash function is public knowledge. Thus in the case of MDCs, given a message as input, anyone may compute the hash-result; and in the case of MACs, given a message as input, anyone with knowledge of the key may compute the hash-result.