Network Working Group K. Kaukonen R. Thayer Internet Draft July 1997 A Stream Cipher Encryption Algorithm "Arcfour" Status of this Memo This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its 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.'' To learn the current status of any Internet-Draft, please check the ``1id-abstracts.txt'' listing contained in the Internet- Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). Abstract This document describes an algorithm here called Arcfour that is believed to be fully interoperable with the RC4 algoritm. RC4 is trademark of RSA Data Security, Inc. There is a need in the Internet community for an encryption algorithm that provides interoperable operation with existing deployed commercial cryptographic applications. This interoperability will allow for a smoother transition to protocols that have been developed through the IETF standards process. Kaukonen, Thayer [Page 1] Internet Draft An Encryption Algorithm July 1997 TABLE OF CONTENTS STATUS OF THIS MEMO..........................................1 ABSTRACT.....................................................1 1. INTRODUCTION..............................................3 2. REQUIREMENTS FOR THIS ENCRYPTION ALGORITHM................3 3. DESCRIPTION OF ALGORITHM..................................4 3.1. KEY SETUP...............................................4 3.2. STREAM GENERATION.......................................4 4. INTELLECTUAL PROPERTY CONSIDERATIONS......................5 5. ACKNOWLEDGEMENTS..........................................5 6. SECURITY CONSIDERATIONS...................................5 7. REFERENCES................................................6 8. AUTHORS' ADDRESSES........................................7 APPENDIX.....................................................7 A. TEST VECTORS..............................................7 B. SAMPLE CODE..............................................10 Kaukonen, Thayer [Page 2] Internet Draft An Encryption Algorithm July 1997 1. Introduction There is a need in the Internet community for an encryption algorithm that provides interoperable operation with existing deployed commercial cryptographic applications. This interoperability allows for a smoother transition to protocols that have been developed through the IETF standards process. This document describes an existing algorithm that satisifies this requirement. There is a large body of experience in developing and deploying encryption applications, especially in the HTTP/HTML browser/server markets. These browsers typically implement the RC4 encryption algorithm provided by [RSA]. It would be beneficial for the IETF standards processes to produce protocols that can be deployed into existing Internet environments. This would allow graceful addition of new (IETF-developed) protocols. It would allow less disruption of existing users, since there would be more interoperability between pre-exisiting protocols and IETF- based protocols. 2. Requirements for this Encryption Algorithm The algorithm described here is called Arcfour, and it has been chosen because it is compatible with the RC4(TM) algoritm that is one of the most popular encryption algorithms in the browser market. (See chapter Intellectual Property Considerations.) Arcfour is potentially useful in several environments, including IPSEC [IPSEC], SSH [SSH], and TLS [TLS]. There are existing Internet Drafts that describe how it can be applied, see e.g. [Caronni], [SSH], and [TLS]. The algorithm can be used with a variety of key lengths. It specifically can be operated with 40-bit keys and with 128-bit keys. See the Security Considerations section for comments on the use of 40-bit keys. Compatibility of the algorithm with commercial algorithms can be tested by comparing the encrypted data that is produced by the test vectors listed in the appendix to this document. Kaukonen, Thayer [Page 3] Internet Draft An Encryption Algorithm July 1997 3. Description of Algorithm The algorithm itself is documented in [Schneier], pages 397-398, in the chapter titled "Other Stream Ciphers and Real Random Sequence Generators". 3.1 Key Setup 1. Allocate an 256 elemment array of 8 bit bytes to be used as an S-box, label it S [0] .. S [255]. 2. Initialize the S-box. Fill each entry first with it's index: S [0] = 0; S [1] = 1; etc. up to S [255] = 255; 3. Fill another array of the same size (256) with the key, repeating bytes as necessary. for (i = 0; i < 256; i = i + 1) S2 [i] = key [i % keylen]; 4. Set j to zero and initialize the S-box like this: for (i = 0; i < 256; i = i + 1) { j = (j + S [i] + S2 [i]) % 256; temp = S [i]; S [i] = S [j]; S [j] = temp; } 5. Initialize i and j to zero. If superuser priviledged program sniffing is feared (that is, always) set also the S2 array and the key array to zero. That gives a slightly better proctection since the key is believed to be not feasible to calculate after it has been zeroed and thus forgotten. 3.2 Stream Generation For either encryption or decryption, the input text is processed one byte at a time. A pseudorandom byte K is generated: i = (i+1) % 256; j = (j + S[i]) % 256; temp = S [i]; S [i] = S [j]; Kaukonen, Thayer [Page 4] Internet Draft An Encryption Algorithm July 1997 S [j] = temp; t = (S [i] + S [j]) % 256; K = S [t]; To encrypt, XOR the value K with the next byte of the plaintext. To decrypt, XOR the value K with the next byte of the ciphertext. 4. Intellectual Property Considerations This document does not address Intellectual Property issues. No claim is made as to who owns this algorithm, of the performance of the algoritm, its cryptographic security or any other liability issues related to the algoritm itself, its implementation or use. The Arcfour algorithm is believed to be fully interoperable with the RC4 algorithm. "RC4" is believed to be trademark of RSA Data Security, Inc. Contact [RSA] if RC4(TM) algorithm is needed. 5. Acknowledgements This work was based on conversations with several collegues within the IETF. 6. Security Considerations This algorithm can be operated with several different key sizes. If the key is 128 bits in length then this algorithm is believed to be secure. If the key length is significantly shorter, specifically 40 bits, then there are known attacts that have been successfully applied. For this algorithm to be operated in a cryptographically sound manner it is believed that a key length of 128 bits or more should be used. On the other hand, the 40-bit version of this algorithm is specifically regulated by the U.S. Government. This means that deployment of 40-bit implementations may be easier to export than alternative algorithms. It must be strongly recommended that no two plaintexts are encrypted with the same key. Otherwise the plaintext can usually be broken, and often even quite easily. If the two encrypted messages are XORed together, the result is XOR of the original plaintexts. Given the encrypted messages are text strings, credit card numbers, or other byte streams with some known properties, the plaintexts can be estimated with great accuracy. See the [DAWSON AND NIELSEN] for more details. Kaukonen, Thayer [Page 5] Internet Draft An Encryption Algorithm July 1997 Initial cryptanalysis results are favorable, but the current literature should be consulted to assess the security of this cipher. A good starting point for a citation search would be [GOLIC]. For Internet news group posting, start with [FINNEY], [JENKINS] and [ROOS]. 7. References [Caronni] Caronni, G., Waldvogel, M. "The ESP Stream Transform", ftp://ds.internic.net/internet-drafts/ draft-caronni-esp-stream-01.txt, September, 1996. [COMMERCE] Test vectors issued by United States Department of Commerce, Bureau of Export Administration, Office of Strategic Trade and Foreign Policy, Strategic Trade Controls Division. [CRYPTLIB] Gutmann, P, Young, E., Plumb, C. "Cryptlib, A Portable Encryption Library", Version 2.00. http://www.cs.auckland.ac.nz/~pgut001/cryptlib.html, 1996. [DAWSON AND NIELSEN] Dawson E. and Nielsen L.: Automated Cryptoanalysis of XOR Plaintext Strings, Cryptologia, April 1996, Volume XX, Number 2. [FINNEY] Finney, H. Internet message posted to sci.crypt 21 September, 1994. [GOLIC] Golic, J. "Linear Statistical Weakness of Alleged RC4 Keystream Generator." In, W. Fumy (ed.), Proceedings of Eurocrypt '97, 226-238, Springer-Verlag, 1997. [IPSEC] Atkinson, R, "Security Architecture for the Internet Protocol", ftp://ds.internic.net/rfc/rfc1825.txt, August 1995. [JENKINS] Jenkins, B. Internet message posted to sci.crypt 22 September, 1994. [ROOS] Roos, A. Internet message posted to sci.crypt 28 September, 1995. [RSA] RSA Data Security, Inc., http://www.rsa.com, Address: RSA Data Security, Inc. 100 Marine Parkway, Suite 500, Redwood City, CA 94065-1031. [SCHNEIER] Schneier, B. "Applied Cryptography", Second Edition, http://www.counterpane.com. Published by John Wiley & Sons, Inc. ISBN 0-471-11709-9, 1996. [SSH] Ylonen, T., "SSH Transport Layer Protocol", ftp://ietf.org/internet-drafts/draft-ietf-secsh-transport-00.txt, March, 1997. Kaukonen, Thayer [Page 6] Internet Draft An Encryption Algorithm July 1997 [SSH ARCFOUR] Kaukonen, K. Long test vectors for Arcfour and RC4 algorithms issued by Kalle Kaukonen, SSH Communications Security, Ltd, July, 1997. [TLS] Freier, A., Karlton, P., Kocher, P., Dierks, T., " The TLS Protocol", ftp://ds.internic.net/internet-drafts/ draft-ietf-tls-protocol-00.txt, December, 1996. 8. Authors' Addresses Kalle Kaukonen SSH Communications Security Tekniikantie 12 02150 Espoo Finland kalle@ssh.fi +358 40 526 0364 Fax +358 9 4354 3206 Rodney Thayer Sable Technology Corporation 246 Walnut Street Newton Massachusetts 02160 rodney@sabletech.com +1 617 332 7292 Fax +1 617 332 7970 Appendix A. Test Vectors 1. Test Vectors from [CRYPTLIB]: Plain Text: 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 Key: 0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF Cipher Text: 0x74, 0x94, 0xC2, 0xE7, 0x10, 0x4B, 0x08, 0x79 2. Test Vectors from [COMMERCE]: Plain Text: 0xdc, 0xee, 0x4c, 0xf9, 0x2c Key: 0x61, 0x8a, 0x63, 0xd2, 0xfb Cipher Text: 0xf1, 0x38, 0x29, 0xc9, 0xde Kaukonen, Thayer [Page 7] Internet Draft An Encryption Algorithm July 1997 3. Test Vectors from [SSH ARCFOUR]: Plain Text: 0x52, 0x75, 0x69, 0x73, 0x6c, 0x69, 0x6e, 0x6e, 0x75, 0x6e, 0x20, 0x6c, 0x61, 0x75, 0x6c, 0x75, 0x20, 0x6b, 0x6f, 0x72, 0x76, 0x69, 0x73, 0x73, 0x73, 0x61, 0x6e, 0x69, 0x2c, 0x20, 0x74, 0xe4, 0x68, 0x6b, 0xe4, 0x70, 0xe4, 0x69, 0x64, 0x65, 0x6e, 0x20, 0x70, 0xe4, 0xe4, 0x6c, 0x6c, 0xe4, 0x20, 0x74, 0xe4, 0x79, 0x73, 0x69, 0x6b, 0x75, 0x75, 0x2e, 0x20, 0x4b, 0x65, 0x73, 0xe4, 0x79, 0xf6, 0x6e, 0x20, 0x6f, 0x6e, 0x20, 0x6f, 0x6e, 0x6e, 0x69, 0x20, 0x6f, 0x6d, 0x61, 0x6e, 0x61, 0x6e, 0x69, 0x2c, 0x20, 0x6b, 0x61, 0x73, 0x6b, 0x69, 0x73, 0x61, 0x76, 0x75, 0x75, 0x6e, 0x20, 0x6c, 0x61, 0x61, 0x6b, 0x73, 0x6f, 0x74, 0x20, 0x76, 0x65, 0x72, 0x68, 0x6f, 0x75, 0x75, 0x2e, 0x20, 0x45, 0x6e, 0x20, 0x6d, 0x61, 0x20, 0x69, 0x6c, 0x6f, 0x69, 0x74, 0x73, 0x65, 0x2c, 0x20, 0x73, 0x75, 0x72, 0x65, 0x20, 0x68, 0x75, 0x6f, 0x6b, 0x61, 0x61, 0x2c, 0x20, 0x6d, 0x75, 0x74, 0x74, 0x61, 0x20, 0x6d, 0x65, 0x74, 0x73, 0xe4, 0x6e, 0x20, 0x74, 0x75, 0x6d, 0x6d, 0x75, 0x75, 0x73, 0x20, 0x6d, 0x75, 0x6c, 0x6c, 0x65, 0x20, 0x74, 0x75, 0x6f, 0x6b, 0x61, 0x61, 0x2e, 0x20, 0x50, 0x75, 0x75, 0x6e, 0x74, 0x6f, 0x20, 0x70, 0x69, 0x6c, 0x76, 0x65, 0x6e, 0x2c, 0x20, 0x6d, 0x69, 0x20, 0x68, 0x75, 0x6b, 0x6b, 0x75, 0x75, 0x2c, 0x20, 0x73, 0x69, 0x69, 0x6e, 0x74, 0x6f, 0x20, 0x76, 0x61, 0x72, 0x61, 0x6e, 0x20, 0x74, 0x75, 0x75, 0x6c, 0x69, 0x73, 0x65, 0x6e, 0x2c, 0x20, 0x6d, 0x69, 0x20, 0x6e, 0x75, 0x6b, 0x6b, 0x75, 0x75, 0x2e, 0x20, 0x54, 0x75, 0x6f, 0x6b, 0x73, 0x75, 0x74, 0x20, 0x76, 0x61, 0x6e, 0x61, 0x6d, 0x6f, 0x6e, 0x20, 0x6a, 0x61, 0x20, 0x76, 0x61, 0x72, 0x6a, 0x6f, 0x74, 0x20, 0x76, 0x65, 0x65, 0x6e, 0x2c, 0x20, 0x6e, 0x69, 0x69, 0x73, 0x74, 0xe4, 0x20, 0x73, 0x79, 0x64, 0xe4, 0x6d, 0x65, 0x6e, 0x69, 0x20, 0x6c, 0x61, 0x75, 0x6c, 0x75, 0x6e, 0x20, 0x74, 0x65, 0x65, 0x6e, 0x2e, 0x20, 0x2d, 0x20, 0x45, 0x69, 0x6e, 0x6f, 0x20, 0x4c, 0x65, 0x69, 0x6e, 0x6f Key: 0x29, 0x04, 0x19, 0x72, 0xfb, 0x42, 0xba, 0x5f, 0xc7, 0x12, 0x77, 0x12, 0xf1, 0x38, 0x29, 0xc9 Kaukonen, Thayer [Page 8] Internet Draft An Encryption Algorithm July 1997 Cipher Text: 0x35, 0x81, 0x86, 0x99, 0x90, 0x01, 0xe6, 0xb5, 0xda, 0xf0, 0x5e, 0xce, 0xeb, 0x7e, 0xee, 0x21, 0xe0, 0x68, 0x9c, 0x1f, 0x00, 0xee, 0xa8, 0x1f, 0x7d, 0xd2, 0xca, 0xae, 0xe1, 0xd2, 0x76, 0x3e, 0x68, 0xaf, 0x0e, 0xad, 0x33, 0xd6, 0x6c, 0x26, 0x8b, 0xc9, 0x46, 0xc4, 0x84, 0xfb, 0xe9, 0x4c, 0x5f, 0x5e, 0x0b, 0x86, 0xa5, 0x92, 0x79, 0xe4, 0xf8, 0x24, 0xe7, 0xa6, 0x40, 0xbd, 0x22, 0x32, 0x10, 0xb0, 0xa6, 0x11, 0x60, 0xb7, 0xbc, 0xe9, 0x86, 0xea, 0x65, 0x68, 0x80, 0x03, 0x59, 0x6b, 0x63, 0x0a, 0x6b, 0x90, 0xf8, 0xe0, 0xca, 0xf6, 0x91, 0x2a, 0x98, 0xeb, 0x87, 0x21, 0x76, 0xe8, 0x3c, 0x20, 0x2c, 0xaa, 0x64, 0x16, 0x6d, 0x2c, 0xce, 0x57, 0xff, 0x1b, 0xca, 0x57, 0xb2, 0x13, 0xf0, 0xed, 0x1a, 0xa7, 0x2f, 0xb8, 0xea, 0x52, 0xb0, 0xbe, 0x01, 0xcd, 0x1e, 0x41, 0x28, 0x67, 0x72, 0x0b, 0x32, 0x6e, 0xb3, 0x89, 0xd0, 0x11, 0xbd, 0x70, 0xd8, 0xaf, 0x03, 0x5f, 0xb0, 0xd8, 0x58, 0x9d, 0xbc, 0xe3, 0xc6, 0x66, 0xf5, 0xea, 0x8d, 0x4c, 0x79, 0x54, 0xc5, 0x0c, 0x3f, 0x34, 0x0b, 0x04, 0x67, 0xf8, 0x1b, 0x42, 0x59, 0x61, 0xc1, 0x18, 0x43, 0x07, 0x4d, 0xf6, 0x20, 0xf2, 0x08, 0x40, 0x4b, 0x39, 0x4c, 0xf9, 0xd3, 0x7f, 0xf5, 0x4b, 0x5f, 0x1a, 0xd8, 0xf6, 0xea, 0x7d, 0xa3, 0xc5, 0x61, 0xdf, 0xa7, 0x28, 0x1f, 0x96, 0x44, 0x63, 0xd2, 0xcc, 0x35, 0xa4, 0xd1, 0xb0, 0x34, 0x90, 0xde, 0xc5, 0x1b, 0x07, 0x11, 0xfb, 0xd6, 0xf5, 0x5f, 0x79, 0x23, 0x4d, 0x5b, 0x7c, 0x76, 0x66, 0x22, 0xa6, 0x6d, 0xe9, 0x2b, 0xe9, 0x96, 0x46, 0x1d, 0x5e, 0x4d, 0xc8, 0x78, 0xef, 0x9b, 0xca, 0x03, 0x05, 0x21, 0xe8, 0x35, 0x1e, 0x4b, 0xae, 0xd2, 0xfd, 0x04, 0xf9, 0x46, 0x73, 0x68, 0xc4, 0xad, 0x6a, 0xc1, 0x86, 0xd0, 0x82, 0x45, 0xb2, 0x63, 0xa2, 0x66, 0x6d, 0x1f, 0x6c, 0x54, 0x20, 0xf1, 0x59, 0x9d, 0xfd, 0x9f, 0x43, 0x89, 0x21, 0xc2, 0xf5, 0xa4, 0x63, 0x93, 0x8c, 0xe0, 0x98, 0x22, 0x65, 0xee, 0xf7, 0x01, 0x79, 0xbc, 0x55, 0x3f, 0x33, 0x9e, 0xb1, 0xa4, 0xc1, 0xaf, 0x5f, 0x6a, 0x54, 0x7f Kaukonen, Thayer [Page 9] Internet Draft An Encryption Algorithm July 1997 B. Sample Code /* This code illustrates a sample implementation * of the Arcfour algorithm * Copyright (c) April 29, 1997 Kalle Kaukonen. * All Rights Reserved. * * Redistribution and use in source and binary forms, with or * without modification, are permitted provided that this copyright * notice and disclaimer are retained. * * THIS SOFTWARE IS PROVIDED BY KALLE KAUKONEN AND CONTRIBUTORS ``AS * IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL KALLE * KAUKONEN OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ typedef struct { unsigned int x; unsigned int y; unsigned char state[256]; } ArcfourContext; void arcfour_init(ArcfourContext *ctx, const unsigned char *key, unsigned int key_len); unsigned int arcfour_byte(ArcfourContext *ctx); void arcfour_encrypt(ArcfourContext *ctx, unsigned char *dest, const unsigned char *src, unsigned int len); int main(int argc, char **argv) { unsigned char dest[500]; unsigned char mykey[] = {0x29, 0x04, 0x19, 0x72, 0xfb, 0x42, 0xba, 0x5f, 0xc7, 0x12, 0x77, 0x12, 0xf1, 0x38, 0x29, 0xc9}; unsigned char src[] = "Know thyself"; ArcfourContext mycontext; Kaukonen, Thayer [Page 10] Internet Draft An Encryption Algorithm July 1997 /* Initialize the algoritm */ arcfour_init(&mycontext, mykey, 16); /* Encrypt 13 bytes of the src string */ arcfour_encrypt(&mycontext, dest, src, 13); /* Now "dest" contains the encrypted string. Do whatever you please with it... */ return 0; } void arcfour_init(ArcfourContext *ctx, const unsigned char *key, unsigned int key_len) { unsigned int t, u; unsigned int keyindex; unsigned int stateindex; unsigned char *state; unsigned int counter; state = ctx->state; ctx->x = 0; ctx->y = 0; for (counter = 0; counter < 256; counter++) state[counter] = counter; keyindex = 0; stateindex = 0; for (counter = 0; counter < 256; counter++) { t = state[counter]; stateindex = (stateindex + key[keyindex] + t) & 0xff; u = state[stateindex]; state[stateindex] = t; state[counter] = u; if (++keyindex >= key_len) keyindex = 0; } } Kaukonen, Thayer [Page 11] Internet Draft An Encryption Algorithm July 1997 unsigned int arcfour_byte(ArcfourContext *ctx) { unsigned int x; unsigned int y; unsigned int sx, sy; unsigned char *state; state = ctx->state; x = (ctx->x + 1) & 0xff; sx = state[x]; y = (sx + ctx->y) & 0xff; sy = state[y]; ctx->x = x; ctx->y = y; state[y] = sx; state[x] = sy; return state[(sx + sy) & 0xff]; } void arcfour_encrypt(ArcfourContext *ctx, unsigned char *dest, const unsigned char *src, unsigned int len) { unsigned int i; for (i = 0; i < len; i++) dest[i] = src[i] ^ arcfour_byte(ctx); } Kaukonen, Thayer [Page 11]