Hash

A Hash function takes a variable-length string as an input, returns a fixed-size output and is efficient.

A hash function H is cryptographically secure if:

• is collision-free: for all x, y, H(x) = H(y) => x = y
  • but collisions do exist because the output has a fixed size whereas the input size is not
• has a hiding property:
  • Given H(x), it is infeasible to find x, it is easy to find x if x does not take many different values
  • better definition: If r is chosen from a probability distribution with high min-entropy, given H(r | x), it is infeasible to find x
• is puzzle-friendly: for every output y, if k is chosen from a probability distribution with high min-entropy, it is infeasible to find x such H(k | x) = y
  • this means there no solving strategy better than trying random value to find it.

SHA-256

breaks the message into 512-bits blocks with some padding in the last block that contains 64-bit length field (length message in bit), 1 bit and some number of 0 bits.

The initial input IV is 256-bit. Given c a hash function, SHA-256=c(block n, c(block n-1, c(block n-2, ..., c(block 0, IV)))).

Theorem: if c is collision-free, then SHA-256 is collision-free.