In our last blog post, we saw that encryption alone isn't enough to protect data from malicious modifications. So what will?
The first solution that will provide security against tampering by malicious adversaries combines symmetric cryptography and a cryptographic hash function. In this construction, both the device generating the data (the sender) and the device verifying the data (the receiver) will share the same private key. The sender will run the data through the hash function to produce a digest, and then the sender will combine the data’s digest with its shared private key to produce a message authentication code (MAC). The sender transmits both the original data and the MAC to the receiver, who must now verify whether or not the data was altered in transit, and whether or not it was sent by the sender. The receiver generates its own MAC using the received data combined with its copy of the private key and compares its MAC with the sender’s MAC to see if they match.
There are different ways to construct MACs, but the most common is the Keyed-Hash MAC (HMAC) approach, illustrated below. In this diagram, the || symbol denotes concatenation, H is the hash function, K0 is the shared private key, and text is the data to be signed. The inner pad (ipad) and outer pad (opad) are constants defined in the NIST HMAC standard.
A natural question is, why is this complicated construction necessary? Why not just calculate the MAC as the hash of the key concatenated with the data, H(K || data)? The complete answer is outside of the scope of this introductory blog series, but in general the more complicated structure provides protection against length extension attacks and also removes the need for stronger assumptions about the properties of the hash function. The straightforward H(K || data) approach is, however, acceptable when the hash function is SHA-3 (Keccak), rather than the older but more common SHA-2 algorithm.
Informally, the HMAC guarantees the integrity and authenticity of the data by relying on the secrecy of the shared private key, and the hash function’s ability to succinctly describe the data.
If an adversary changed even a single bit in the data, on average about half of the output bits of the hash function would change. But how do we know the adversary didn’t just recompute the hash over the altered data, and include the updated hash in the MAC? So long as the adversary doesn’t know the shared private key K0, they can’t compute the MAC at all. Taken together, if the verifier’s computed MAC matches the MAC from the sender, they are convinced that (i) the original data has not been altered, and (ii) only someone with the shared private key K0 sent the data.
Note that if the system has more than two users that share the same private key K0, there is no way for a MAC to prove which one generated the data. Requiring each pair of users to share a distinct private key doesn’t scale well, resulting in O(n2) key pairs. Although the HMAC construction is very lightweight, requiring only a cryptographic hash function and the ability to store a private key, it is frequently desirable to know which particular device generated data. Our next construction provides that capability.
While MACs are very lightweight, they are only able to prove that someone with access to the shared private key generated the data. When more than two users share the same private key, it is no longer possible to determine which particular user generated the data. Although digital signatures will require more computational ability of a device, they have the benefit of uniquely identifying the sender of a message.
Rather than distribute a single shared private key to all the users, digital signatures construct a pair of keys that are unique to each individual user: a private key, known only to the user, and a mathematically related public key which is shared with all users. It’s easy for the user to generate the public key from their private key, but it’s computationally infeasible to recover a user’s private key with only knowledge of their public key.
This property is particularly useful for secure boot, as the device can verify the integrity of its boot code using only the author’s (e.g., ADI’s) public key and the signature over the code. Even if the memory contents of the device are extracted, the public key used to verify the boot code is not sensitive.
As with MACs, it’s much more efficient to compute a digital signature over a short digest of the data rather than the data itself, which may be very large. After generating the hash of the data, the signer performs operations using their private key to construct the digital signature. There are many different solutions for generating a digital signature, depending on the underlying mathematical framework. Rather than describe a particular construction, we will focus on the elements common to all of them.
Unlike MACs, digital signatures are not both constructed and verified by the same private key, as in the asymmetric setting the private key is known only to the user. To construct a digital signature, the user applies their private key in an operation over the hash (fingerprint) of the data.
To verify the digital signature, the receiver calculates the hash of the data and verifies the digital signature using the sender’s public key. A user’s public key is not sensitive, so it is available to all of the users of the system. With knowledge of someone’s public key, users can either encrypt a message to that user (see here for more details) or verify their signature over data. Similarly, a user can decrypt messages that were encrypted for them and construct a digital signature over messages using their private key.
Since each user is now associated with only a single public key, the key distribution problem is greatly simplified in comparison to the setting for MACs. Each user has only one public key associated with them, rather than a separate private key for each potential user with whom they may want to communicate.
Now that we've seen how to properly protect data integrity, let's review the key takeaways from this 3-part series. We've seen that although cyclic redundancy checks (CRCs) are lightweight and able to detect errors caused by benign events such as channel noise or unstable memory cells, they can be circumvented by an actively malicious adversary. Even encrypting the data along with its CRC isn’t sufficient. To protect the integrity and authenticity of our data, we must use cryptographically secure solutions designed to protect data against intentional modifications.
MACs are a lightweight solution, requiring devices to support only a cryptographic hash function and the ability to store a shared private key. However, it’s difficult for MACs to uniquely identify the author of data. Digital signatures require a bit more processing power, usually at least a hardware accelerator for finite field operations. However, they have the ability to uniquely identify the author of data while only requiring knowledge of a single public key for each user of the system, and they are required to support important features such as secure boot.
