FIT1093 Chap.4 Hash Functions and Message Authentication Codes
Hash Functions and Message Authentication Codes
Week 3 turns from keeping data secret to detecting when it has been changed or faked. On an insecure channel, modifications cannot be prevented, so the sender attaches a checksum and the receiver checks it.
The catch is that an attacker who changes the data can usually change an ordinary checksum too, which is why the useful checksums are computed with a secret key.
The chapter first covers cryptographic hash functions, which compress a message of any length into a short fixed-length digest. MD5 and SHA-1 are obsolete; SHA-2 and SHA-3 with 256 to 512-bit outputs are recommended.
A secure hash is one-way, so a digest does not reveal a matching message, and collision resistant, so nobody can find two messages with the same digest. Collisions always exist by the pigeonhole principle, and the birthday paradox shows that a generic search finds one after about 2 to the power n/2 tries for an n-bit hash, which is why output length matters so much.
A hash has no key, so anyone can compute it.
A message authentication code adds a shared secret key: the tag can only be produced by someone who knows the key, and the defining security property is unforgeability.
The lecture builds MACs in two ways, CMAC from a block cipher in a CBC-like mode, and HMAC from a hash function wrapped twice around the key, standardised as RFC 2104. Workshop 3 adds two warnings: a digest that travels with the file it protects proves nothing if the attacker controls both, and encryption alone is not a MAC, since counter-mode ciphertext can be altered bit by bit.
The recommended combination is encrypt-then-MAC with separate keys, or an authenticated encryption mode such as GCM.
What this chapter covers
- 01
Integrity and authenticity on a channel you cannot control
- 02
Hash function outputs, MD5 and SHA-1 versus SHA-2 and SHA-3
- 03
One-wayness and collision resistance
- 04
The pigeonhole principle and the birthday bound
- 05
MAC unforgeability, CMAC and HMAC
- 06
Why encryption alone does not give integrity
- 07
Encrypt-then-MAC and authenticated encryption
Worked example · free
Break a toy hash with an anagram
- 2LISTEN: 76 + 73 + 83 + 84 + 69 + 78 = 463, and 463 mod 100 = 63.
- 1SILENT uses exactly the same letters, so its sum is also 463 and its hash is also 63: a collision.
- 2Collision resistance fails because addition ignores order, and one-wayness fails because the last character can be chosen to hit any target value.
Key terms
- Hash Function
- A keyless function that maps a message of any length to a short digest of fixed length.
- Preimage Resistance
- The property that, given a digest, finding any message that hashes to it is computationally infeasible; also called one-wayness.
- Birthday Bound
- The rule of thumb that collisions in an n-bit hash appear after roughly 2 to the power n/2 random inputs.
- Unforgeability
- The MAC property that, without the key, producing a valid tag for any new message is computationally infeasible.
- HMAC
- A message authentication code built by hashing the padded key with the message in two nested passes, standardised as RFC 2104.
Hash Functions and Message Authentication Codes FAQ
Why can't a hash alone prove a file is genuine?
A hash has no key, so anyone can compute it. If an attacker can replace both the file and the digest, the receiver's check still matches. Only a keyed tag or a signature ties the value to the real sender.
What does the birthday paradox mean for hash length?
Collisions in an n-bit hash can be found with about 2 to the power n/2 attempts rather than 2 to the power n. A 256-bit hash therefore gives collision security of about 2 to the power 128 operations.
What is the difference between CMAC and HMAC?
CMAC builds a MAC from a block cipher such as AES using a CBC-style chain and two derived keys. HMAC builds one from a hash function, nesting two hash computations around the padded key and message.
Why is counter-mode encryption not a secure MAC?
Flipping a bit of counter-mode ciphertext flips the same bit of the decrypted plaintext. An attacker who knows the original amount can therefore change it to any chosen amount without the key, so the ciphertext proves nothing about integrity.
Assessment move
Draw a three-row comparison of hash, MAC and signature, and for each write what goes in, who can compute it, and what it proves; most questions in this chapter are answered by that table. Then practise the birthday estimate on several output lengths so you can quote collision effort instantly.
Work the counter-mode forgery once with your own bit strings, because seeing the keystream cancel out makes the integrity failure memorable. When reviewing Workshop 3, ask for each scenario which channel the attacker controls, since the answer decides whether a digest is enough or a keyed MAC is required.
Finish by writing the HMAC formula from memory and explaining in a sentence why the naive hash of key and message was not adopted.
Working through Hash Functions and Message Authentication Codes in FIT1093? Sia is AskSia’s AI Cybersecurity tutor — ask any FIT1093 Hash Functions and Message Authentication Codes question and get a clear, step-by-step explanation grounded in how FIT1093 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
