Exploring Authenticated Encryption with Associated Data

Exploring Authenticated Encryption with Associated Data

In previous security solutions blogs, we discussed the importance of data integrity, and why encryption on its own does not provide semantic security. We introduced message authentication codes (MACs) and digital signatures as ways to authenticate data and protect it against modification.

In another blog,   enlightened us about lightweight cryptography for resource constrained environments such as in IoT and embedded systems. Most of these new lightweight algorithms are authenticated encryption with additional data (AEAD) ciphers which can both provide confidentiality through encryption as well as integrity (assurance the data has not been modified) and authenticity (assurance the data came from a particular entity) of the data which protect it against modification. In this blog, we will discuss AEAD encryption more in-depth.

What is AEAD?

Encryption only provides confidentiality but does not provide integrity or authenticity. Ciphertext is malleable if modifications can be made to the ciphertext which result in predictable modifications to the resulting plaintext. Changes can be made to the message, and these changes can be undetectable. Encrypting a message alone does not protect against this.

As an example, suppose that Alice wants to send Bob $100. The financial service encrypts transactions using a stream cipher, which works by XORing the plaintext transactions with a key stream. Each transaction has a fixed format, which specifies who is the recipient and the amount of money to be transferred. Alice encrypts the $100 transaction and sends the ciphertext to Bob.

An adversary intercepts the encrypted transaction and wants to modify the data without being detected. The adversary XORs the ciphertext with the digit 9 at the position of the thousands placeholder in the transaction format. Although the adversary can’t decrypt the message, knowledge of the transaction format tells them where to make the modification.

Bob receives the modified ciphertext and decrypts using his keystream. Due to the adversary’s modification, Bob receives a transaction in the amount of $9100, instead of $100. Since only encryption was used, there is no way for Bob to detect this modification!

To protect a message against modification, we must transmit additional data along with the message which can be used to authenticate the message. For AEAD, this usually takes the form of a message authentication code (MAC). The MAC must have the properties that make it difficult to find a valid MAC for any message without knowledge of the authentication key. It must also be difficult to find a second message (second preimage resistance) with the same MAC for a given message and MAC tag. It must also be difficult to find a pair of messages which result in the same MAC tag (collision resistance).

Keyed (cryptographic) hash functions are usually used to generate message authentication codes. When paired with encryption algorithms, they can be used to create an AEAD cryptosystem which can both encrypt and authenticate the data. Examples include AES CCM which combines AES CTR mode with AES CBCMAC for authentication. Another example is AES GCM which combines AES CTR mode with the GHASH algorithm for the MAC. In each of these, a MAC called a tag is computed over the transmitted message and sent together with the message. The tag is usually 16 bytes long for each message and adds this additional overhead to the message. The receiver of the message can validate the tag together with the message. If the message or tag have been modified in any way, then the receiver will reject the message as invalid. This will prevent tampering of the message.



2 TinyJAMBU (NIST lightweight crypto finalist) [TinyJAMBU: A Family of Lightwieght Authenticated Encryption Algorithms, Wu et al]

Additional Data

AEAD provides authenticity of data, and confidentiality is optional. It allows for the use of additional data to be sent together with encrypted data without having to encrypt it. The additional plaintext data and encrypted data are all authenticated together: if any part of either changes then it will result in an invalid tag. This is useful in many contexts, like in a packet header for example. If data is packetized and sent across a network, the packet often contains a header with metadata such as sender and receiver addresses. This data cannot be encrypted when it is sent because other nodes along the route need to be able to read this information so that the packet can be sent to the correct destination. We still want to protect this information against modification. AEAD allows this plaintext data to be authenticated along with the rest of the message even when parts of the message are encrypted. AEAD can even be used to send messages without encrypting any of the data, while still providing authenticity of the message.

Ease of use

One major benefit of AEAD is that authentication is built into the algorithm. This makes it harder for the implementer to make mistakes.

HMAC, which is a keyed hash function, can be used together with encryption for authenticated encryption. The data can be run through HMAC to generate a MAC which can be sent together with the data to authenticate it. This can be done with any algorithm, but one must be careful when combining cryptographic primitives. One potential mistake is not authenticating all the necessary data. For instance, there is usually an initialization vector used in the encryption algorithm. This needs to be included in the authenticated data.

The entirety of the data needs to be included. This can also be problematic if the data is variable length. There may be a field that the transmitter sends to the receiver which contains the length of the message. This length too needs to be included in the authenticated data so that parts of the message are not omitted, or parts added.

Another risk is side channel leakage when comparing the received tag to the computed tag. If the tag is computed byte per byte and exiting as soon as it reaches a mismatch then the time that this comparison takes depends on the number of bytes which match or mismatch. This may occur if the function memcmp() is used to naively compare the tag. This leaks information which may aid an attacker who can measure the execution time and determine the number of bytes which match or do not match. This is still a risk in most AEAD modes, but the comparison might be implemented in the cryptographic library in a secure manner.

Using an existing AEAD mode in a standard protocol reduces the risk of introducing vulnerabilities like these which may be difficult to anticipate.

Cryptographic Protocols

There are also entire classes of attacks for which AEAD on its own does not protect against. This can include replay attacks, reflection attacks, and other attacks. In a replay attack, an adversary can monitor traffic protected with AEAD and record it. The adversary can later attempt to resend a previously transmitted message that it observed without modifying it. The message has not been modified so it will have a valid MAC tag, and the AEAD algorithm will not detect that it had been sent by an adversary. These types of attacks cannot be solved at the algorithm level but are resolved by cryptographic protocols. The protocol may include something like a monotonically increasing packet number that the receiver checks before authenticating the message. If the receiver had already received the same packet number (or maybe had received a higher number already) it will reject the packet to prevent replay. This packet number or extra information can also be included in the additional authenticated data. AES CCM is also a cryptographic protocol under IEEE 802.15.4 and in certain configurations it can also prevent replay attacks and other protocol level attacks.

In summary, encryption only guarantees confidentiality, yet the integrity and authenticity of our data are also important to guarantee. AEAD modes provide this guarantee and are easier to use correctly than separate constructions. Cryptography is a minefield which is treacherous even for experts. Adopting AEAD encryption and only using standard cryptographic protocols is the best practice for protecting our data.