▶ 8.5 Data Integrity and Digital Signatures
Consider the following:
Bob borrows $3 from Kevin. Bob writes himself a reminder note that says “I owe Kevin $3.” He saves it in a file on his USB drive. Bob encrypts the file with RC4 or some other stream cipher.
A week later he pays back the $3. Before he deletes the note, he looks at it again. Now it says “I owe Kevin $7.”
If Kevin knows exactly what the file says, he can change its contents bit by bit without knowing the encryption key. This is sometimes called the bit-flipping attack (FIGURE 8.18).
FIGURE 8.18 Bit-flipping attack on encryption with xor.
Because stream ciphers encrypt the data bit by bit, we can reverse a bit in the plaintext by reversing the corresponding ciphertext bit. In this particular case, we want to change the $3 to $7, tricking Bob into repaying an extra $4. This requires that we change a single bit in a single ASCII character in the encrypted file.
The lower bits of the ASCII character “3” are “0011,” which by itself is equal to three in binary. The lower bits of the ASCII character “7” are “0111,” which equals seven in binary. If we change that single bit from 0 to 1, we add 4 to the binary value. In the figure, we invert the ciphertext bit corresponding to that plaintext bit. When we decrypt the message, the “3” comes out as a “7.”
Bit-flipping works reliably only if two facts are true. First, we must be working with a stream cipher. If we decrypt the data one bit at a time, then we invert a decrypted plaintext bit by inverting the corresponding ciphertext bit.
Second, we must know exactly what the plaintext says, so that we change exactly the bits we want. Even if we don’t know what the entire encrypted file says, we might be able to make a few significant changes that don’t scramble the file’s contents. The recipient might detect our changes if the decrypted plaintext looks garbled.
We examined checksums, CRCs, and other ways to detect random errors. (See Section 5.4.1.) These techniques detect errors caused by failures of underlying hardware, and some errors caused by software flaws. Computers became useful only after they reached an incredibly high degree of internal reliability. Although modern computers, hard drives, USB sticks, and other devices are very reliable, there are still many cases where they need to check for errors.
However, checksums and CRCs are intended to detect accidental changes caused by unpredictable failures. They can’t detect intentional, malicious changes by themselves. If attackers are intent on tricking the system, they can simply recompute the error check to match the changed data.
8.5.1 Detecting Malicious Changes
To detect malicious changes, we must prevent attackers from knowing how to accurately revise the CRC or other error check value. The obvious approach is to add a secret to the process, as in FIGURE 8.19. Without knowing the secret, attackers won’t know how to accurately revise the check value.
FIGURE 8.19 Data encrypted with its checksum.
The attacker can’t modify both the text and the check value without knowing exactly what the file says. Any mistake could make the checksum fail. If the attacker does know exactly what the file says, then he can replace its contents with a different message and a new checksum, just by flipping appropriate bits as shown in Figure 8.18.
Software distributed on the internet occasionally takes a different approach; it publishes the check value on a website next to a link for the downloaded file. If Alice, for example, downloads a program, she can calculate the file’s check value and compare it with the value published on the website. This strategy poses a problem: What if an attacker replaces the good file with a subverted one whose check value matches the original file’s check value? This problem leads us to one-way hash functions.
One-Way Hash Functions
We encountered one-way hash functions when protecting passwords from disclosure. (See Section 6.2.1.) Although a checksum or CRC tries to detect random changes to a file, a one-way hash tries to detect any change to a file. If its contents change a little or a lot, its hash value changes unpredictably. Thus, an attacker can’t modify a file and preserve its hash value. Sites that publish check values for downloadable files usually publish an SHA or MD5 hash value. Although MD5 is no longer recommended for high-security applications, it still provides a much safer check value than we get from a CRC value.
Hash values are very large; the smallest is 16 bytes long, and more recent functions yield much longer results (as shown in Table 6.3). The large results are intended to make it as hard as possible to produce two different, but similar, documents that yield the same hash value.
For example, imagine that Bob uses a one-way hash that yields an 8-bit check value. He owes Kevin $10, and Kevin provides him with an IOU, based on the template shown in FIGURE 8.20. Bob computes the hash, saves it, and gives the IOU file to Kevin for safe keeping.
FIGURE 8.20 An IOU with an adjustable check value.
The flowery language allows Kevin to make numerous substitutions in the text, yielding hundreds of different hash values. If Kevin changes the amount from $10 to anything else, he can probably find a different flowery statement that yields the same hash value as the signed message. Kevin then replaces the original IOU message with the new one, and the original hash value doesn’t detect the difference.
Kevin’s trickery works because the output of the one-way hash is too small. An effective one-way hash yields so many possible values that it’s impractical to search for a document with a matching value. A 160-bit hash, like that produced by the SHA yields too large a search space. If Bob used SHA, Kevin would have to construct 2160 different versions of the file to try to find a matching hash. That isn’t practical.
Birthday Attacks
A more practical approach to this is the birthday attack. The name comes from the “birthday paradox,” a classic parlor game. If we have a group of about two dozen people, the odds are good that at least two have their birthday on the same day. This may not seem obvious, because the chances of someone having a particular birthday are 1 in 365. We narrow the odds if we search a group to find any two people with the same birthday.
This attack lets Kevin take advantage of the fact that he creates the IOU file. He doesn’t just create a single file and then search 256 alternatives for a match. Instead, he randomly creates files of both types until two of them yield the same hash value.
According to the birthday paradox, when we’re searching for a match among K elements, we only have to search 
random elements until a match becomes likely. If we have an n-bit number, then a match is likely if we search approximately 2n/2 elements. Therefore, in Kevin’s case, he’ll probably construct two matching IOUs after trying around 16 times.
If Bob decides to use a 64-bit hash value, Kevin’s work gets a lot harder, but it’s not really impossible. He has to search “only” about 4 billion alternatives (232) before he’s likely to hit a matching pair.
When we do this search for document check values, we search at random to try to find any two documents with the same check value. If we can find two such documents, one can masquerade as the other, based on its check value. This doesn’t necessarily yield a practical attack on documents protected with one-way hash values, but it illustrates a possible risk.
The birthday attack is the reason one-way hash values are so large. To avoid a birthday attack, the value must contain twice as many bits as the largest number of attempts in a practical birthday attack. If 280 guesses seem implausible, then a 160-bit hash value should be safe.
8.5.2 Detecting a Changed Hash Value
If Bob just saves the hash value in an IOU file, he won’t necessarily detect a malicious change. The forger could simply compute the new hash value that matches the new text. Bob would have to memorize a hash in order to tell if someone changed it.
Hash values aren’t easy to memorize; they are long, random-looking binary values. Such values are great for security, but terrible to remember. Bob needs to incorporate some secret information that only he knows into the process. If he encrypts the hash value with secret information, no one can change it reliably. FIGURE 8.21 illustrates the construction of an encrypted hash.
FIGURE 8.21 Encrypting a hash: two steps.
Bob can store the actual message in plaintext, assuming the actual information isn’t secret. The hash value will be an incomprehensible block of data that he stores with the readable text. He can compute the hash and encrypt it to check the integrity of the text.
If we use a strong one-way hash and effective encryption, the operation in Figure 8.21 should provide some protection. However, we can’t use a stream cipher in situations like this, because the attacker knows the message text. The hash value is vulnerable to a known plaintext attack. The attacker can simply recompute the hash on the current message, and xor the hash with the encrypted hash to recover the key stream. Then the attacker can compose a new message, calculate its hash, and use the key stream to reencrypt the corrected hash.
One way to avoid this is to use a strong block cipher instead of a stream cipher. We study block ciphers in Chapter 9.
Keyed Hash
A much easier approach avoids encryption altogether. Instead, we include the secret information in the hashed data. We call this a keyed hash. We don’t need to perform a separate encryption step, hash the passphrase, or incorporate a nonce. FIGURE 8.22 illustrates an early approach to do this.
FIGURE 8.22 Keying a hash: one step.
The process works as follows. First, we place a copy of the secret at the beginning of a buffer. Next, we place the text we want to protect in the buffer. We follow it with another copy of the secret. Then we compute the hash over the whole buffer, including both copies of the secret. We reduce risks from weaker hash functions if we place the secret at both the beginning and end of the text.
A keyed hash is easy to implement because it relies on only a single cryptographic function: the one-way hash. However, this is also a source of weakness. Although hash functions are designed to produce a different hash if someone omits the first or last few bytes, some functions are less reliable than others. Thus, the result might not always rely on the presence of the secret keys. Internet security protocols described in Chapter 13 use a more sophisticated technique for keyed hashing.
8.5.3 Digital Signatures
A keyed hash gives us a way to verify that some of our own data has not been modified by an attacker—or at least it hasn’t been modified by someone who doesn’t share the secret key. This technique is moderately useful, but it doesn’t let mutually suspicious people verify information.
For example, Bob can’t share a secret key with his bank in order to verify electronic checks or digitized bank statements. Bob could write the check and use his secret to “sign” it, and the bank could verify it with that same secret. Later, though, either Bob or the bank could forge a different version of the same check using the same secret key. The forged version could have a different amount, date, or recipient. It’s impossible to tell if the bank produced the forgery or if Bob did.
A digital signature, on the other hand, uses asymmetric keys to sign or verify digital data. If Bob has a bank account that accepts his digital signature, he uses his private key to sign his checks. Anyone can then use his public key to verify his signature (FIGURE 8.23).
FIGURE 8.23 Signing a check with a digital signature.
For example, Bob writes a $10 check to Kevin. He provides an electronic copy to Kevin, his bank, or both. When Kevin gets the check, he uses Bob’s public key to verify the check’s signature. When the bank gets the check, it also uses Bob’s public key to verify the signature. In fact, it doesn’t matter whether the bank gets a copy of the check from Bob, Kevin, or someone else. No matter how many hands the electronic check passes through, the digital signature confirms that it contains exactly what Bob said it should: the date, the amount, and “Pay Kevin.”
We create digital signatures with two cryptographic building blocks. In FIGURE 8.24, Bob creates a digital signature using his RSA private key. First, he calculates the one-way hash of the data to sign. Second, he encrypts the hash using his private key.
FIGURE 8.24 Constructing an RSA digital signature.
Anyone can verify the digital signature using Bob’s public key. For example, Bob’s bank can verify an electronically signed check, as shown in FIGURE 8.25. The bank recalculates the one-way hash and decrypts the digital signature. The two answers match if the check has not changed since Bob signed it.
FIGURE 8.25 Verifying an RSA digital signature.
Note that RSA is subject to the same weaknesses when encrypting a one-way hash as it is when encrypting a secret encryption key. In both cases, we must be sure to encrypt a value that contains more bits than the public key’s N value. This may involve either padding the hash value with additional, randomly generated data or using a sufficiently large hash value. As with key wrapping, there are established standards for constructing RSA digital signatures. We provide the strongest and safest signatures by following the latest standards and recommendations.
So far, we have used RSA public-key encryption to produce digital signatures, although this is not the only public-key algorithm for digital signatures. In the United States, NIST created the DSS, which provides an alternative to RSA. As noted, DSS implements a variant of the El Gamal cipher, which is based on Diffie–Hellman. When signing a document, the DSS requires a random input value in addition to the text being signed. Unlike a nonce, this value must be truly random and unpredictable by the attacker.
A DSS digital signature requires a similar process to an RSA signature. First, we compute a one-way hash of the document; then we find a random number to use. The DSS algorithm has three inputs: the hash value, the random number, and the signer’s private key.
The process becomes vulnerable if we ever reuse a random value for two different signatures. This is unlikely in practice, as long as we always choose a large, truly random number.
Nonrepudiation
A digital signature provides the strongest practical indication that the key’s owner signed the digital data. This is why some use digital signatures to provide nonrepudiation. If we can assume that only one person controls a particular private key, then we can argue that anything signed by that key was knowingly signed by that person.
In practice, unfortunately, we can’t absolutely assert that a particular person always controls what their private key will sign. Computer programs may be subverted, which could result in signing a document without the owner’s knowledge. We can only assert nonrepudiation if we can completely trust the computing system that applies the signature. Commercial systems rarely merit that level of trust.