SyntaxPilot
Courses/Cybersecurity Fundamentals/Lesson 13
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Cybersecurity Fundamentals · Lesson 13 of 90

Hash functions

cryptographic hashone-way propertypreimage resistancesecond-preimage resistancecollision resistancebirthday paradoxavalanche effectMD5 and SHA-1 (broken)SHA-2 (SHA-256/512)SHA-3BLAKE2/BLAKE3length-extension (concept)checksum (CRC) vs cryptographic hashfile integrity verification

These are the notes for Cybersecurity Fundamentals (defensive), episode 13. For three episodes we used SHA-256 as a magic fingerprint. Today you open the box. The question is: how can a short value prove that a file of any size hasn't been changed? You'll invent each idea from a real-life problem: the hash function and its digest, the difference between a checksum (CRC) and a cryptographic hash, collisions and the birthday paradox, the three promises (preimage resistance or the one-way property, second-preimage resistance, collision resistance), the avalanche effect, why MD5 and SHA-1 are broken, the modern choices (SHA-2, SHA-3, BLAKE2/BLAKE3), length extension (as a concept), file integrity verification, and the Merkle tree. Every term is explained the first time it appears, and the Glossary at the end defines them all again.

Riya, Aman and the payments are made up. Every code sample runs as-is with Python 3.13 and only the standard library; outputs are real, copied from actual runs. A few demos use randomness with a fixed seed (a starting value that makes "random" numbers repeat exactly), so you will get the same output.

The problems you'll solve

Problem Idea it teaches
Is my 2 GB download the real file? Hash function, digest, deterministic
A checksum gets forged in under a second Checksum (CRC-32) vs cryptographic hash, collision
Why was forging so fast? The birthday paradox: collisions after about √N tries
What must a safe hash promise? Preimage, second-preimage and collision resistance; avalanche effect
A hashed PIN falls anyway One-way is not the same as unguessable
Famous hashes that broke MD5, SHA-1 (SHAttered), SHA-2, SHA-3, BLAKE2, BLAKE3
A do-it-yourself MAC Length-extension attack (concept), use HMAC
Checking a download, and one block of a huge file File integrity verification, Merkle tree

The one-line lesson: a cryptographic hash is a fingerprint built to survive attackers, not just accidents.

Problem 1: is it the real file?

You download a 2 GB Linux installer from a mirror: a copy server, often run by volunteers, that shares the load of a popular download. Was it changed on the way? A failing disk can flip a byte; an attacker who controls the mirror can hide malware (harmful software, episode 5) inside. You can't compare it byte by byte with the original, because the original is exactly what you don't have.

The obvious check is the file size.

Demo 1: same size, different file

a = b"PAY RAVI RS 500"      # the real file
b = b"PAY RAVI RS 900"      # one byte changed

print("same size?", len(a) == len(b))
print("same file?", a == b)

Output:

same size? True
same file? False
  • b"..." is a bytes literal: raw bytes rather than text. Hash functions work on bytes.
  • len() gives the size in bytes. The sizes match, the contents don't. Size tells you almost nothing.

The idea: a fingerprint for data

People Data
A fingerprint is small but unique to one person A hash value, or digest: a short, fixed-size number computed from data of any size
The same finger always gives the same print A hash function is deterministic: the same input always gives the same output
You can't rebuild the person from the print You shouldn't be able to rebuild the data from its hash (one-way)

A hash function takes input of any length and returns a fixed-length output. The website publishes the hash of the real file; you hash your download and compare two short strings. Hashes are usually shown in hexadecimal (hex): base 16, digits 0-9 and a-f, so each hex character is 4 bits (a bit is a single 0 or 1). A 256-bit hash is 64 hex characters.

Problem 2: a checksum gets forged

A checksum is a small value computed from data to catch errors. The classic one is CRC-32, a cyclic redundancy check with a 32-bit output. Its most common form is used by Ethernet networks, gzip, ZIP files and PNG images. CRC is excellent at catching accidents, like noise on a cable or a bad disk sector. But can a forger make two different messages with the same CRC?

Demo 2: a CRC-32 collision in about 80,000 tries

import zlib, random
random.seed(13)

print(hex(zlib.crc32(b"PAY RAVI RS 500")))
print(hex(zlib.crc32(b"PAY RAVI RS 501")))  # typo: caught

seen = {}                    # forger: find two messages
for tries in range(1, 1_000_000):   # with the same CRC-32
    n = random.randrange(10**9)
    msg = b"PAY RAVI RS %d" % n
    c = zlib.crc32(msg)
    if c in seen and seen[c] != msg:
        print("collision after", tries, "tries:")
        print(seen[c], msg, hex(c))
        break
    seen[c] = msg

Output:

0xffa75513
0x88a06585
collision after 79680 tries:
b'PAY RAVI RS 587783812' b'PAY RAVI RS 493369603' 0xf257d040
  • zlib.crc32 computes CRC-32; hex() shows it in hexadecimal.
  • A one-digit typo gives a totally different CRC, so accidents are caught.
  • The forger keeps a dictionary (seen) from each CRC to the message that produced it. When a new message lands on a CRC already in the dictionary, two different messages share one value.
  • That is a collision: two different inputs with the same hash. It took a fraction of a second.

There are about 4.3 billion possible CRC-32 values (2³²). Why did a collision come after only 80,000 tries?

Problem 3: the birthday paradox

A class has 23 students. What's the chance that two share a birthday? Most people guess around 5%. The trick is to count pairs, not people: 23 students make 23 × 22 ÷ 2 = 253 pairs, and every pair is a chance for a match.

Demo 3: the maths

from math import prod

def p_shared(people, days=365):
    # chance that at least two share a birthday
    p_none = prod((days - i) / days for i in range(people))
    return 1 - p_none

for n in (10, 23, 50, 70):
    print(n, "people:", round(p_shared(n) * 100, 1), "%")

Output:

10 people: 11.7 %
23 people: 50.7 %
50 people: 97.0 %
70 people: 99.9 %
  • The chance that nobody shares is 365/365 × 364/365 × 363/365 × ... (each new person must avoid all earlier birthdays). prod multiplies them.
  • One minus that is the chance of at least one match.

This is the birthday paradox: with N possible values, you expect a first collision after only about √N tries (more precisely about 1.25 √N). For CRC-32, √(2³²) = 2¹⁶ ≈ 65,000, which matches the 80,000 tries above.

Hash size Collision after about Possible?
32 bits (CRC-32) 2¹⁶ ≈ 65 thousand Instantly
128 bits (MD5) 2⁶⁴ by brute force (far less with MD5's flaws) Yes, and MD5 is broken anyway
160 bits (SHA-1) 2⁸⁰ by brute force (SHAttered needed ~2⁶³) Done in 2017
256 bits (SHA-256) 2¹²⁸ No: far beyond all computers on Earth

The rule: an n-bit hash gives only n/2 bits of collision resistance. That's why modern hashes are at least 256 bits.

Problem 4: what a safe hash promises

A cryptographic hash function is a hash built to survive attackers. It keeps three promises:

Promise Plain words Attacker's goal it stops
Preimage resistance (the one-way property) Given a hash, you can't find any input that produces it Recover data from its hash
Second-preimage resistance Given one specific input, you can't find a different input with the same hash Swap a real file for a look-alike
Collision resistance You can't find any two different inputs with the same hash, even ones you choose freely Make two documents, sign one, swap in the other

Collision resistance is the hardest to keep, because of the birthday paradox. CRC keeps none of the three: it's linear maths designed for accidents. That's the difference between a checksum and a cryptographic hash.

Demo 4a: the beginner's error

import hashlib

print(hashlib.sha256("PAY RAVI RS 500").hexdigest())

Output:

Traceback (most recent call last):
  File "main.py", line 3, in <module>
    print(hashlib.sha256("PAY RAVI RS 500").hexdigest())
          ~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^
TypeError: Strings must be encoded before hashing

A hash works on bytes, not text (str). Use b"PAY RAVI RS 500" or "PAY RAVI RS 500".encode().

Demo 4b: the avalanche effect

import hashlib

a = hashlib.sha256(b"PAY RAVI RS 500").hexdigest()
b = hashlib.sha256(b"PAY RAVI RS 501").hexdigest()
print("500:", a[:32], "...")
print("501:", b[:32], "...")

bits = bin(int(a, 16) ^ int(b, 16)).count("1")
print(bits, "of 256 bits changed")

Output:

500: c9e7a266cbcccdb53704099d0183a795 ...
501: 5c473188c87609f7ca1c1d458089d2d4 ...
110 of 256 bits changed
  • .hexdigest() returns the hash as hex text; int(a, 16) turns it into a number.
  • ^ is XOR (1 where two bits differ), so counting the 1s counts the differing bits.
  • One digit changed and 110 of 256 bits flipped, close to half. This is the avalanche effect: a tiny change in the input changes about half the output bits, so similar inputs give no hint of being similar.

Demo 5: one-way is not unguessable

A bank stores SHA-256 of each 4-digit ATM PIN and the table leaks.

import hashlib

# leaked: SHA-256 of a 4-digit ATM PIN
leak = hashlib.sha256(b"4821").hexdigest()

for pin in range(10_000):          # try every PIN
    guess = b"%04d" % pin
    if hashlib.sha256(guess).hexdigest() == leak:
        print("PIN found:", guess.decode())
        print("tries:", pin + 1)
        break

Output:

PIN found: 4821
tries: 4822
  • b"%04d" % pin formats the number with leading zeros (7 becomes 0007).
  • The attacker never "reverses" SHA-256. He hashes every possible input and compares. With only 10,000 inputs, that's milliseconds.
  • One-way means you can't run the maths backwards; it doesn't stop guessing. When inputs are few or predictable (PINs, passwords), guessing wins. Episode 14 fixes this for passwords.

Problem 5: the hashes that broke

Hash Output Status What happened
MD5 128 bits Broken The first full MD5 collision was demonstrated in August 2004; a colliding X.509 certificate followed within months
SHA-1 160 bits Broken Feb 2017, SHAttered (CWI Amsterdam + Google): two different PDF files with the same SHA-1, after about 9,223,372,036,854,775,808 (≈9.2 quintillion) SHA-1 computations: 6,500 CPU-years plus 110 GPU-years
SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512) 224-512 bits Safe, today's default Named after the output size
SHA-3 (SHA3-224/256/384/512, plus SHAKE128/256) 224-512 bits Safe A completely different design (Keccak, winner of NIST's SHA-3 competition), standardised in FIPS 202 on 4 Aug 2015
BLAKE2 (BLAKE2b, BLAKE2s) up to 512 bits Safe Fast modern hash, in Python's hashlib
BLAKE3 256 bits (extendable) Safe Based on BLAKE2; its authors say it's "much faster than MD5, SHA-1, SHA-2, SHA-3, and BLAKE2"; a Merkle tree inside lets it use many cores

In December 2022 NIST (the US National Institute of Standards and Technology, which publishes security standards) said SHA-1 "has reached the end of its useful life", recommended SHA-2 or SHA-3, and set a deadline to phase it out by 31 December 2030. SHA-1 had been a federal standard since 1995. Git, which names every stored object by the hash of its content, chose SHA-256 as SHA-1's successor in 2018 after SHAttered.

Never use MD5 or SHA-1 for security. (Python lets you use MD5 for non-security tasks like cache keys with hashlib.md5(data, usedforsecurity=False).)

Demo 6: the family in hashlib

import hashlib

msg = b"meet at the chai stall"
for name in ("md5", "sha1", "sha256", "sha512",
             "sha3_256", "blake2b"):
    h = hashlib.new(name, msg).hexdigest()
    print(f"{name:9}{len(h) * 4:4} bits  {h[:24]}...")

Output:

md5       128 bits  87e81a384e44b2b1961461cc...
sha1      160 bits  e1f7575a6140d90b6b742ab2...
sha256    256 bits  e9063870d247286fa5ba84bd...
sha512    512 bits  c6d901712b8be144b8318b50...
sha3_256  256 bits  de38758e51512dd7226ef83c...
blake2b   512 bits  fae918639998a6504e9a54be...
  • hashlib.new(name, data) picks a hash by name. Each hex character is 4 bits, so len(h) * 4 is the output size.
  • A wrong name fails loudly: hashlib.new("sha3") raises ValueError: unsupported hash type sha3 (the right name is sha3_256).

Problem 6: length extension (concept only)

A developer builds a do-it-yourself MAC: tag = sha256(secret + message). Without the secret, nobody can make the tag... right?

  1. SHA-256 (like MD5, SHA-1 and SHA-512) processes data block by block, carrying an internal state from block to block.
  2. The final hash is that internal state at the end.
  3. So an attacker who knows tag and the message length can continue hashing from that state and append extra data, like &amount=900, producing a valid tag for secret + message + padding + "&amount=900", without ever knowing the secret.

This is a length-extension attack. The fix is HMAC (episode 12), which hashes twice exactly to block this. SHA-3 and BLAKE2 aren't vulnerable to length extension (and BLAKE2 has a built-in keyed mode), but HMAC-SHA256 is the standard answer whenever a key is involved.

Problem 7: verifying a download

File integrity verification means comparing a file's hash with a trusted published hash.

Demo 7: one flipped bit in 232,000

import hashlib

def sha256_file(path):
    with open(path, "rb") as f:
        return hashlib.file_digest(f, "sha256").hexdigest()

iso = b"pretend this is 2 GB of Linux" * 1000
open("real.iso", "wb").write(iso)
published = sha256_file("real.iso")   # shown on the website

bad = bytearray(iso); bad[5000] ^= 1  # a mirror flips 1 bit
open("download.iso", "wb").write(bad)

mine = sha256_file("download.iso")
print("published:", published[:16])
print("mine:     ", mine[:16])
print("OK" if mine == published else "DO NOT INSTALL")

Output:

published: 792e13e6faff6104
mine:      becded8510438295
DO NOT INSTALL
  • hashlib.file_digest (Python 3.11+) reads the file in chunks, so even a 2 GB file never has to fit in memory.
  • bytearray is a changeable copy of the bytes; ^= 1 flips the lowest bit of byte 5,000.
  • One bit out of 29,000 bytes (232,000 bits) changed, and the hashes are unrelated.
  • On Linux the same check is sha256sum download.iso; many projects publish a SHA256SUMS file.

The catch: the published hash must come from somewhere the attacker can't edit, such as the official HTTPS website. If the attacker controls both the file and the page showing its hash, he just publishes his own hash. Proving who published a hash needs digital signatures (episode 16).

Problem 8: Merkle trees

A huge file or a log with millions of entries arrives in blocks. Re-hashing everything to check one block is slow. Think of a school: each class teacher signs a mark sheet, section heads sign over pairs of teachers' signatures, and the principal signs once for the whole school.

School Merkle tree
Each class's signed mark sheet Leaf hash: the hash of one data block
Section heads sign two sheets Node hash: the hash of its two children's hashes
The principal's single signature Merkle root: one hash covering everything

A Merkle tree is a tree of hashes. Change any block, and its leaf changes, then its parent, all the way up to the root.

Demo 8: a 4-block Merkle tree

from hashlib import sha256

def leaf(d):   return sha256(b"\x00" + d).digest()
def node(l, r): return sha256(b"\x01" + l + r).digest()

def root(blocks):
    a, b, c, d = map(leaf, blocks)
    return node(node(a, b), node(c, d)).hex()[:16]

blocks = [b"block 1", b"block 2", b"block 3", b"block 4"]
print("root:", root(blocks))
blocks[2] = b"block 3 (changed)"
print("root:", root(blocks))

Output:

root: 75b3467d94740e94
root: 2634a358cd2148d6
  • .digest() returns raw bytes (32 for SHA-256); .hex() shows them as hex.
  • The \x00 prefix for leaves and \x01 for nodes is domain separation: it stops an attacker from presenting an inner node as if it were a leaf. This exact design comes from RFC 6962, Certificate Transparency (June 2013), the public logs of HTTPS certificates (episode 16), which use a binary Merkle tree with SHA-256.
  • To prove one block belongs to the tree you only need the sibling hashes on the path to the root (a Merkle proof): about 20 hashes for a million blocks, since 2²⁰ ≈ 1 million.
                root
              /      \
        node(a,b)   node(c,d)
         /   \        /   \
        a     b      c     d        ← leaf hashes
     block1 block2 block3 block4    ← data

The whole chain

Step Problem Invention
1 Same size, different file Hash function, digest
2 CRC forged in 80,000 tries Cryptographic hash vs checksum
3 Why so fast? Birthday paradox: √N
4 What must a hash promise? Preimage, second preimage, collision resistance; avalanche
5 A hashed PIN falls One-way ≠ unguessable (next episode)
6 MD5 and SHA-1 broke SHA-2, SHA-3, BLAKE2/3
7 sha256(secret + msg) Length extension → HMAC
8 Check a download / one block File integrity verification, Merkle tree

Common mistakes (and what they print)

Mistake What you see Why Fix
hashlib.sha256("text") TypeError: Strings must be encoded before hashing Hashes take bytes b"text" or "text".encode()
hashlib.new("sha3") ValueError: unsupported hash type sha3 Wrong algorithm name "sha3_256"
zlib.crc32 to detect tampering collision after 79680 tries CRC is for accidents SHA-256
MD5 / SHA-1 for security SHAttered: two PDFs, one SHA-1 Collisions are practical SHA-256, SHA-3, BLAKE2
sha256(secret + msg) as a MAC Length-extension forgery The hash is the internal state hmac.new(key, msg, hashlib.sha256)
Hashing small inputs (PINs) and calling it safe PIN found: 4821 One-way doesn't stop guessing Slow, salted password hashing (episode 14)
Trusting a hash shown on the same mirror as the file Attacker publishes his own hash Hash has no author Get the hash over HTTPS, or check a signature

Mini project: verify a set of downloads

Build a small tool that checks files against a SHA256SUMS manifest (a list of hash filename lines), and reports OK, MISMATCH or MISSING.

import hashlib, os

def sha256_file(path):
    with open(path, "rb") as f:
        return hashlib.file_digest(f, "sha256").hexdigest()

# 1. The "publisher" makes three files and a manifest of their hashes
files = {"notes.txt": b"hash functions are fingerprints\n",
         "photo.png": bytes(range(256)) * 40,
         "setup.iso": b"pretend installer" * 5000}
for name, data in files.items():
    open(name, "wb").write(data)
with open("SHA256SUMS", "w") as m:
    for name in files:
        m.write(f"{sha256_file(name)}  {name}\n")

# 2. Something goes wrong on the way
with open("photo.png", "r+b") as f:     # one byte changed
    f.seek(100); f.write(b"\x00")
os.remove("notes.txt")                  # one file missing

# 3. The user verifies every file against the manifest
def verify(manifest):
    bad = 0
    for line in open(manifest):
        expected, name = line.split()
        if not os.path.exists(name):
            print(f"{name:10} MISSING"); bad += 1
        elif sha256_file(name) != expected:
            print(f"{name:10} MISMATCH (do not use)"); bad += 1
        else:
            print(f"{name:10} OK")
    print("all good" if bad == 0 else f"{bad} problem(s) found")

verify("SHA256SUMS")

Output:

notes.txt  MISSING
photo.png  MISMATCH (do not use)
setup.iso  OK
2 problem(s) found
  • "r+b" opens a file for reading and writing in binary; seek(100) moves to byte 100.
  • The manifest format is the same one sha256sum -c SHA256SUMS checks on Linux.
  • Remember the catch: in real life the manifest itself must be trusted (fetched over HTTPS, or signed).

Practice

1. Homework: birthdays on another planet. Rerun the birthday maths with 1,000 possible "days". How many people give a 50% chance?

Solution
from math import prod

def p_shared(people, days):
    return 1 - prod((days - i) / days for i in range(people))

for n in (23, 38, 50):
    print(n, "people, 1000 days:", round(p_shared(n, 1000) * 100, 1), "%")

Output:

23 people, 1000 days: 22.5 %
38 people, 1000 days: 50.9 %
50 people, 1000 days: 71.2 %

About 38 people, and √1000 ≈ 32: the square-root rule again.

2. Homework: an 8-block Merkle tree. Generalise Demo 8 to any power-of-two number of blocks.

Solution
from hashlib import sha256

def leaf(d):    return sha256(b"\x00" + d).digest()
def node(l, r): return sha256(b"\x01" + l + r).digest()

def merkle_root(blocks):
    level = [leaf(b) for b in blocks]
    while len(level) > 1:
        level = [node(level[i], level[i + 1])
                 for i in range(0, len(level), 2)]
    return level[0].hex()[:16]

blocks = [b"block %d" % i for i in range(1, 9)]
print("8-block root:", merkle_root(blocks))
blocks[6] = b"block 7 (changed)"
print("after change:", merkle_root(blocks))

Output:

8-block root: ce0999cff2396b16
after change: b2ca5b4d82a7372d

Each loop replaces a level with the level above it, halving its size until only the root is left.

3. See the birthday bound on a cut-down SHA-256. Keep only the first 24 bits (3 bytes) of SHA-256 and search for a collision.

Solution
import hashlib, random
random.seed(1)

def h24(msg):                    # SHA-256 cut down to 24 bits
    return hashlib.sha256(msg).digest()[:3]

seen = {}
for tries in range(1, 10_000_000):
    msg = b"msg %d" % random.randrange(10**12)
    d = h24(msg)
    if d in seen and seen[d] != msg:
        print("24-bit collision after", tries, "tries")
        print("sqrt(2**24) =", int((2**24) ** 0.5))
        break
    seen[d] = msg

Output:

24-bit collision after 13865 tries
sqrt(2**24) = 4096

The same order of magnitude as √N (a single run varies a lot; the average is about 1.25 × 4096 ≈ 5,100). Even SHA-256 collides fast if you truncate it: strength comes from the full 256 bits.

4. A Merkle proof. Prove that block 3 is in the 4-block tree using only two sibling hashes.

Solution
from hashlib import sha256

def leaf(d):    return sha256(b"\x00" + d).digest()
def node(l, r): return sha256(b"\x01" + l + r).digest()

blocks = [b"block 1", b"block 2", b"block 3", b"block 4"]
a, b, c, d = map(leaf, blocks)
root = node(node(a, b), node(c, d))

# proof that "block 3" is in the tree: its sibling d, then node(a, b)
proof = [("right", d), ("left", node(a, b))]

def verify(block, proof, root):
    h = leaf(block)
    for side, sibling in proof:
        h = node(h, sibling) if side == "right" else node(sibling, h)
    return h == root

print("block 3 in tree?", verify(b"block 3", proof, root))
print("fake block in tree?", verify(b"block X", proof, root))

Output:

block 3 in tree? True
fake block in tree? False

The verifier needs only the root (trusted) and two hashes, not blocks 1, 2 and 4.

5. Avalanche in three hashes. Count the changed bits for SHA-256, SHA3-256 and BLAKE2s when 500 becomes 501.

Solution
import hashlib

for name in ("sha256", "sha3_256", "blake2s"):
    a = hashlib.new(name, b"PAY RAVI RS 500").hexdigest()
    b = hashlib.new(name, b"PAY RAVI RS 501").hexdigest()
    bits = bin(int(a, 16) ^ int(b, 16)).count("1")
    print(f"{name:9} {bits} of {len(a) * 4} bits changed")

Output:

sha256    110 of 256 bits changed
sha3_256  130 of 256 bits changed
blake2s   139 of 256 bits changed

All close to half (128), as a good hash should be.

6. Which property? (a) An attacker wants any two contracts with the same hash. (b) An attacker has your file and wants another with its hash. (c) An attacker has only a hash and wants the data.

Solution

(a) Collision resistance. (b) Second-preimage resistance. (c) Preimage resistance (one-way). Note (a) is the easiest attack, thanks to the birthday paradox.

7. Checksum or cryptographic hash? (a) Detect cable noise in a network frame. (b) Prove a downloaded installer is the one the vendor published. (c) A quick cache key for non-secret data.

Solution

(a) A checksum like CRC-32 is perfect: fast, and noise is accidental. (b) A cryptographic hash (SHA-256) from a trusted source, or better, a signature. (c) Either; even MD5 with usedforsecurity=False is fine because no attacker is involved.

Quick quiz

The website publishes SHA-256(real.iso). An attacker wants a different file with the same hash as real.iso. Which property stops him?

A. Collision resistance B. Second-preimage resistance C. The avalanche effect D. Determinism

Answer

B. The real file is fixed and given; finding another file with its hash is a second preimage. Collision resistance is about any two files the attacker picks freely, which is easier for him thanks to the birthday paradox.

Interview questions

  1. What is a cryptographic hash function? A deterministic function mapping any input to a fixed-size digest that is preimage-, second-preimage- and collision-resistant, with a strong avalanche effect.
  2. Checksum vs cryptographic hash? A checksum (CRC) catches accidental errors cheaply but is easy to forge; a cryptographic hash is designed so attackers can't find inputs matching a given hash or each other.
  3. Explain the birthday paradox and its effect on hash size. With N outputs, a collision is expected after about √N inputs, so an n-bit hash has only n/2 bits of collision resistance. SHA-256 gives 128-bit collision resistance.
  4. Why are MD5 and SHA-1 considered broken? Practical collisions exist: MD5 since 2004, SHA-1 since SHAttered (Google and CWI, 2017). NIST retired SHA-1, with a phase-out by 2030.
  5. What's the difference between SHA-2 and SHA-3? Different internal designs: SHA-2 is a Merkle-Damgård construction (block by block with a carried state), SHA-3 is Keccak, a sponge construction. SHA-3 is a backup in case SHA-2 is ever broken, and isn't vulnerable to length extension.
  6. What is a length-extension attack and how do you avoid it? With Merkle-Damgård hashes (MD5, SHA-1, SHA-256), an attacker who knows H(secret‖m) can compute H(secret‖m‖padding‖extra) without the secret. Use HMAC.
  7. What is a Merkle tree and where is it used? A tree where leaves are block hashes and each parent hashes its children; the root commits to all data and a proof of membership needs only log₂(n) hashes. Used in Certificate Transparency logs, Git-like content-addressed systems and BLAKE3's internal structure.
  8. Is hashing a password with SHA-256 enough? No: SHA-256 is fast and unsalted, so guessing is cheap. Use a slow, salted password hash like Argon2id (episode 14).

Glossary

Term Meaning in plain words Example
Hash function A function that turns data of any size into a fixed-size value hashlib.sha256(data)
Hash value / digest The fixed-size output of a hash function, the data's "fingerprint" 64 hex characters for SHA-256
Deterministic Same input always gives the same output Hash a file twice: identical digests
Bytes Raw 8-bit values, what files and hashes work on (b"..." in Python) b"PAY RAVI RS 500"
Bit A single 0 or 1; 8 bits make a byte SHA-256 outputs 256 bits
Hexadecimal (hex) Base-16 numbers written with 0-9 and a-f; one hex digit = 4 bits 0xffa75513
Mirror A copy server that hosts the same downloads to share the load A volunteer Linux mirror
Checksum A small value computed from data to detect accidental errors A CRC on a network frame
CRC-32 Cyclic redundancy check, 32 bits; fast, linear, used by Ethernet, ZIP, PNG zlib.crc32(data)
Collision Two different inputs with the same hash Two payment messages, one CRC
Birthday paradox With N possible values, a repeat is expected after about √N picks 23 people: 50.7% share a birthday
Cryptographic hash function A hash designed to resist attackers, not just accidents SHA-256, SHA-3, BLAKE2
Preimage resistance / one-way property Given a hash, you can't find an input that produces it Can't recover a file from its SHA-256
Second-preimage resistance Given one input, you can't find a different input with the same hash Can't make a fake installer matching the real hash
Collision resistance You can't find any two inputs with the same hash No two contracts with one SHA-256
Avalanche effect A tiny input change flips about half the output bits 500 → 501 flips 110 of 256 bits
XOR Bit operation: 1 where two bits differ (^ in Python) Counting differing bits
Brute force Trying every possible input All 10,000 PINs
MD5 Old 128-bit hash; collisions since 2004; broken Never for security
SHA-1 160-bit hash from 1995; broken by SHAttered (2017); NIST phase-out by 2030 Git's original object names
SHAttered The 2017 CWI/Google attack: two PDFs with the same SHA-1 ~9.2 quintillion SHA-1 computations
NIST US National Institute of Standards and Technology, publishes crypto standards FIPS 202 (SHA-3)
SHA-2 Hash family: SHA-224, SHA-256, SHA-384, SHA-512 Today's default, SHA-256
SHA-256 / SHA-512 SHA-2 members with 256- and 512-bit outputs hashlib.sha512(data)
SHA-3 NIST hash standard (FIPS 202, 2015) based on Keccak hashlib.sha3_256(data)
Keccak The design that won NIST's SHA-3 competition Inside SHA-3
BLAKE2 Fast modern hash family (BLAKE2b, BLAKE2s) hashlib.blake2b(data)
BLAKE3 Successor of BLAKE2, very fast, Merkle tree inside The blake3 package
Internal state The running value a hash carries from block to block What length extension continues from
Length-extension attack Extending H(secret + msg) into a valid hash of a longer message without the secret Appending &amount=900
HMAC Hash-based MAC that hashes twice; immune to length extension (episode 12) hmac.new(key, msg, sha256)
File integrity verification Comparing a file's hash with a trusted published hash sha256sum -c SHA256SUMS
Merkle tree A tree of hashes: leaves hash blocks, parents hash children Certificate Transparency logs
Leaf hash / node hash Hash of one block / hash of two child hashes leaf(d), node(l, r)
Merkle root The single top hash covering all blocks 75b3467d94740e94
Merkle proof The sibling hashes needed to prove one block is in the tree ~20 hashes for 1 million blocks
Domain separation Different prefixes for different uses so values can't be confused \x00 for leaves, \x01 for nodes
Certificate Transparency Public append-only logs of HTTPS certificates (RFC 6962), built as Merkle trees Episode 16
Seed A starting value that makes pseudo-random numbers repeat exactly random.seed(13)

Summary

  • A hash function turns any data into a short, fixed-size digest; it's deterministic.
  • A checksum like CRC-32 catches accidents but is forged in a fraction of a second. A cryptographic hash is built for attackers.
  • The birthday paradox: collisions after about √N tries, so an n-bit hash gives n/2 bits of collision resistance.
  • The three promises: preimage (one-way), second-preimage and collision resistance, plus the avalanche effect.
  • One-way doesn't stop guessing: small inputs like PINs fall instantly (passwords: next episode).
  • MD5 and SHA-1 are broken. Use SHA-256 (SHA-2), SHA-3 or BLAKE2/BLAKE3.
  • sha256(secret + msg) suffers length extension: use HMAC for anything with a key.
  • Verify downloads against a hash from a trusted source; a Merkle tree covers huge data with one root and short proofs.

Next episode: storing passwords correctly: salts, peppers, rainbow tables, credential stuffing, bcrypt, scrypt, Argon2id and NIST's password rules.

Sources: EFF, "Cryptographers Demonstrate Collision in Popular SHA-1 Algorithm" (23 Feb 2017); NIST, "NIST Retires SHA-1 Cryptographic Algorithm" (15 Dec 2022); NIST FIPS 202, SHA-3 Standard (4 Aug 2015); BLAKE3 README (github.com/BLAKE3-team/BLAKE3); Git documentation, "hash-function-transition"; RFC 6962, Certificate Transparency (June 2013); Go hash/crc32 documentation (IEEE polynomial users). Code outputs from Python 3.13. Fetched 29 Oct 2026.