Computer Security :: Lessons :: Message Authentication
Message authentication is a mechanism used to verify the integrity of a message. Message authentication ensures that data received are exactly the same as data sent. A message authentication code, or MAC, is the actual data used to verify the integrity of the message. The following attacks can occur on data transmitted over a network:
- Disclosure: Release of the message contents to a person or process not possessing the appropriate key.
- Traffic Analysis: Discovery of a pattern of traffic between parties. Similar to a timing attack.
- Masquerade: Insertion of messages into the network from a fraudulent source.
- Content Modification: Changes to the contents of a message.
- Sequence Modification: Any modification to a sequence of messages between parties.
- Timing Modification: Delay or replay of messages.
- Source/Destination Repudiation: Denial of transmission or receipt of a message.
Message authentication deals with items 3 through 6 in the preceding list. Message authentication functions typically fall into one of three categories: hash functions, message encryption, or message authentication codes.
Symmetric encryption assures that a message came from the purported sender because the sender is the only other party that possesses key K, as seen in the diagram below. If the message is received by party B, it cannot have been altered without the K to produce a different ciphertext. So symmetric encryption provides authentication, or integrity, as well as confidentiality.
It can be difficult to automatically determine if incoming ciphertext decrypts to intelligible plaintext. While plaintext in English can be determined, if the plaintext is a binary file storing information it becomes more challenging. One solution is append an error-detecting code, or frame check sequence (FCS), also known as a checksum, for each message. The source prepares a plaintext message and provides it as input to a function that produces an FCS. The FCS is appended to the message and the entire block in encrypted. The block is decrypted by the receiver and the result is treated as a plaintext message with an appended FCS. The message is then passed through the same function that generated the FCS and compares it to the FCS value to determine if the message is authentic.
The basic model of public-key encryption provides confidentiality but not authentication. The sender uses the receivers public key to encrypt the message and the receiver decrypts the message with their private key. Since only the receiver has the private key it protects the confidentiality of the message, but any opponent could use the public key to send a message pretending to be someone else.
Another model that provides authentication is sending a message using the sender's private key. The receiver can then decrypt the message using the sender's public key and the message must have come from the sender since they are the only person in possession of their own private key. This scheme does not provide any confidentiality, however, since anyone with the sender's public key can decrypt the message.
A model that provides confidentiality and authentication is the sender encrypting the message twice, once with their private key and once with the recipient's public key. The recipient then decrypts using their own private key and then the sender's public key. The disadvantage of this approach is the use of the encryption algorithm four times as opposed to two times.
The final way of authenticating data involves using a secret key to generate a small fixed-size block of data known as a cryptographic checksum, or MAC, that is appended to the message. The message plus the MAC are transmitted to the recipient. The recipient uses the same process on the received message to generate a new MAC, which is compared to the received MAC as a test of authentication. This process is similar to encryption, but the difference is that the MAC algorithm does not need to be reversible. The MAC can be added either before (b) or after (c) encryption.
Since symmetric encryption provides authentication, why would a MAC ever be necessary. Here are a few possible situations where a MAC is preferable:
- Applications where the same message is broadcast to several destinations. An example would be when a network is unavailable to users. It is cheaper to send the message as plaintext and have one destination responsible for authenticity.
- One side has a heavy load and cannot afford to decrypt all incoming messages. Messages are chosen at random for authentication.
- Authentication of a computer program to assure the integrity of the program.
A MAC function generates a fixed-length authenticator sometimes called a tag. Since a MAC function is a many-to-one function with more messages than tags. The MAC function must satisfy the following requirements:
- If an opponent observes the message and the tag, it should be computationally infeasible for the opponent to constructor a new message with the same tag.
- The tag should be uniformly distributed so there is a small probability that two messages will have the same tag.
- The MAC algorithm should not be weaker with respect to certain bits of the message than others so an opponent with the message and tag could attempt variations on the message that might produce the same tag.