Hashing and message authentication

Introductions

• introductions of two students

Questions on the readings

The readings today are from Computer Security and the Internet, Chapter 2, sections 2.5, 2.6

Cryptographic hash functions

A cryptographic hash function takes an arbitrary length string as input and produces a fixed length hash as an output. The output is also called a message digest or fingerprint in some applications.

• desirable properties:

  • one-way or preimage resistance: For any given value h, it is computationally infeasible to find x such that H(x) = h

    • there are actually many inputs that map to a single output (since the output is fixed size), but it is still comptuationally infeasible to find them

  • second preimage resistance: For any given block x, it is computationally infeasible to find y ≠ x with H(y) = H(x)

  • collision resistance : it is computationally infeasible to find any pair (x, y) such that H(x) = H(y)

• Schneier (Secrets and Lies): “They are probably the single most useful tool in a cryptographer’s toolbox”

• MD5 is deprecated

  • shown to not be collision resistant, so not suitable for digital signatures or TLS certificates

• SHA-1 is also deprecated — discontinued by web browsers in 2017, by Microsoft for Windows Update in 2020

  • shown to not be collision resistant
  • chosen-prefix attack — given two different prefixes, p1 and p2, attacker can find two suffixes, s1 and s2, such that H(p1 | s1) = hash(p2| s2) — an attack in 2019 would cost $100,000

• SHA-2 and SHA-3 are considered secure

Digital signatures

When we use digital signatures, we typically sign a hash instead of the original message or file.

• hash needs to be collision resistant

Message authentication

A message authentication code covers both the integrity of the data and the identity of the party that sent the message (since the other party is the only one that shares a secret key).

• sender computes and sends a message authentication code (MAC), which the receiver verifies

• does not provide non-repudiation since either party could have created the message and MAC using the shared key

• HMAC builds a MAC from a hash function, e.g. HMAC-SHA256

  • H((K’ ⊕ opad) || H((K’ ⊕ ipad) || m))
    • H: a cryptographic hash function
    • m: the message to be authenticated
    • K’: H(K) if K is larger than the block size, otherwise K
    • opad: 0x5c5c5c…5c5c, one-block-long constant
    • ipad: 0x363636…3636, one-block-long constant
    • ⊕: XOR
    • ||: concatenation

• recommendation

  • if you need just a MAC, use HMAC
  • if you need encryption and a MAC, use AEAD, e.g. AES-GCM

Extra Reading

• Secure Hash Algorithms
• Hash Functions
• breaking SHA
  • from 2005, Chinese researchers discovered first SHA-1 collisions faster than brute force (2^69)
  • from 2017, Google can generate PDF files with the same SHA-1 hash 100,000 times faster than brute force
• Why I hate CBC-MAC
• Blake2 and Blake3 hash functions

Class exercises

We are using the Rust Crypto crates.

See the Rust Cryptography repo for SHA2 and SHA3 code examples.