Internet Engineering Task Force David A. McGrew
INTERNET-DRAFT Cisco Systems, Inc.
Expires May 2002 November, 2001
The Universal Security Transform
<draft-mcgrew-saag-ust-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 describes a cryptographic transform which uses a
keystream generator (which can generate keystream segments in
arbitrary order) and a universal hash function to provide both
confidentiality, message authentication, and replay protection.
This transform is efficient, provably secure, and is appropriate
for network security.
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].
Terms which are defined in this specification are capitalized
to distinguish them from generic terminology.
McGrew [Page 1]
Internet Draft Universal Security Transform November, 2001
3. Universal Security Transform
The Universal Security Transform (UST) is a cryptographic transform
for providing confidentiality, message authentication, and replay
protection. This transform is sufficient for providing these
services to network protocols, though it does not specify a
protocol itself. Conceptually, it is somewhere in between a
combined cipher mode of operation which provides confidentiality
and authentication (such as OCB [MW]) and a completely specified
security protocol (such as IPsec ESP [KA98]).
A UST input consists of an Index field and a Message field which
contains the data to be protected. A UST output consists of a
Ciphertext field and an Authentication Tag field. All of these
fields are octet strings, and all lengths below are expressed in
octets.
The Message field is divided into two parts: a Clear field, which
contains data which is not altered by the transform, and an Opaque
field, which is altered by the transform. Confidentiality is
provided on the Opaque field through encryption, and message
authentication is provided on both fields.
The Ciphertext contains the encrypted form of the unprotected
Opaque field; the length of those fields are equal. The
Authentication Tag provides message authentication of the
Ciphertext and the Clear field. The Index is an unsigned integer
in network byte order that acts as a nonce (that is, its value is
unique for each distinct Message for each fixed key).
The UST uses a Keystream Generator (as defined in Section 5) and an
Authentication 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.
The transform procedure is illustrated in Figure 1. The Index is
fed into the Keystream Generator, 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 Opaque field. The Ciphertext is generated by bitwise
exclusive-oring the Suffix into the Opaque field. The
Authentication Tag is computed by the Authentication Function,
using the concatenation of the Clear field followed by the
Ciphertext field as the data input and the and the Prefix as the
masking input. (Some operations may be optional, as described in
Section 3.1).
McGrew [Page 2]
Internet Draft Universal Security Transform November, 2001
Figure 1. The UST transform. Here and below (+) denotes the
bitwise exclusive-or operation.
+---------+
| Index |
+---------+
|
v <----------- Keystream Segment ----------->
+===========+ +-------------+---------------------------+
" Keystream "->| Prefix | Suffix |---+
" Generator " +-------------+---------------------------+ |
+===========+ | |
| <-------------- Message ------------> |
| +-------+---------------------------+ v
| | Clear | Opaque |->(+)
| +-------+---------------------------+ |
| | |
| +----------------------------+ |
| | |
+--------------------+ | |
| | |
v | |
+-----------+ +================+ | |
| Auth. Tag |<----" Authentication "<-+ |
+-----------+ " Function "<-+ |
+================+ | |
| |
+-----------+ |
| |
+---------------------------+ |
| Ciphertext |<--+
+---------------------------+
The inverse transform procedure is illustrated in Figure 2. The
Index is fed into the Keystream Generator, and the Prefix is
generated. The authenticity of the message is checked by computing
the value of the tag as done in the transform, and comparing the
value computed with that in the Authentication Tag field of the
message. If those values are equal, the Message and Authentication
Tag pair is considered valid; otherwise, it is not. In the case of
an authentication failure, the procedure reports an authentication
error and halts. Otherwise, the Suffix is computed and is bitwise
exclusive-ored into the Ciphertext, giving the Plaintext, and the
procedure reports a successful authentication. (Some operations
may be optional, see Section 3.1)
McGrew [Page 3]
Internet Draft Universal Security Transform November, 2001
Figure 2. The UST inverse transform. Here "Auth. Tag" denotes the
tag associated with the message; the authenticity of the message is
checked by comparing that value with that of a tag computed from the
other fields.
+---------+
| Index |
+---------+
|
v <----------- Keystream Segment ----------->
+===========+ +-------------+---------------------------+
" Keystream "->| Prefix | Suffix |---+
" Generator " +-------------+---------------------------+ |
+===========+ | |
| <-------------- Message ------------> |
| +-------+---------------------------+ v
| | Clear | Opaque |<-(+)
| +-------+---------------------------+ ^
| | |
| +----------------------------+ |
| | |
+--------------------+ | |
| | |
v | |
+-----------+ +================+ | |
| Auth. Tag |----> Equal? <---" Authentication "<-+ |
+-----------+ " Function "<-+ |
+================+ | |
| |
+-----------+ |
| |
+---------------------------+ |
| Ciphertext |---+
+---------------------------+
An example application programming interface is provided in
Appendix A.
3.1 Options
UST can provide confidentiality, message authentication, and replay
protection, or just the latter two security services. The
signaling of what services are in effect for any particular use of
UST are external to the transform.
When confidentiality is not provided, the Suffix MUST not added
into the Plaintext or the Ciphertext.
McGrew [Page 4]
Internet Draft Universal Security Transform November, 2001
Different messages protected with the same UST context MAY have
different security services applied to them. For example, a
protocol may use UST to encrypt and authenticate the data that it
transports, while using the same UST context to provide only
authentication to its keepalive messages.
3.2 Parameters
UST has the following parameters:
Parameter Meaning
--------------------------------------------------------------------
INDEX_LENGTH The number of octets in an Index.
MAX_KEYSTREAM_LENGTH The maximum number of octets in a keystream
segment.
PREFIX_LENGTH The number of octets in the keystream prefix.
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 UST
context. The parameters INDEX_LENGTH and MAX_KEYSTREAM_LENGTH are
defined by the keystream generator. The parameters TAG_LENGTH,
MAX_HASH_LENGTH, and HASH_KEY_LENGTH are defined by the hash
function.
The length of any Plaintext protected by UST MUST NOT exceed the
smaller of (MAX_KEYSTREAM_LENGTH - TAG_LENGTH) and MAX_HASH_LEN.
The value of HASH_KEY_LENGTH MUST be no greater than
MAX_KEYSTREAM_LENGTH. The value of TAG_LENGTH MUST be no greater
than HASH_KEY_LENGTH.
3.3 Format
Unless otherwise specified, the format of the UST output is:
+---------+-----------------------------------------+-----------+
| Index | Ciphertext | Auth. Tag |
+---------+-----------------------------------------+-----------+
McGrew [Page 5]
Internet Draft Universal Security Transform November, 2001
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 UST
For each fixed UST key, each Index value MUST be distinct. This
MAY be accomplished by using successive integer values (though
implementors are free to use non-sequential Index values, e.g. to
aid in parallelization).
The inverse transform MUST check that the value that appears in the
Index has not appeared in any other inverse transform. The inverse
transform MAY return a false positive (that is, report that an
index has been used when in fact it has not), but MUST NOT return a
false negative. This check enforces replay protection, and false
positives are allowed in order to allow implementations to reduce
the amount of state which they need to maintain.
The transform SHOULD check that the value that appears in the Index
has not appeared in any previous transform. This enables a UST
implementation to enforce proper security practices, rather than
relying on other components of a system to meet these requirements.
4.1 UST Initialization
To initialize the context needed to use the UST transform, the
following procedure MAY be 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.
McGrew [Page 6]
Internet Draft Universal Security Transform November, 2001
If this initialization method is used, then the zero index MUST NOT
be used in any other invocation of the transform with that
particular key, and the inverse transform MUST check that the value
that appears in the Index is not zero.
5. Keystream Generators
For the purposes of UST, a Keystream Generator is an algorithm that
maps a secret key and an Index to a pseudorandom keystream segment
of fixed length. Each Keystream Generator MUST define the parameters
INDEX_LENGTH and MAX_KEYSTREAM_LENGTH (defined in Section 3.2).
MAX_KEYSTREAM_LENGTH 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 keystream generators used
in UST are families of length-expanding pseudorandom functions.
6. Authentication Functions and Universal Hash Functions
An Authentication Function takes as input a data field (the
Message) and a pseudorandom masking value (the Prefix). UST is
designed for use with authentication functions which are based on
universal hashing, in the Wegman-Carter paradigm [WC81]. In this
method, the message is hashed using the fixed hash key, then the
resulting hash value is masked (encrypted) using the prefix. The
masking stage is a simple operation such as exclusive-or; the exact
operation to combine the mask and the hash value depends on the
universal hash function definition. Each Authentication Function
MUST define the parameters TAG_LENGTH, PREFIX_LENGTH,
HASH_KEY_LENGTH, and MAX_HASH_LENGTH (defined in Section 3.2).
For the purposes of UST, 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 hash values of distinct
messages appear to be random. The formal mathematical requirement
is that the set of functions defined by the hash with each member
of the set of all possible keys is epsilon-Delta Universal [S96].
The secret key used by the universal hash is an octet string of
length no greater than MAX_KEYSTREAM_LENGTH. The output of the
hash function is an octet string of length TAG_LENGTH. The value
PREFIX_LENGTH denotes the number of octets in the Prefix.
McGrew [Page 7]
Internet Draft Universal Security Transform November, 2001
For use in UST, 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
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. The TMMH
specification resolves that exception [TMMH].
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.
Authentication Functions which are not based on universal hashing
MAY be used within UST. These functions can specify that the
parameter PREFIX_LENGTH has a value of zero.
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 Message is divided into Clear and Opaque fields so that UST can
provide message authentication but not confidentiality to some
component of a message. This feature is sometimes desirable, e.g.
so that protocol headers can be protected from alteration but
remain unencrypted to facilitate processing.
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, UST has the following important advantages over those
modes:
* UST 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 UST provides it with resilience
against denial of service attacks.
* UST can be operated in an authentication-only mode, whereas the
McGrew [Page 8]
Internet Draft Universal Security Transform November, 2001
other modes cannot.
* UST has minimal packet expansion.
* UST can be implemented without infringing on any patents (to
the best knowledge of the authors).
Note that UST 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 not provide
confidentiality. In contrast, UST provides both security services
and amortizes the per-index keystream generation cost over both
services.
UST 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 UST's components are well understood. A
brief analysis of these properties is provided in the Security
Considerations Section.
8. Security Considerations
The security of UST follows from the indistiniguishability of the
keystream generator 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 cryptosystem. (Note that the
converse is also true; the security of UST stands and falls on that
single assumption).
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 [S96].
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 UST
receiver. The theoretical maximum value for T is
McGrew [Page 9]
Internet Draft Universal Security Transform November, 2001
(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 UST implementation to forgery attacks can be
improved in some circumstances by limiting the number of
authentication failures that will be tolerated. This limitation
could be enforced by the implementation of the UST 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, until a new key is derived. If no
more than F failures will be tolerated by the UST inverse
transform, then the expected number N of successful forgeries can
be no more than F * epsilon. Of course, the there is a denial of
service implication in this approach which can outweigh its
benefits in some scenarios.
UST permits arbitrarily small authentication tags. This is because
the goal of this specification is to provide a mechanism, rather
than to dictate a policy. It is expected that some applications
can tolerate a one in a billion likelihood of forgery. In
particular, digital representations of analog data such as voice,
audio, or video may be able to tolerate such a forgery likelihood
due to the error-tolerant nature of analog data.
9. History
This is the second version of this draft. Changes include:
* The authentication tag was previously defined as the exor of
the prefix and the hash output. This has been changed to allow
different hashes to be used within this specification, by
pushing the exor (or other combining operation) into the
message authentication function.
* The original draft did not divide the Message field into a
Clear and an Opaque component.
* The UST was originally named SST. The name was changed to
avoid confusion with the Shiva Smart Tunneling Protocol.
The original specification was documented in
draft-mcgrew-saag-sst-00.txt.
McGrew [Page 10]
Internet Draft Universal Security Transform November, 2001
10. Acknowledgments
Thanks are due to Jesse Walker, Doug Smith, Scott Fluhrer, David
Wagner, Mats Naslund, Burt Kaliski, and Mark Baugher for critical
review and insights. Their comments significantly improved this
specification.
11. Contact Information
Questions and comments on this draft SHOULD be sent to:
David A. McGrew
Cisco Systems, Inc.
mcgrew@cisco.com
and MAY be copied to the Security Area Advisory Group at
saag@mit.edu.
12. 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.
[KA98] S. Kent and R. Atkinson, "IP Encapsulating Security
Payload (ESP)", RFC 2406, November 1998.
[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/
[MW] R. Moskowitz and J. Walker, The AES128 OCB Mode of
Operation and Its Use with IPsec, Work in Progress,
draft-moskowitz-aes128-ocb-00.txt.
McGrew [Page 11]
Internet Draft Universal Security Transform November, 2001
[S96] Stinson, D. R., On the connections between universal
hashing, combinatorical designs and error-correcting
codes, Congressus Numerantium, 114, 1996, 7-27.
[SCESP] McGrew, Fluhrer, and Madson, The Stream Cipher ESP,
draft-mcgrew-ipsec-scesp-03.txt.
[SRTP] The Secure Real-time Transport Protocol, Blohm et. al.,
Work in Progress, draft-ietf-avt-srtp-02.txt.
[TMMH] Mcgrew, D. A., The Truncated Multi-Modular Hash Function,
Work in Progress, draft-mcgrew-saag-tmmh-01.txt
[UMAC] T. Krovetz et. al., Work in Progress,
draft-krovetz-umac-01.txt.
McGrew [Page 12]
Internet Draft Universal Security Transform November, 2001
Appendix A. A C language API for UST.
The following C API is provided as an example of an interface to
UST.
typedef unsigned char octet;
typedef struct ust_ctx_t; /* context associated with a use of ust */
/* a ust_status describes the error states of a ust context */
typedef enum {
ust_status_ok = 0, /* no errors */
ust_status_fail = 1, /* unspecified failure */
ust_status_unsupported_param = 2, /* parameter not supported */
ust_status_alloc_fail = 3, /* memory allocation failure */
ust_status_init_fail = 4, /* initialization failure */
ust_status_auth_fail = 5, /* authentication check failed */
ust_status_replay_fail = 6 /* replay check failed */
} ust_status;
/* ust_init(...) initializes a ust_ctx_t */
ust_status
ust_init(ust_ctx_t *ctx, /* ust context */
int index_length, /* number of octets in the index */
cipher_type cipher_algo, /* keystream generator specification */
octet *cipher_key, /* cipher key */
int cipher_key_len, /* number of octets in cipher key */
hash_type hash_algo, /* hash algorithm specification */
octet *hash_key, /* hash key */
int hash_key_len, /* number of octets in the hash key */
int hash_tag_len, /* number of octets in the hash tag */
int replay_window_len /* length of replay window (0 == none) */
);
/* ust_xfm(...) applies the ust transform */
ust_status
ust_xfm(ust_ctx_t *ctx, /* ust context */
packet_index idx, /* index */
octet *enc_start, /* pointer to encryption start */
int enc_len, /* number of octets to encrypt */
octet *auth_start, /* pointer to authentication start */
int auth_len, /* number of octets to authenticate */
octet *tag /* authentication tag */
);
McGrew [Page 13]
Internet Draft Universal Security Transform November, 2001
/* ust_inv_xfm(...) applies the ust inverse transform */
ust_status
ust_inv_xfm(ust_ctx_t *ctx, /* ust context */
packet_index idx, /* index */
octet *enc_start, /* pointer to encryption start */
int enc_len, /* number of octets to encrypt */
octet *auth_start, /* pointer to authentication start */
int auth_len, /* number of octets to authenticate */
octet *tag /* authentication tag */
);
/*
* ust_xfmv(...) and ust_inv_xfmv(...) implement an iovec scatter/gather
* version of the ust transform and inverse transform, respectively.
*
* struct iovec defines a buffer and length; this definition follows
* that in the U*NX <sys/uio.h> header
*/
struct iovec {
octet *iov_base; size_t
iov_len;
};
ust_status
ust_xfmv(ust_ctx_t *ctx, /* ust context */
packet_index idx, /* index */
struct iovec *enc_vec, /* iovec of data to be encrypted */
int enc_vec_count, /* length of iovec of data to be encrypted */
struct iovec *auth_vec, /* iovec of data to be authenticated */
int auth_vec_count, /* length of iovec of data to be authntctd */
octet *tag /* authentication tag */
);
ust_status
ust_inv_xfmv(ust_ctx_t *ctx, /* ust context */
packet_index idx, /* index */
struct iovec *enc_vec, /* iovec of data to be encrypted */
int enc_vec_count, /* length of iovec of data to be enc. */
struct iovec *auth_vec, /* iovec of data to be authenticated */
int auth_vec_count, /* length of iovec of data to be auth. */
octet *tag /* authentication tag */
);
McGrew [Page 14]