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.

Chains of trust use hashes to verify each component before it runs.

Strict Avalanche Criterion

Also known as 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

$H$ is the hash function and is modelled to be a uniformly random function.

Computationally Efficient

$H(m)$ is fast to compute for any $m$ and does not vary much.

Deterministic

Same plaintext input produces the same digest.

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

Also known as 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

Basic Mathematical Hash Functions

The following functions map non-negative integers to a fixed range. They illustrate hashing, but they are not cryptographically secure.

Examples:

• $H_1(42) = 2$
• $H_1(52) = 2$
• $H_2(7) = 2$
• $H_2(17) = 2$

Both functions have collisions. $42$ and $52$ have the same digest under $H_1$. $7$ and $17$ have the same digest under $H_2$. A digest of $2$ does not identify a unique input.

OAEP

Also known as 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.