Hash Function

6 min read#cryptography

A one-way fingerprint that turns any input into a fixed-size digest, where flipping one input bit scrambles roughly half the output.

Contents

Hash Function

A cryptographic hash function crushes an input of any size — a word, a file, a movie — into a short, fixed-length digest (a "fingerprint"), in a way that is easy to compute but impossible to reverse or fool. SHA-256, for instance, maps anything to exactly 256 bits. It is the workhorse of modern cryptography: it backs Digital Signatures, password storage, blockchains, and integrity checks everywhere.

A good hash h = H(m) must satisfy three properties:

  • Pre-image resistance — given a digest h, you cannot find any m with H(m) = h (one-way).
  • Second pre-image resistance — given m, you cannot find a different m' with the same digest.
  • Collision resistance — you cannot find any two inputs that hash to the same value.

The avalanche effect

The property that makes a fingerprint trustworthy is the avalanche effect: change the input by a single bit and about half of the output bits flip, with no visible pattern. The digest of hello and the digest of hellp should look completely unrelated. Measured with Hamming Distance — the number of differing bits — a one-bit input nudge should land you roughly halfway across the entire output space.

Two inputs differing by a single character, run through a small illustrative hash. The output bit-grids share almost nothing — click to re-roll the inputs and watch the avalanche hold near 50% every time. (This toy hash is for demonstration, not real security.)

Notice the digest stays near 50% flipped no matter which inputs you roll. That near-total decorrelation, viewed through Entropy, is what makes a digest behave like a random draw and lets it stand in for the message itself.

Where hashes earn their keep

The avalanche and one-wayness combine into a few indispensable jobs:

  • Integrity. Publish a file's digest; a single altered byte avalanches the hash, exposing tampering instantly.
  • Signatures. Public-key signing is slow, so you sign the short hash of a message rather than the whole thing — the heart of a Digital Signature.
  • Passwords. Store H(\text{password}), never the password. A breach leaks digests, and one-wayness keeps the originals hidden.
  • Commitments and blockchains. Hash-link records so any change to history breaks every fingerprint downstream.

A good cryptographic hash has the avalanche property. What does flipping a single input bit do to the output?

See also

Related topics

  • Digital SignatureSign a message's hash with your private key so anyone can verify, with your public key, that you wrote it and nobody altered it.
  • CryptographyThe art and mathematics of keeping secrets and proving identity — from a Roman shift cipher to the public-key algebra that secures the modern web.
  • EntropyThe average surprise of a random source, measured in bits — and the hard floor on how far it can be compressed.
  • Hamming DistanceThe number of positions in which two equal-length strings differ — the metric behind error correction.
  • RSAPublic-key encryption and signatures built on the difficulty of factoring a product of two large primes.
  • Diffie–HellmanTwo strangers agree on a shared secret over a fully public channel — the paint-mixing trick that launched public-key cryptography.

Referenced by