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.