See more Collision resistance articles on AOD.

Powered by
TTSReader
Share this page on
Article provided by Wikipedia


( => ( => ( => Collision resistance [pageid] => 2982326 ) =>

Collision resistance is a property of "cryptographic hash functions: a hash function H is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H(a) = H(b), and ab.[1]:136

Every hash function with more inputs than outputs will necessarily have collisions.[1]:136 Consider a hash function such as "SHA-256 that produces 256 bits of output from an arbitrarily large input. Since it must generate one of 2256 outputs for each member of a much larger set of inputs, the "pigeonhole principle guarantees that some inputs will hash to the same output. Collision resistance does not mean that no collisions exist; simply that they are hard to find.[1]:143

The ""birthday paradox" places an upper bound on collision resistance: if a hash function produces N bits of output, an attacker who computes only 2N/2 (or ) hash operations on random input is likely to find two matching outputs. If there is an easier method than this "brute-force attack, it is typically considered a flaw in the hash function.[2]

"Cryptographic hash functions are usually designed to be collision resistant. But many hash functions that were once thought to be collision resistant were later broken. "MD5 and "SHA-1 in particular both have published techniques more efficient than brute force for finding collisions.[3][4] However, some hash functions have a proof that finding collisions is at least as difficult as some hard mathematical problem (such as "integer factorization or "discrete logarithm). Those functions are called "provably secure.[2]

Contents

Definition[edit]

A family of functions {hk : {0, 1}m(k) → {0, 1}l(k)} generated by some algorithm G is a family of collision resistant hash functions, if |m(k)| > |l(k)| for any k, i.e., hk compresses the input string, and every hk can be computed within polynomial time given k, but for any probabilistic polynomial algorithm A, we have

Pr [kG(1n), (x1, x2) ← A(k, 1n) s.t. x1x2 but hk(x1) = hk(x2)] < negl(n),

where negl(·) denotes some negligible function, and n is the security parameter.[5]

Rationale[edit]

Collision resistance is desirable for several reasons.

See also[edit]

References[edit]

  1. ^ a b c "Goldwasser, S. and "Bellare, M. "Lecture Notes on Cryptography". Summer course on cryptography, MIT, 1996-2001
  2. ^ a b Pass, R. "Lecture 21: Collision-Resistant Hash Functions and General Digital Signature Scheme". Course on Cryptography, Cornell University, 2009
  3. ^ Xiaoyun Wang; Hongbo Yu. "How to Break MD5 and Other Hash Functions" (PDF). Retrieved 2009-12-21. 
  4. ^ Xiaoyun Wang; Yiquin Lisa Yin; Hongobo Yu. "Finding Collisions in the Full SHA-1" (PDF). 
  5. ^ Dodis, Yevgeniy. "Lecture 12 of Introduction to Cryptography" (PDF). Retrieved 3 January 2016. , def 1.
) )