Pseudo-collisions and compression function attacks

The exhaustive or brute force methods discussed in §9.3.4, producing preimages, 2nd-pre- images, and collisions for hash functions, are always theoretically possible. They are not considered true “attacks” unless the number of operations required is significantly less than both the strength conjectured by the hash function designer and that of hash functions of similar parameters with ideal strength. An attack requiring such a reduced number of operations is informally said to break the hash function, whether or not this computational effort is feasible in practice. Any attack method which demonstrates that conjectured properties do not hold must be taken seriously; when this occurs, one must admit the possibility of additional weaknesses.

In addition to considering the complexity of finding (ordinary) preimages and collisions, it is common to examine the feasibility of attacks on slightly modified versions of the hash function in question, for reasons explained below. The most common case is examination of the difficulty of finding preimages or collisions if one allows free choice of IVs. Attacks on hash functions with unconstrained IVs dictate upper bounds on the security of the actual algorithms. Vulnerabilities found, while not direct weaknesses in the overall hash function, are nonetheless considered certificational weaknesses and cast suspicion on overall security. In some cases, restricted attacks can be extended to full attacks by standard techniques.

Table 9.11 lists the most commonly examined variations, including pseudo-collisions - collisions allowing different IVs for the different message inputs. In contrast to preimages and collisions, pseudo-preimages and pseudo-collisions are of limited direct practical significance.

  • 9.94 Note (alternate names for collision and preimage attacks) Alternate names for those in Table 9.11 are as follows: preimage or 2nd-preimage = target attack; pseudo-preimage =free-start target attack; collision (fixed IV) = collision attack; collision (random IV) = semi-free-start collision attack; pseudo-collision = free-start collision attack.
  • 9.95 Note (relative difficultу of attacks) Finding a collision can be no harder than finding a 2nd- preimage. Similarly, finding a pseudo-collision can be no harder than finding (two distinct) pseudo-preimages.

.[.Type of attack






Find ...




collision (fixed IV)

collision (random IV)


Table 9.11: Definition of preimage and collision attacks. V and V' denote (potentially different) TVs used for MDC h applied to inputs x and x respectively; Vo denotes the IV pre-specified in the definition of h, xo a pre-specified target input, and у = y<> a pre-specified target output. * Denotes IVs or inputs which may be freely chosen by an attacker; h(Vo, xo) denotes the hash-code resulting from applying h with fixed TV V = Vo to input x = xo. — Means not applicable.

9.96 Example (trivial collisions for random IVs) If free choice of IV is allowed, then trivial pseudo-collisions can be found by deleting leading blocks from a target message. For example, for an iterated hash (cf. equation (9.1) on page 333), h(IV, X1X2) = xi),X2). Thus, for IV = f(IV, xi), h(IV', xff) = h(IV. 3:1X2) yields a pseudo-collision of /1, independent of the strength of /. (MD-strengthening as per Algorithm 9.26 precludes this.)

Another common analysis technique is to consider the strength of weakened variants of an algorithm, or attack specific subcomponents, akin to cryptanalyzing an 8-round version of DES in place of the full 16 rounds.

9.97 Definition An attack on the compression function of an iterated hash functionis any attack

as per Table 9.11 with xf) replacing h(V0,x) - the compression function / in place

of hash function h, chaining variable Я,-_ 1 in place of initializing value V, and a single input block Xi in place of the arbitrary-length message x.

An attack on a compression function focuses on one fixed step i of the iterative function of equation (9.1). The entire message consists of a single block xt = x (without MD-strengthening), and the hash output is taken to be the compression function output so h(x) = Hj. The importance of such attacks arises from the following.

9.98 Note (compression function vs. hash function attacks) Any of the six attacks of Table 9.11 which is found for the compression function of an iterated hash can be extended to a similar attack of roughly equal complexity on the overall hash. An iterated hash function is thus in this regard at most as strong as its compression function. (However note, for example, an overall pseudo-collision is not always of practical concern, since most hash functions specify a fixed IV.)

For example, consider a message x = X1X2 ... xt. Suppose a successful 2nd-preimage attack on compression function / yields a 2nd-preimage x', x such that f(IV, x^) = f(IV. xi). Then, x' = х[х,2 ... x« is a preimage of /i(x).

More positively, if MD-strengthening is used, the strength of an iterated hash with respect to the attacks of Table 9.11 is the same as that of its compression function (cf.

Fact 9.24). However, an iterated hash may certainly be weaker than its compression function (e.g., Example 9.96; Fact 9.37).

In summary, a compression function secure against preimage, 2nd-preimage, and collision (fixed IV) attacks is necessary and sometimes, but not always, sufficient for a secure iterated hash; and security against the other (i.e., free-start) attacks of Table 9.11 is desirable, but not always necessary for a secure hash function in practice. For this reason, compression functions are analyzed in isolation, and attacks on compression functions as per Definition 9.97 are considered. A further result motivating the study of pseudo-preimages is the following.

9.99 Fact {pseudo-preimages yielding preimages) If the compression function / of an «-bit iterated hash function h does not have ideal computational security (2,!) against pseudopreimage attacks, then preimages for h can be found in fewer than 2" operations (cf. §9.3.4, Table 9.2). This result is true even if h has MD-strengthening.

Justification. The attack requires messages of 3 or more blocks, with 2 or more unconstrained to allow a meet-in-the-middle attack (page 374). If pseudo-preimages can be found in 2s operations, then 2(n+s^2 forward points and 2("-s^2 backward points are employed (fewer backward points are used since they are more costly). Preimages can thus be found in 2 • 2(n+s)/2 operations.

< Prev   CONTENTS   Source   Next >