Bitsizes required for practical security

Suppose that a hash function produces n-bit hash-values, and as a representative benchmark assume that 280 (but not fewer) operations is acceptably beyond computational feasibility.[1] Then the following statements may be made regarding n.

  • 1. For a OWHF, n > 80 is required. Exhaustive off-line attacks require at most 2" operations; this may be reduced with precomputation (Remark 9.35).
  • 2. For a CRHF, n > 160 is required. Birthday attacks are applicable (Fact 9.33).
  • 3. For a MAC, n > 64 along with a MAC key of 64-80 bits is sufficient for most applications and environments (cf. Table 9.1). If a single MAC key remains in use, off-line attacks may be possible given one or more text-MAC pairs; but for a proper MAC algorithm, preimage and 2nd-prehnage resistance (as well as collision resistance) should follow directly from lack of knowledge of the key, and thus security with respect to such attacks should depend on the keysize rather than n. For attacks requiring on-line queries, additional controls may be used to limit the number of such queries, constrain the format of MAC inputs, or prevent disclosure of MAC outputs for random (chosen-text) inputs. Given special controls, values as small as n = 32 or 40 may be acceptable; but caution is advised, since even with one-time MAC keys, the chance any randomly guessed MAC being correct is 2~n, and the relevant factors are the total number of trials a system is subject to over its lifetime, and the consequences of a single successful forgery.

These guidelines may be relaxed somewhat if a lower threshold of computational infeasibility is assumed (e.g., 264 instead of 280). However, an additional consideration to be taken into account is that for both a CRHF and a OWHF, not only can off-line attacks be earned out, but these can typically be parallelized. Key search attacks against MACs may also be parallelized.

  • [1] Circa 1996,240 simple operations is quite feasible, and 256 is considered quite reachable by those with sufficient motivation (possibly using parallelization or customized machines).
< Prev   CONTENTS   Source   Next >