Skip to content

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.