Hash Function

A hash function $H$ maps input of variable size to an output of fixed size.

$$H(\cdot): \{0,1\}^* \rightarrow \{0,1\}^k$$

with hash function $H$, an input bit stream $\{0,1\}^*$ and output digest $\{0,1\}^k$ of $k$ bit.

{{ FOLDER_TOC }}

Properties

• Deterministic: the same input produces the same output
• Uniformity: random input is mapped evenly over the output range
• Continuity: similar inputs produce similar outputs. (search index)

Cryptographic Hash Functions

• Non-invertible: it should be practically impossible to reconstruct the input $x$ from its hash value $h(x)$ alone without spending great amounts of computing time (one way function)

Attributes

• perfect iff it maps each valid input to a different hash value (no collisions)

• minimal iff the output range consists of $n$ consecutive integers for $n$ possible keys (no empty slots)

Algorithms

• CRC: CRC-16
• Checksums: sum, Fletcher
• Non-cryptographic: Pearson
• cryptographic: MDx, SHA-x, Whirlpool

Crypto Hash	Output bits	Security bits	Block size bits
MD5	128	< 64	512
SHA-1	160	< 63	512
SHA-256	256	128	512
SHA3-256	256	128	1088

Cryptographic hashes often divide the input in fixed length blocks $m_i$ and iteratively compute $h_i = f(h_{i-1}, m_i)$

Attacks

• Preimage Attack: find any input that has a specific hash value.
• Collision Attack: find any two inputs producing the same hash value
• Length extension attack: find a new hash that corresponds to the original input with some arbitrary appended data.