Cryptography 101: Data Integrity and Authenticated Encryption

This is the second post in a 3 part series on basics of cryptography based on Stanfords online coursera Cryptography I course as taught by Dan Boneh. The series is outlined as follows:

1. Symmetric Encryption
2. Data Integrity & Authenticated Encryption
3. Asymmetric Encryption with Public/Private Key Pairs

These blogposts are sequential and it’s crucial to understand the concepts in the previous post before moving onto any subsequent posts.

Message Integrity

In the previous post we covered a lot about encryption. Another core concept in cryptography is message integrity. While encryption keeps messages confidential, data integrity ensures full confidence that the data you are receiving is the actual valid data from the sender, and has not been tampered with or manipulated. There are many scenarios where you may want data integrity without encryption, such as protecting public data saved to your disk, or ensuring the banner ads you’re seeing haven’t been modified by malware. In this post we’ll explore the mechanics of data integrity and why encryption alone (without data integrity) cannot guarantee privacy of content.

Message Authentication Codes (MAC)

A MAC produces a type of digital signature that all parties can verify to ensure the data they are receiving is valid. This mechanism is made up of 3 core components:

1. Secret Key: All communicating parties share a secret key used throughout the MAC process.
2. MAC Signing Algorithm: This algorithm combines the secret key and the message to produce a short tag. This tag is essentially a digital signature that ensures a sent message corresponds to the shared secret key, hence came from the expected sender.
3. MAC Validation Algorithm: This algorithm takes as inputs: the secret key, message, and tag. It then outputs whether the tag is a valid signature based on the secret key and message.

This process is illustrated in the slide above. Alice generates a tag by combining the secret key (k) and plaintext message (m) via the signing algorithm S(key, message). This tag is sent along with the message. Since Bob already knows the secret key, he uses the validation algorithm to check whether the tag is in fact the valid tag based on the message and secret key.

Similar to the encryption schemes covered in the previous post, the algorithms are public knowledge and the secret key is what protects attackers from successfully deceiving recipients into accepting manipulated messages.

To generate a secure tag, you must use a secure PRF (defined in part 1) that results in a sufficiently long tag. Although the tag is relatively short, it cannot be too short, or else an attacker can simply guess the tag any number of times until it finally matches the message. To ensure a secure tag, it should be at least 80 bits. Since for each bit there’s 2 possibilities (either 1 or 0), that means an 80 bit tag has 2⁸⁰ (in the septillions!) unique possibilities. Therefore, the probability of someone guessing the tag trends towards impossible. To put this in perspective: there’s about 31 million seconds in a year. If you produced one million guesses per second, it would still take tens of billions of years to guess just one third of the possibilities. Very powerful! Pondering that is basically analogous to looking at the stars in the night sky. 0_o Although, it should be addressed that as time marches forward and technology improves, what measures as unbreakable is contested. According to the course though, for a simple MAC, 80 bits should do the trick.

MAC Constructions

Up until this point, the signing and validation algorithms have been a mysterious black box. So how do we create a secure tag from a message and a secret key? What happens inside the signing algorithm? To follow along properly, I highly recommend understanding the block cipher explanations from the first post in this series.

ECBC MAC Construction

Pictured above is encrypted CBC-MAC, or ECBC. This looks similar to the CBC mode of operation for block ciphers covered in Part I. This process requires two keys (k and k1). Represented in the blue boxes, F is a PRP (e.g. AES). The process is as follows:

1. We take the first block of the message (m[0]) and use F to combine our message block and secret key to result in an encrypted intermediate result.
2. Then we take this intermediate result and XOR it with our next message block, m[1].
3. This XOR’d value is once again processed via F along with our secret k. The process is repeated until we’ve reached our final block.
4. The final intermediate value is processed via F with the second secret key (k1). This results in the tag.

This final step of taking the the last result and processing it through our PRP with a second key k1 is there because otherwise the process becomes vulnerable to attack.

Without the final step, messages are vulnerable to chosen message attacks. Chosen message attacks is an attack model which presumes the attacker can obtain the tags for arbitrary one block messages (similar to chosen plaintext attacks covered in the first post). Using this method, an attacker could forge a two block message with the correct tag without knowing the secret key. To perform this forgery first we request tag t for arbitrary, one block message m such that t = S(k,m). Then we forge the correct tag for 2 block message: [m, m⊕ t]

As we saw in the first post, due to the nature of XOR (⊕), if we XOR two thing together, they will cancel out (i.e. 0101 ⊕ 0101 = 0000). With the ECBC process in mind, we forge the tag for message [m, m⊕ t] as follows:

1. Since we know t is the proper tag for m, hence the result of F(k, m), we know the intermediate result for the first block m is t. So we take t and XOR it with our second block m⊕ t. m⊕ t ⊕ t equals m since the t’s cancel out.
2. We take the XOR’d value which equals m and would perform F(k, m). We do not know the secret key, but we do know the output for m is t. Therefore, t is the tag for this 2 block message as well as one block message, [m].

NMAC Construction

NMAC is another MAC construction which is quite similar to ECBC. NMAC uses a PRF F (unlike CBC which uses a PRP) to combine our key k and message block m. The intermediate output produced by the PRF is the size of our key whereas in ECBC the PRP results match the size of the message block. In NMAC, all intermediate values serve as the key to the next iteration until we reach the final block. In the final step, we pad the result to become the length of a message block and use this value to serve as the message block in the final PRF operation that is used with a second key k1. Similar to ECBC, this final step is important so that attackers cannot forge new tags. Since the intermediate result serves as the key to the next iteration, an attacker could simply use the final tag as the key to further iterations, easily appending endlessly onto the original message.

HMAC Construction

HMAC uses a hash function, such as SHA-256, which is a deterministic procedure to compress chunks of data into a smaller pseudorandom chunks. For instance, SHA-256 transforms blocks of 521 bits into pseudorandom outputs of 256 bits. HMAC is based on the Merkle-Damgard construction which is a notion focused around collision resistance. Collision resistance is the idea that no two distinct inputs result in a matching output hash. Merkle-Damgard is built on the notion that if a hash function is collision resistant on a fixed amount of bytes, then the hash function is also collision resistant for much larger inputs given they are operated on in a chained sequence (as pictured below).

HMAC stands for Keyed-Hashing for Message Authentication. It has a similar structure to NMAC in that intermediate values serve as they key to subsequent operations. However, in HMAC, the first value is a fixed IV. This IV is a constant and public knowledge. HMAC also utilizes two secrets, each of which is constructed of the same secret key, which is then XOR’d with the ipad (“internal pad”) and opad (“outer pad”) respectively to make two distinct keys. The ipad and opad are both fixed constants. PB, represented in the final block above, signifies extra padding that gets added onto the final block if it is not long enough.

Authenticated Encryption

In order to communicate securely and maintain confidentiality over the internet, both encryption and integrity are crucial. You cannot have guaranteed confidentiality without integrity. Authenticated encryption combines encryption and MAC constructions to ensure full security. The following narrative uses a simplified TCP-IP construction to illustrate the necessity of message integrity to ensure confidentiality.

Imagine the scenario that Al (ponytail guy) is sending an encrypted packet to the destination machine that has a few processes it runs. On port 80 there’s a web server and another user named Bob is listening on port 25. When a packet comes in, the server decrypts it, reads the destination port, and forwards the data there.

If Bob is malicious, he could intercept Al’s packet, and without any knowledge of the secret key, modify the ciphertext so the destination decrypts to port 25 instead of port 80. Then the server will send Al’s unencrypted data over to Bob. If we’re using CBC with a random IV for encryption (as defined in the first post), all we need to do is tamper with the IV to modify the packet so it decrypts to the port 25 destination.

When decrypting CBC with a random IV (as shown above and in Part I), we XOR the IV with the intermediate result of c[0] to equal decrypted m[0]. At some bit in the first block, port 80 would be the result. So if we XOR these bits with 80, they equal 00 (since XOR-ing identical values cancel out). Then we can XOR those same bits with 25 (since XOR-ing some value with 0 equals the value). So we take IV and XOR it accordingly:

IV’ = ...IV…⊕ …80… ⊕ …25…

The packet will now decrypt as being intended for destination port 25. The server is completely naive to the fact our packet has been tampered with so Bob receives Al’s data. If we had used a MAC to verify our message authenticity, the server would immediately drop the message and take no action. Without it, our confidentiality is compromised. Hence, encryption without authenticity does not guarantee privacy.

Standard Constructions for Authenticated Encryption

Above are three protocols for authenticated encryption. All protocols have 2 independent keys: an encryption key and a MAC key.

• Option 1: In the SSL protocol, a tag is generated based on the plaintext message. Then the plaintext and tag both get encrypted.
• Option 2: In the IPsec protocol, first the plaintext gets encrypted, then a tag is generated for the ciphertext, but remains unencrypted.
• Option 3: Finally in the SSH protocol, a tag is generated on the plaintext, the plaintext gets encrypted but the tag remains unencrypted.

These 3 protocols are sometimes referred to as mac-then-encrypt, encrypt-then-mac, and encrypt-and-mac respectively. Generally, the recommended method is the IPsec method. SSH can be ruled out as the most secure since MAC’s aren’t required to provide confidentiality. If the MAC construction reveals any information about the plaintext, this is no longer secure. SSL can be insecure against chosen ciphertext attacks, unless it is used with encryption constructions: randomized counter-mode or CBC with a random IV.

Standards of authenticated encryption have emerged and you should always follow a tried and tested standard rather than implement authenticated encryption on your own. These standards listed above are:

Galois/Counter Mode (GCM): Encrypt-then-Mac: This uses the Randomized Counter Mode (CTR) encryption scheme and MAC’s the ciphertext with the Carter-Wegman MAC, a very fast MAC construction not covered in this post.

Counter with CBC-MAC (CCM): Mac-then-Encrypt: MAC’s the plaintext with CBC-MAC then uses Randomized Counter Mode to encrypt the message plus tag. Both CBC-MAC and CTR here use AES in their process. As AES engines are built into most hardware processors this requires little code to implement. Used for encrypted Wifi in the 802.11i standard.

Encrypt-then-Authenticate-then-translate (EAX): Encrypt-then-Mac: Uses Randomized Counter Mode to encrypt the message and Mac’s the ciphertext using CMAC.

All these modes have a few things in common. Each mode uses a nonce that can never be repeated for a given key. This prevents attackers from resending an already verified packet. Since each packet needs a unique nonce, it would be invalid to send an identical packet twice.

In Conclusion

That concludes our high level overview of Authenticated Encryption! We reviewed the MAC process and summarized three (of many) MAC constructions: ECBC MAC, NMAC, and HMAC. Then we reviewed why encrypted messages are not private if they are not authenticated. Lastly, we went over common standards that have evolved for performing authenticated encryption. As always, it is better to utilize these tried and tested standards than try and do it yourself.

Thanks for reading 🌈