Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 80 ยท Cryptography Basics

Hash Functions and Integrity

Learn how cryptographic hash functions work, why one changed bit rewrites the whole digest, how to verify files with hashlib, and why MD5 and SHA-1 are broken.

A cryptographic hash function turns any amount of data into a short, fixed-size fingerprint called a digest. Feed it a single word or a four-gigabyte disk image and you get the same number of output bits. Change one character of the input and the digest changes completely. That makes hashes the standard tool for answering the question "is this exactly the data I expected?"

You met the difference between hashing, encoding and encryption in Cryptography in Plain Language. This lesson goes deeper: the properties a good hash must have, the algorithms you should use today, how to check file integrity with Python's hashlib, and why older algorithms such as MD5 and SHA-1 are no longer trusted.

What a hash function promises

A cryptographic hash function H is designed to have three properties:

  • Preimage resistance. Given a digest d, it is infeasible to find any input m with H(m) = d. The function is one-way.
  • Second-preimage resistance. Given an input m1, it is infeasible to find a different input m2 with the same digest.
  • Collision resistance. It is infeasible to find any two different inputs with the same digest.

Two more properties follow from good design. The function is deterministic (the same input always gives the same digest) and fast to compute. A hash has no key and no secret: anyone can compute it. That is why a bare hash proves that data matches something, but not who produced it. For that you need a MAC or a signature, which the next lessons cover.

flowchart LR
    M["Message of any length"] --> H["Hash function<br/>(SHA-256)"]
    H --> D["Digest: always 256 bits"]
    D -. "one-way: cannot go back" .-> M

Any input goes in, a fixed-size fingerprint comes out, and the arrow back does not exist.

The algorithms you should know

Family Digest sizes Status
MD5 128 bits Broken. Collisions are easy to produce.
SHA-1 160 bits Broken. A practical collision was shown in 2017.
SHA-2 (SHA-256, SHA-384, SHA-512) 256 to 512 bits Safe and widely used.
SHA-3 (SHA3-256, SHA3-512) 224 to 512 bits Safe. A different internal design from SHA-2.
BLAKE2 up to 512 bits Safe and very fast.

SHA-3 was not created because SHA-2 was weak. It was standardized as a backup with a completely different construction, so that one future attack could not break both families. For most new work, SHA-256 is a sensible default.

Here is hashlib computing the same message with several algorithms. The input abc is the classic test vector, so you can compare the first line with any reference:

Python SHA-2 and SHA-3 digests

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.

Notice three things. The input is bytes, because hashes work on bytes and not on text (encode strings with .encode("utf-8") first). The length of the hex string is always the same for a given algorithm. And even the empty input has a digest.

The avalanche effect

A good hash behaves like a scrambler: flipping a single input bit should flip about half of the output bits, in an unpredictable pattern. This is the avalanche effect. It is why you cannot "nudge" an input toward a digest you want.

Python Flip one bit, count the damage

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 two digests look unrelated, and the number of differing bits lands close to 128, half of 256. If the number were small, an attacker could learn something about the input from the output, and the hash would be weak.

File integrity checks

The most common daily use of hashing is verifying downloads and backups. A publisher posts the SHA-256 of a file; you hash your copy and compare. A match means the bytes are identical, whether the damage would have come from a flaky network or a malicious mirror.

Large files should be hashed in chunks so they never have to fit in memory. hashlib objects support this with update():

Python Verify data in chunks

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.

Chunked hashing gives the same answer as hashing everything at once, which is why the "good copy" matches. In real code you would open the file with open(path, "rb") and pass it to the same function.

A checksum that is published next to the file on the same server only protects against accidental corruption. An attacker who can replace the file can replace the checksum too. Real integrity needs the hash delivered over a separate trusted channel, or better, a digital signature (see Public-Key Cryptography).

Collisions and the birthday bound

A hash maps infinite inputs onto a finite set of digests, so collisions must exist. Security means that finding one is out of reach. The cost of finding a collision in an n-bit hash is about 2^(n/2) operations, not 2^n, because of the birthday paradox: in a room of 23 people there is already a better than even chance that two share a birthday.

This means a 128-bit hash offers only about 64 bits of collision resistance, and a 256-bit hash about 128 bits. To see the effect without waiting for the heat death of the universe, we can shorten SHA-256 to 24 bits and hunt for a collision:

Python The birthday effect on a 24-bit 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 collision appears after a few thousand messages, not after 16 million. The same square-root shortcut applies to real hashes, which is why designers choose digest sizes with a generous margin.

Why MD5 and SHA-1 are broken

Cryptanalysts found shortcuts that beat the birthday bound. For MD5, collisions can be produced on an ordinary laptop in seconds; researchers have even built two different certificates with the same MD5 digest. For SHA-1, the 2017 "SHAttered" attack produced two different PDF files with identical digests, and later work made chosen-prefix attacks practical.

What does "broken" mean in practice?

  • You must not use MD5 or SHA-1 where an attacker can influence the data being hashed: signatures, certificates, software updates, deduplication of untrusted uploads.
  • Using them for non-security purposes, such as a quick cache key, is not a vulnerability by itself. It still tends to end up copied into places where it matters, so prefer SHA-256 anyway.
  • Never use any plain fast hash to store passwords. Password hashing needs a deliberately slow, salted algorithm. See Password Storage Done Right.

Python lets you declare intent. When a library needs MD5 only for a non-security checksum, hashlib.md5(data, usedforsecurity=False) says so explicitly, and it keeps working on systems that disable MD5 for security use.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the avalanche effect mean for a hash function?

    A good hash scrambles the output so thoroughly that a tiny input change looks like an unrelated digest. Equal inputs always give equal digests, and the size of the digest never depends on the input.
  2. 2. Why is a SHA-256 checksum posted beside a download on the same website weak protection against a malicious attacker?

    A hash has no secret. If the attacker controls the server, they can publish a matching hash for their modified file. You need a separate trusted channel or a digital signature.
  3. 3. Roughly how much collision resistance does a 256-bit hash offer because of the birthday bound?

    Collisions can be found in about the square root of the search space, so an n-bit hash gives about n/2 bits of collision resistance.
  4. 4. Which algorithm is NOT suitable for signing documents or certificates today?

    Practical collisions exist for SHA-1, so an attacker could craft two documents with the same digest. SHA-2 and SHA-3 have no known practical attacks.

Summary

  • A cryptographic hash maps any input to a fixed-size digest and should be one-way, second-preimage resistant and collision resistant.
  • Use SHA-256, SHA-512, SHA-3 or BLAKE2. Treat MD5 and SHA-1 as broken for anything an attacker can influence.
  • The avalanche effect makes a one-bit change produce a digest that looks completely different.
  • Hash large files in chunks with update(), and publish the expected digest through a trusted channel.
  • An n-bit hash gives about n/2 bits of collision resistance because of the birthday bound.
  • A bare hash has no key, so it detects change but cannot prove who made the data.

Next: HMAC and Message Authentication, where a secret key turns a hash into proof of origin.