Hash properties required for specific applications
Because there may be costs associated with specific properties  e.g., CRHFs are in general harder to construct than OWHFs and have hashvalues roughly twice the bitlength  it should be understood which properties are actually required for particular applications, and why. Selected techniques whereby hash functions are used for data integrity, and the corresponding properties required thereof by these applications, are summarized in Table 9.1.
In general, an MDC should be a CRHF if an untrusted party has control over the exact content of hash function inputs (see Remark 9.93); a OWHF suffices otherwise, including the case where there is only a single party involved (e.g., a storeandretrieve application). Control over precise format of inputs may be eliminated by introducing into the message randomization that is uncontrollable by one or both parties. Note, however, that data integrity techniques based on a shared secret key typically involve mutual trust and do not address nonrepudiation; in this case, collision resistance may or may not be a requirement.
Hash properties required r Integrity application i 
Preimage resistant 
2nd preimage 
Collision resistant 
Details 
MDC + asymmetric signature 
yes 
yes 
yesf 
page 324 
MDC + authentic channel 
yes 
yesf 
page 364 

MDC + symmetric encryption 
page 365 

hash for oneway password file 
yes 
page 389 

MAC (key unknown to attacker) 
yes 
yes 
yesf 
page 326 
MAC (key known to attacker) 
yes 
page 325 
Table 9.1: Resistance properties required for specified data integrity applications. fResistance required if attacker is able to mount a chosen message attack. ^Resistance required in rare case of multicast authentication (see page 378).
Oneway functions and compression functions
Related to Definition 9.3 of a OWHF is the following, which is unrestrictive with respect to a compression property.
 9.9 Definition A oneway function (OWF) is a function / such that for each x in the domain of /, it is easy to compute }{x)but for essentially all у in the range of /, it is computationally infeasible to find any x such that у = f(x).
 9.10 Remark (OWF vs. domainrestricted OWHF) A OWF as defined here differs from a OWHF with domain restricted to fixedsize inputs in that Definition 9.9 does not require 2ndpreimage resistance. Many oneway functions are, in fact, noncompressing, in which case most image elements have unique preimages, and for these 2ndpreimage resistance holds vacuously  making the difference minor (but see Example 9.11).
9.11 Example {oneway functions and modular squaring) The squaring of integers modulo a
prime p, e.g., f(x) = x^{2} — 1 mod p, behaves in many ways like a random mapping. However. f(x) is not a OWF because finding square roots modulo prunes is easy (§3.5.1). On the other hand, g(x) = x^{2} mod n is a OWF (Definition 9.9) for appropriate randomly chosen prunes p and q where n = pq and the factorization of n is unknown, as finding a preimage (i.e., computing a square root mod n) is computationally equivalent to factoring (Fact 3.46) and thus intractable. Nonetheless, finding a 2ndpreimage, and, therefore, collisions, is trivial (given x, x yields a collision), and thus g fits neither the definition of a OWHF nor a CRHF with domain restricted to fixedsize inputs. □
9.12 Remark (candidate oneway functions) There are, in fact, no known instances of functions which are provably oneway (with no assumptions); indeed, despite known hash function constructions which are provably as secure as NPcomplete problems, there is no assurance the latter are difficult. All instances of “oneway functions” to date should thus more properly be qualified as “conjectured” or “candidate” oneway functions. (It thus remains possible, although widely believed most unlikely, that oneway functions do not exist.) A proof of existence would establish P Ф NP, while nonexistence would have devastating cryptographic consequences (see page 377), although not directly implying P = NP.
Hash functions are often used in applications (cf. §9.2.6) which require the oneway property, but not compression. It is, therefore, useful to distinguish three classes of functions (based on the relative size of inputs and outputs):
 1. (general) hash functions. These are functions as per Definition 9.1, typically with additional oneway properties, which compress arbitrarylength inputs to ггbit outputs.
 2. compression functions (fixedsize hash functions). These are functions as per Definition 9.1, typically with additional oneway properties, but with domain restricted to fixedsize inputs  i.e., compressing mbit inputs to nbit outputs, m > n.
 3. noncompressing oneway functions. These are fixedsize hash functions as above, except that n = m. These include oneway permutations, and can be more explicitly described as computationally noninvertible functions.
 9.13 Example (DESbased OWF) A oneway function can be constructed from DES or any
block cipher E which behaves essentially as a random function (see Remark 9.14), as follows: f(x) = Е_{к}(х)фх, for any fixed known key k. The oneway nature of this construction can be proven under the assumption that E is a random permutation. An intuitive argument follows. For any choice of y, finding any x (and key к) such that Е_{к}(х)фх = у is difficult because for any chosen x, E_{k}(x) will be essentially random (for any key к) and thus so will Ek(x)фж; hence, this will equal у with no better than random chance. By similar reasoning, if one attempts to use decryption and chooses an x, the probability that Е^^{1}(хфу) = x is no better than random chance. Thus /(x) appears to be a OWF. While f (x) is not a OWHF (it handles only fixedlength inputs), it can be extended to yield one (see Algorithm 9.41). □
9.14 Remark (block ciphers and random functions) Regarding random functions and their properties, see §2.1.6. If a block cipher behaved as a random function, then encryption and decryption would be equivalent to looking up values in a large table of random numbers; for a fixed input, the mapping from a key to an output would behave as a random mapping. However, block ciphers such as DES are bijections, and thus at best exhibit behavior more like random permutations than random functions.
 9.15 Example (onewayness w.r.t. two inputs) Consider f{x,k) = Е^(х), where E represents DES. This is not a oneway function of the joint input (x, k), because given any function value у = f(x, k), one can choose any key k' and compute x' = Ef,^{1} (y) yielding a preimage (x^{1}, к'). Similarly, f(x, k) is not a oneway function of x if к is known, as given у = f(x, k) and k, decryption of у using к yields x. (However, a “blackbox” which computes f(x, k) for fixed, externallyunknown к is a oneway function of x.) hi contrast, f(x, k) is a oneway function of /с; given у = f(x, k) and x, it is not known how to find a preimage к in less than about 2^{55} operations. (This latter concept is utilized in onetime digital signature schemes  see § 11.6.2.) □
 9.16 Example (OWF  multiplication of large primes) For appropriate choices of primes p and q, /(Pi q) = pq is a oneway function: given p and q, computing n = pq is easy, but given n, finding p and q, i.e., integerfactorization, is difficult. RSA and many other cryptographic systems rely on this property (see Chapter 3, Chapter 8). Note that contrary to many oneway functions, this function f does not have properties resembling a “random” function. □
 9.17 Example (OWF  exponentiation infinite fields) For most choices of appropriately large
primes p and any element a € Z* of sufficiently large multiplicative order (e.g., a generator), f(x) = a^{x} mod p is a oneway function. (For example, p must not be such that all the prime divisors of p  1 are small, otherwise the discrete log problem is feasible by the PohligHellman algorithm of §3.6.4.) f(x) is easily computed given a, x, and p using the squareandmultiply technique (Algorithm 2.143), but for most choices p it is difficult, given (y. p, a), to find an x in the range 0 < x < p  2 such that a^{x} mod p = y, due to the apparent intractability of the discrete logarithm problem (§3.6). Of course, for specific values of f(x) the function can be inverted trivially. For example, the respective preimages of 1 and 1 are known to be 0 and (p  l)/2, and by computing f(x) for any small set of values for x (e.g., x = 1.2,... , 10), these are also known. However, for essentially all у in the range, the preimage of у is difficult to find. □