Internet Engineering Task Force David A. McGrew INTERNET-DRAFT Cisco Systems, Inc. Expires May 2002 November, 2001 The Universal 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 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 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]