Hash Functions and MACs
2026-11-18
notes / Cryptography
Properties
A hash family is a four-tuple where
- is a set of possible messages (may be infinite)
- is the finite set of possible hashes/digests/tags
- is the keyspace
- for each there is a hash function
The perfect hash function is a random oracle which is impossible to achieve
properties
- arbitrary input size
- fixed output size
- efficiency
- pseudorandomness, i.e. should nto be possible to derive a relation between and
- one way
- computationally impossible to find collision
Security Requirements
Preimage Resistance (One-wayness)
Infeasible to find such that for a given is the preimage of
Second Preimage Resistance
given and it should be infeasible to find such that
this is just weak collision resistance
Collision Resistance
infeasible to find a pair such that and
just need 23 people for a 50% chance of same birthday
and so on
Number of messages required to find a collision with decent probability
and
let =
and
hashes needed to find a collision with decent probability
Relation of These Properties

- finding collisions is easier than finding TCR or PI
- collision resistance => second preimage resistance and preimage resistance
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 that compresses from you can expand this to create collision resistant function that compresses from
Iterated Hashes 
Merkle and Damgard independently proved that if is collision resistant then is too. I am NOT proving ts
Message Authentication Codes
keyed cryptographic hash. So you want to hash your key together with your message.
- IV = key
- can't make hash function public or something i think
- -> secret prefix
- can just append extra blocks with no issue
- -> secret suffix
These are vulnerable to length extension attacks
HMAC is the standard
- proveable security based on SHA-1 (which is broken atp lol)
- opad and ipad are fixed constants (ipad lol)
- hash of hash -> nested hash
Authenticated Encryption
linked from