Cryptographic Hash Functions

A hash function must be able to:

• takes a string as input
• generate output that is a fixed size
• generate the output quickly

In order to be secure, a cryptographic hash function must be:

• collision-free
  • H(x) != H(y)
  • The hash of x cannot equal the hash of y
  • There are no hash functions that are collision free, but for the best out there, the probability of collisions is low
• hiding property
  • if you're given the output of the H(x) function, it's impossible to find x
  • H(r | x): if H(r) is concatenated with x, it's infeasible to find x.
  • Envelope metaphor: the message is sealed in an envelope and hidden by the paper on the outside
• puzzle-friendly
  • given an id (from high min-entropy distribution*) and a target set Y
  • No solving strategy is any better than trying random values for x

* Chosen from a set of numbers that has a large distribution. Lots of different possibilities that are spread out from one another.

• Bitcoin uses the SHA-256 hash function
  • Breaks the input into blocks, smashes something on the end, and creates a has. It does this 3 times (?)