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 hash-values 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 store-and-retrieve 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 non-repudiation; in this case, collision resistance may or may not be a requirement.

Hash properties required -r Integrity application i








MDC + asymmetric signature




page 324

MDC + authentic channel



page 364

MDC + symmetric encryption

page 365

hash for one-way password file


page 389

MAC (key unknown to attacker)




page 326

MAC (key known to attacker)


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 multi-cast authentication (see page 378).

One-way 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 one-way 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. domain-restricted OWHF) A OWF as defined here differs from a OWHF with domain restricted to fixed-size inputs in that Definition 9.9 does not require 2nd-preimage resistance. Many one-way functions are, in fact, non-compressing, in which case most image elements have unique preimages, and for these 2nd-preimage resistance holds vacuously - making the difference minor (but see Example 9.11).

9.11 Example {one-way functions and modular squaring) The squaring of integers modulo a

prime p, e.g., f(x) = x2 — 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) = x2 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 2nd-preimage, 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 fixed-size inputs. □

9.12 Remark (candidate one-way functions) There are, in fact, no known instances of functions which are provably one-way (with no assumptions); indeed, despite known hash function constructions which are provably as secure as NP-complete problems, there is no assurance the latter are difficult. All instances of “one-way functions” to date should thus more properly be qualified as “conjectured” or “candidate” one-way functions. (It thus remains possible, although widely believed most unlikely, that one-way functions do not exist.) A proof of existence would establish P Ф NP, while non-existence 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 one-way 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 one-way properties, which compress arbitrary-length inputs to гг-bit outputs.
  • 2. compression functions (fixed-size hash functions). These are functions as per Definition 9.1, typically with additional one-way properties, but with domain restricted to fixed-size inputs - i.e., compressing m-bit inputs to n-bit outputs, m > n.
  • 3. non-compressing one-way functions. These are fixed-size hash functions as above, except that n = m. These include one-way permutations, and can be more explicitly described as computationally non-invertible functions.
  • 9.13 Example (DES-based OWF) A one-way 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 one-way 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, Ek(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 fixed-length 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 (one-wayness w.r.t. two inputs) Consider f{x,k) = Е^(х), where E represents DES. This is not a one-way 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 (x1, к'). Similarly, f(x, k) is not a one-way function of x if к is known, as given у = f(x, k) and k, decryption of у using к yields x. (However, a “black-box” which computes f(x, k) for fixed, externally-unknown к is a one-way function of x.) hi contrast, f(x, k) is a one-way function of /с; given у = f(x, k) and x, it is not known how to find a preimage к in less than about 255 operations. (This latter concept is utilized in one-time 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 one-way 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) = ax mod p is a one-way 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 Pohlig-Hellman algorithm of §3.6.4.) f(x) is easily computed given a, x, and p using the square-and-multiply 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 ax 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. □

< Prev   CONTENTS   Source   Next >