Today: Cryptographic hash functions


Hash functions

Definition: A cryptographic hash function h maps bit-strings of arbitrary length to a fixed-length output in an efficient, deterministic, public, “random”, manner

h : {0,1}* -> {0,1}^d
      /\        /\
       \         \
        \         \--------- all strings of length d
          \---- all strings of any length >= 0

Ideal hash function: Random oracle (RO)

Random oracle theoretical model not achievable in practice (some proofs on the storage requirements I think are out there)

Oracle “in the sky”:

Many cryptographic schemes are proved secure in the Random Oracle Model (ROM), which assumes the existence of such an RO. Then, we assumes it is fine (a big assumption that some cryptographers don’t like) to replace the RO with a normal hash function like SHA in practice.

Hash function properties

These properties are expressed informally here:

  1. One way (OW) (pre-image resistance)
  2. (Strong) Collision-resistance (CR)
  3. Target (or weak) collision resistance (TCR) (2nd preimage resistance)
  4. Pseudo-randomness (PRF)
  5. Non-malleability (NM)

Theorem: If h is CR, then h is TCR.
Theorem: h is OW does not imply h is CR.
Theorem: h is CR does not imply h is OW.
Theorem: h is CR and h “compresses” implies h is OW.

See Phillip Rogaway’s paper for proofs and for more interesting properties of hash functions.


Password storage

File modification detector

Digital signatures



How can we build a commitment scheme?

Let the commitment be equal to C(x), where C(x) = h(r||x), r <--R-- {0,1}^256