Internet Engineering Task Force David A. McGrew
INTERNET-DRAFT Cisco Systems, Inc.
Expires December 2001 June, 2001
The Stream Cipher Security Transform
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 describes a cryptographic transform which uses a
stream cipher (which can generate keystream segments in arbitrary
order) and a universal hash function to provide both privacy and
authentication together, or either security service separately.
This transform is efficient, provably secure, appropriate for
network security, and is believed to be patent free.
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 Stream Cipher Security Transform June, 2001
3. Stream Cipher Security Transform
The Stream Cipher Security Transform (SST) transforms a plaintext
message into a ciphertext, and computes an authentication tag for
the ciphertext. An SST input consists of an Index and a Plaintext,
and its output consists of a Ciphertext and an Authentication Tag.
All of these fields are octet strings, and lengths below are
expressed in octets.
The Plaintext contains the data which is to be protected. The
Ciphertext contains binary data; its length is equal to that of the
Plaintext. The Authentication Tag provides message authentication
of the ciphertext. The Index is an unsigned integer in network
byte order that acts as a nonce (that is, its value is unique for
each distinct Plaintext for each fixed key).
The SST uses a Stream Cipher (as defined in Section 5) and a
Universal Hash Function (as defined in Section 6). The interfaces
to these components, but not the components themselves, are defined
in this specification. Any such components can be used.
Figure 1. The SST transform. Here (+) denotes the bitwise
exclusive-or operation.
+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Index | | Plaintext |---+
+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| |
v |
+=========+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ v
" Stream "->| Prefix | Suffix |->(+)
" Cipher " +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
+=========+ | |
v |
(+)<---------------------------------+ |
| | |
v | |
+-+-+-+-+-+-+ +===========+ |
| Auth. Tag | " Universal " |
+-+-+-+-+-+-+ " Hash " |
+===========+ |
^ |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Ciphertext |<--+
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
McGrew [Page 2]
Internet Draft Stream Cipher Security Transform June, 2001
The transform procedure is illustrated in Figure 1. The Index is
fed into the Stream Cipher, which then outputs the keystream
segment which corresponds to that Index. The keystream segment is
conceptually divided into a Prefix, whose length is equal to that
of the Authentication Tag, followed by a Suffix, whose length is
that of the Plaintext. The Ciphertext is generated by bitwise
exclusive-oring the Suffix into the Plaintext. The Authentication
Tag is generated by computing the universal hash of the Ciphertext
and then bitwise exclusive-oring that result with the Prefix.
(Some operations may be optional, as described in Section 3.1).
The inverse transform procedure is illustrated in Figure 2. The
Index is fed into the Stream Cipher, and the Prefix is generated.
The Authentication Tag is computed by universal hashing the
Ciphertext, then bitwise exclusive-oring the result into the
Prefix. The computed value is compared to that in the transform.
If they do not match, then the procedure reports an authentication
error and halts. Otherwise, the Suffix is computed and is bitwise
exclusive-ored into the Ciphertext, resulting in the Plaintext, and
the procedure reports a successful authentication. (Some
operations may be optional, see Section 3.1)
Figure 2. The SST inverse transform. Here (?=) denotes the test
for equality and (+) denotes the bitwise exclusive-or operation.
+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Index | | Ciphertext |---+
+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| |
| +===========+ |
| +-+-+-+-+-+-+ " Universal " |
| | Auth. Tag | " Hash "<--+
| +-+-+-+-+-+-+ +===========+ |
| | | |
| V | |
| (?=) | |
| ^ | |
| | | |
| (+)<---------------------------------+ |
| ^ |
v | |
+=========+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ v
" Stream "->| Prefix | Suffix |->(+)
" Cipher " +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
+=========+ |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
| Plaintext |<--+
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
McGrew [Page 3]
Internet Draft Stream Cipher Security Transform June, 2001
An example application programming interface is provided in
Appendix A.
3.1 Options
SST can provide privacy, privacy and message authentication, or
just message authentication. The signaling of what options
are in effect for any particular use of SST are assumed to be
external.
When privacy is not provided, the Suffix MUST not added into the
Plaintext or the Ciphertext.
When message authentication is not provided, the Authentication Tag
MUST be omitted. When message authentication is provided, the
Authentication Tag MUST be present, and its absence MUST cause an
authentication error to be reported.
Different messages protected with the same SST context MAY have
different security services applied to them. For example, a
protocol may use SST to encrypt and authenticate the data that it
transports, while using the same SST context to provide only
authentication to its keepalive messages.
3.2 Parameters
SST has the following parameters:
Parameter Meaning
--------------------------------------------------------------------
INDEX_LENGTH The number of octets in an Index.
MAX_CIPHER_LENGTH The maximum number of octets in a keystream
segment.
TAG_LENGTH The number of octets in an Authentication Tag.
MAX_HASH_LENGTH The maximum number of octets that can be input
to the hash function.
HASH_KEY_LENGTH The number of octets in a hash key.
All of these parameters MUST remain fixed for any given SST
context. The parameters INDEX_LENGTH and MAX_CIPHER_LENGTH are
defined by the stream cipher. The parameters TAG_LENGTH,
MAX_HASH_LENGTH, and HASH_KEY_LENGTH are defined by the hash
function.
McGrew [Page 4]
Internet Draft Stream Cipher Security Transform June, 2001
The length of any Plaintext protected by SST MUST NOT exceed the
smaller of (MAX_CIPHER_LENGTH - TAG_LENGTH) and MAX_HASH_LEN.
The value of HASH_KEY_LENGTH MUST be no greater than
MAX_CIPHER_LENGTH. The value of TAG_LENGTH MUST be no greater than
HASH_KEY_LENGTH.
3.3 Format
Unless otherwise specified, the format of the SST output is:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Index | Ciphertext | Auth. Tag |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Here the leftmost octet denotes the first in the address range.
The octets of the Index field, from left to right, are the radix
256 digits of the Index value. The Index MAY be omitted. This
option is useful when the Index can be inferred through external
information, and this case is called Implicit Index (the other case
is Explicit Index).
The ordering and encoding of the Ciphertext, Authentication Tag,
and Index are unimportant for security purposes. Other
specifications which specialize or adapt this one are encouraged to
use formats which better suit their needs.
4. Using the SST
The Index values used in each SST transform MUST be distinct for
each key. This MAY be accomplished by using successive integer
values (though implementers are free to use non-sequential Index
values, e.g. to aid in paralellization).
The Index value of zero (e.g., all octets of the Index are zero)
MUST NOT be used in any SST transform procedure. This Index value
is reserved for use in the SST initialization procedure (Section
4.1).
The inverse transform MUST check that the value that appears in
the Index is not zero.
The inverse transform SHOULD check that the value that appears in
the Index has not appeared in any other inverse transform. This
check is equivalent to replay protection.
McGrew [Page 5]
Internet Draft Stream Cipher Security Transform June, 2001
4.1 SST Initialization
To initialize the context needed to use the SST transform, the
following procedure is used:
1) The cipher key is initialized, if needed, using the
cipher-dependent initialization procedure.
2) The cipher is used to generate the first HASH_KEY_LENGTH octets
of the segment corresponding to the zero index. The hash
function key is set to this value, and the hash function is
initialized, if needed, using the hash-dependent key
initialization procedure.
5. Requirements for Stream Ciphers
For the purposes of SST, a stream cipher is an algorithm that maps
a secret key and an Index to a pseudorandom keystream segment of
fixed length. Each stream cipher MUST define the parameters
INDEX_LENGTH and MAX_CIPHER_LENGTH (defined in Section 3.2).
MAX_CIPHER_LEN SHOULD be at least 65,535, so that any IP version
four packet can be encrypted.
The cipher MUST map each possible value of the Index to a distinct
value of the keystream segment, for each fixed key.
In the terms of cryptographic theory, the stream ciphers used in
SST are length-expanding pseudorandom functions.
6. Requirements for Universal Hash Functions
For the purposes of SST, a universal hash function is an algorithm
that maps a fixed-length secret key and a variable-length message
to a fixed-length hash value, such that the bitwise exclusive-or of
the hash values of distinct messages appear to be random. (The
formal mathematical requirement is below).
The secret key used by the universal hash is an octet string of
length no greater than MAX_CIPHER_LENGTH. The output of the hash
function is an octet string of length TAG_LENGTH.
For use in SST, a hash function MUST be epsilon-Delta Universal
(epsilon-DU) for some small value of epsilon. The value of epsilon
SHOULD be close to 1/256 to the power TAG_LENGTH, so that the
cryptographic strength of the tag is as large as possible. This
McGrew [Page 6]
Internet Draft Stream Cipher Security Transform June, 2001
means that the probability that the bitwise exclusive-or of the
hash of any two distinct messages will be any particular fixed
value is no greater than epsilon.
The functions UHASH-16 and UHASH-32 [UMAC] meet these requirements.
The functions MMH and NMH [MMH] meet all of these requirements
except for the variable-length message requirement.
Note that it is technically improper to call a keyed hash function
"universal". Rather, one should say that the key is an index into
a universal family of hash functions. We abuse this terminology
for simplicity's sake.
7. Rationale
This transform is computationally efficient, has minimal expansion,
and reduces key management overhead and local state information by
eliminating the need for a separate encryption key.
The benefits described above are shared with some of the recently
proposed modes of operation for the Advanced Encryption Standard
[AES], such as OCB, IACBC, IAPM, XCBC, and XECB modes [MODES].
However, SST has the following important advantages over those
modes:
* SST can identify and reject bogus messages much faster, as it
can use hash functions that are an order of magnitude faster
than AES (and authentication precedes decryption in the inverse
transform). This property of SST protects it against denial of
service attacks.
* SST can be operated in an authentication-only mode, whereas the
other modes cannot.
* SST can be implemented without infringing on any patents (to
the best knowledge of the authors).
Note that SST can be used with any block cipher mode that meets
the requirements of Section 5, such as Counter Mode [MODES].
The benefits of universal hashing for message authentication are
well known in the cryptographic literature [CW81]. The UMAC
message authentication code [UMAC] is a recent proposal which uses
this technique. However, this approach does does not provide
privacy. In contrast, SST provides both security services and
amortizes the per-index setup cost over both of them.
McGrew [Page 7]
Internet Draft Stream Cipher Security Transform June, 2001
SST reflects implementation experience from the Secure Real-time
Transport Protocol [SRTP] and the Stream Cipher ESP [SCESP], as
well as input from the 802.11 security team.
The security properties of SST's components are well understood.
An analysis of these properties is provided in the Security
Considerations Section.
8. Security Considerations
The security of SST follows from the indistiniguishability of the
stream cipher from a truly unpredictable source and the properties
of the hash function. The number of unprovable assumptions which
underlie the transform are thus reduced to one, the minimum number
required for any crypto system.
Given the indistinguishability of the cipher, the adversary gains
no knowledge about the plaintext from the ciphertext.
The probability with which an adversary can successfully forge an
Authentication Tag for any given message is at most epsilon, when
the hash function is epsilon-Delta Universal.
The expected number N of successful forgeries is T / epsilon, where
T is the number of forgery attempts, that is, the number of bogus
index/ciphertext/tag values sent by the adversary to the SST
receiver. The theoretical maximum value for T is
(256)^INDEX_LENGTH. This value of T implies that every single
message processed by the receiver is a forgery attempt. Note that
if INDEX_LENGTH is greater than TAG_LENGTH, then N can be greater
than one.
The resistance of an SST implementation to forgery attacks can be
significantly improved by limiting the number of authentication
failures that will be tolerated. This limitation could be enforced
by the implementation of the SST inverse transform, by maintaining
a count of the total number of authentication failures and causing
the inverse transform to indicate an authentication failure on all
messages after the threshold has been exceeded.
If no more than F failures will be tolerated by the SST inverse
transform, then the expected number N of successful forgeries can
be no more than F / epsilon.
SST permits arbitrarily small authentication tags in order to
provide a mechanism, rather than to dictate policy. It is expected
that some applications can tolerate a one in a billion likelihood
McGrew [Page 8]
Internet Draft Stream Cipher Security Transform June, 2001
of forgery. In particular, analog data such as voice, audio, or
video may be able to tolerate such a forgery likelihood due to the
limited effect of a single forged packet.
9. Intellectual Property
SST does not contain any known intellectual property. To the best
knowledge of the authors, it is possible to implement SST without
infringing on any patents.
10. Acknowledgments
As always, thanks are due to Scott Fluhrer for his critical review
and insights.
Thanks are also due to Phil Rogaway for pointing out that it is
sufficient to use only bitwise exclusive-or for tag encryption.
This fact is implicit in a forthcoming publication from Krovetz and
Rogaway, and it simplifies SST nicely.
11. Contact Information
Questions and comments on this draft SHOULD be sent to:
David A. McGrew, Ph.D.
Cisco Systems, Inc.
mcgrew@cisco.com
and MAY be copied to the Security Area Advisory Group at
saag@mit.edu
11. References
[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),
http://www.nist.gov/aes/.
[CW81] M. Wegman and L. Carter, New hash functions and their
use in authentication and set equality, J. of Computer
and System Sciences, vol. 22, 1981.
McGrew [Page 9]
Internet Draft Stream Cipher Security Transform June, 2001
[MMH] S. Halevi, and H. Krawczyk, MMH: Software Authentication in
the Gbit/second rates, Fast Software Encryption Workshop,
1997. Also available online at
http://www.research.ibm.com/people/s/shaih/pubs/.
[MODES] Proposed Modes of Operation, NIST web page,
http://csrc.nist.gov/encryption/modes/proposedmodes/
[SCESP] McGrew, Fluhrer, and Madson, The Stream Cipher ESP,
draft-mcgrew-ipsec-scesp-02.txt.
[SRTP] The Secure Real-time Transport Protocol, Blohm et. al.,
Internet Draft, draft-ietf-avt-srtp-00.txt.
[UMAC] T. Krovetz et. al., Internet Draft,
draft-krovetz-umac-01.txt.
Appendix A. A C language API for SST.
A C API is provided as an example interface into SST. The
interface uses a vararg list of void pointers to hide the
implementation details of the cipher and hash function.
typedef unsigned char octet;
typedef struct sst_ctx_t *sst_ptr_t; /* points to sst context */ typedef
struct idx_t *index_ptr_t; /* points to sst index */
typedef enum {
sec_serv_none = 0, /* null xfm, */
sec_serv_privacy = 1, /* privacy only */
sec_serv_auth = 2, /* authentication only */
sec_serv_privacy_and_auth = 3 /* privacy and authentication */ }
sst_sec_serv;
typedef enum {
sst_ok, /* no errors */
sst_fail, /* unspecified failure */
sst_auth_ok, /* authentication okay */
sst_auth_fail, /* authentication failure */
sst_fail_index_not_unique /* index not unique in sst inv. xfm */ }
sst_status;
McGrew [Page 10]
Internet Draft Stream Cipher Security Transform June, 2001
/*
* sst_xfm(...)
*
* Uses context to apply services to the octet string pointed to by msg
* of length *len. If authentication is provided, then the
* authentication tag is written into the memory location immediately
* after the msg, and the new length of the buffer is written into *len.
*/
sst_status sst_xfm(sst_ptr_t context,
index_ptr_t idx,
octet *msg,
int *len);
/*
* sst_inverse_xfm(...)
*
* Uses context to process the octet string pointed to by msg, of
* length *len, expecting the security services as described by
* the flag in the context. If authentication is expected, then
* the authentication tag is expected to be contained in the
* last TAG_LENGTH octets of *msg.
*
* If the function returns sst_auth_ok, then *msg contains the
* plaintext *len contains the length of the ciphertext. Otherwise,
* the *msg buffer is unchanged.
*
*/
sst_status sst_inverse_xfm(sst_ptr_t context,
index_ptr_t idx,
octet *msg,
int *len);
McGrew [Page 11]
Internet Draft Stream Cipher Security Transform June, 2001
/*
* sst_init(...)
*
* Initialies ctx, given the index_length, tag_length, the security
* services to provide (or expect) and a list of cipher and hash
* dependent initialization parameters.
*/
#include <varargs.h>
sst_status sst_init(sst_ptr_t ctx,
int index_length,
int tag_length,
sst_sec_serv services,
void *param, ...);
McGrew [Page 12]