Internet Engineering Task Force David A. McGrew
INTERNET-DRAFT Cisco Systems, Inc.
Expires May, 2002 November, 2001
Integer Counter Mode
<draft-mcgrew-saag-icm-00.txt>
Status of this Memo
This document is an Internet Draft and is in full conformance with
all provisions of Section 10 of RFC-2026. Internet Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and 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.
1. Abstract
This document specifies Integer Counter Mode (ICM), a mode of
operation of a block cipher which defines a keystream generator.
This mode is efficient, parallelizable, and proven secure given
realistic assumptions about the block cipher. Test vectors are
provided for RIJNDAEL.
Counter Mode admits many variations. The variant specified in
this document is secure and flexible, yet it enables a single
implementation of a keystream generator to suffice in different
application domains.
2. Notational Conventions
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 RFC-2119 [B97].
McGrew [Page 1]
Internet Draft Integer Counter Mode November, 2001
3. Introduction
Counter Mode is a way to define a pseudorandom keystream generator
using a block cipher [LRW00,M00]. The keystream can be used for
additive encryption, key derivation, or any other application
requiring pseudorandom data.
In ICM, the keystream is logically broken into segments. Each
segment is identified with a segment index, and the segments have
equal lengths. This segmentation makes ICM especially appropriate
for securing packet-based protocols.
4. ICM
In this section, ICM keystream generation and encryption are
defined.
4.1. ICM Parameters
The following parameters are used in ICM. These parameters MUST
remain fixed for any given use of a key.
Parameter Meaning
-----------------------------------------------------------------
BLOCK_LENGTH the number of octets in the cipher block
KEY_LENGTH the number of octets in the cipher key
SEGMENT_INDEX_LENGTH the number of octets in the segment index
BLOCK_INDEX_LENGTH the number of octets in the block index
SEGMENT_LENGTH the maximum number of octets in a segment
The index lengths are related to the other parameters, but are
defined in order to promote clarity.
4.2. Keystream Segments
Conceptually, ICM is a keystream generator that takes a secret key
and a segment index as an input and then outputs a keystream
segment. The segmentation lends itself to packet encryption, as
each keystream segment can be used to encrypt a distinct packet.
A counter is a value containing BLOCK_LENGTH octets which is
incremented using integer addition modulo 256^BLOCK_LENGTH, to
produce a sequence of distinct values which are used as inputs to
the block cipher. (In the context of this specification, an integer
is an octet string BLOCK_LENGTH octets in length, the most
significant of which is the first.) The output blocks of the cipher
are concatenated to form the keystream segment. The first octet of
the segment is the first octet of the first output block, and so on.
McGrew [Page 2]
Internet Draft Integer Counter Mode November, 2001
A schematic of this process is shown in Figure 1.
Figure 1. The generation of a keystream segment given a segment
index and a block cipher key K. Here C[i] and S[i] denote the ith
counter and keystream block, respectively, and (++) denotes integer
addition modulo 256^BLOCK_LENGTH.
segment
index
|
v
C[0] ->(++)-> C[1] ->(++)-> C[2] ->(++)-> ...
| | |
v v v
+---+ +---+ +---+
K->| E | K->| E | K->| E | ...
+---+ +---+ +---+
| | |
v v v
S[0] S[1] S[2] ...
The initial counter of the keystream segment with segment index s is
defined as
C[0] = (s * (256^BLOCK_INDEX_LENGTH) + r) modulo (256^BLOCK_LENGTH)
where r denotes the Offset. The ith counter of that keystream
segment is defined as
C[i] = (C[0] + i) modulo (256^BLOCK_LENGTH).
The number of blocks in any segment MUST NOT exceed
256^BLOCK_INDEX_LENGTH. The number of segments MUST NOT exceed
256^SEGMENT_INDEX_LENGTH. These restrictions ensure the uniqueness
of each block cipher input.
Each segment contains SEGMENT_LENGTH octets; this value MUST NOT
exceed the value (256^BLOCK_INDEX_LENGTH)*BLOCK_LENGTH.
The sum of SEGMENT_INDEX_LENGTH and BLOCK_INDEX_LENGTH MUST NOT
exceed BLOCK_LENGTH / 2. This requirement protects the ICM
keystream generator from potentially failing to be pseudorandom (see
the rationale).
McGrew [Page 3]
Internet Draft Integer Counter Mode November, 2001
Figure 2. An illustration of the structure of a counter with
BLOCK_LENGTH = 8, SEGMENT_INDEX_LENGTH = 2, and BLOCK_INDEX_LENGTH
= 2. The field marked `null' is not part of either the block
or segment indices.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| null |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| segment index | block index |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
4.3. ICM Encryption
Unless otherwise specified, ICM encryption consists of bitwise
exclusive-oring the keystream into the plaintext to produce
the ciphertext.
4.4 ICM KEY
An ICM key consists of the block cipher key and an Offset. The
Offset is an integer with BLOCK_LENGTH octets, which is used to
`randomize' the logical starting point of keystream. The Offset is
crucial to providing security; see the rationale.
For the purposes of transporting an ICM key, e.g. in a signaling
protocol, that key SHOULD be considered a sequence of octets in
which the block cipher key precedes the Offset.
5. Implementation Considerations
Implementation of the `add one modulo 2^m' operation is simple. For
example, with BLOCK_LENGTH = 8 (m=64), it can be implemented in C as
if (!++x) ++y;
where x and y are 32-bit unsigned integers in network byte order.
The implementation of general purpose addition modulo 2^m is
slightly more complicated.
6. Parameters and Test Vectors for RIJNDAEL
This section provides ICM parameters and test vectors for RIJNDAEL
with a 128 bit block size and 128 bit key (that is, with a
BLOCK_LENGTH and KEY_LENGTH of 16).
McGrew [Page 4]
Internet Draft Integer Counter Mode November, 2001
Although a BLOCK_INDEX_LENGTH, SEGMENT_INDEX_LENGTH, and Segment
Index are given for each test vector, it is easy to generalize these
cases to other values of those parameters.
Notation: all integers are expressed in hexadecimal. Each
consecutive pair of hex digits corresponds to an octet, so that the
integer 000102030405060708090A0B0C0D0E0F corresponds to the octet
sequence { 00, 01, 02, 02 ... }. The counter values corresponding
to the output blocks are shown for clarity.
Test Vector One
ICM Key:
000102030405060708090A0B0C0D0E0F000102030405060708090A0B0C0D0E0F
Block Cipher Key: 000102030405060708090A0B0C0D0E0F
Offset: 000102030405060708090A0B0C0D0E0F
BLOCK_INDEX_LENGTH: 4
SEGMENT_INDEX_LENGTH: 4
Segment Index: 00000000
Counter Keystream
000102030405060708090A0B0C0D0E0F 0A940BB5416EF045F1C39458C653EA5A
000102030405060708090A0B0C0D0E10 0263EC94661872969ADAFD0F4BA40FDC
000102030405060708090A0B0C0D0E11 1A2D94B3111CA5F8BDC2C84DCC29EC47
000102030405060708090A0B0C0D0E12 4D0BABD2995F9F076223246847B5D30E
000102030405060708090A0B0C0D0E13 8D33F128463B88EFD3F8A52505020379
Keystream Segment (final output)
0A940BB5416EF045F1C39458C653EA5A0263EC94661872969ADAFD0F4BA40FDC
1A2D94B3111CA5F8BDC2C84DCC29EC474D0BABD2995F9F076223246847B5D30E
8D33F128463B88EFD3F8A52505020379...
Test Vector Two
ICM Key:
75387824D1F1F3815641B65D78D51EDB96C9781981053CBBCB36927844F1932C
Block Cipher Key: 75387824D1F1F3815641B65D78D51EDB
Offset: 96C9781981053CBBCB36927844F1932C
BLOCK_INDEX_LENGTH: 2
SEGMENT_INDEX_LENGTH: 6
Segment Index: 12345678
McGrew [Page 5]
Internet Draft Integer Counter Mode November, 2001
Counter Keystream
96C9781981053CBBCB36A4AC9B69932C EA0AA027BA6D56E44B28F43A7E3E5F58
96C9781981053CBBCB36A4AC9B69932D CBDB3107EDA8D420D3EF7AB7FF290166
96C9781981053CBBCB36A4AC9B69932E AED6F7CB14ED49174336CC010AEB8780
96C9781981053CBBCB36A4AC9B69932F 4C3A754AF027A5C8CCB40E0FE20AF246
96C9781981053CBBCB36A4AC9B699330 01A6D1CE983EF993E980CC9568587E3D
Keystream Segment (final output)
EA0AA027BA6D56E44B28F43A7E3E5F58CBDB3107EDA8D420D3EF7AB7FF290166
AED6F7CB14ED49174336CC010AEB87804C3A754AF027A5C8CCB40E0FE20AF246
01A6D1CE983EF993E980CC9568587E3D...
7. Security Considerations
Each block cipher input is distinct for any segment and any block
index. To see this fact, subtract any two counter values with
distinct segment or block indices; the result is non-zero.
The limitation on the number of segments which can be generated
ensures that the probability with which an adversary can distinguish
the keystream generator from random is negligible. For a
theoretical justification of this fact, see Bellare et. al. [BR98].
Their analysis shows that if the block cipher cannot be
distinguished from a random permutation, then the keystream
generated by ICM cannot be distinguished from keystream generated by
a truly random process, as long as the length of keystream which is
generated is kept below some threshold. The threshold defined in
Section 4.2 is sufficient for most uses of ICM for encryption. This
specification refrains from dictating a lower threshold in order to
refrain from dictating a particular policy, and to avoid a
complicated digression.
The use of the Offset, a key-dependent value which randomizes the
starting position of the keystream, is essential for security. The
omission of this mechanism leaves the door open for practical
attacks, such as the key collision attack and Hellman's time-memory
tradeoff attack; see McGrew and Fluhrer [MF00] for a description of
these attacks which is applicable to ICM. Several counter mode
proposals do not include an offset, and are thus vulnerable to these
attacks.
McGrew [Page 6]
Internet Draft Integer Counter Mode November, 2001
8. Rationale
This specification includes input from implementation experience with
several counter mode variants. The goals of ICM are to provide:
o a secure keystream generator and cipher, and
o a definition flexible enough that a single implementation can be
used for a variety of applications (e.g., Secure RTP [SRTP],
IPsec ESP [KA96]).
The Offset slightly increases the key management overhead, but this
minor disadvantage is well outweighed by other savings. The Offset
is exactly as large as an IV, and ICM enables the use of an explicit
IV (as is commonly used with CBC [MD98]) to be avoided.
9. Acknowledgments
Thanks are due to Helger Lipmaa, Jerome Etienne, Steve Kent, and Mats
Naslund for their helpful discussion and comments.
10. Contact Information
Questions and comments on this draft SHOULD be sent to:
David A. McGrew
Cisco Systems, Inc.
mcgrew@cisco.com
and copied to the Security Area Advisory Group at
saag@mit.edu.
11. References
[BR98] M. Bellare, A. Desai, E. Lokipii and P. Rogaway, A
Concrete Security Treatment of Symmetric Encryption:
Analysis of DES Modes of Operation, Proceedings of
the 38th Symposium on Foundations of Computer
Science, IEEE, 1997.
[B97] S. Bradner, Key words for use in RFCs to Indicate
Requirement Levels, RFC 2119, March 1997.
[AES] The Advanced Encryption Standard, United States
National Institute for Standards and Technology (NIST),
McGrew [Page 7]
Internet Draft Integer Counter Mode November, 2001
http://www.nist.gov/aes/.
[LRW00] H. Lipmaa, P. Rogaway, and D. Wagner, Comments to NIST
Concerning AES Modes of Operation: CTR-Mode Encryption, NIST
Workshop on AES Modes of Operation,
http://csrc.nist.gov/encryption/aes/modes/lipmaa-ctr.pdf
[MD98] Madson, C., and Doraswamy, N., "The ESP DES-CBC Cipher
Algorithm With Explicit IV", RFC 2405, November 1998.
[M00] McGrew, D., "Segmented Integer Counter Mode: Specification
and Rationale", comment to NIST Workshop on AES Modes of
Operation, http://www.mindspring.com/~dmcgrew/sic-mode.pdf
[MF00] D. McGrew and S. Fluhrer, Attacks on Additive Encryption and
Implications on Internet Security, Selected Areas in
Cryptography 2000.
[SRTP] The Secure Real-time Transport Protocol, Blohm et. al.,
Internet Draft, draft-ietf-avt-srtp-02.txt.
McGrew [Page 8]