Uses and abuses of cryptograph hashes

A whirlwind tour

by David Turner

Properties of hashes

  • One-way functions
  • Small, fixed-size output
  • Collision-resistant
  • Super-useful

Output size

  • SHA-1: 160 bits (20 bytes)
  • SHA-256: 256 bits (32 bytes)
  • SHA-3: arbitrary

Collisions

  • Two different inputs, same output
  • Given N possible outputs, ~N inputs give a 50% probability of collision
  • Assuming your hash function is good

Contents

74136fa137c00edf7166034ea2a0bc5a0d1d22b7

Contents

  • deduplication
  • content-addressed storage
  • data integrity (sometimes)
  • password storage
  • bitcoin
  • flipping coins over the telephone
  • bittorrent

Deduplication

  • Same hash implies same content
  • Store a mapping from hash to content location

Content-addressed storage

  • A file's hash is its name
  • Automatic naming
  • Automatic deduplication
  • Git

Data integrity

  • Protects against random data changes
  • Any change to your file will change the hash
  • But you have to control the hash

Data integrity (with teeth)

  • Keyed hash
  • Can only be reproduced with the secret
  • Protects against bad people
  • HMAC(K, m) = H((K xor opad) | H((K xor ipad) | m))

Data integrity (with teeth)

  • Keyed hash
  • Protects against bad people
  • Can only be reproduced with the secret
  • [APPROPRIATELY LONG BLACK BOX]

Hashing fast and slow

  • Hashing is usually fast
  • SHA-1: ~11 cycles per byte
  • Even faster on GPUs or ASICs
  • $50 = 10 GH/s

One-way in theory...

  • You can reverse a hash...
  • ...by trying lots of possible inputs...
  • ... like all possible 8-letter passwords!

Slow hashing

  • Add a "salt"
  • Repeatedly hash
  • Use lots of memory

Time is money

  • Bitcoin mining
  • Find some input where H(x) ends with ...000
  • More zeros = more work

Hashes of hashes

  • A hash validates its input
  • Yo, Dawg
  • Transitively
  • Git commits contain parent hashes

Merkle trees

  • Leaves contain hashes of content
  • Non-leaf nodes contain hashes of children
  • Git "trees" (directories) work like this
  • Fine-grained corruption detection

Bittorrent and Merkle trees

To validate a chunk, we need
  • The chunk's hash
  • The chunk's sibling's hash
  • The chunk's uncles' hashes
  • The root hash

Flipping coins over the telephone

Flipping coins over the telephone

Bit commitment

  • Committing to a value without revealing it
  • Commit to H(random number, value)
  • Later, reveal random number, value

Thank you