Collision-resistant hash function

As explained in Real-World Cryptography

Collision resistance is the property that it is computationally infeasible to find two distinct inputs that produce the same hash output.

A collision-resistant hash function makes it computationally infeasible to find two distinct inputs that produce the same digest. The attacker chooses both inputs, unlike second pre-image resistance, where one input is fixed. section 2.2

Keep these practical limits in mind:

• Treat collision resistance as a security property whose value depends on how the hash function is used, not as a guarantee that collisions are mathematically impossible. section 2.3
• Use sufficiently large digests: a two-bit hash makes collisions easy, while practical hash functions require at least 256-bit outputs. section 2.3
• Retire algorithms whose collision resistance has been broken; published collisions made MD5 and SHA-1 unsuitable when collision resistance matters. section 2.5

A small-output warning

Imagine a hash function with only two output bits. Since it has just four possible digests, hashing a few random strings should quickly produce two different inputs with the same output. Larger digests push this search out of practical reach. section 2.3

Figure 2.5 One should never be able to find two inputs (represented on the left as two random blobs of data) that hash to the same output value (on the right). This security property is called collision resistance.

Visualize two independently chosen input blobs converging on one identical digest. section 2.2

How Real-World Cryptography covers it

How deep it goes

Defines attacker choice, contrasts second pre-image resistance, and explains digest-size limits without proving security.

Examples

Uses two-bit outputs, random input pairs, published MD5 and SHA-1 collisions, and a visual two-input-to-one-digest diagram.

What it assumes

Assumes familiarity with inputs and digests while distinguishing the three principal hash-function security properties.

What you can do after

Evaluate hash choices by attacker control, digest size, and known collision attacks.

How it connects

Connects collision resistance with pre-image resistance, second pre-image resistance, random oracle models, SHA-2, and SHA-3.

liveBookmanning.com

Read Real-World Cryptography on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Hacking CryptographyThe property that it is computationally infeasible to find any two distinct inputs that produce the same hash output.
• 

  liveBookmanning.com
  Software Security for DevelopersCollision resistance is the computational infeasibility of finding two distinct inputs that produce the same cryptographic hash value.

Compare how 3 books explain collision-resistant hash function →

Related concepts

• hash functionproduced by · A hash function deterministically maps input data to a value in a bounded output range, commonly for indexing, lookup, comparison, or integrity checking.
• security propertykind of · A security property is a security-relevant characteristic that a cryptographic primitive or protocol is intended to provide.
• capacityconfigured by · In a sponge construction, capacity is the portion of the internal state not directly exposed to input or output and determining security strength.
• hash-based signature schemecontrasts with · A hash-based signature scheme is a digital signature scheme whose security is based on cryptographic hash-function properties rather than algebraic number-theoretic assumptions.
• cryptographic hashpart of · A cryptographic hash is a fixed-length digest computed from input data by a deterministic function designed to resist preimage, second-preimage, and collision attacks.

This explainer was generated by Manning's knowledge graph from the text of Real-World Cryptography. The section links point to the parts of the book it draws on.