Digest functions

Give a fixed-length value from a variable-length text.

• Sort of text “fingerprint”

Produce very different values for similar texts.

• Cryptographic one-way hash functions.

Relevant properties:

• Preimage resistance.

  • Given a digest, it is infeasible to find an original text producing it.

• 2nd-preimage resistance.

  • Given a text, it is infeasible to find another one with the same digest.

• Collision resistance.

  • It is infeasible to find any two texts with the same digest.

• Birthday paradox.

Approaches

Merkle-Damgård construction

• Iterative compression.

• Collision-resistent, one-way compression functions.

• Length padding (1, followed by zeros, followed by length).

Sponge functions

• Absorption: update a finite internal state (entropy pool) from a variable-length, padded input stream.

• Squeezing: produce an arbitrary-length output from the internal state.

Common Algorithms

• MD5 (128 bits)

  • No longer secure! It’s easy to find collisions!

  • Disclaimer: it can be used when collisions are not an issue.

• SHA-1 (Secure Hash Algorithm, 160 bits)

  • Also no longer secure ... (collisions found in 2017).

• RIPEMD (128 and 160)

• SHA-2, aka SHA-256 / SHA-348 / SHA-512

• SHA-3 (Keccak)