Message Authentication Code (MAC)
A Message Authentication Code (MAC) is a short piece of information used to
authenticate a message and ensure its integrity. Essentially, it provides a way to
check that a message has not been altered during transmission and verifies the
sender's identity. A MAC is generated using a secret key and a cryptographic
algorithm, producing a fixed-size output, commonly known as a tag or checksum.
Importance of MAC in Digital Communication
Data Integrity: MACs ensure that the data received is exactly what was sent, with no
alterations or corruption during transit. Any modification in the message would
result in a different MAC, alerting the recipient to the potential tampering.
Authentication: By using a secret key known only to the sender and the receiver,
MACs authenticate the source of the message, ensuring it comes from a trusted
sender.
Security: In secure communication protocols, MACs play a crucial role in maintaining
confidentiality and preventing unauthorized access to data.
How Does MAC Work?
The process of generating and verifying a MAC involves several steps:
Message Preparation: The sender prepares the message that needs to be
transmitted.
Key Generation: A secret key, known only to the sender and the receiver, is used.
This key must be securely shared between the parties beforehand.
MAC Generation: The sender uses a MAC algorithm (such as HMAC, CMAC, etc.) to
combine the message with the secret key, generating a unique MAC value.
Transmission: The original message and the MAC are sent to the receiver.
Verification: Upon receiving the message and the MAC, the receiver uses the same
secret key and MAC algorithm to generate a new MAC for the received message. The
receiver then compares the newly generated MAC with the received MAC. If they
match, the message is authenticated and considered intact.
Applications of MACs
Beyond their fundamental role in securing communication channels, MACs have
found applications in various advanced security scenarios:
Digital Signatures: MACs can be used as building blocks for digital signatures. By
combining a message with a private key using a MAC algorithm, a digital signature
can be created. This signature can then be verified using the corresponding public
key, ensuring the authenticity and integrity of the signed message.
Data Integrity Verification: MACs play a crucial role in data integrity verification. They
can be used to ensure that stored data on a disk or transmitted data packets haven't
been modified without authorization. This is critical for maintaining data consistency
and preventing security breaches.
Message Replay Protection: MACs can offer a degree of protection against message
replay attacks. Since a valid MAC value is tied to a specific message and secret key,
an attacker cannot simply capture and replay a message with the same MAC as it
won't match the independently generated MAC at the receiver's end. However, it's
important to note that additional mechanisms like sequence numbers might be
necessary for robust replay protection.
Challenges and Considerations
While MACs are essential for secure communication, there are challenges and
considerations to keep in mind:
Key Management: Securely sharing and storing the secret key is crucial. If the key is
compromised, the security of the MAC is also compromised.
Algorithm Selection: Choosing the right MAC algorithm depends on the specific use
case and security requirements. For instance, HMAC is suitable for most general
purposes, while CMAC may be preferred in environments using block ciphers.
Performance: The performance of MAC algorithms can vary. In high-performance
environments, algorithms like PMAC, which leverage parallel processing, may be
more suitable.
Security: Ensuring the cryptographic strength of the MAC algorithm is vital. Using
weak or outdated algorithms can expose the system to attacks.
Message Authenticity
Message Authenticity is the assurance that a message received was indeed created
by the claimed sender and that it has not been altered in transit. It's different from
confidentiality (keeping the message secret). You might not care if someone sees a
command, but you absolutely care if someone can change it from "transfer $10" to
"transfer $10,000".
Malleability
Malleability is a property of a cryptographic system where it is possible to transform
a ciphertext (encrypted message) into another ciphertext that decrypts to a related
plaintext, without knowing the key.
Authenticity problem: If a cipher is malleable, an attacker can intercept a valid,
encrypted message, tweak it, and produce a new, fraudulent message that will
decrypt to something meaningful and different. The receiver has no way of knowing
the message was tampered with.
Example: A simple stream cipher or one-time pad is highly malleable. If you flip a bit
in the ciphertext, the same bit will be flipped in the decrypted plaintext. An attacker
can change "YES" to "NO" without any difficulty.
Goal: We need non-malleable encryption or a separate mechanism to detect any
tampering. This is where MACs come in.
Message Authentication Codes
A Message Authentication Code (MAC) is a cryptographic checksum that is sent
alongside a message to ensure authenticity and integrity.
How it works:
Sender and Receiver share a secret key, K.
Generation: The sender computes a short tag T = MAC(K, M) for the message M.
Transmission: The sender sends (M, T).
Verification: The receiver computes T' = MAC(K, M) on the received M. If T' equals
the received T, the message is authentic; otherwise, it is rejected.
Security Goal: It should be computationally infeasible for an attacker who doesn't
know K to forge a valid (M, T) pair, even after seeing many valid pairs (M1, T1), (M2,
T2), ....
Existential Unforgeability
Existential Unforgeability under an Adaptive Chosen-Message Attack (EUF-CMA) is
the gold standard security definition for MACs.
A MAC is secure (EUF-CMA) if an attacker, even after tricking you into generating
MACs for a bunch of messages they pick, cannot create a valid MAC for a single new
message that you have never MACed for them before.
Existential Unforgeability: The attacker's goal is to forge a valid MAC tag for any
message—even a meaningless one—that they have not previously seen a valid tag
for. They don't get to choose which message to forge; any new message is a win for
them.
Adaptive Chosen-Message Attack: This is the power we give to the attacker. The
attacker can ask for MAC tags on any messages of their choice, and they can adapt
their choices based on the tags they've seen so far. This is a very strong attack
model.
HMAC
HMAC is a specific construction for creating Message Authentication Codes using
cryptographic hash functions. It's designed to be secure even if the underlying hash
function has some weaknesses, making it one of the most widely used and trusted
MAC algorithms.
HMAC as a security envelope:
First, the message is sealed inside with one layer of security
Then, the entire package is sealed again with another layer
This double protection makes it extremely resistant to tampering
How HMAC Works:
HMAC follows a specific standardized structure that processes the message twice
with the hash function, using the secret key in both stages.
The HMAC Formula:
HMAC(K, m) = H( (K ⊕ opad) || H( (K ⊕ ipad) || m ) )
Where:
H = Cryptographic hash function (SHA-256, SHA-1, etc.)
K = Secret key
m = Message
opad = Outer padding (constant value)
ipad = Inner padding (constant value)
⊕ = XOR operation
|| = Concatenation (joining bytes together)
CBC-MAC
Message Blocks: M₁ M₂ M₃ ... Mₙ
│ │ │ │
▼ ▼ ▼ ▼
IV (00..0) ──→⊕──→┌─┐ ─→⊕──→┌─┐ ─→⊕──→ ... ──→⊕──→┌─┐
│ │E│ │ │E│ │ │ │E│
│ │n│ │ │n│ │ │ │n│
│ │c│ │ │c│ │ │ │c│
│ │r│ │ │r│ │ │ │r│
│ │y│ │ │y│ │ │ │y│
│ │p│ │ │p│ │ │ │p│
│ │t│ │ │t│ │ │ │t│
│ └─┘ │ └─┘ │ │ └─┘
│ │ │ │ │
│ ▼ │ │ ▼
│ C₁ │ │ Cₙ (MAC Tag)
│ │ │
└────────────────────────┴───────┘
Feedback Links
Step-by-Step Process
Initialization Phase
Message Preparation: The input message is divided into equal-sized blocks (M₁,
M₂, ..., Mₙ)
Padding: If the last block is shorter than the block size, it's padded using a standard
method (like PKCS#7)
IV: CBC-MAC uses a fixed Initialization Vector - typically all zeros (00...0)
Processing Phase
First Block (M₁):
M₁ ⊕ IV → Encrypt with Key K → C₁
The first message block M₁ is XORed with the IV
The result is encrypted using the block cipher (e.g., AES) with secret key K
Output: C₁ (first ciphertext block)
Subsequent Blocks (M₂, M₃, ..., Mₙ):
For each block i (from 2 to n):
Mᵢ ⊕ Cᵢ₋₁ → Encrypt with Key K → Cᵢ
Each message block Mᵢ is XORed with the previous ciphertext block Cᵢ₋₁
The XOR result is encrypted with the same key K
This creates the chaining effect where each block depends on all previous blocks
Final Output
The last ciphertext block (Cₙ) becomes the MAC Tag
Only this final block is used as the authentication tag
All intermediate ciphertext blocks (C₁ through Cₙ₋₁) are discarded
Mₙ ⊕ Cₙ₋₁ = [last block] ⊕ [previous ciphertext]
Encrypt(result, K) = Cₙ = MAC Tag
ECBC-MAC
Message Blocks: M₁ M₂ M₃ ... Mₙ
│ │ │ │
▼ ▼ ▼ ▼
IV (00..0) ──→⊕──→┌─┐ ─→⊕──→┌─┐ ─→⊕──→ ... ──→⊕──→┌─┐
│ │E│ │ │E│ │ │ │E│
│ │n│ │ │n│ │ │ │n│
│ │c│ │ │c│ │ │ │c│
│ │r│ │ │r│ │ │ │r│
│ │y│ │ │y│ │ │ │y│
│ │p│ │ │p│ │ │ │p│
│ │t│ │ │t│ │ │ │t│
│ ││ │ ││ │ │ ││
│ │K₁│ │ │K₁│ │ │ │K₁│
│ └─┘ │ └─┘ │ │ └─┘
│ │ │ │ │
│ ▼ │ │ ▼
│ C₁ │ │ Cₙ
│ │ │ │
└────────────────────────┴───────┘ │
│
▼
┌─┐
│E│
│n│
│c│
│r│
│y│
│p│
│t│
││
│K₂│
└─┘
│
▼
Final MAC Tag
Step-by-Step Process
Initialization Phase
Message Preparation: Input message divided into equal-sized blocks (M₁, M₂, ..., M ₙ)
Padding: Last block padded if shorter than block size
IV: Fixed initialization vector (typically all zeros: 00...0)
Two Independent Keys: K₁ (for CBC processing) and K₂ (for final encryption)
CBC Processing Phase (Same as Basic CBC-MAC)
First Block:
text
M₁ ⊕ IV → Encrypt with Key K₁ → C₁
Subsequent Blocks:
For i = 2 to n:
Mᵢ ⊕ Cᵢ₋₁ → Encrypt with Key K₁ → Cᵢ
This creates the chaining dependency where each block's encryption depends on all
previous blocks.
Final Encryption Phase (The Critical Enhancement)
Cₙ → Encrypt with Key K₂ → Final MAC Tag
The last ciphertext block from the CBC phase (Cₙ) is encrypted again using a different
key K₂.