COMP5563 Chap.5 Message Authentication and Integrity
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.
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
- 2Use the observed tag as the first chaining state.
- 2Choose a block cancelling that state.
- 2Show the final block-cipher input repeats x.
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.
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.
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.