Hash Functions¶

links: AC1 TOC - Random Oracle & Applications - Modern Cryptography MOC - Index

Hash functions are simply functions that take inputs of some length and compress them into short, fixed-length outputs.

Hash functions can be viewed as lying between the worlds of private- and public-key cryptography, because they have important applications in both settings.

Cryptographic Hash Functions

a hash function with a fixed output length
has to be deterministic
Collision resistant (which implies pre-image- and second-image resistance)
hash must therefore be a one-way function

Collision Resistance¶

a function $H$ is collision resistant if it is infeasible for any probabilistic polynomial-time algorithm to find a collision in $H$ .
The domain of a hash function is normally larger than their range $\to$ in this case collisions must exist, but such collisions should be hard to find.

Keyed hash functions¶

Keyed hash functions: $H$ takes as input a key $s$ and a string $x$ and outputs a string $\to$ the key is generally not kept secret!
Cryptographic hash functions used in practice are generally unkeyed and have a fixed output length

Weaker Notions of Security¶

Second-preimage resistance¶

We have $x$ and cannot find a $x^{'}$ which results to the same Hash $y$ for both $x$ and $x^{'}$ :

H (x) = H (x^{'}), x \neq x^{'}

Preimage resistance¶

$H$ is one-way, if we have a hash $y$ ( $y = H (x)$ is known, $x$ is unknown) we cannot go back to find a $x^{'}$ to compute $y$ :

H^{- 1} (H (x)) = x, let H^{- 1} be the inverse of H

Overview of Security Notions¶

Collision resistance implies second-preimage resistance, but does not guarantee preimage resistance $\to$ A second-preimage attack implies a collision attack.

Compress Functions¶

Merkle-Damgård Transform¶

maps inputs of arbitrary length to outputs of length $n$

Davies-Meyer¶

Davies-Meyer is a compress function from a block cipher
$F$ is a strong pseudorandom permutation

Attacks on Hash Functions¶

in symmetric-key using a $n$ -bit secret key is vulnerable to a brute-force attack in which an attacker enumerates all $2^{n}$ possible keys
for a hash function $H$ to be collision resistant against attackers running in time $2^{n}$ it is required that $H$ has output at least $2 n$ bits long

Birthday attacks¶

if $q$ people are in a room, what is the probability that some two of them share a birthday? $\to$ matching birthdays correspond to collisions
if $H$ has an output length of $l$ , $q = Θ (2^{l / 2}) \to$ yields a collision with probability roughly $1 / 2$

Rho Method¶

algorithm for finding collisions
unlike the birthday attack, requires only a small amount of memory
Method: start with a random value $x$ , calculate $H_{1} (x)$ , then compute $H_{2} (H_{1})$ , then $H_{3} (H_{2})$ , ...
Aim: find a cycle/ collision in the evaluation

Universal Hash Function¶

Universal hashes can be extremely cheap to evaluate - much cheaper than block ciphers, pseudorandom functions, and especially collision-resistant hashes. (...) Universal hashing gives us strong guarantees with extremely cheap options

selecting a hash function at random from a family of hash functions with a certain mathematical property
Example of universal hash families: GHASH (used in GMAC) or Poly1305

Source: Link

links: AC1 TOC - Random Oracle & Applications - Modern Cryptography MOC - Index