Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 40 ยท Hashing

Cryptographic Hash Functions

Understand what makes a hash function cryptographic: preimage and collision resistance, the avalanche effect, and how to use hashlib with SHA-256, SHA-3 and BLAKE2.

A cryptographic hash function takes input of any length and produces a short, fixed-size output called a digest (or hash). SHA-256, for example, turns a single letter or a whole movie into exactly 32 bytes. The same input always gives the same digest, a tiny change in the input gives a completely different digest, and, crucially, nobody can work backwards from a digest to an input.

Hashes are the Swiss army knife of cryptography. They fingerprint files, build message authentication codes, stretch passwords, link blockchain blocks and sit inside digital signatures. Before using them you need to know exactly which promises a hash makes. Do not confuse them with the other two tools from encoding, hashing and encryption: a hash has no key and cannot be reversed.

Using hashlib

Python's hashlib module offers the standard algorithms. You feed it bytes (not text; see bytes and bytearray) and ask for the digest, as hex or raw bytes.

Python Hashing with hashlib

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The incremental interface (update) matters for large files, which you can hash chunk by chunk without loading them into memory. The two cafรฉ digests differ because the byte sequences differ: always state your encoding.

The three security properties

Three properties define what "cryptographic" means. Let H be the hash and n the digest size in bits.

  1. Preimage resistance (one-wayness). Given a digest y, it is infeasible to find any input x with H(x) = y. The best generic attack is to try inputs, which takes about 2n evaluations.
  2. Second-preimage resistance. Given a specific input x1, it is infeasible to find a different x2 with the same digest. Again about 2n work.
  3. Collision resistance. It is infeasible to find any two different inputs with the same digest. Because of the birthday effect, the generic cost is only about 2n/2, which is why SHA-256 is said to give 128-bit collision security and 256-bit preimage security.
flowchart TD
    A["Preimage<br/>given y, find x"] --> C["Cost about 2^n"]
    B["Second preimage<br/>given x1, find x2"] --> C
    D["Collision<br/>find any x1, x2"] --> E["Cost about 2^(n/2)"]

Collisions are easier to find than preimages because you may pick both inputs freely.

Every hash has collisions, since infinitely many inputs map to a finite number of digests. The claim is only that finding one is computationally out of reach. When someone finds a faster way than the generic bound, the function is called broken, which happened to MD5 and SHA-1 (see hash attacks).

The avalanche effect

A good hash behaves like a random function: change one bit of the input and about half of the output bits flip, in an unpredictable pattern. This is called the avalanche effect. It means similar inputs leave no similarity in their digests, so a digest reveals nothing about how close a guess is.

Python Flip one bit, change half the digest

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The average lands very close to 128, which is exactly what a random function would give. A hash that flipped only a few bits would let an attacker walk toward a target digest step by step.

Preimage search by brute force

How strong is a given digest size? You can feel it by attacking a deliberately truncated hash. If we keep only the first 16 bits of SHA-256, a preimage should take about 216 = 65,536 guesses. Keeping 32 bits would need about four billion. Each extra bit doubles the work.

Python Brute-forcing a truncated hash

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The input found is not secret message; it is merely a second input with the same truncated digest. For a full 256-bit digest the same search would need more attempts than there are atoms in the observable universe, so preimage resistance holds.

The main families

  • SHA-2 (SHA-256, SHA-512): the workhorse, designed by the NSA and standardized by NIST. No practical attacks are known. SHA-512 is often faster on 64-bit CPUs. Both are built with the Merkle-Damgard construction, which is why they suffer from length extension (see hash attacks).
  • SHA-3 (Keccak): a different design, a sponge construction chosen in a public competition. It is not vulnerable to length extension and is a good alternative if you want diversity from SHA-2.
  • BLAKE2 (blake2b, blake2s): very fast, with a built-in keyed mode and personalization options. BLAKE3 is its newer relative.
  • MD5 and SHA-1: broken for collisions. Do not use them for security. They still appear as non-security checksums in old systems.

A hash is also the wrong tool for storing passwords. Plain SHA-256 is far too fast, so attackers can test billions of guesses per second. Password storage needs a deliberately slow, salted function, covered in password hashing.

Python Digest sizes and the keyed BLAKE2 mode

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Note that the 10-byte SHAKE output is a prefix of the 20-byte one: you can ask for as many output bytes as you need. For authentication in real programs, though, use the hmac module covered in MACs and HMAC.

Inside MD5 and the Merkle-Damgard family

MD5 (Ronald Rivest, 1991) shows the structure shared by MD5, SHA-1 and SHA-2. A message of any length is processed like this:

  1. Pad the message: append a single 1 bit, then 0 bits until the length is 448 mod 512, then the original length as a 64-bit number. The padded message is a whole number of 512-bit (64-byte) blocks. This is why the message length is encoded: it makes two different messages unable to pad to the same thing.
  2. Initialize the chaining state. MD5 keeps four 32-bit words (A, B, C, D), 128 bits in total, starting from fixed constants.
  3. Compress each block: a compression function runs 64 steps (four rounds of 16) of additions, bitwise operations and rotations that mix the block into the state. The output state of one block is the input state of the next.
  4. The final state is the digest.

The next program reproduces the padding step and checks the invariants with hashlib.

Python MD5 padding and block count

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Real attacks on this family are the subject of hash attacks. To summarize the comparison:

Algorithm Digest Block Status
MD5 128 bits 512 bits Broken: collisions in seconds, chosen-prefix collisions used to forge certificates. Fine only as a non-security checksum
SHA-1 160 bits 512 bits Broken: practical collision (SHAttered, 2017). Retired for signatures
SHA-256 / SHA-512 256 / 512 bits 512 / 1024 bits Secure; Merkle-Damgard, so use HMAC (not H(key + msg)) for keyed hashing
SHA-3 224 to 512 bits sponge Secure; different design, immune to length extension
RIPEMD-160 160 bits 512 bits Still unbroken, used in Bitcoin addresses (after SHA-256)
Whirlpool 512 bits 512 bits Built from an AES-like block cipher; standardized by ISO but little used

MD5 is irreversible in the sense that a digest does not contain the message, but "irreversible" does not mean "safe": short or guessable inputs are recovered by searching, which is why password storage needs slow salted hashing.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which property says that, given a digest y, you cannot find any input that hashes to y?

    Preimage resistance (one-wayness) is the inability to invert the hash. Collision resistance is about finding any two inputs with the same digest.
  2. 2. Why does a hash with an n-bit digest offer only about n/2 bits of collision resistance?

    When you are free to choose both colliding inputs, the birthday paradox lets you find a pair after roughly the square root of the number of possible digests.
  3. 3. About how many of SHA-256's 256 output bits change when one input bit is flipped?

    Avalanche: each output bit flips with probability about one half, so on average 128 bits change.
  4. 4. Which of these is NOT suitable for security-sensitive collision resistance today?

    MD5 has practical collision attacks. SHA-256, SHA3-256 and BLAKE2b have none known.

Summary

  • A cryptographic hash maps any input to a fixed-size digest, deterministically and without a key.
  • It must resist preimage (about 2^n work), second-preimage (about 2^n) and collision (about 2^(n/2)) attacks.
  • The avalanche effect makes a one-bit input change flip about half the output bits.
  • Use SHA-256, SHA-3 or BLAKE2 from hashlib; avoid MD5 and SHA-1 for security; do not use fast hashes for passwords.
  • Hash bytes, not text, and fix the encoding.

Next: Using Hashes: Integrity, Fingerprints and Commitments.