CYS406 · Chapter 7 · Annotated SlidesMACs and Hash Functions
Original
Overview

MACs and Hash Functions

Message authentication, MACs and their requirements, HMAC, one-way hash functions and their properties (preimage, second-preimage and collision resistance), attacks and the birthday paradox, UNIX password storage with salt, dictionary attacks, MD5 and the SHA family.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 49 slides
  1. 1 Slide 1
  2. 2 Message Security Requirements
  3. 3 Message Authentication
  4. 4 Message Authentication without message encryption
  5. 5 Message Authentication Code (MAC)
  6. 6 Message Authentication Code (MAC)
  7. 7 Message Authentication Code (MAC)
  8. 8 Message Authentication Code (MAC)
  9. 9 Requirements for MACs
  10. 10 HMAC Design Objectives
  11. 11 HMAC Algorithm
  12. 12 HMAC Security
  13. 13 One-way hash function
  14. 14 Hash functions
  15. 15 Hash Functions are Versatile
  16. 16 Hash functions, definition
  17. 17 Properties of good hash functions
  18. 18 Desirable properties of hash function
  19. 19 Hash Functions & Authenticated Encryption
  20. 20 Hash Functions &
  21. 21 Hash Function Requirements
  22. 22 Attacks on Hash Functions
  23. 23 Example
  24. 24 UNIX Password System
  25. 25 Unix passwords
  26. 26 Salt
  27. 27 Unix passwords - crypt(3)
  28. 28 Unix crypt(3)
  29. 29 UNIX Password security
  30. 30 Unix passwords - salt
  31. 31 Dictionary Attack
  32. 32 Dictionary Attack – some numbers
  33. 33 Hash Algorithms
  34. 34 Hash Algorithms - general structure
  35. 35 MD5 Message Digest Algorithm
  36. 36 MD5 Message Digest Algorithm
  37. 37 MD5 Message Digest Algorithm
  38. 38 MD5 Message Digest Algorithm
  39. 39 MD5 Reference
  40. 40 MD5 Message Digest Algorithm
  41. 41 MD5 Message Digest Algorithm
  42. 42 Secure Hash Algorithm
  43. 43 Revised Secure Hash Standard
  44. 44 SHA Versions
  45. 45 Secure Hash Algorithm
  46. 46 Secure Hash Algorithm
  47. 47 Secure Hash Algorithm
  48. 48 SHA-512 Overview
  49. 49 SHA-512 Compression Function
Slide 1 / 49

Slide 1

Slide 1: Slide 1
Slide 2 / 49

Message Security Requirements

Slide 2: Message Security Requirements
Slide 3 / 49

Message Authentication

Slide 3: Message Authentication
Slide 4 / 49

Message Authentication without message encryption

Slide 4: Message Authentication without message encryption
Slide 5 / 49

Message Authentication Code (MAC)

Slide 5: Message Authentication Code (MAC)

Notes

  1. MAC: a short tag computed from the message AND a shared secret key; proves integrity and origin.

Exam angle

PredictionQ1

A MAC provides:

Slide 6 / 49

Message Authentication Code (MAC)

Slide 6: Message Authentication Code (MAC)
Slide 7 / 49

Message Authentication Code (MAC)

Slide 7: Message Authentication Code (MAC)
Slide 8 / 49

Message Authentication Code (MAC)

Slide 8: Message Authentication Code (MAC)
Slide 9 / 49

Requirements for MACs

Slide 9: Requirements for MACs
Slide 10 / 49

HMAC Design Objectives

Slide 10: HMAC Design Objectives
Slide 11 / 49

HMAC Algorithm

Slide 11: HMAC Algorithm
Slide 12 / 49

HMAC Security

Slide 12: HMAC Security
Slide 13 / 49

One-way hash function

Slide 13: One-way hash function
Slide 14 / 49

Hash functions

Slide 14: Hash functions
Slide 15 / 49

Hash Functions are Versatile

Slide 15: Hash Functions are Versatile
Slide 16 / 49

Hash functions, definition

Slide 16: Hash functions, definition
Slide 17 / 49

Properties of good hash functions

Slide 17: Properties of good hash functions

Notes

  1. Properties: preimage resistance (one-way), second-preimage resistance (weak collision), collision resistance (strong collision).

Exam angle

PredictionQ1

Finding ANY two messages with the same hash breaks:

Slide 18 / 49

Desirable properties of hash function

Slide 18: Desirable properties of hash function
Slide 19 / 49

Hash Functions & Authenticated Encryption

Slide 19: Hash Functions & Authenticated Encryption
Slide 20 / 49

Hash Functions &

Slide 20: Hash Functions &
Slide 21 / 49

Hash Function Requirements

Slide 21: Hash Function Requirements
Slide 22 / 49

Attacks on Hash Functions

Slide 22: Attacks on Hash Functions

Notes

  1. Birthday attack: collisions take about 2^(n/2) tries for an n-bit hash, so 128-bit hashes give only ~64-bit collision security.

Exam angle

PredictionQ1

For a 160-bit hash, a birthday attack needs about:

Slide 23 / 49

Example

Slide 23: Example
Slide 24 / 49

UNIX Password System

Slide 24: UNIX Password System
Slide 25 / 49

Unix passwords

Slide 25: Unix passwords
Slide 26 / 49

Salt

Slide 26: Salt

Notes

  1. Salt: a random value stored with each password hash; identical passwords give different hashes and precomputed tables fail.

  2. Seen again This deck, slide 31: dictionary attacks

Slide 27 / 49

Unix passwords - crypt(3)

Slide 27: Unix passwords - crypt(3)
Slide 28 / 49

Unix crypt(3)

Slide 28: Unix crypt(3)
Slide 29 / 49

UNIX Password security

Slide 29: UNIX Password security
Slide 30 / 49

Unix passwords - salt

Slide 30: Unix passwords - salt
Slide 31 / 49

Dictionary Attack

Slide 31: Dictionary Attack

Notes

  1. Dictionary attack: hash common words and compare. Salt + slow hashes make it expensive.

Slide 32 / 49

Dictionary Attack – some numbers

Slide 32: Dictionary Attack – some numbers
Slide 33 / 49

Hash Algorithms

Slide 33: Hash Algorithms
Slide 34 / 49

Hash Algorithms - general structure

Slide 34: Hash Algorithms - general structure
Slide 35 / 49

MD5 Message Digest Algorithm

Slide 35: MD5 Message Digest Algorithm

Notes

  1. MD5: 128-bit digest, 512-bit blocks. Broken (collisions); don’t use for security.

Slide 36 / 49

MD5 Message Digest Algorithm

Slide 36: MD5 Message Digest Algorithm
Slide 37 / 49

MD5 Message Digest Algorithm

Slide 37: MD5 Message Digest Algorithm
Slide 38 / 49

MD5 Message Digest Algorithm

Slide 38: MD5 Message Digest Algorithm
Slide 39 / 49

MD5 Reference

Slide 39: MD5 Reference
Slide 40 / 49

MD5 Message Digest Algorithm

Slide 40: MD5 Message Digest Algorithm
Slide 41 / 49

MD5 Message Digest Algorithm

Slide 41: MD5 Message Digest Algorithm
Slide 42 / 49

Secure Hash Algorithm

Slide 42: Secure Hash Algorithm
Slide 43 / 49

Revised Secure Hash Standard

Slide 43: Revised Secure Hash Standard
Slide 44 / 49

SHA Versions

Slide 44: SHA Versions

Notes

  1. SHA-1: 160-bit (broken). SHA-2: SHA-224/256/384/512. SHA-512 processes 1024-bit blocks in 80 rounds.

Exam angle

PredictionQ1

The digest size of SHA-256 is:

Slide 45 / 49

Secure Hash Algorithm

Slide 45: Secure Hash Algorithm
Slide 46 / 49

Secure Hash Algorithm

Slide 46: Secure Hash Algorithm
Slide 47 / 49

Secure Hash Algorithm

Slide 47: Secure Hash Algorithm
Slide 48 / 49

SHA-512 Overview

Slide 48: SHA-512 Overview
Slide 49 / 49

SHA-512 Compression Function

Slide 49: SHA-512 Compression Function