Hash Functions and MACs

2026-11-18

notes / Cryptography

Properties

A hash family is a four-tuple (X,Y,K,H) where

Note

unkeyed hash => |K|=1

The perfect hash function is a random oracle which is impossible to achieve

properties

Security Requirements

Preimage Resistance (One-wayness)

OW

Infeasible to find x such that h(x)=y for a given y∈{0,1}d x is the preimage of y

Second Preimage Resistance

TCR

given x1 and h(x1) it should be infeasible to find x2 such that h(x2)=h(x1)

this is just weak collision resistance

Collision Resistance

CR

infeasible to find a pair (x,x′) such that x≠x; and h(x)=h(x′)

Birthday Paradox

just need 23 people for a 50% chance of same birthday

Pr(no collision in 2 people)=(365−1365)

Pr(no collision in 3 people)=(365−1365)⋅(365−2365)

and so on

Number of messages required to find a collision with decent probability

Pr(no collision)=∏i=1t−1(1−i2n) and e−x≈(1−x)

Pr(no collision)=∏i=1t−1ei2n

Pr(no collision)=e−(t−1)t2(n+1)

let λ = Pr(collision)

λ=1−e−(t−1)t2(n+1)

t(t−1)=2n+1ln(11−λ) and t(t−1)≈t2

t≈2n+1ln(11−λ)

collision finding

t≈2n2 hashes needed to find a collision with decent probability

Relation of These Properties

Reading Further

Discussion of these attacks in terms of graphs, where # of edges is the “number of chances” to get a collision. Collision-resistance brute force is a complete graph (need √N vertices to have N edges / chances for a collision) . Second-preimage brute force is a star graph (need N vertices to N edges). Can generalize to consider complete bipartite graph between √N + √N vertices.

Merkle-Damgard Paradigm

if you have collision resistance function h(x) that compresses from m+t→m you can expand this to create collision resistant function H(x) that compresses from ∞→m

Iterated Hashes

Merkle and Damgard independently proved that if h(x) is collision resistant then H(x) is too. I am NOT proving ts

Message Authentication Codes

keyed cryptographic hash. So you want to hash your key together with your message.

  1. IV = key
    • can't make hash function public or something i think
  2. h(K||x) -> secret prefix
    • can just append extra blocks with no issue
  3. h(x||K) -> secret suffix
    • weak to collisions

These are vulnerable to length extension attacks

HMAC is the standard

HMACK(x)=SHA-1((K⊕opad)||SHA-1((K⊕ipad)||x))

Authenticated Encryption

linked from