The Hong Kong Polytechnic University · FACULTY OF COMPUTER SCIENCE

COMP5563 Chap.5 Message Authentication and Integrity

- one subject, every graph, every model, every mark
6 Chapters5-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 5 of 5 · COMP5563

Message Authentication and Integrity

Generate, verify, reject

A message authentication code uses a shared key to tag a precisely encoded message and to verify a received pair. Security prevents an efficient chosen-message adversary from producing a valid tag for a new message except with negligible probability.

Verification must occur before unauthenticated data drives parsing or business action.

Extend with proof, not improvisation

PRF-MAC protects fixed-length messages and makes tag guessing explicit. Variable-length constructions must bind order, position and length.

Raw CBC-MAC exposes a chaining state that enables extension, while ECBC, NMAC, PMAC and Carter-Wegman use finalisation, masks or universal hashing to protect long domains.

Authenticate business meaning

The tag must cover an unambiguous encoding of version, type, identities, nonce, amount, currency and length where those fields affect action. Authenticating only a payload can leave its context editable.

Sender and receiver must interpret identical bytes identically.

Count guesses globally

An ideal n-bit tag gives blind one-try success near 2^-n, but many attempts accumulate. Tag length, rate limits, monitoring and key rotation jointly determine exposure.

Shared keys require counting attempts across every endpoint in the trust domain.

Keep freshness separate

Replaying an old genuine message is not a MAC forgery. Protected transaction identifiers, sequence numbers or timestamps need receiver-side state. Integrity proves unchanged origin under a key; anti-replay proves that an accepted instruction is new.

In this chapter

What this chapter covers

  • 01

    MAC syntax and correctness

  • 02

    Chosen-message unforgeability

  • 03

    PRF-MAC and tag guessing

  • 04

    Variable-length domain extension

  • 05

    CBC-MAC forgery and finalisation

  • 06

    PMAC and Carter-Wegman approaches

Worked example · free

Extend a one-block CBC-MAC message

Q [6 marks]. AskSia-authored practice. Raw CBC-MAC with zero IV gives one-block message x the tag t. Construct a new two-block message that verifies under t. The marks shown are an AskSia study allocation and are not the University's marking scheme.
Verification is a control boundary.Verification is a control boundary. The receiver must authenticate the full record and reject failures before decrypted or parsed fields can trigger any financial action. A MAC is a generate-and-verify process message mplus context tagt = S(k,m) receive m,tverify tag V(k,m,t)accept? yes: process recordno: reject before use
Verification is a control boundary. The receiver must authenticate the full record and reject failures before decrypted or parsed fields can trigger any financial action.
  • 2Use the observed tag as the first chaining state.
  • 2Choose a block cancelling that state.
  • 2Show the final block-cipher input repeats x.
Use x concatenated with x XOR t and submit tag t. After the first block the state is t. The next input is t XOR x XOR t = x, so the final output is E(k,x)=t. This is a deterministic new-message forgery.
Sia tip — When a tag equals an internal state, ask whether the next block can cancel it into a known input.
Glossary

Key terms

Message Authentication Code
A shared-key algorithm pair for generating and verifying integrity tags.
Tag Truncation
Reducing transmitted tag bits and thereby increasing generic guessing probability.
Universal Hashing
A keyed hash family with bounded collision probability, used with a pseudorandom mask in efficient MACs.
FAQ

Message Authentication and Integrity FAQ

Does a MAC prove who sent a message to a third party?

Not generally. Every holder of the shared key can generate valid tags, so a recipient cannot use the tag to prove which key holder created it. The MAC supplies shared-key integrity and authentication within the protocol.

Why is raw CBC-MAC restricted to fixed-length messages?

Its tag is the final chaining state. Across lengths, an adversary can use a valid state to craft a continuation that returns to a known block-cipher input. Length commitment or a proven finalisation construction removes that extension path.

How should tag length be selected?

Begin with the acceptable total forgery probability and the number of attempts allowed under one key. A blind one-try success floor is about 2^-n for an n-bit ideal tag, and many attempts accumulate risk.

Why is replay protection separate from a MAC?

An old genuine message and tag still verify, so replay does not create a new-message forgery. The protocol must authenticate a transaction identifier, sequence number or protected timestamp and keep receiver state that rejects reuse. The MAC protects integrity; the freshness mechanism decides whether an authentic record is new.

Study strategy

Exam move

Trace authentication as an end-to-end process rather than studying only the tag formula. Write the exact byte encoding of a payment record, including version, type, identities, nonce, currency, amount and length. Mark where the tag is generated, where verification occurs and which state prevents replay. For PRF-MAC, reconstruct the ideal-function argument and connect tag length to guessing probability.

For CBC-MAC, reproduce the extension attack from the cancellation equation, then explain how fixed length or separate finalisation changes the domain. Compare ECBC, NMAC, PMAC and Carter-Wegman by the problem each solves rather than by acronym. On every practice question, state whether confidentiality, integrity, origin within a shared-key group or freshness is being claimed.

End with the receiver action: reject failed verification before decryption output or parsed fields are allowed to affect balances or workflow. Add the number of permitted verification attempts to every tag-length calculation and aggregate attempts across services sharing a key. Test two serialisations for ambiguity by writing their exact bytes.

Then replay one genuine message and explain why it is not a forgery, which protected identifier detects it, and what receiver state must remember. This separates primitive unforgeability from protocol freshness.

Working through Message Authentication and Integrity in COMP5563? Sia is AskSia’s AI Computer Science tutor — ask any COMP5563 Message Authentication and Integrity question and get a clear, step-by-step explanation grounded in how COMP5563 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.

A+Everything unlocked
Unlocks this Bible + all 24 of your subjects at The Hong Kong Polytechnic University, plus 1,000+ more Bibles across the AskSia library.
Sia - your COMP5563 tutor, unlimited, worked the way the exam marks it
The full 5-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works