Internet Draft M. Boesgaard, M. Vesterager, E. Zenner Cryptico A/S March 18, 2005 This document expires September 18, 2005 A Description of the Rabbit Stream Cipher Algorithm IPR Statement By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, or will be disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668. Internet-Draft Boilerplate 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." The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Abstract This document describes the encryption algorithm Rabbit. It is a stream cipher algorithm with a 128-bit key and 64-bit IV. The method was published in 2003 and has been subject to public security and performance revision. Its high performance makes it particularly suited for the use with internet protocols where large amounts of data have to be processed. Boesgaard et al. Informational [page 1] INTERNET DRAFT Rabbit Encryption March 2005 1. Introduction Rabbit is a stream cipher algorithm that has been designed for high performance in software implementations. Both key setup and encryption are very fast, making the algorithm particularly suited for all applications where large amounts of data or large numbers of data packages have to be encrypted. Examples include, but are not limited to, server-side encryption, multimedia encryption, hard-disk encryption, and encryption on limited-resource devices. The cipher is based on ideas derived from the behavior of certain chaotic maps. These maps have been carefully discretized, resulting in a compact stream cipher. Rabbit has been openly published in 2003 [1] and has not displayed any weaknesses to the time of this writing. To ensure ongoing security evaluation, it will also be submitted to analysis by the upcoming ECRYPT stream cipher lounge [2]. Technically, Rabbit consists of a pseudorandom bitstream generator that takes a 128-bit key and a 64-bit initialization vector (IV) as input and generates a stream of 128-bit blocks. Encryption is performed by combining this output with the message, using the exclusive-OR operation. Decryption is performed in exactly the same way as encryption. Further information about Rabbit, including reference implementation, test vectors, performance figures, and security white papers, is available from http://www.cryptico.com/. 2. Algorithm Description 2.1 Notation This document uses the following elementary operators: + integer addition. * integer multiplication. div integer division. mod integer modulus. ^ bitwise exclusive-OR operation. <<< left rotation operator. || concatenation operator. When labeling bits of a variable A, the least significant bit is denoted by A[0]. The notation A[h..g] represents bits h through g of variable A, where h is more significant than g. Given a 64-bit word, the function MSW extracts the most significant 32 bits, while the function LSW extracts the least significant 32 bits. Boesgaard et al. Informational [page 2] INTERNET DRAFT Rabbit Encryption March 2005 Constants prefixed with 0x are in hexadecimal notation. In particular, the constant WORDSIZE is defined to be 0x100000000. 2.2 Inner State The internal state of the stream cipher consists of 513 bits. 512 bits are divided between eight 32-bit state variables x1,...,x8 and eight 32-bit counter variables c1,...,c8. In addition, there is one counter carry bit b. 2.3 Key Setup Scheme The counter bit b is initialized to zero. The state and counter words are derived from the key K[127..0]. The key is divided into subkeys K0 = K[15..0], K1 = K[31..16], ... K7 = K[127..112]. The initial state is initialized as follows: for j=0 to 7: if j is even: Xj = K(j+1 mod 8) || Kj Cj = K(j+4 mod 8) || K(j+5 mod 8) else: Xj = K(j+5 mod 8) || K(j+4 mod 8) Cj = Kj || K(j+1 mod 8) The system is then iterated four times, each iteration consisting of counter update (section 2.5) and next-state function (section 2.6). After that, the counter variables are reinitialized to: for j=0 to 7: Cj = Cj ^ X(j+4 mod 8) 2.4 IV Setup Scheme If an IV is used for encryption, the counter variables are modified after the key setup. Denoting the IV bits by IV[63..0], the setup proceeds as follows: C0 = C0 ^ IV[31..0] C1 = C1 ^ (IV[63..48] || IV[31..16]) C2 = C2 ^ IV[63..32] C3 = C3 ^ (IV[47..32] || IV[15..0]) C4 = C4 ^ IV[31..0] C5 = C5 ^ (IV[63..48] || IV[31..16]) C6 = C6 ^ IV[63..32] C7 = C7 ^ (IV[47..32] || IV[15..0]) The system is then iterated another 4 times, each iteration consisting of counter update (section 2.5) and next-state function (section 2.6). Boesgaard et al. Informational [page 3] INTERNET DRAFT Rabbit Encryption March 2005 2.5 Counter System Before each execution of the next-state function (section 2.6), the counter system has to be updated. This system uses constants A1,...,A7, as follows: A0 = 0x4D34D34D A1 = 0xD34D34D3 A2 = 0x34D34D34 A3 = 0x4D34D34D A4 = 0xD34D34D3 A5 = 0x34D34D34 A6 = 0x4D34D34D A7 = 0xD34D34D3 It also uses the carry bit b to update the counter system, as follows: for j=0 to 7: Cj = Cj + Aj + b b = Cj div WORDSIZE Cj = Cj mod WORDSIZE Note that on exiting this loop, the variable b has to be preserved for the next iteration of the system. 2.6 Next-State Function The core of the Rabbit algorithm is the next-state function. It is based on the function g, which transforms two 32-bit inputs into one 32-bit output, as follows: g(u,v) = LSW(square(u+v)) ^ MSW(square(u+v)) where square(u+v) = ((u+v mod WORDSIZE) * (u+v mod WORDSIZE)). Using this function, the algorithm updates the inner state as follows: X0 = g(X0,C0) + (g(X7,C7) <<< 16) + (g(X6,C6) <<< 16) mod WORDSIZE X1 = g(X1,C1) + (g(X0,C0) <<< 8) + g(X7,C7) mod WORDSIZE X2 = g(X2,C2) + (g(X1,C1) <<< 16) + (g(X0,C0) <<< 16) mod WORDSIZE X3 = g(X3,C3) + (g(X2,C2) <<< 8) + g(X1,C1) mod WORDSIZE X4 = g(X4,C4) + (g(X3,C3) <<< 16) + (g(X2,C2) <<< 16) mod WORDSIZE X5 = g(X5,C5) + (g(X4,C4) <<< 8) + g(X3,C3) mod WORDSIZE X6 = g(X6,C6) + (g(X5,C5) <<< 16) + (g(X4,C4) <<< 16) mod WORDSIZE X7 = g(X7,C7) + (g(X6,C6) <<< 8) + g(X5,C5) mod WORDSIZE 2.7 Extraction Scheme After iteration of step 2.5 and 2.6 (with the exception of key setup and IV setup), a 128-bit output S[127..0] is extracted as follows: Boesgaard et al. Informational [page 4] INTERNET DRAFT Rabbit Encryption March 2005 S[15..0] = X0[15..0] ^ X5[31..16] S[31..16] = X0[31..16] ^ X3[15..0] S[47..32] = X2[15..0] ^ X7[31..16] S[63..48] = X2[31..16] ^ X5[15..0] S[79..64] = X4[15..0] ^ X1[31..16] S[95..80] = X4[31..16] ^ X7[15..0] S[111..96] = X6[15..0] ^ X3[31..16] S[127..112] = X6[31..16] ^ X1[15..0] 2.8 Encryption / Decryption Scheme Given a 128-bit message block M, encryption and decryption are computed via E = M ^ S and M = E ^ S. The encryption/decryption scheme is repeated until all blocks in the message have been encrypted or decrypted. If the size of the message is not a multiple of 128 bit, only the needed amount of bits from the last output block S is used to encrypt the last message block M. 3. Security Considerations For an encryption algorithm, the security provided is of course the most important issue. Note that a full discussion of Rabbit's security against known cryptanalytic techniques is provided in [3]. No security weaknesses have been found until today, neither by the designers nor by independent cryptographers scrutinizing the algorithms after its publication in [1]. In the following, we restrict ourselves to some rules on how to use the Rabbit algorithm properly. 3.1 Message length Rabbit was designed to encrypt up to 2 to the power of 64 bytes of message under the same the key. Should this amount of data ever be exceeded, the key has to be replaced. 3.2 Initialization vector In principle, it is possible to run Rabbit without the IV setup. However, in this case, the generator must never be reset, since this would destroy the cipher's security (for a recent example, see [4]). Boesgaard et al. Informational [page 5] INTERNET DRAFT Rabbit Encryption March 2005 However, in order to guarantee synchronization between sender and receiver, ciphers are frequently reset in practice. This means that both sender and receiver set the inner state of the cipher back to a known value and then derive the new encryption state using an IV. If this is done, it is important to make sure that no IV is ever reused under the same key. For Rabbit, re-initialization is handled as follows: - After the key setup, the resulting inner state is saved as a master state. Then the IV setup is run to obtain the first encryption starting state. - Whenever re-initialization under a new IV is necessary, the IV setup is run on the master again to derive the next encryption starting state. 4. IANA Consideration No IANA considerations. Appendix A. Test Vectors. This is a set of test vectors for conformance testing, given in hexadecimal form. A.1 Testing without IV setup key = [00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00] S[0] = [02 F7 4A 1C 26 45 6B F5 EC D6 A5 36 F0 54 57 B1] S[1] = [A7 8A C6 89 47 6C 69 7B 39 0C 9C C5 15 D8 E8 88] S[2] = [96 D6 73 16 88 D1 68 DA 51 D4 0C 70 C3 A1 16 F4] key = [AC C3 51 DC F1 62 FC 3B FE 36 3D 2E 29 13 28 91] S[0] = [9C 51 E2 87 84 C3 7F E9 A1 27 F6 3E C8 F3 2D 3D] S[1] = [19 FC 54 85 AA 53 BF 96 88 5B 40 F4 61 CD 76 F5] S[2] = [5E 4C 4D 20 20 3B E5 8A 50 43 DB FB 73 74 54 E5] key = [43 00 9B C0 01 AB E9 E9 33 C7 E0 87 15 74 95 83] S[0] = [9B 60 D0 02 FD 5C EB 32 AC CD 41 A0 CD 0D B1 0C] S[1] = [AD 3E FF 4C 11 92 70 7B 5A 01 17 0F CA 9F FC 95] S[2] = [28 74 94 3A AD 47 41 92 3F 7F FC 8B DE E5 49 96] A.2 Testing with IV setup mkey = [00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00] iv = [00 00 00 00 00 00 00 00] S[0] = [ED B7 05 67 37 5D CD 7C D8 95 54 F8 5E 27 A7 C6] S[1] = [8D 4A DC 70 32 29 8F 7B D4 EF F5 04 AC A6 29 5F] S[2] = [66 8F BF 47 8A DB 2B E5 1E 6C DE 29 2B 82 DE 2A] Boesgaard et al. Informational [page 6] INTERNET DRAFT Rabbit Encryption March 2005 iv = [59 7E 26 C1 75 F5 73 C3] S[0] = [6D 7D 01 22 92 CC DC E0 E2 12 00 58 B9 4E CD 1F] S[1] = [2E 6F 93 ED FF 99 24 7B 01 25 21 D1 10 4E 5F A7] S[2] = [A7 9B 02 12 D0 BD 56 23 39 38 E7 93 C3 12 C1 EB] iv = [27 17 F4 D2 1A 56 EB A6] S[0] = [4D 10 51 A1 23 AF B6 70 BF 8D 85 05 C8 D8 5A 44] S[1] = [03 5B C3 AC C6 67 AE AE 5B 2C F4 47 79 F2 C8 96] S[2] = [CB 51 15 F0 34 F0 3D 31 17 1C A7 5F 89 FC CB 9F] References [1] M. Boesgaard, M. Vesterager, T. Pedersen, J. Christiansen, O. Scavenius. "Rabbit: A New High-Performance Stream Cipher". Proc. Fast Software Encryption 2003, Lecture Notes in Computer Science 2887, p. 307-329. Springer, 2003. [2] ECRYPT call for stream cipher primitives, available from http://www.ecrypt.eu.org/stream/ [3] M. Boesgaard, T. Pedersen, M. Vesterager, E. Zenner. "The Rabbit Stream Cipher - Design and Security Analysis". Proc. SASC Workshop 2004, available from http://www.isg.rhul.ac.uk/ research/projects/ecrypt/stvl/sasc.html. [4] H. Wu. "The Misuse of RC4 in Microsoft Word and Excel". IACR eprint archive 2005/007, available from http://eprint.iacr.org/2005/007.pdf. Authors' Address Martin Boesgaard, Mette Vesterager, Erik Zenner Cryptico A/S Fruebjergvej 3 2100 Copenhagen Denmark phone: +45 39 17 96 06 email: {mab,mvp,ez}@cryptico.com URL: http://wwww.cryptico.com Copyright Notice Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Boesgaard et al. Informational [page 7] INTERNET DRAFT Rabbit Encryption March 2005 This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. This document expires September 18, 2005 Boesgaard et al. Informational [page 8]