L14 · Hashing

Module 3: Cryptography Essentials · ~20 min · Lesson 14 of 71

🎯 What you'll learn

• What a cryptographic hash is: deterministic, fixed-size, one-way, and wildly sensitive to change
• The three security properties (preimage, second preimage, collision resistance) and the birthday bound
• Why MD5 and SHA-1 are dead, and what to use instead
• Where hashes already run in a typical cloud stack (Git, container digests, S3), and why a hash is not encryption or a MAC

🔥 Why this matters

On Monday your team scans and approves policy-service:1.4.2. On Wednesday someone pushes a different build under the same tag, and Thursday's EKS rollout pulls it. The YAML didn't change, so nobody notices. The fix is the image's sha256: digest, a hash naming the exact bytes you approved. And in 2012, a broken hash (MD5) let the Flame spyware pose as Windows Update.

1. A fingerprint for any data

A vendor's download page says SHA-256: 1e0d5dd1...c17a. You run one command on the 300 MB file, get the same 64 hex characters, and know it arrived intact. How can 32 bytes vouch for 300 MB?

A cryptographic hash function takes input of any size and returns a short, fixed-size value called a digest (or hash). SHA-256 always returns 256 bits (64 hex characters). Think of a fingerprint: small, unique in practice, and you can't rebuild the person from it.

  any size input                         fixed-size output
 ┌──────────────┐                      ┌────────────────────┐
 │ "hello"      │──┐                ┌─▶│ 2cf24dba...938b9824│
 └──────────────┘  │  ┌──────────┐  │  └────────────────────┘
                   ├─▶│ SHA-256  │──┤      256 bits each
 ┌──────────────┐  │  └──────────┘  │  ┌────────────────────┐
 │ 300 MB .tgz  │──┘   no key,      └─▶│ 1e0d5dd1...eef08c17│
 └──────────────┘      public algo     └────────────────────┘
        ▲                                        │
        └──────── no way back (one-way) ◀────────┘

Four properties make it useful:

• Deterministic: the same input always gives the same digest, on any machine, forever.
• Fast: a laptop computes millions per second. (Great for files, terrible for passwords: L18.)
• One-way: given a digest, there's no practical way to compute the input.
• Avalanche effect: change one bit of input and about half the output bits flip, so similar inputs give unrelated digests. hello and jello differ by one bit; their SHA-256 digests differ in 119 of 256 bits.

There is no key: anyone can compute SHA-256 of anything. That matters in section 4.

2. The three security properties

"Hard to break" means three different things, and attacks break them separately:

A collision is two different inputs with the same digest. Collisions must exist (infinite inputs, finite outputs), so the question is only whether anyone can find one.

Collision resistance falls first, because the attacker controls both inputs. That sounds harmless until the innocent twin gets approved or signed and the evil twin inherits the approval. That's how certificate forgeries work.

The birthday bound

In a room of just 23 people, there's a 50% chance two share a birthday. You're comparing every pair (253 of them), not looking for one specific date. Hashes behave the same way:

 n-bit hash        find a preimage      find ANY collision
                   (match one target)   (match any pair)
 ───────────────────────────────────────────────────────────
 MD5     128 bit       ~2^128              ~2^64  generic
                                           seconds with attacks
 SHA-1   160 bit       ~2^160              ~2^80  generic
                                           ~2^63  SHAttered, 2017
 SHA-256 256 bit       ~2^256              ~2^128 (out of reach)

The birthday bound says a generic collision search on an n-bit hash takes about 2^(n/2) tries, so a 256-bit hash gives 128 bits of collision security, a comfortable modern minimum. MD5 and SHA-1 are worse than their bounds: researchers found shortcuts.

3. Why MD5 and SHA-1 are dead

• MD5 (1992): practical collisions since 2004; a laptop finds one in seconds. Used to forge a rogue CA certificate in 2008 (a research demo) and a Microsoft one in 2012 (Flame).
• SHA-1 (1995): in 2017 Google and CWI published SHAttered, two different PDFs with the same SHA-1 (about 6,500 CPU-years plus 110 GPU-years of work). By 2020 a more dangerous kind of collision cost an estimated US$45,000. NIST says to stop using SHA-1 by the end of 2030.

Use instead: SHA-256 or SHA-512 (the SHA-2 family), SHA-3, or BLAKE2/BLAKE3. MD5 still spots accidental corruption, but if an attacker might choose the input, it's broken. The first deep dive walks through these attacks.

4. Where hashes already run in a typical stack

• Git: every commit ID is a hash (SHA-1 by default) over the commit's content, its tree, and its parent's ID. Rewrite one old commit and every later commit ID changes, which is why history rewrites are visible. Git is moving to SHA-256 (first deep dive).
• Container images: an image digest sha256:9f74... is the hash of the image manifest, which lists the hashes of every layer. Tags like :1.4.2 are movable labels; digests aren't.
• S3: the ETag looks like an MD5 of the object, but it isn't for multipart uploads or SSE-KMS objects. Use S3's checksum fields instead: the default CRC64NVME (since December
  2024. catches accidents; request SHA-256 if you need a cryptographic hash.
• Lookups: idempotency keys, gateway cache keys, and deduplication often hash request fields. MongoDB's hashed shard keys spread writes across shards: distribution, not security.

A hash is not encryption, and not a MAC

This is the integrity-versus-confidentiality line from L01, drawn precisely:

Two traps follow from "no key":

1. A hash next to the data proves nothing against an attacker. Whoever can change the message can recompute the hash too (L01's AEAD Q&A). Trust a digest only if it came from somewhere the attacker can't touch: a signed release, a pin in your own Git repo.
2. Hashing isn't hiding. "We store SHA-256 of the SSN, so it's anonymized" fails: there are under a billion possible SSNs, and one core of the Mac this was written on hashes about 4 million per second in Python, so trying them all takes about 4 minutes. Passwords have the same problem, which is why L18 uses slow, salted functions.

🧪 Worked example: pin the image you approved

A deployment that trusts a tag:

# deploy.yaml  (mutable: pulls whatever 1.4.2 means today)
containers:
  - name: policy-service
    image: registry.example.com/policy-svc:1.4.2

The same deployment pinned by digest (the 64 hex characters are shortened here):

# deploy.yaml  (immutable: only these exact bytes)
containers:
  - name: policy-service
    image: registry.example.com/policy-svc@sha256:9f74e4ef…6006

What happens when someone re-pushes 1.4.2 with different content:

 registry                         EKS node (containerd)
 ┌──────────────────────────┐
 │ tag 1.4.2 ──▶ sha256:9f74│  Mon: scanned + approved
 │ tag 1.4.2 ──▶ sha256:d33c│  Wed: tag moved (re-push)
 └──────────────────────────┘
   :1.4.2 pin ───────────────────▶ pulls d33c  ✗ unreviewed
   @sha256:9f74 pin ─────────────▶ pulls 9f74  ✔ approved
                                   (or fails if 9f74 deleted)

The container runtime on the node (containerd on EKS) hashes what it downloads and rejects content that doesn't match the digest, so the registry can't substitute bytes either. To see what a running pod actually got:

$ kubectl get pod policy-svc-7d9f -o \
    jsonpath='{.status.containerStatuses[0].imageID}'
registry.example.com/policy-svc@sha256:9f74e4efee8db5b6f7…

Also turn on tag immutability in ECR (IMMUTABLE) so tags can't move, and let CI write the digest into the manifest so nobody copies 64 hex characters by hand.

🛠 Try it (optional, ~5 min)

In a terminal on macOS (zsh) or Linux:

$ echo -n hello | shasum -a 256
2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824  -
$ echo -n jello | shasum -a 256
187c9bceeb919e1b3e6d20fa50ecabf7d9d50b5343e8f9a3d912abb13929102e  -

One letter (h 0x68 to j 0x6a, a single bit) and the digests look unrelated. Now the classic gotcha, without -n:

$ echo hello | shasum -a 256
5891b5b522d5df086d0ff0b110fbd9d21bb4fc7163af34d08286a2e846f6be03  -

Different: plain echo adds a newline, so you hashed hello\n. This bites people comparing a webhook body's hash with a partner's. A macOS trap too: in /bin/sh scripts, echo -n hello prints the literal text -n hello plus a newline. In scripts, use printf 'hello'.

Then verify a file the way release pages expect (recent macOS also ships sha256sum):

$ cd "$(mktemp -d)" && printf 'release 1.4.2\n' > tool.tar.gz
$ shasum -a 256 tool.tar.gz > tool.tar.gz.sha256
$ shasum -a 256 -c tool.tar.gz.sha256
tool.tar.gz: OK
$ printf 'X' >> tool.tar.gz        # tamper: add one byte
$ shasum -a 256 -c tool.tar.gz.sha256
tool.tar.gz: FAILED
shasum: WARNING: 1 computed checksum did NOT match

-c exits non-zero on a mismatch, so it can fail a CI step. But if the .sha256 file came from the same server as the download, it only catches accidents (section 4).

🧠 Key takeaways

• A hash maps any input to a fixed-size digest: deterministic, fast, one-way, avalanche.
• Collision resistance breaks first, and the birthday bound means n bits give n/2 bits of it.
• MD5 and SHA-1 have practical collisions; use SHA-256/512, SHA-3, or BLAKE2/3.
• No key means no secrecy and no tamper-proofing: trust a digest only as much as its source.
• Pin by digest (images, actions, dependencies) when you need "exactly these bytes."

📖 Words to know

⏭ Next time

L15: symmetric encryption: AES, why the "ECB penguin" leaks its outline, and why reusing a GCM nonce is a disaster.

Two kinds of collision

Not all collisions are equally useful to an attacker:

• Identical-prefix collision: both files start with the same content, then the attacker inserts two carefully computed blocks that differ, and after that both files can continue identically. SHAttered was this kind: two PDFs that show different images.
• Chosen-prefix collision: the attacker picks two different starting texts (say, "Name: alice.example.com" and "Name: anything, CA:TRUE") and computes suffixes that make the hashes match. Far more dangerous, and more expensive. MD5 fell to this in 2007; SHA-1 in 2020 ("SHA-1 is a Shambles", Leurent and Peyrin, which built two PGP keys with colliding SHA-1 certifications).

Why the suffix trick works: MD5 and SHA-1 process input in blocks, carrying a running internal state. Once two inputs reach the same state, identical bytes appended afterward keep them equal.

How a collision forges a certificate

A CA doesn't sign the whole certificate directly. It signs the hash of the certificate's content (L11's "signature over all of the above"). So if two certificate bodies share a hash, one signature fits both:

 attacker builds two bodies with the SAME MD5 hash
 ┌─────────────────────────┐     ┌─────────────────────────┐
 │ A: leaf for my domain   │     │ B: CA:TRUE, or a code-  │
 │    (looks normal)       │     │    signing cert for     │
 │                         │     │    "Microsoft"          │
 └────────────┬────────────┘     └────────────┬────────────┘
              │ 1. submit A to the CA         │
              ▼                               │
 ┌─────────────────────────┐                  │
 │ CA signs MD5(A)         │ 2. returns sig   │
 └────────────┬────────────┘                  │
              │ 3. copy sig onto B ───────────▶ MD5(B)=MD5(A)
              ▼                                 sig verifies ✔
     clients trust B: it chains to a real CA

The attacker never touched the CA's private key. They got a legitimate signature on an innocent request and moved it to the evil twin.

• 2008, rogue CA: researchers (Sotirov, Stevens and others) used a cluster of about 200 PlayStation 3s to build a chosen-prefix MD5 collision against a commercial CA that still signed with MD5. Their "B" was an intermediate CA certificate that browsers would have trusted for any site. They gave it a validity period already in the past, so it couldn't be abused.
• 2012, Flame: espionage malware spread inside networks by posing as Windows Update. Its code was signed with a certificate forged via an MD5 chosen-prefix collision against Microsoft's Terminal Server Licensing Service, which still used MD5 and issued certificates that could sign code. Cryptanalysts at CWI found the attack was a new, previously unpublished variant. Microsoft revoked the whole CA hierarchy (Security Advisory 2718704).

The lesson: one old algorithm in a forgotten corner (a licensing service!) undid strong crypto everywhere else.

What SHAttered actually cost and changed

SHAttered took roughly 2^63 SHA-1 computations; Google said that was about 100,000 times faster than the generic birthday attack. It was an identical-prefix collision, so it couldn't directly forge a certificate, but it ended any argument that SHA-1 was "theoretical." The 2020 chosen-prefix result removed the remaining doubt. The CA/Browser Forum had already banned new SHA-1 TLS certificates from 2016, and the major browsers distrusted them in early 2017.

Git and SHA-1

Git names every object by its SHA-1. You can reproduce it:

$ printf 'hello' | git hash-object --stdin
b6fc4c620b67d95f953a5c1c1230aaab5db5a1b0
$ printf 'blob 5\0hello' | shasum -a 1
b6fc4c620b67d95f953a5c1c1230aaab5db5a1b0  -

Git hashes a small header (blob <size>\0) plus the content. A collision would let an attacker get an innocent-looking file merged, then serve a different file with the same ID from a mirror. That's hard (the "innocent" file contains odd random blocks), and Git reacted quickly:

 2017  SHAttered
   │
 2017  Git 2.13 switches to SHA-1DC by default: SHA-1 that detects
   │   the known collision-attack patterns and refuses them
   │
 2020  Git 2.29: experimental SHA-256 repositories
   │   (git init --object-format=sha256)
   │
 2025  Git 2.51: SHA-256 named the default for new repos in 3.0
   │
 now   Git 3.0 not released yet (as of Nov 2026), and GitHub
       doesn't yet host SHA-256 repos

You can make a SHA-256 repo today (git init --object-format=sha256; the same blob becomes 8aec4e48...aeb60), but you couldn't push it to GitHub as of this writing, and converting an existing repo rewrites every ID. Expect years of mixed SHA-1 and SHA-256. The exact Git 3.0 timeline has already slipped once, so check the Git release notes for the current state.

🛠 Try it (~3 min)

Run the two commands above to reproduce a Git blob ID by hand. Then visit shattered.io and read how the two PDFs differ, and why the SHA-256 of each is still different.

🧠 Extra takeaways

• Chosen-prefix collisions are what forge certificates; identical-prefix ones forge files.
• A signature is over a hash, so a broken hash makes the signature transferable.
• One forgotten MD5 signer (Flame) was enough to impersonate Windows Update.
• Git uses collision-detecting SHA-1 now and is slowly moving to SHA-256.

Name it by what it is

Most names are labels someone assigns: policy-svc:1.4.2, v46, latest. Labels can be moved. Content addressing names a thing by the hash of its content instead. The name is the fingerprint, so if the content changes, the name changes. You can download from an untrusted mirror and still check you got the right bytes, because you know what the hash must be.

Merkle trees: one hash vouches for everything below it

Git and container images both chain hashes into a Merkle tree: each node contains the hashes of its children, so the top hash commits to every byte underneath.

 container image                     Git
 ┌───────────────────────┐           ┌───────────────────────┐
 │ manifest  sha256:9f74 │◀─ pin     │ commit  a1b2...       │◀─ pin
 │  config   sha256:8998 │           │  tree    c3d4...      │
 │  layer 1  sha256:8c80 │           │  parent  e5f6...      │
 │  layer 2  sha256:f64a │           │  author, message      │
 └───┬───────────┬───────┘           └───┬───────────────────┘
     ▼           ▼                       ▼
  config JSON  layer tar.gz           tree: file name ▶ blob
  (hash must   (hash must             hash, subdir ▶ tree hash
   match)       match)

Change one byte in layer 2 and its hash changes, so the manifest's content changes, so the manifest digest changes. That's why pinning one digest pins the whole image. (A multi-arch image adds one level: an image index listing a manifest per platform, and the digest you usually pin is the index's.)

Pin everything that can move

The same idea protects every input to a build or deploy:

Why this is not theoretical: in March 2025 an attacker with write access to the popular tj-actions/changed-files GitHub Action moved its existing version tags (v1 through v45) to a malicious commit that printed CI secrets into build logs (CVE-2025-30066, now in CISA's KEV list from L02). Thousands of repos referenced it by tag and ran the malicious code on their next build. Repos that pinned the full commit SHA kept running the old, clean code.

 (commit IDs shortened; 9a1b is illustrative)
 uses: tj-actions/changed-files@v45
   Mar 13: v45 ──▶ commit 9a1b... (clean)
   Mar 14: v45 ──▶ commit 0e58... (dumps secrets) ✗ you run it

 uses: tj-actions/changed-files@<full 40-hex SHA of 9a1b...>
   Mar 14: still commit 9a1b...                   ✔ unchanged

🧪 Worked example: a pinning policy for an EKS service

A reasonable baseline for a service like policy-service:

1. CI builds the image, pushes it to ECR (tag immutability on), and records the digest it got back from the push.
2. CI writes image: …/policy-svc@sha256:<digest> into the deployment manifest in Git, so the reviewed PR names exactly the bytes that will run.
3. The Dockerfile's FROM and every GitHub Action are pinned by digest or commit SHA. A bot such as Dependabot or Renovate opens PRs to bump them, so pins don't rot.
4. An admission policy in the cluster (for example Kyverno or OPA Gatekeeper) rejects pods whose image has no @sha256: digest.

What a pin does not tell you

A digest proves these are the same bytes as before. It doesn't prove the bytes were safe, or who made them. If you pin a malicious image, the pin faithfully keeps you on it. Answering "who built this?" needs a signature over the digest (for example Sigstore's cosign), which is L17's territory. Pins also mean you won't get security fixes until someone bumps them, so pinning without automated updates trades one risk for another (L04's balance between goals).

🛠 Try it (~5 min)

Open one of your team's workflow files in .github/workflows/. For each uses: line, is it a tag or a 40-character commit SHA? Then look at one deployment manifest: tag or @sha256:? Note which references could change under you without a PR.

🧠 Extra takeaways

• Content addressing names data by its hash, so a name can't point at different bytes.
• Merkle trees let one top hash vouch for every layer, file, or commit below it.
• Pin images, base images, actions, and packages by digest; let a bot keep the pins fresh.
• A pin proves sameness, not trustworthiness: add signatures (L17) for "who built this."