Hash functions

Understand what a cryptographic hash function guarantees — preimage, second-preimage and collision resistance — the random-oracle intuition behind those guarantees, and why hashing is the quiet workhorse under commitments, integrity checks and content addressing.

Track

Fundamentals

Module

2 · Applied cryptography for agents

Prerequisites

Basic bit/byte representation · Comfort reading pseudocode

A hash function takes an input of any size and returns a short, fixed-length value called a digest or hash. A cryptographic hash function adds a crucial promise: the digest behaves like a unique fingerprint of the input. Change one bit of the input and the digest changes completely and unpredictably; yet the same input always yields the same digest. This lets a tiny value stand in for arbitrarily large data when you only need to answer "is this still exactly what it was?"

Cryptographic strength is captured by three resistance properties. They are related but distinct, and systems rely on different ones.

Preimage resistance

Given a digest h, it is infeasible to find any input m with hash(m) = h. This is the "one-way" property — you cannot invert the function.

Second-preimage resistance

Given a specific input m1, it is infeasible to find a different m2 with hash(m2) = hash(m1). An attacker cannot forge a second file matching a known file’s digest.

Collision resistance

It is infeasible to find ANY two distinct inputs m1, m2 with the same digest. This is the strongest property, and the easiest to attack because of the birthday bound.

The birthday bound is why collision resistance is weaker than it looks: for an n-bit digest, brute-force preimage search costs about 2^n work, but a collision can be found in only about 2^(n/2) work. That is why SHA-256 gives roughly 128-bit collision security, not 256-bit, and why truncating digests too aggressively is dangerous.

The idealized mental model is the random oracle: imagine a function that, for each new input, returns an independent uniformly random digest and remembers its answers so repeats are consistent. Real hash functions are deterministic public algorithms, not random oracles, but proofs and intuitions often assume the random-oracle model (ROM) as an approximation.

random-oracle intuition + resistance goals
# Idealized oracle H (for intuition only)
H(m):
  if m already queried:  return stored[m]
  else:                  stored[m] = uniform_random(n_bits); return stored[m]

# Security goals for an n-bit digest (best known attack cost):
preimage        : given h,        find m  : H(m)=h           ~ 2^n
second-preimage : given m1,       find m2 : H(m2)=H(m1), m2!=m1  ~ 2^n
collision       : find any m1!=m2 : H(m1)=H(m2)              ~ 2^(n/2)   # birthday bound

Note what the model does NOT claim: outputs are not literally random (the algorithm is fixed and public), and the ROM is a heuristic, not a theorem about SHA-256. Real functions also have internal structure — SHA-256 uses the Merkle–Damgård construction, which makes it vulnerable to length-extension attacks (see Risks), while SHA-3 uses the sponge construction, which is not.

1. 1Pick a vetted algorithm sized for your threat model: SHA-256 or SHA-512 (SHA-2 family, FIPS 180-4) or SHA3-256 (FIPS 202). Avoid MD5 and SHA-1 — both are broken for collision resistance.
2. 2Serialize the input to exact, unambiguous bytes before hashing (encoding, field order and separators fixed) so the same logical object always produces the same digest.
3. 3Feed the bytes through the hash to get a fixed-length digest (256 bits for SHA-256).
4. 4Store, publish or compare the digest. To verify integrity later, re-hash the data and compare digests with a constant-time comparison.
5. 5If the data is secret or low-entropy (like a password), a plain hash is NOT enough — use a purpose-built password hash (Argon2, scrypt, bcrypt) or an HMAC, not a bare SHA-256.

synthetic — commitment then reveal
# A commitment: prove you fixed a value without revealing it yet.
value   = "agent-plan-v7"
nonce   = random_128_bits()                 # blinding, prevents guessing
commit  = SHA256( nonce || value )          # publish this now

# ... later, to open the commitment, reveal (value, nonce):
ok = ( SHA256(reveal_nonce || reveal_value) == commit )
# A different value or nonce yields a different digest -> ok == False

This is a hash-based commitment. The digest binds the committer to one value (they cannot later open it as something else, by second-preimage resistance) while hiding it (the random nonce prevents an attacker from guessing and confirming the value from a small set). Binding and hiding are exactly the two things an auditable "I decided X before I saw Y" claim needs.

Hashing is everywhere under an agent system even when no one mentions it. Integrity: a tool result or a model output can carry a digest so a downstream agent detects any tampering in transit or storage. Content addressing: referring to an artifact by its hash (a "content ID") means the reference itself certifies the content — fetch it, re-hash, and you know you got the exact bytes that were named. Commitments: an agent can commit to a plan or a random choice before seeing an input, then reveal it, giving an auditor a tamper-evident record of order-of-operations.

Hashing is also the first step of almost every other primitive in this track: signatures sign the hash of a message, MACs and HMAC are built on hashes, Merkle trees and hash chains (later lessons) are entirely hash-structured, and transparency logs chain digests to make audit trails append-only.

• ▸Collision resistance degrades with digest size (birthday bound ~2^(n/2)); do not truncate digests below your collision-security target, and avoid broken functions (MD5, SHA-1).
• ▸Merkle–Damgård hashes (MD5, SHA-1, SHA-2) are vulnerable to length-extension: given H(secret || m) and the length, an attacker can compute H(secret || m || padding || extra) without the secret. Use HMAC or SHA-3 instead of raw hashing for authentication.
• ▸A bare hash of low-entropy data (passwords, PINs, short identifiers) is brute-forceable by precomputation; use salted password hashes (Argon2/scrypt/bcrypt), never plain SHA-256.
• ▸Hashing provides integrity, not authenticity: anyone can recompute a digest, so a digest alone does not prove WHO produced the data. Pair it with a MAC or a signature when origin matters.
• ▸A matching digest proves the bytes are unchanged — not that the content is correct, safe or trustworthy. Integrity is not validity.

Expected direction: (a) Second-preimage (and more generally collision) resistance: it cannot find another plan hashing to the same digest, so it is bound to the committed one. (b) Without a nonce, an attacker who knows the small set of possible plans can hash each candidate and match the digest, defeating hiding; a random nonce adds enough entropy that the digest reveals nothing about which plan was chosen.

Why does SHA-256 provide roughly 128-bit collision security rather than 256-bit?

Because of the birthday bound: a collision for an n-bit digest can be found in about 2^(n/2) work, so a 256-bit digest gives ~128-bit collision resistance.

What is the difference between second-preimage resistance and collision resistance?

Second-preimage: given a specific input, you cannot find a different input with the same digest. Collision: you cannot find ANY two distinct inputs with the same digest. Collision resistance is strictly stronger.

Does a matching hash digest prove who produced the data?

No. Anyone can recompute a digest, so it proves integrity (unchanged bytes) but not authenticity. Origin requires a MAC or signature.