Bit-Flipping Attacks Against Stream Ciphers

Bit-Flipping Attacks Against Stream Ciphers

As I've already mentioned, a stream cipher encrypts and decrypts data, usually 1 bit at a time, by XORing the plaintext with the key stream generated by the stream cipher. Because of this, stream ciphers are susceptible to bit-flipping attack. Because stream ciphers encrypt data 1 bit at a time, an attacker could modify 1 bit of ciphertext and the recipient might not know the data had changed. This is particularly dangerous if someone knows the format of a message but not the content of the message.

Imagine you know that the format of a message is

hh:mm dd-mmm-yyyy. bbbbbbbbbbbbbbbbbbbbbbbbbbbb

where hh is hour using 24-hour clock, mm is minutes, dd is day, mmm is a three-letter month abbreviation, yyyy is a full four-digit year, and bbbbb is the message body. Squirt decides to send a message to Major. Before encryption using a stream cipher, the message is

16:00 03-Sep-2004. Meet at the dog park. Squirt.

NOTE
We assume that Squirt and Major have a predetermined shared key they use to encrypt and decrypt data.

As you can see, Squirt wants to meet Major at the dog park at 4 P.M. on September 3, 2004. As an attacker, you do not have the plaintext, only the ciphertext and an understanding of the message format. However, you could change one or more of the encrypted bytes in the time and date fields (or any field, for that matter) and then forward the changed message to Major. There would be no way for anyone to detect that a malicious change had taken place. When Major decrypts the message, the time will not read 16:00, and Major will not make it to the dog park at the allotted time. This is a simple and possibly dangerous attack!

Solving Bit-Flipping Attacks

You can prevent bit-flipping attacks by using a digital signature or a keyed hash (explained shortly). Both of these technologies provide data-integrity checking and authentication. You could use a hash, but a hash is somewhat weak because the attacker can change the data, recalculate the hash, and add the new hash to the data stream. Once again, you have no way to determine whether the data was modified.

If you choose to use a hash, keyed hash, or digital signature, your encrypted data stream changes, as shown in Figure 8-5.

Figure 8-5. Stream cipher encrypted data, with and without integrity checking.

When to Use a Hash, Keyed Hash, or Digital Signature

As I've already mentioned, you can hash the data and append the hash to the end of the encrypted message, but this method is not recommended because an attacker can simply recalculate the hash after changing the data. Using keyed hashes or digital signatures provides better protection against tampering.

Creating a Keyed Hash

A keyed hash is a hash that includes some secret data, data known only to the sender and recipients. It is typically created by hashing the plaintext concatenated to some secret key or a derivation of the secret key. Without knowing the secret key, you could not calculate the proper keyed hash.

NOTE
A keyed hash is one kind of message authentication code (MAC). For more information, see What Are Message Authentication Codes at http://www.rsasecurity.com/rsalabs/faq/2-1-7.html.

The diagram in Figure 8-6 outlines how a keyed-hash encryption process operates.

Figure 8-6. Encrypting a message and creating a keyed hash for the message.

Developers make a number of mistakes when creating keyed hashes. Let's look at some of these mistakes and then at how to generate a keyed hash securely.

Forgetting to use a key

Not using a key whatsoever when using a keyed hash is a surprisingly common mistake this is as bad as creating only a hash! Do not fall into this trap.

Using the same key to encrypt data and key-hash data

Another common mistake, because of its ease, is using the same key to encrypt data and key-hash data. When you encrypt data with one key, K₁, and key-hash the data with another, K₂, the attacker must know K₁ to decrypt the data and must know K₂ to change the data. If you encrypt and key-hash the data with K₁ only, the attacker need only determine one key to decrypt and tamper with the data.

Basing K₂ on K₁

In some cases, developers create subsequent keys by performing some operation, such as bit-shifting it, on a previous key. Remember: if you can easily perform that operation, so can an attacker!

Creating a Keyed Hash

Both CryptoAPI and the .NET Framework classes provide support for key-hashing data. The following is some example CryptoAPI code that key-hashes data and uses an algorithm named hash-based message authentication code (HMAC). You can also find a similar code listing with the book's sample files in the folder Secureco2\Chapter08\MAC. More information about the HMAC algorithm can be found in RFC 2104 (http://www.ietf.org/rfc/rfc2104.txt).

/* MAC.cpp */ #include "stdafx.h" DWORD HMACStuff(void *szKey, DWORD cbKey, void *pbData, DWORD cbData, LPBYTE *pbHMAC, LPDWORD pcbHMAC) { DWORD dwErr = 0; HCRYPTPROV hProv; HCRYPTKEY hKey; HCRYPTHASH hHash, hKeyHash; try { if (!CryptAcquireContext(&hProv, 0, 0, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT)) throw; //Derive the hash key. if (!CryptCreateHash(hProv, CALG_SHA1, 0, 0, &hKeyHash)) throw; if (!CryptHashData(hKeyHash, (LPBYTE)szKey, cbKey, 0)) throw; if (!CryptDeriveKey(hProv, CALG_DES, hKeyHash, 0, &hKey)) throw; //Create a hash object. if(!CryptCreateHash(hProv, CALG_HMAC, hKey, 0, &hHash)) throw; HMAC_INFO hmacInfo; ZeroMemory(&hmacInfo, sizeof(HMAC_INFO)); hmacInfo.HashAlgid = CALG_SHA1; if(!CryptSetHashParam(hHash, HP_HMAC_INFO, (LPBYTE)&hmacInfo, 0)) throw; //Compute the HMAC for the data. if(!CryptHashData(hHash, (LPBYTE)pbData, cbData, 0)) throw; //Allocate memory, and get the HMAC. DWORD cbHMAC = 0; if(!CryptGetHashParam(hHash, HP_HASHVAL, NULL, &cbHMAC, 0)) throw; //Retrieve the size of the hash. *pcbHMAC = cbHMAC; *pbHMAC = new BYTE[cbHMAC]; if (NULL == *pbHMAC) throw; if(!CryptGetHashParam(hHash, HP_HASHVAL, *pbHMAC, &cbHMAC, 0)) throw; SetLastError() } catch(...) { dwErr = GetLastError(); printf("Error - %d\n", GetLastError()); } if (hProv) CryptReleaseContext(hProv, 0); if (hKeyHash) CryptDestroyKey(hKeyHash); if (hKey) CryptDestroyKey(hKey); if (hHash) CryptDestroyHash(hHash); return dwErr; } void main() { //Key comes from the user. char *szKey = GetKeyFromUser(); DWORD cbKey = lstrlen(szKey); if (cbKey == 0) { printf("Error you did not provide a key.\n"); return -1; } char *szData="In a hole in the ground..."; DWORD cbData = lstrlen(szData); //pbHMAC will contain the HMAC. //The HMAC is cbHMAC bytes in length. LPBYTE pbHMAC = NULL; DWORD cbHMAC = 0; DWORD dwErr = HMACStuff(szKey, cbKey, szData, cbData, &pbHMAC, &cbHMAC); //Do something with pbHMAC. delete [] pbHMAC; }

Creating a keyed hash in the .NET Framework is almost the same as creating a nonkeyed hash; the only difference is you include a key when creating a keyed hash:

HMACSHA1 hmac = new HMACSHA1(); hmac.Key = key; byte [] hash = hmac.ComputeHash(message);

In this example, key and message are provided elsewhere in the code and hash is the resulting HMAC.

IMPORTANT
When creating a keyed hash, use the operating system or the .NET Framework class libraries. It's much easier than doing the work yourself.

Creating a Digital Signature

Digital signatures differ from keyed hashes, and from MACs in general, in a number of ways:

• You create a digital signature by encrypting a hash with a private key. MACs use a shared session key.

• Digital signatures do not use a shared key; MACs do.

• You could use a digital signature for nonrepudiation purposes, legal issues aside. You can't use a MAC for such purposes because more than one party shares the MAC key. Either party having knowledge of the key could produce the MAC.

• Digital signatures are somewhat slower than MACs, which are very quick.

Despite these differences, digital signatures provide for authentication and integrity checking, just as MACs do. The process of creating a digital signature is shown in Figure 8-7.

Figure 8-7. Encrypting a message and creating a digital signature for the message.

Anyone who has access to your public key certificate can verify that a message came from you or, more accurately, anyone who has your private key! So you should make sure you protect the private key from attack.

CAPICOM offers an incredibly easy way to sign data and to verify a digital signature. The following VBScript code signs some text and then verifies the signature produced by the signing process:

strText = "I agree to pay the lender $42.69." Set oDigSig = CreateObject("CAPICOM.SignedData") oDigSig.Content = strText fDetached = TRUE signature = oDigSig.Sign(Nothing, fDetached) oDigSig.Verify signature, fDetached

Note a few points about this code. Normally, the signer would not verify the signature once it is created. It's usually the message recipient who determines the validity of the signature. The code produces a detached signature, which is just the signature and not a message and the signature. Finally, this code will use or prompt the user to select a valid private key with which to sign the message.

Digital signatures are a breeze in the .NET Framework. However, if you want to access a certificate a private key stored by CryptoAPI, you'll need to call CryptoAPI or CAPICOM directly from managed code because the System.Security.Cryptography.X509Certificates does not interoperate with CryptoAPI stores. A great example of how to do this appears in .NET Framework Security (Addison-Wesley Professional, 2002). (Details of the book are in the bibliography.) This book is a must-read for anyone doing security work with the .NET Framework and the common language runtime.

IMPORTANT
When hashing, MACing or signing data, make sure you include all sensitive data in the result. Any data not covered by the hash can be tampered with, and may be used as a component of a more complex attack.

IMPORTANT
Use a MAC or a digital signature to verify that encrypted data has not been tampered with.