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 sst_status sst_init(sst_ptr_t ctx, int index_length, int tag_length, sst_sec_serv services, void *param, ...); McGrew [Page 12]