Leanpub: Publish Early, Publish Often

Chapter 3: Symmetric Security

Symmetric cryptography is the simplest form of cryptography: all parties share the same key. It also tends to be the fastest type of cryptography. Fundamentally, the key used by a symmetric algorithm is a sequence of bytes that are used as the input to a transformation algorithm that operates on bits. Key distribution with symmetric cryptography is more difficult than with asymmetric cryptography as the transmission of sensitive key material requires a secure channel. In the next chapter, we’ll look at means of exchanging keys.

There are two components to symmetric encryption: the algorithm that provides confidentiality (which is a block or stream cipher), and the component that provides integrity and authenticity (the MAC algorithm). Most ciphers do not provide both in the same algorithm, but those that do are called Authenticated Encryption (AE), or Authenticated Encryption with Additional Data (AEAD), ciphers. In this chapter, we’ll consider four ciphersuites: NaCl, AES-GCM, AES-CTR with an HMAC, and AES-CBC with an HMAC; a ciphersuite is a selection of algorithms that we’ll use to provide security.

Indistinguishability

One of the properties of a secure encryption system is that it provides indistinguishability. There are two particular kinds of indistinguishability that are relevant here: IND-CPA, or indistinguishability under a chosen plaintext attack, and IND-CCA, or indistinguishability under a chosen ciphertext attack.

In IND-CPA, the attacker sends a pair of messages that are the same length to the server to be encrypted. The server chooses one of the messages, encrypts it, and sends back the ciphertext. The attacker should not be able to determine which message was encrypted. This property maintains confidentiality. It’s useful to consider the requirement that messages be the same length: the length of an encrypted message is related to the length of the original message in most ciphers. That is, encrypting a message does not hide its length.

In IND-CCA, the attacker submits ciphertexts of its own choosing that the server decrypts. After some observations, the attacker submits two challenge ciphertexts and the server picks one at random to decrypt and send back to the attacker. The attacker should not be able to distinguish which ciphertext the plaintext corresponds to. This attack is often seen in symmetric security as a padding oracle attack, in which the encryption scheme used does not include a message authentication code (such as AES-CBC without an HMAC), and can allow the attacker to recover the key used for encryption. There are two variants of IND-CCA; the first (IND-CCA1) means that an attacker cannot submit new ciphertexts after the challenge is sent. The second (IND-CCA2, or adaptive CCA) allows the attacker to continue submitting ciphertexts after the challenge. This may seem like a trivial difference, but a system that is IND-CCA1 secure but not IND-CCA2 secure enables the padding oracle attack.

Both the confidentiality component (such as AES-CBC) and the integrity and authenticity component (such as HMAC-SHA-256) are required for security.

Another indistinguishability requirement that is desirable is that our key material be indistinguishable from random, specifically from the uniform distribution.

Authenticity and integrity

Why are the integrity and authenticity components required? One common thing that crops up when people try to build a secure system is that only the confidentiality aspect is used: the programmer will use just AES with some non-authenticated mode (like the CBC, OFB, or CTR modes). AES ciphertexts are malleable: they can be modified and the receiver is often none the wiser. In the context of an encrypted instant message or email or web page, it might seem this modification would become obvious. However, an attacker can exploit the different responses between invalid ciphertext (when decryption fails) and invalid message (the plaintext is wrong) to extract the key. Perhaps the most well-known such attack is the padding oracle attack. In other cases, the invalid plaintext might be used to exploit bugs in the message handler. This is especially problematic in systems that use encryption to secure messages intended for automated systems.

Appending an HMAC or using an authenticated mode (like GCM) requires that the attacker prove they have the key used to authenticate the message. Rejecting a message that fails the MAC reduces the possibility of an invalid message. It also means that an attacker that is just sending invalid data has their message dropped before even wasting processor time on decryption.

To effectively authenticate with an HMAC, the HMAC key should be a different key than the AES key. In this book, we use HMACs with AES, and we’ll append the HMAC key to the AES key for the full encryption or decryption key. For AES-256 in CBC or CTR mode with an HMAC-SHA-256, that means 32 bytes of AES key and 32 bytes of HMAC key for a total key size of 64 bytes; the choice of HMAC-SHA-256 is clarified in a later section.

There are several choices for how to apply a MAC. The right answer is to encrypt-and-MAC:

Encrypt-and-MAC: in this case, we would apply a MAC to the plaintext, then send the encrypted plaintext and MAC. In order to verify the MAC, the receiver has to decrypt the message; this still permits an attacker to submit modified ciphertexts with the same problems described earlier. This presents a surface for IND-CCA attacks.
MAC-then-encrypt: a MAC is applied and appended to the plaintext, and both are encrypted. Note that the receiver still has to decrypt the message, and the MAC can be modified by modifying the resulting ciphertext, which is a surface for IND-CCA attacks as well.
Encrypt-then-MAC: encrypt the message and append a MAC of the ciphertext. The receiver verifies the MAC, and does not proceed to decrypt if the MAC is invalid. This removes the IND-CCA surface.

Moxie Marlinspike’s Cryptographic Doom Principle [Moxie11] contains a more thorough discussion of this.

Always use either an authenticated mode (like GCM), or encrypt-then-MAC.

NaCl

NaCl is the Networking and Cryptography library that has a symmetric library (secretbox) and an asymmetric library (box), and was designed by Daniel J. Bernstein. The additional Go cryptography packages contain an implementation of NaCl. It uses a 32-byte key and 24-byte nonces. A nonce is a number used once: a nonce should never be reused in a set of messages encrypted with the same key, or else a compromise may occur. In some cases, a randomly generated nonce is suitable. In other cases, it will be part of a stateful system; perhaps it is a message counter or sequence number.

The secretbox system uses a stream cipher called “XSalsa20” to provide confidentiality, and a MAC called “Poly1305”. The package uses the data types *[32]byte for the key and *[24]byte for the nonce. Working with these data types may be a bit unfamiliar; the code below demonstrates generating a random key and a random nonce and how to interoperate with functions that expect a []byte.

const (
       KeySize   = 32
       NonceSize = 24
)

// GenerateKey creates a new random secret key.
func GenerateKey() (*[KeySize]byte, error) {
    key := new([KeySize]byte)
    _, err := io.ReadFull(rand.Reader, key[:])
    if err != nil {
    	return nil, err
    }

    return key, nil
}

// GenerateNonce creates a new random nonce.
func GenerateNonce() (*[NonceSize]byte, error) {
    nonce := new([NonceSize]byte)
    _, err := io.ReadFull(rand.Reader, nonce[:])
    if err != nil {
    	return nil, err
    }

    return nonce, nil
}

NaCl uses the term seal to mean securing a message (such that it now is confidential, and that its integrity and authenticity may be verified), and open to mean recovering a message (verifying its integrity and authenticity, and decrypting the message).

In this code, randomly generated nonces will be used; in the key exchange chapter, this choice will be clarified. Notably, the selected key exchange methods will permit randomly chosen nonces as secure means of obtaining a nonce. In other use cases, this may not be the case! The recipient will need some way of recovering the nonce, so it will be prepended to the message. If another means of getting a nonce is used, there might be a different way to ensure the recipient has the same nonce used to seal the message.

var (
       ErrEncrypt = errors.New("secret: encryption failed")
       ErrDecrypt = errors.New("secret: decryption failed")
)

// Encrypt generates a random nonce and encrypts the input using
// NaCl's secretbox package. The nonce is prepended to the ciphertext.
// A sealed message will the same size as the original message plus
// secretbox.Overhead bytes long.
func Encrypt(key *[KeySize]byte, message []byte) ([]byte, error) {
    nonce, err := GenerateNonce()
    if err != nil {
    	return nil, ErrEncrypt
    }

    out := make([]byte, len(nonce))
    copy(out, nonce[:])
    out = secretbox.Seal(out, message, nonce, key)
    return out, nil
}

Decryption expects that the message contains a prepended nonce, and we verify this assumption by checking the length of the message. A message that is too short to be a valid encryption message is dropped right away.

// Decrypt extracts the nonce from the ciphertext, and attempts to
// decrypt with NaCl's secretbox.
func Decrypt(key *[KeySize]byte, message []byte) ([]byte, error) {
    if len(message) < (NonceSize + secretbox.Overhead) {
    	return nil, ErrDecrypt
    }

    var nonce [NonceSize]byte
    copy(nonce[:], message[:NonceSize])
    out, ok := secretbox.Open(nil, message[NonceSize:], &nonce, key)
    if !ok {
    	return nil, ErrDecrypt
    }

    return out, nil
}

Keep in mind that random nonces are not always the right choice. We’ll talk more about this in a chapter on key exchanges, where we’ll talk about how we actually get and share the keys that we’re using.

Behind the scenes, NaCl will encrypt a message, then apply a MAC algorithm to this ciphertext to get the final message. This procedure of “encrypt-then-MAC” is how to properly combine an encryption cipher and a MAC.

AES-GCM

If AES is required or chosen, AES-GCM is often the best choice; it pairs the AES block cipher with the GCM block cipher mode. It is an AEAD cipher: authenticated encryption with additional data. It encrypts some data, which will be authenticated along with some optional additional data that is not encrypted. The key length is 16 bytes for AES-128, 24 bytes for AES-192, or 32 bytes for AES-256. It also takes a nonce as input, and the same caveats apply to the nonce selection here. Another caveat is that GCM is difficult to implement properly, so it is important to vet the quality of the packages that may be used in a system using AES-GCM.

Which key size should you choose? That depends on the application. Generally, if there’s a specification, use the key size indicated. Cryptography Engineering ([Ferg10]) recommends using 256-bit keys; that’s what we’ll use here. Again, the security model for your system should dictate these parameters. In the AES examples in this chapter, changing the key size to 16 will suffice to switch to AES-128 (and 24 for AES-192). The nonce size does not change across the three versions.

Unlike most block cipher modes, GCM provides authentication. It also allows the for the authentication of some additional, unencrypted data along with the ciphertext. Given that it is an AEAD mode (which provides integrity and authenticity), an HMAC does not need to be appended for this mode.

The AEAD type in the crypto/cipher package uses the same “open” and “seal” terms as NaCl. The AES-GCM analogue of the NaCl encryption above would be:

// Encrypt secures a message using AES-GCM.
func Encrypt(key, message []byte) ([]byte, error) {
       c, err := aes.NewCipher(key)
       if err != nil {
               return nil, ErrEncrypt
       }

       gcm, err := cipher.NewGCM(c)
       if err != nil {
               return nil, ErrEncrypt
       }

       nonce, err := GenerateNonce()
       if err != nil {
               return nil, ErrEncrypt
       }

       // Seal will append the output to the first argument; the usage
       // here appends the ciphertext to the nonce. The final parameter
       // is any additional data to be authenticated.
       out := gcm.Seal(nonce, nonce, message, nil)
       return out, nil
}

This version does not provide any additional (unencrypted but authenticated) data in the ciphertext.

Perhaps there is a system in which the message is prefixed with a 32-bit sender ID, which allows the receiver to select the appropriate decryption key. The following example will authenticate this sender ID:

// EncryptWithID secures a message and prepends a 4-byte sender ID
// to the message.
func EncryptWithID(key, message []byte, sender uint32) ([]byte, error) {
       buf := make([]byte, 4)
       binary.BigEndian.PutUint32(buf, sender)
       
       c, err := aes.NewCipher(key)
       if err != nil {
               return nil, ErrEncrypt
       }
       
       gcm, err := cipher.NewGCM(c)
       if err != nil {
               return nil, ErrEncrypt
       }
       
       nonce, err := GenerateNonce()
       if err != nil {
               return nil, ErrEncrypt
       }

       buf = append(buf, nonce)
       buf := gcm.Seal(buf, nonce, message, message[:4])
       return buf, nil
}

In order to decrypt the message, the receiver will need to provide the appropriate sender ID as well. As before, we check some basic assumptions about the length of the message first, accounting for the prepended message ID and nonce.

func DecryptWithID(message []byte) ([]byte, error) {
       if len(message) <= NonceSize+4 {
               return nil, ErrDecrypt
       }

   // SelectKeyForID is a mock call to a database or key cache.
       id := binary.BigEndian.Uint32(message[:4])
       key, ok := SelectKeyForID(id)
       if !ok {
               return nil, ErrDecrypt
       }

       c, err := aes.NewCipher(key)
       if err != nil {
               return nil, ErrDecrypt
       }

       gcm, err := cipher.NewGCM(c)
       if err != nil {
               return nil, ErrDecrypt
       }

       nonce := make([]byte, NonceSize)
       copy(nonce, message[4:])

       // Decrypt the message, using the sender ID as the additional
       // data requiring authentication.
       out, err := gcm.Open(nil, nonce, message[4+NonceSize:], message[:4])
       if err != nil {
               return nil, ErrDecrypt
       }
       return out, nil
}

If the message header is altered at all, even if the new sender ID returns the same key, the message will fail to decrypt: any alteration to the additional data results in a decryption failure.

AES-CTR with HMAC

The last options you should consider, if you have a choice, are AES-CTR and AES-CBC with an HMAC. In these ciphersuites, data is first encrypted with AES in the appropriate mode, then an HMAC is appended. In this book, we assume the use of these ciphersuites only when required as part of a specification or for compatibility.

CTR also uses a nonce; again, the nonce must be only ever used once with the same key. Reusing a nonce can be catastrophic, and will leak information about the message; the system will now fail the indistinguishability requirements and therefore becomes insecure. If there is any question as to whether a nonce is unique, a random nonce should be generated. If this is being used for compatibility with an existing system, you’ll need to consider how that system handles nonces.

If you’re using AES-CTR, you’re probably following along with some sort of specification that should specify which HMAC construction to use. The general rule of thumb from the FIPS guidelines is HMAC-SHA-256 for AES-128 and HMAC-SHA-384 for AES-256; Cryptography Engineering ([Ferg10]) and [Perc09] recommend HMAC-SHA-256. We’ll use HMAC-SHA-256 with AES-256.

Here, we’ll encrypt by selecting a random nonce, encrypting the data, and computing the MAC for the ciphertext. The nonce will be prepended to the message and the MAC appended. The message will be encrypted in-place. The key is expected to be the HMAC key appended to the AES key.

const (
       NonceSize = aes.BlockSize
       MACSize = 32 // Output size of HMAC-SHA-256
       CKeySize = 32 // Cipher key size - AES-256
       MKeySize = 32 // HMAC key size - HMAC-SHA-256
)

var KeySize = CKeySize + MKeySize

func Encrypt(key, message []byte) ([]byte, error) {
       if len(key) != KeySize {
               return nil, ErrEncrypt
       }

       nonce, err := util.RandBytes(NonceSize)
       if err != nil {
               return nil, ErrEncrypt
       }

       ct := make([]byte, len(message))

       // NewCipher only returns an error with an invalid key size,
       // but the key size was checked at the beginning of the function.
       c, _ := aes.NewCipher(key[:CKeySize])
       ctr := cipher.NewCTR(c, nonce)
       ctr.XORKeyStream(ct, message)

       h := hmac.New(sha256.New, key[CKeySize:])
       ct = append(nonce, ct...)
       h.Write(ct)
       ct = h.Sum(ct)
       return ct, nil
}

In order to decrypt, the message length is checked to make sure it has a nonce, MAC, and a non-zero message size. Then, the MAC is checked. If it’s valid, the message is decrypted.

func Decrypt(key, message []byte) ([]byte, error) {
       if len(key) != KeySize {
               return nil, ErrDecrypt
       }

       if len(message) <= (NonceSize + MACSize) {
               return nil, ErrDecrypt
       }

       macStart := len(message) - MACSize
       tag := message[macStart:]
       out := make([]byte, macStart-NonceSize)
       message = message[:macStart]

       h := hmac.New(sha256.New, key[CKeySize:])
       h.Write(message)
       mac := h.Sum(nil)
       if !hmac.Equal(mac, tag) {
               return nil, ErrDecrypt
       }

       c, _ := aes.NewCipher(key[:CKeySize])
       ctr := cipher.NewCTR(c, message[:NonceSize])
       ctr.XORKeyStream(out, message[NonceSize:])
       return out, nil
}

AES-CBC

The previous modes mask the underlying nature of the block cipher: AES operates on blocks of data, and a full block is needed to encrypt or decrypt. The previous modes act as stream ciphers, where messages lengths do not need to be a multiple of the block size. CBC, however, does not act in this way, and requires messages be padded to the appropriate length. CBC also does not use nonces in the same way.

In CBC mode, each block of ciphertext is XOR’d with the previous block. This leads to the question of what the first block is XOR’d with. In CBC, we use a sort of dummy block called an initialisation vector. It may be randomly generated, which is often the right choice. We also noted that with the other encryption schemes, it was possible to use a message or sequence number as the IV: such numbers should not be directly used with CBC. They should be encrypted (using AES-ECB) with a separate IV encryption key. An IV should never be reused with the same message and key.

The standard padding scheme used is the PKCS #7 padding scheme. We pad the remaining bytes with a byte containing the number of bytes of padding: if we have to add three bytes of padding, we’ll append 0x03 0x03 0x03 to the end of our plaintext.

func pad(in []byte) []byte {
       padding := 16 - (len(in) % 16)
       for i := 0; i < padding; i++ {
               in = append(in, byte(padding))
       }
       return in
}

When we unpad, we’ll take the last byte, check to see if it makes sense (does it indicate padding longer than the message? Is the padding more than a block length?), and then make sure that all the padding bytes are present. Always check your assumptions about the message before accepting the message. Once that’s done, we strip the padding characters and return the plain text.

func unpad(in []byte) []byte {
       if len(in) == 0 {
               return nil
       }

       padding := in[len(in)-1]
       if int(padding) > len(in) || padding > aes.BlockSize {
               return nil
       } else if padding == 0 {
               return nil
       }

       for i := len(in) - 1; i > len(in)-int(padding)-1; i-- {
               if in[i] != padding {
                       return nil
               }
       }
       return in[:len(in)-int(padding)]
}

The padding takes place outside of encryption: we pad before encrypting data and unpad after decrypting.

Encryption is done by padding the message and generating a random IV.

func Encrypt(key, message []byte) ([]byte, error) {
       if len(key) != KeySize {
               return nil, ErrEncrypt
       }

       iv, err := util.RandBytes(NonceSize)
       if err != nil {
               return nil, ErrEncrypt
       }

       pmessage := pad(message)
       ct := make([]byte, len(pmessage))

       // NewCipher only returns an error with an invalid key size,
       // but the key size was checked at the beginning of the function.
       c, _ := aes.NewCipher(key[:CKeySize])
       ctr := cipher.NewCBCEncrypter(c, iv)
       ctr.CryptBlocks(ct, pmessage)

       h := hmac.New(sha256.New, key[CKeySize:])
       ct = append(iv, ct...)
       h.Write(ct)
       ct = h.Sum(ct)
       return ct, nil
}

Encryption proceeds much as with CTR mode, with the addition of message padding.

In decryption, we validate two of our assumptions:

The message length should be a multiple of the AES block size (which is 16). HMAC-SHA-256 produces a 32-byte MAC, which is also a multiple of the block size; we can check the length of the entire message and not try to check only the ciphertext. A message that isn’t a multiple of the block size wasn’t padded prior to encryption, and therefore is an invalid message.
The message must be at least four blocks long: one block for the IV, one block for the message, and two blocks for the HMAC. If an HMAC function is used with a larger output size, this assumption will need to be revisited.

The decryption also checks the HMAC before actually decrypting the message, and verifies that the plaintext was properly padded.

func Decrypt(key, message []byte) ([]byte, error) {
       if len(key) != KeySize {
               return nil, ErrEncrypt
       }

       // HMAC-SHA-256 returns a MAC that is also a multiple of the
       // block size.
       if (len(message) % aes.BlockSize) != 0 {
               return nil, ErrDecrypt
       }

       // A message must have at least an IV block, a message block,
       // and two blocks of HMAC.
       if len(message) < (4 * aes.BlockSize) {
               return nil, ErrDecrypt
       }

       macStart := len(message) - MACSize
       tag := message[macStart:]
       out := make([]byte, macStart-NonceSize)
       message = message[:macStart]

       h := hmac.New(sha256.New, key[CKeySize:])
       h.Write(message)
       mac := h.Sum(nil)
       if !hmac.Equal(mac, tag) {
               return nil, ErrDecrypt
       }

       // NewCipher only returns an error with an invalid key size,
       // but the key size was checked at the beginning of the function.
       c, _ := aes.NewCipher(key[:CKeySize])
       ctr := cipher.NewCBCDecrypter(c, message[:NonceSize])
       ctr.CryptBlocks(out, message[NonceSize:])

       pt := unpad(out)
       if pt == nil {
               return nil, ErrDecrypt
       }

       return pt, nil
}

Messages v. streams

In this book, we operate on messages: discrete-sized chunks of data. Processing streams of data is more difficult due to the authenticity requirement. How do you supply authentication information? Let’s think about encrypting a stream, trying to provide the same security properties we’ve employed in this chapter.

We can’t encrypt-then-MAC: by it’s nature, we usually don’t know the size of a stream. We can’t send the MAC after the stream is complete, as that usually is indicated by the stream being closed. We can’t decrypt a stream on the fly, because we have to see the entire ciphertext in order to check the MAC. Attempting to secure a stream adds enormous complexity to the problem, with no good answers. The solution is to break the stream into discrete chunks, and treat them as messages. Unfortunately, this means we can’t encrypt or decrypt io.Readers and io.Writers easily, and must operate on []byte messages. Dropping the MAC is simply not an option.

Conclusions

In this chapter, we’ve elided discussion about how we actually get the keys (usually, generating a random key isn’t useful). This is a large enough topic to warrant discussion in a chapter of its own.

Some key points:

Prefer NaCl where you can. Use AES-GCM if AES is required and you have a choice. Use AES-CBC and AES-CTR for compatibility.
Always encrypt-then-MAC. Don’t ever just encrypt.
Always check assumptions about the message, including its authenticity, before decrypting the message.
Think about how you’re getting nonces and IVs, and whether it’s the appropriate method.