Hash Functions

A hash function $H$ maps a message $m$ of any length to a fixed $n$-bit digest $H(m)$. It is public and keyless.

A cryptographically secure hash function is:

• Computationally efficient
  $H(m)$ is fast to compute for any $m$.
• Deterministic
  The same $m$ always gives the same digest.
• One-way
  Preimage resistant, defined below.
• Collision resistant
  Defined below.

Strict Avalanche Criterion

Also called SAC or bit diffusion. When a single input bit is flipped, about 50% of the output bits flip on average, and the probability that any given output bit flips is independent of which input bit was flipped and of the input value.

Properties

Each property is stated as work an attacker cannot afford. $H$ is modelled to be a uniformly random function, for the below analysis.

Preimage Resistance

Given a digest $d$, an attacker cannot find any $m$ with $H(m) = d$ practically.

The attacker is aiming at one fixed digest $d$. Each trial message lands on it with chance $1$ in $2^n$, so about $2^n$ trials are needed.

Weak Collision Resistance

Aka. second-preimage resistance. Given a fixed message $m$, an attacker cannot find a different $m'$ with $H(m') = H(m)$.

Again one fixed target, the digest of the given $m$. Each trial $m'$ lands on it with chance $1$ in $2^n$, so about $2^n$ trials are needed, the same as preimage resistance.

Strong Collision Resistance

An attacker cannot find any pair $m \neq m'$ with $H(m) = H(m')$, both of their choosing.

Any two of the attacker’s own messages sharing a digest is a win. Each new message can pair with every earlier one, so after hashing $k$ messages there are about $k^2/2$ candidate pairs. That many pairs cover the $2^n$ possible digests once $k \approx 2^{n/2}$, so the work drops to the square root.

Same effect as the birthday problem: matching one given birthday needs about $365$ people, but finding any shared birthday needs only about $23$.

Uses

Cryptographic uses:

• Padding
  Randomised padding schemes such as OAEP mix message bits with hash output before public key encryption.
• Signing
  A signature is computed over $H(m)$, so it covers an input of any length at fixed cost.
• Key derivation
  A raw secret is hashed to produce a symmetric key of the required length with no algebraic structure.

In real world:

• File integrity
  A published digest lets anyone check a downloaded file was not altered.
• Blockchain security
  Each block stores the digest of the previous block, so any edit breaks the chain.
• Password storage
  The database keeps $H(\text{password})$, not the password. Even if the database leaks, the attacker cannot reverse the digests back to plaintext passwords.

Examples

OAEP

Optimal Asymmetric Encryption Padding. A randomised padding applied to a message before RSA encryption.

It is a 2-round Feistel network over the message $M$ and a random seed $r$, with round functions built from a hash $H$:

• $\text{maskedM} = (M \,\|\, \text{padding}) \oplus G(r)$, where $G$ expands $r$ to the block width.
• $\text{maskedR} = r \oplus H(\text{maskedM})$.
• The RSA input is $\text{maskedM} \,\|\, \text{maskedR}$.

Effects:

• Randomised
  The same $M$ encrypts differently each run through $r$.
• All-or-nothing
  Every output bit depends on every bit of $M$ and $r$, so a tampered block fails the padding check on decryption.

This makes RSA encryption secure against chosen-ciphertext attacks. The hash is used only as padding, so no collision property is relied on.