Network Working Group D. Whiting
Request for Comments: 3610 Hifn
Category: Informational R. Housley
Vigil Security
N. Ferguson
MacFergus
September 2003
Counter with CBC-MAC (CCM)
Status of this Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2003). All Rights Reserved.
Abstract
Counter with CBC-MAC (CCM) is a generic authenticated encryption
block cipher mode. CCM is defined for use with 128-bit block
ciphers, such as the Advanced Encryption Standard (AES).
Counter with CBC-MAC (CCM) is a generic authenticated encryption
block cipher mode. CCM is only defined for use with 128-bit block
ciphers, such as AES [AES]. The CCM design principles can easily be
applied to other block sizes, but these modes will require their own
specifications.
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 [STDWORDS].
For the generic CCM mode there are two parameter choices. The first
choice is M, the size of the authentication field. The choice of the
value for M involves a trade-off between message expansion and the
probability that an attacker can undetectably modify a message.
Valid values are 4, 6, 8, 10, 12, 14, and 16 octets. The second
Whiting, et al. Informational [Page 1]
RFC 3610 Counter with CBC-MAC (CCM) September 2003
choice is L, the size of the length field. This value requires a
trade-off between the maximum message size and the size of the Nonce.
Different applications require different trade-offs, so L is a
parameter. Valid values of L range between 2 octets and 8 octets
(the value L=1 is reserved).
Name Description Size Encoding
---- ---------------------------------------- ------ --------
M Number of octets in authentication field 3 bits (M-2)/2
L Number of octets in length field 3 bits L-1
To authenticate and encrypt a message the following information is
required:
1. An encryption key K suitable for the block cipher.
2. A nonce N of 15-L octets. Within the scope of any encryption key
K, the nonce value MUST be unique. That is, the set of nonce
values used with any given key MUST NOT contain any duplicate
values. Using the same nonce for two different messages
encrypted with the same key destroys the security properties of
this mode.
3. The message m, consisting of a string of l(m) octets where 0 <=
l(m) < 2^(8L). The length restriction ensures that l(m) can be
encoded in a field of L octets.
4. Additional authenticated data a, consisting of a string of l(a)
octets where 0 <= l(a) < 2^64. This additional data is
authenticated but not encrypted, and is not included in the
output of this mode. It can be used to authenticate plaintext
packet headers, or contextual information that affects the
interpretation of the message. Users who do not wish to
authenticate additional data can provide a string of length zero.
The inputs are summarized as:
Name Description Size
---- ----------------------------------- -----------------------
K Block cipher key Depends on block cipher
N Nonce 15-L octets
m Message to authenticate and encrypt l(m) octets
a Additional authenticated data l(a) octets
Whiting, et al. Informational [Page 2]
RFC 3610 Counter with CBC-MAC (CCM) September 2003
The first step is to compute the authentication field T. This is
done using CBC-MAC [MAC]. We first define a sequence of blocks B_0,
B_1, ..., B_n and then apply CBC-MAC to these blocks.
The first block B_0 is formatted as follows, where l(m) is encoded in
most-significant-byte first order:
Octet Number Contents
------------ ---------
0 Flags
1 ... 15-L Nonce N
16-L ... 15 l(m)
Within the first block B_0, the Flags field is formatted as follows:
Bit Number Contents
---------- ----------------------
7 Reserved (always zero)
6 Adata
5 ... 3 M'
2 ... 0 L'
Another way say the same thing is: Flags = 64*Adata + 8*M' + L'.
The Reserved bit is reserved for future expansions and should always
be set to zero. The Adata bit is set to zero if l(a)=0, and set to
one if l(a)>0. The M' field is set to (M-2)/2. As M can take on the
even values from 4 to 16, the 3-bit M' field can take on the values
from one to seven. The 3-bit field MUST NOT have a value of zero,
which would correspond to a 16-bit integrity check value. The L'
field encodes the size of the length field used to store l(m). The
parameter L can take on the values from 2 to 8 (recall, the value L=1
is reserved). This value is encoded in the 3-bit L' field using the
values from one to seven by choosing L' = L-1 (the zero value is
reserved).
If l(a)>0 (as indicated by the Adata field), then one or more blocks
of authentication data are added. These blocks contain l(a) and a
encoded in a reversible manner. We first construct a string that
encodes l(a).
If 0 < l(a) < (2^16 - 2^8), then the length field is encoded as two
octets which contain the value l(a) in most-significant-byte first
order.
Whiting, et al. Informational [Page 3]
RFC 3610 Counter with CBC-MAC (CCM) September 2003
If (2^16 - 2^8) <= l(a) < 2^32, then the length field is encoded as
six octets consisting of the octets 0xff, 0xfe, and four octets
encoding l(a) in most-significant-byte-first order.
If 2^32 <= l(a) < 2^64, then the length field is encoded as ten
octets consisting of the octets 0xff, 0xff, and eight octets encoding
l(a) in most-significant-byte-first order.
The length encoding conventions are summarized in the following
table. Note that all fields are interpreted in most-significant-byte
first order.
First two octets Followed by Comment
----------------- ---------------- -------------------------------
0x0000 Nothing Reserved
0x0001 ... 0xFEFF Nothing For 0 < l(a) < (2^16 - 2^8)
0xFF00 ... 0xFFFD Nothing Reserved
0xFFFE 4 octets of l(a) For (2^16 - 2^8) <= l(a) < 2^32
0xFFFF 8 octets of l(a) For 2^32 <= l(a) < 2^64
The blocks encoding a are formed by concatenating this string that
encodes l(a) with a itself, and splitting the result into 16-octet
blocks, and then padding the last block with zeroes if necessary.
These blocks are appended to the first block B0.
After the (optional) additional authentication blocks have been
added, we add the message blocks. The message blocks are formed by
splitting the message m into 16-octet blocks, and then padding the
last block with zeroes if necessary. If the message m consists of
the empty string, then no blocks are added in this step.
The result is a sequence of blocks B0, B1, ..., Bn. The CBC-MAC is
computed by:
X_1 := E( K, B_0 )
X_i+1 := E( K, X_i XOR B_i ) for i=1, ..., n
T := first-M-bytes( X_n+1 )
where E() is the block cipher encryption function, and T is the MAC
value. CCM was designed with AES in mind for the E() function, but
any 128-bit block cipher can be used. Note that the last block B_n
is XORed with X_n, and the result is encrypted with the block cipher.
If needed, the ciphertext is truncated to give T.
Whiting, et al. Informational [Page 4]
RFC 3610 Counter with CBC-MAC (CCM) September 2003
To encrypt the message data we use Counter (CTR) mode. We first
define the key stream blocks by:
S_i := E( K, A_i ) for i=0, 1, 2, ...
The values A_i are formatted as follows, where the Counter field i is
encoded in most-significant-byte first order:
Octet Number Contents
------------ ---------
0 Flags
1 ... 15-L Nonce N
16-L ... 15 Counter i
The Flags field is formatted as follows:
Bit Number Contents
---------- ----------------------
7 Reserved (always zero)
6 Reserved (always zero)
5 ... 3 Zero
2 ... 0 L'
Another way say the same thing is: Flags = L'.
The Reserved bits are reserved for future expansions and MUST be set
to zero. Bit 6 corresponds to the Adata bit in the B_0 block, but as
this bit is not used here, it is reserved and MUST be set to zero.
Bits 3, 4, and 5 are also set to zero, ensuring that all the A blocks
are distinct from B_0, which has the non-zero encoding of M in this
position. Bits 0, 1, and 2 contain L', using the same encoding as in
B_0.
The message is encrypted by XORing the octets of message m with the
first l(m) octets of the concatenation of S_1, S_2, S_3, ... . Note
that S_0 is not used to encrypt the message.
The authentication value U is computed by encrypting T with the key
stream block S_0 and truncating it to the desired length.
U := T XOR first-M-bytes( S_0 )
The final result c consists of the encrypted message followed by the
encrypted authentication value U.
Whiting, et al. Informational [Page 5]
RFC 3610 Counter with CBC-MAC (CCM) September 2003
To decrypt a message the following information is required:
1. The encryption key K.
2. The nonce N.
3. The additional authenticated data a.
4. The encrypted and authenticated message c.
Decryption starts by recomputing the key stream to recover the
message m and the MAC value T. The message and additional
authentication data is then used to recompute the CBC-MAC value and
check T.
If the T value is not correct, the receiver MUST NOT reveal any
information except for the fact that T is incorrect. The receiver
MUST NOT reveal the decrypted message, the value T, or any other
information.
To preserve security, implementations need to limit the total amount
of data that is encrypted with a single key; the total number of
block cipher encryption operations in the CBC-MAC and encryption
together cannot exceed 2^61. (This allows nearly 2^64 octets to be
encrypted and authenticated using CCM. This is roughly 16 million
terabytes, which should be more than enough for most applications.)
In an environment where this limit might be reached, the sender MUST
ensure that the total number of block cipher encryption operations in
the CBC-MAC and encryption together does not exceed 2^61. Receivers
that do not expect to decrypt the same message twice MAY also check
this limit.
The recipient MUST verify the CBC-MAC before releasing any
information such as the plaintext. If the CBC-MAC verification
fails, the receiver MUST destroy all information, except for the fact
that the CBC-MAC verification failed.
Jakob Jonsson has developed a security proof of CCM [PROOF]. The
resulting paper was presented at the SAC 2002 conference. The proof
shows that CCM provides a level of confidentiality and authenticity
that is in line with other proposed authenticated encryption modes,
such as OCB mode [OCB].
Whiting, et al. Informational [Page 6]
RFC 3610 Counter with CBC-MAC (CCM) September 2003
The main difficulty in specifying this mode is the trade-off between
nonce size and counter size. For a general mode we want to support
large messages. Some applications use only small messages, but would
rather have a larger nonce. Introducing the L parameter solves this
issue. The parameter M gives the traditional trade-off between
message expansion and probability of forgery. For most applications,
we recommend choosing M at least 8.
The CBC-MAC is computed over a sequence of blocks that encode the
relevant data in a unique way. Given the block sequence it is easy
to recover N, M, L, m, and a. The length encoding of a was chosen to
be simple and efficient when a is empty and when a is small. We
expect that many implementations will limit the maximum size of a.
CCM encryption is a straightforward application of CTR mode [MODES].
As some implementations will support a variable length counter field,
we have ensured that the least significant octet of the counter is at
one end of the field. This also ensures that the counter is aligned
on the block boundary.
By encrypting T we avoid CBC-MAC collision attacks. If the block
cipher behaves as a pseudo-random permutation, then the key stream is
indistinguishable from a random string. Thus, the attacker gets no
information about the CBC-MAC results. The only avenue of attack
that is left is a differential-style attack, which has no significant
chance of success if the block cipher is a pseudo-random permutation.
To simplify implementation we use the same block cipher key for the
encryption and authentication functions. In our design this is not a
problem. All the A blocks are different, and they are different from
the B_0 block. If the block cipher behaves like a random
permutation, then the outputs are independent of each other, up to
the insignificant limitation that they are all different. The only
cases where the inputs to the block cipher can overlap are an
intermediate value in the CBC-MAC and one of the other encryptions.
As all the intermediate values of the CBC-MAC computation are
essentially random (because the block cipher behaves like a random
permutation) the probability of such a collision is very small. Even
if there is a collision, these values only affect T, which is
encrypted so that an attacker cannot deduce any information, or
detect any collision.
Whiting, et al. Informational [Page 7]
RFC 3610 Counter with CBC-MAC (CCM) September 2003
Care has been taken to ensure that the blocks used by the
authentication function match up with the blocks used by the
encryption function. This should simplify hardware implementations,
and reduce the amount of byte-shifting required by software
implementations.
The main requirement is that, within the scope of a single key, the
nonce values are unique for each message. A common technique is to
number messages sequentially, and to use this number as the nonce.
Sequential message numbers are also used to detect replay attacks and
to detect message reordering, so in many situations (such as IPsec
ESP [ESP]) the sequence numbers are already available.
Users of CCM, and all other block cipher modes, should be aware of
precomputation attacks. These are effectively collision attacks on
the cipher key. Let us suppose the key K is 128 bits, and the same
nonce value N' is used with many different keys. The attacker
chooses a particular nonce N'. She chooses 2^64 different keys at
random and computes a table entry for each K value, generating a pair
of the form (K,S_1). (Given the key and the nonce, computing S_1 is
easy.) She then waits for messages to be sent with nonce N'. We
will assume the first 16 bytes of each message are known so that she
can compute S_1 for each message. She looks in her table for a pair
with a matching S_1 value. She can expect to find a match after
checking about 2^64 messages. Once a match is found, the other part
of the matched pair is the key in question. The total workload of
the attacker is only 2^64 steps, rather than the expected 2^128
steps. Similar precomputation attacks exist for all block cipher
modes.
The main weapon against precomputation attacks is to use a larger
key. Using a 256-bit key forces the attacker to perform at least
2^128 precomputations, which is infeasible. In situations where
using a large key is not possible or desirable (for example, due to
the resulting performance impact), users can use part of the nonce to
reduce the number of times any specific nonce value is used with
different keys. If there is room in the nonce, the sender could add
a few random bytes, and send these random bytes along with the
message. This makes the precomputation attack much harder, as the
attacker now has to precompute a table for each of the possible
random values. An alternative is to use something like the sender's
Ethernet address. Note that due to the widespread use of DHCP and
NAT, IP addresses are rarely unique. Including the Ethernet address
forces the attacker to perform the precomputation specifically for a
specific source address, and the resulting table could not be used to
attack anyone else. Although these solutions can all work, they need
Whiting, et al. Informational [Page 8]
RFC 3610 Counter with CBC-MAC (CCM) September 2003
careful analysis and almost never entirely prevent these attacks.
Where possible, we recommend using a larger key, as this solves all
the problems.
Performance depends on the speed of the block cipher implementation.
In hardware, for large packets, the speed achievable for CCM is
roughly the same as that achievable with the CBC encryption mode.
Encrypting and authenticating an empty message, without any
additional authentication data, requires two block cipher encryption
operations. For each block of additional authentication data one
additional block cipher encryption operation is required (if one
includes the length encoding). Each message block requires two block
cipher encryption operations. The worst-case situation is when both
the message and the additional authentication data are a single
octet. In this case, CCM requires five block cipher encryption
operations.
CCM results in the minimal possible message expansion; the only bits
added are the authentication bits.
Both the CCM encryption and CCM decryption operations require only
the block cipher encryption function. In AES, the encryption and
decryption algorithms have some significant differences. Thus, using
only the encrypt operation can lead to a significant savings in code
size or hardware size.
In hardware, CCM can compute the message authentication code and
perform encryption in a single pass. That is, the implementation
does not have to complete calculation of the message authentication
code before encryption can begin.
CCM was designed for use in the packet processing environment. The
authentication processing requires the message length to be known at
the beginning of the operation, which makes one-pass processing
difficult in some environments. However, in almost all environments,
message or packet lengths are known in advance.
Whiting, et al. Informational [Page 9]
RFC 3610 Counter with CBC-MAC (CCM) September 2003
Security Function
authenticated encryption
Error Propagation
none
Synchronization
same nonce used by sender and recipient
Parallelizability
encryption can be parallelized, but authentication cannot
Keying Material Requirements
one key
Counter/IV/Nonce Requirements
counter and nonce are part of the counter block
Memory Requirements
requires memory for encrypt operation of the underlying block
cipher, plaintext, ciphertext (expanded for CBC-MAC), and a per-
packet counter (an integer; at most L octets in size)
Pre-processing Capability
encryption key stream can be precomputed, but authentication
cannot
Message Length Requirements
octet aligned message of arbitrary length, up to 2^(8*L) octets,
and octet aligned arbitrary additional authenticated data, up to
2^64 octets
Ciphertext Expansion
4, 6, 8, 10, 12, 14, or 16 octets depending on size of MAC
selected
The authors hereby explicitly release any intellectual property
rights to CCM to the public domain. Further, the authors are not
aware of any patent or patent application anywhere in the world that
covers CCM mode. It is our belief that CCM is a simple combination
of well-established techniques, and we believe that CCM is obvious to
a person of ordinary skill in the arts.
We claim that this block cipher mode is secure against attackers
limited to 2^128 steps of operation if the key K is 256 bits or
larger. There are fairly generic precomputation attacks against all
block cipher modes that allow a meet-in-the-middle attack on the key
K. If these attacks can be made, then the theoretical strength of
this, and any other, block cipher mode is limited to 2^(n/2) where n
is the number of bits in the key. The strength of the authentication
is of course limited by M.
Users of smaller key sizes (such as 128-bits) should take precautions
to make the precomputation attacks more difficult. Repeated use of
the same nonce value (with different keys of course) ought to be
avoided. One solution is to include a random value within the nonce.
Of course, a packet counter is also needed within the nonce. Since
the nonce is of limited size, a random value in the nonce provides a
limited amount of additional security.
[AES] NIST, FIPS PUB 197, "Advanced Encryption Standard (AES),"
November 2001.
[CCM] Whiting, D., Housley, R. and N. Ferguson, "AES Encryption
& Authentication Using CTR Mode & CBC-MAC," IEEE P802.11
doc 02/001r2, May 2002.
[ESP] Kent, S. and R. Atkinson, "IP Encapsulating Security
Payload (ESP)", RFC 2406, November 1998.
Whiting, et al. Informational [Page 23]
RFC 3610 Counter with CBC-MAC (CCM) September 2003
[MAC] NIST, FIPS PUB 113, "Computer Data Authentication," May
1985.
[MODES] Dworkin, M., "Recommendation for Block Cipher Modes of
Operation: Methods and Techniques," NIST Special
Publication 800-38A, December 2001.
[OCB] Rogaway, P., Bellare, M., Black, J. and T, Krovetz, "OCB:
A block-Cipher Mod of Operation for Efficient
Authenticated Encryption," 8th ACM Conference on Computer
and Communications Security, pp 196-295, ACM Press, 2001.
[PROOF] Jonsson, J., "On the Security of CTR + CBC-MAC," SAC 2002
-- Ninth Annual Workshop on Selected Areas of
Cryptography, Workshop Record version, 2002. Final
version to appear in the LNCS Proceedings.
Russ Housley thanks the management at RSA Laboratories, especially
Burt Kaliski, who supported the development of this cryptographic
mode and this specification. The vast majority of this work was done
while Russ was employed at RSA Laboratories.
Whiting, et al. Informational [Page 24]
RFC 3610 Counter with CBC-MAC (CCM) September 2003
Copyright (C) The Internet Society (2003). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assignees.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
Whiting, et al. Informational [Page 26]