Introduction

Similarly as digital signatures, Message Authentication Codes provide message integrity and message authentication. When Alice generates a MAC and sends the message and MAC to Bob, Bob verifies that the message has integrity by calculating the MAC himself. He also authenticates the message, because only Alice could have generated the MAC.

Unlike digital signatures they do however not provide nonrepudiation, since all involved parties share the secret key \(k\). MAC's can be implemented using cryptographically secure hash functions (HMAC) or symmetric block ciphers like AES.

A MAC consists of a set of messages \(X\), a finite set of hash values \(Y\) and a key space \(K\). Each key \(k\) specifies a hash function \(h_k: X \rightarrow Y\). Let \(n=|X|\) and \(m=|Y|\) and \(l=|K|\).

Each MAC must have a property known as computation resistance: Even if an attacker knows \(n\) text-hash pairs \((x_n, h_k(x_n))\), it remains computationally unfeasible to find a valid MAC for a message without knowledge of the used key \(k\).

The goal of an attacker is to compute a valid MAC for a message \(x \in X\) without knowing the secret key \(k\). There are a series of different …

Continue reading