Authenticated Encryption with AES-CBC and HMAC-SHA1 (and other generic combinations of ciphers and MACs)
draft-mcgrew-aead-aes-cbc-hmac-sha1-01.txt

Status of this Memo

This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as “work in progress.”

The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt.

The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html.

This Internet-Draft will expire on September 11, 2009.

Copyright Notice

Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document.

Abstract

This document specifies algorithms for authenticated encryption with additional authenticated data (AEAD) that are based on the composition of the Advanced Encryption Standard (AES) in the Cipher Block Chaining (CBC) mode of operation for encryption, and the HMAC-SHA1 message authentication code (MAC). It also separately defines a generic composition method that can be used with other MACs and randomized ciphers (that is, ciphers that use random initialization vectors).

These algorithms are randomized, and thus are suitable for use with applications that cannot provide distinct nonces to each invocation of the AEAD encrypt operation.

Table of Contents

1.  Introduction
    1.1.  Conventions Used In This Document
2.  A Generic Composition Method
    2.1.  Encryption
    2.2.  Decryption
    2.3.  Length
3.  AEAD_AES_CBC_128_HMAC_SHA1
    3.1.  Encryption
    3.2.  Message Authentication
    3.3.  Decryption
    3.4.  Length Restrictions
    3.5.  Test Cases
4.  AEAD_AES_256_HMAC_SHA_256
5.  Rationale
6.  Security Considerations
7.  References
    7.1.  Normative References
    7.2.  Informative References
§  Author's Address

1.  Introduction

Authenticated encryption [BN00] (, “Authenticated encryption: Relations among notions and analysis of the generic composition paradigm,” .) is a form of encryption that, in addition to providing confidentiality for the plaintext that is encrypted, provides a way to check its integrity and authenticity. Authenticated encryption with Associated Data, or AEAD, adds the ability to check the integrity and authenticity of some associated data (also called "additional authenticated data") that is not encrypted. This document defines two AEAD algorithms, using the interface defined in [RFC5116] (McGrew, D., “An Interface and Algorithms for Authenticated Encryption,” January 2008.), based on AES and HMAC-SHA1, with key sizes of 128 bits and 256 bits.

1.1.  Conventions Used In This Document

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119] (Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” March 1997.).

2.  A Generic Composition Method

This section defines a particular "generic composition" method, using the the encrypt-then-MAC method defined in Section 4.3 of [AE] (, “Authenticated encryption: Relations among notions and analysis of the generic composition paradigm,” .). The method describes how to make a randomized AEAD algorithm out of a randomized cipher, such as a block cipher mode of operation that uses a random initialization vector, and a MAC.

2.1.  Encryption

We briefly recall the interface defined in Section 2 of [RFC5116] (McGrew, D., “An Interface and Algorithms for Authenticated Encryption,” January 2008.). The AEAD encryption algorithm takes as input four octet strings: a secret key K, a plaintext P, associated data A, and a nonce N. An authenticated ciphertext value is provided as output. The data in the plaintext are encrypted and authenticated, and the associated data are authenticated, but not encrypted. The AEAD encryption process is as follows, or uses an equivalent set of steps:

1. The secondary keys MAC_KEY and ENC_KEY are generated from the input key K as follows. Each of these two keys is an octet string.

   A.

   MAC_KEY consists of the first MAC_KEY_LEN octets of K, in order.

   B.

   ENC_KEY consists of the last ENC_KEY_LEN octets of K, in order.

   Here we denote the number of octets in the MAC_KEY as MAC_KEY_LEN, and the number of bits in ENC_KEY as ENC_KEY_LEN.
2. An Initialization Vector (IV) is generated uniformly at random, for use in the cipher. (Note that this IV is distinct from the nonce that may be provided as an input to the authenticated encryption operation.)
3. The plaintext P is encrypted using the cipher with ENC_KEY as the key, and the IV generated in the previous step. We denote the ciphertext output from this step as S, and it MUST include the IV as its prefix.
4. A message authentication code (MAC) is computed by applying the MAC to the following data, in order:

   A.

   the nonce N,

   B.

   the associated data A,

   C.

   the ciphertext S computed in the previous step

   D.

   the number of bits in N expressed as a 64-bit unsigned integer in network byte order,

   E.

   and the number of bits in A expressed as a 64-bit unsigned integer in network byte order.

   The string MAC_KEY is used as the MAC key. We denote the output of the MAC computed in this step as T.
5. The AEAD Ciphertext consists of the string S, with the string T appended to it. This Ciphertext is returned as the output of the AEAD encryption operation.

The encryption process can be illustrated as follows. Here P, A, and C denote the AEAD plaintext, associated data, and ciphertext, respectively.

S = ENC(ENC_KEY, P)

T = MAC(MAC_KEY, N || A || S || len(N) || len(A))

C = S || T

Here ENC(X,P) denotes the encryption of P using the cipher with the key X; recall that the IV is included in its output. The expression MAC(Y,M) denotes the application of the MAC to the message M, using the key Y. The concatenation of two octet strings A and B is denoted as A || B, and len(X) denotes the number of bits in the string X, expressed as an unsigned integer in network byte order.

2.2.  Decryption

The authenticated decryption operation has four inputs: K, N, and A, as defined above, and the Ciphertext C. It has only a single output, either a plaintext value P or a special symbol FAIL that indicates that the inputs are not authentic. The authenticated decryption algorithm takes is as follows, or uses an equivalent set of steps:

1. The secondary keys MAC_KEY and ENC_KEY are generated from the input key K as follows. Each of these two keys is an octet string.

   A.

   MAC_KEY consists of the first MAC_KEY_LEN octets of K, in order.

   B.

   ENC_KEY consists of the last ENC_KEY_LEN octets of K, in order.

   As above, we denote the number of octets in the MAC_KEY as MAC_KEY_LEN, and the number of bits in ENC_KEY as ENC_KEY_LEN.
2. The final T_LEN octets are stripped from C. Here T_LEN denotes the number of octets in the MAC, which is a fixed parameter of the AEAD algorithm. We denote the initial octets of C as S, and denote the final T_LEN octets as T.
3. The integrity and authenticity of N, A, and C are checked by computing MAC validation algorithm, using the same inputs as in Step 5 of the encryption operation. In the MAC-validation step, the message consists of N, A, the number of bits in N expressed as a 64-bit unsigned integer in network byte order, the number of bits in A expressed as a 64-bit unsigned integer in network byte order, as S, in that order. The value MAC_KEY is used as the key. The value T, from the previous step, is used as the correct MAC value for validation purposes. If the MAC-validation operation indicates that the MAC T is valid, then the processing is continued. Otherwise, all of the data used in the MAC validation are discard, and the AEAD decryption operation returns an indication that it failed, and the operation halts.
4. The value S is decrypted, using the first 128 bits of the ciphertext as the IV. The value ENC_KEY is used as the decryption key.
5. The plaintext value is returned..

2.3.  Length

The length of the ciphertext can be inferred from that of the plaintext. The number L of octets in the ciphertext is given by

L = 16 * ( floor(M / 16) + 2)

where M denotes the number of octets in the plaintext, and the function floor() rounds its argument down to the nearest integer. This fact is useful to applications that need to reserve space for a ciphertext within a message or data structure.

3.  AEAD_AES_CBC_128_HMAC_SHA1

This algorithm is randomized and stateless. It is based on the "generic composition" of CBC encryption with HMAC authentication, with the the encrypt-then-MAC method defined in Section 4.3 of [AE] (, “Authenticated encryption: Relations among notions and analysis of the generic composition paradigm,” .). It uses the HMAC message authentication code [RFC2104] (Krawczyk, H., Bellare, M., and R. Canetti, “HMAC: Keyed-Hashing for Message Authentication,” February 1997.) with the SHA-1 hash function [SHA1] (, “FIPS 180-1: Secure Hash Standard,,” .) to provide message authentication. Test cases for HMAC_SHA1 are provided in [RFC2202] (Cheng, P. and R. Glenn, “Test Cases for HMAC-MD5 and HMAC-SHA-1,” September 1997.). For encryption, it uses AES in the cipher block chaining (CBC) mode of operation as defined in Section 6.2 of [MODES] (Dworkin, M., “NIST Special Publication 800-38: Recommendation for Block Cipher Modes of Operation,” .), with the padding method defined by Appendix A of the same reference.

The input key K is 36 octets long.

3.1.  Encryption

The AES CBC IV is 16 octets long. ENC_KEY_LEN is 16 octets.

Prior to CBC encryption, the plaintext is padded by appending a single '1' bit to that data and then appending to the resulting string as few '0' bits as are necessary to make the number of bits in the plaintext into a multiple of 128. Note that padding MUST be added to the data; if the number of bits in the payload data is a multiple of 128, then 128 bits of padding will be added.

The plaintext is then encrypted using AES-128 in CBC mode, using ENC_KEY as the key and the random IV. The IV is included in the ciphertext as its initial 16 octets.

3.2.  Message Authentication

HMAC-SHA1 is used as the MAC. MAC_KEY_LEN is 20 octets. The HMAC-SHA1 output is truncated to 16 octets, by stripping off the final four octets.

3.3.  Decryption

After CBC decryption, the padding is removed by deleting the final '1' bit and all of the following '0' bits. The remaining data forms the plaintext.

The HMAC-SHA1 validation operation consists of computing the HMAC-SHA1 value of the message, truncating it to 16 octets by discarding the final four octets, then comparing that value with the MAC value. If values are not equal, then the message is rejected. Otherwise, it is accepted.

3.4.  Length Restrictions

The lengths of the inputs are restricted as follows:

K_LEN is 36 octets,

P_MAX is 2^64 - 1 octets,

A_MAX is 2^64 - 1 octets,

N_MIN is zero octets,

N_MAX is 2^64 octets, and

C_MAX is 2^64 + 47 octets.

3.5.  Test Cases

A future version of this document will include test cases.

4.  AEAD_AES_256_HMAC_SHA_256

AEAD_AES_CBC_256_HMAC_SHA_256 is like AEAD_AES_CBC_128_HMAC_SHA1, with the following differences:

AES-256 is used instead of AES-128.

HMAC-SHA-256 is used instead of HMAC-SHA1.

ENC_KEY_LEN and MAC_KEY_LEN are each 32 octets.

The input key length is 64 octets.

5.  Rationale

The AEAD_AES_CBC_128_HMAC_SHA1 and AEAD_AES_CBC_256_HMAC_SHA_256 algorithms are intended for use in applications that make use of the AEAD interface. It is expected to be useful with cryptomodules that contain efficient implementations of AES-CBC and HMAC-SHA1, but which do not implement any other AEAD algorithms. They are not intended to replace existing uses of AES-CBC and HMAC-SHA1, except in those circumstances where the existing use is not sufficiently secure or sufficiently general-purpose.

One advantage of these algorithms is that they are suitable for use in applications that cannot provide distinct nonces to each invocation of the AEAD encryption operation. In short, they can be used with zero-length nonces. However, the algorithms can accept nonces; this ensures that they can be used with applications that are designed to work primarily with algorithms that expect nonces. The nonce data is authenticated.

6.  Security Considerations

This initial version of this document has not been reviewed; regarding security, it should be considered guilty until proven innocent. Review has been requested from the IRTF Crypto Forum Research Group (CFRG).

The algorithms defined in this document use the "generic composition" of CBC encryption with HMAC authentication, with the encrypt-then-MAC method defined in Section 4.3 of [AE] (, “Authenticated encryption: Relations among notions and analysis of the generic composition paradigm,” .). This method has sound and well-understood security properties; for details, please see that reference.

As with any block cipher mode of operation, the security of AES-CBC degrades as the amount of data that is process increases. Each fixed key value SHOULD NOT be used to protect more than 2^64 bytes of data. This limit ensures that the AES-CBC algorithm will stay under the "birthday bound", i.e., that it is unlikely that there will be two AES plaintext inputs that are equal. (If this event occurs, information about the colliding plaintexts is leaked, so it is desirable to bound the amount of plaintext processed in order to make it unlikely.)

The nonce data is authenticated, as is expected in [RFC5116] (McGrew, D., “An Interface and Algorithms for Authenticated Encryption,” January 2008.).

7.  References

7.1. Normative References

7.2. Informative References

Author's Address