Message Authentication Codes #
Provides integrity and authenticity via Symmetric Key Cryptography.
We want to make sure that the data was not tempered with during transmission.
Procedure #
The sender uses the message and a shared key to generate a tag (MAC). \( k : key \)
\( m : message \) \( tag = S(k, m) \)Tag is then sent along with the message. The receiver uses the message, the shared key and the tag to verify the integrity of the message.
\( V(k, m, tag) \stackrel{?}{=} yes \)If a secret shared key is not used. An adversary can act as a man-in-the-middle and generate a new (message, tag) pair and the receiver will not be able to detect the tampering.
MAC Security & Chosen Message Attack #
The attacker in this scenario can choose messages to be hashed and get access to the corresponding tags.
The attackers goal is to achieve existential forgery which means creating a new valid message and a tag pair that was not generated by the sender.
If the attacker can not achieve this in a reasonable amount of time, the MAC is considered secure.
If the tag space is small, the attacker will be able to exhaustively search the tag space and find a valid tag for a new message rendering the MAC insecure.
CBC-MAC - Securing MAC using AES #
The algorithm utilizes two keys to generate a tag.
Key 1 is used to encrypt the message using AES in CBC mode. This is called raw-CBC.
Key 2 is used with the output of the last block to create the tag.
\( k_1 : key_1 \) \( k_2 : key_2 \) \( m : message \) \( tag = AES_{k_2}(AES_{k_1}(m)) \)Why do we need 2 keys? #
CBC-MAC with only one key can be broken by a chosen message attack.
An attacker who knows the message and its authentication tag can manipulate the last block of the message to produce a new message with the same tag.
For example, let’s say that an attacker intercepts the message “Hello” and its authentication tag “ABCD” from a system that uses CBC-MAC with a single key. The attacker can then create a new message “Goodbye” by constructing the following blocks: “Goo”, “dby”, and “eABCD”. The last block is constructed by XORing the original authentication tag with the final block of the “Goodbye” message. When this new message is authenticated using CBC-MAC, the system will accept it as valid because it has the same authentication tag as the original message.
This vulnerability exists because of the properties of the XOR operation.