Relationships between properties

In this section several relationships between the hash function properties stated in the preceding section are examined.

9.18 Fact Collision resistance implies 2nd-preimage resistance of hash functions.

Justification. Suppose h has collision resistance. Fix an input xj. If h does not have 2nd- preimage resistance, then it is feasible to find a distinct input хг such that h{xf) = h(xj), in which case (xi.Xj) is a pair of distinct inputs hashing to the same output, contradicting collision resistance.

9.19 Remark (one-way vs. preimage and 2nd-preimage resistant) While the term “one-way” is generally taken to mean preimage resistant, in the hash function literature it is sometimes also used to imply that a function is 2nd-preimage resistant or computationally non- invertible. (Computationally non-invertible is a more explicit term for preimage resistance when preimages are unique, e.g., for one-way permutations. In the case that two or more preimages exist, a function fails to be computationally non-invertible if any one can be found.) This causes ambiguity as 2nd-preimage resistance does not guarantee preimage- resistance (Note 9.20), nor does preimage resistance guarantee 2nd-preimage resistance (Example 9.11); see also Remark 9.10. An attempt is thus made to avoid unqualified use of the term “one-way”.

9.20 Note (collision resistance does not guarantee preimage resistance) Let д be a hash function which is collision resistant and maps arbitrary-length inputs to n-bit outputs. Consider the function h defined as (here and elsewhere, || denotes concatenation):

Then h is an (n + l)-bit hash function which is collision resistant but not preimage resistant. As a simpler example, the identity function on fixed-length inputs is collision and 2nd- preimage resistant (prehnages are unique) but not preimage resistant. While such pathological examples illustrate that collision resistance does not guarantee the difficulty of finding preimages of specific (or even most) hash outputs, for most CRHFs arising in practice it nonetheless appears reasonable to assume that collision resistance does indeed imply preimage resistance.

9.21 Fact (implications of MAC properties) Let hk be a keyed hash function which is a MAC algorithm per Definition 9.7 (and thus has the property of computation-resistance). Then hk is, against chosen-text attack by an adversary without knowledge of the key к, (i) both 2nd-preimage resistant and collision resistant; and (ii) preimage resistant (with respect to the hash-input).

Justification. For (i), note that computation-resistance implies hash-results should not even be computable by those without secret key к. For (ii), by way of contradiction, assume h were not preimage resistant. Then recovery of the preimage x for a randomly selected hash-output у violates computation-resistance.

< Prev   CONTENTS   Source   Next >