Network Working Group Michael Richardson Request for Comments: XXXX Sandelman Software Works Bruce Schneier April 1, 1999 CounterPane Systems Category: Informational Tero Kivinen SSH Communications Security Oy The use of 3ROT13 in the IPsec Encapsulated Security Payload Status of This memo This memo provides information for the Internet community. This memo does not specity an Internet standard of any kind. Distribution of this memo is unlimited. This memo is offered in full conformance with all provisions of Section 10 of RFC2026. Abstract This draft defines the 3ROT13 encryption algorithm and its use with the IPsec Encapsulating Security Payload (ESP). The 3ROT13 encryption algo- rithm is a high-performance cipher. When properly used, 3ROT13 can guar- antee that the plaintext data will not be known to anyone other than the sender. While it has a key of only 39 bits, recent work has shown it to be as effective at keeping secrets as single-DES. Michael Richardson mcr@sandelman.ottawa.on.ca [page 1] RFCXXXX April 1, 1999 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Algorithm Definition . . . . . . . . . . . . . . . . . . . . . . 2 3. Triple ROT13 . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.1. Keying Material . . . . . . . . . . . . . . . . . . . . . . 3 3.2. Cryptographic Synchronization . . . . . . . . . . . . . . . 3 3.3. Padding . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.4. Performance . . . . . . . . . . . . . . . . . . . . . . . . 3 3.5. Test Vectors . . . . . . . . . . . . . . . . . . . . . . . . 3 4. 3ROT13 Operational Requirements . . . . . . . . . . . . . . . . 3 5. Security Considerations . . . . . . . . . . . . . . . . . . . . 4 6. Intellectual Property Rights . . . . . . . . . . . . . . . . . . 4 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . 4 8. References: . . . . . . . . . . . . . . . . . . . . . . . . . . 4 9. Contact information . . . . . . . . . . . . . . . . . . . . . . . 5 9.2. Author's Address . . . . . . . . . . . . . . . . . . . . . . 5 10. Appendix: Key derivation . . . . . . . . . . . . . . . . . . . 6 1. Introduction ROT13 is a substitution cipher originally invented by citizens of Usenet for concealing punchlines to jokes or endings of TV programs. In its single use form it was appropriate for such low security uses. Triple ROT13 is an enhancement to ROT13 designed to make it more suitable for high-security encryption applications. Triple ROT13 is extremely efficient when implemented in either hardware or software. 2. Algorithm Definition The algorithm can be described as applying the following function to integers in the range 0-255: E_k(x) = x if (x < 65 OR x > 122) x+13 if ((x > 64 and x < 78) OR (x > 96 and x < 110)) x-13 if ((x > 77 and x < 91) OR (x > 109 and x < 123)) k = encryption key. The data may be recovered by a receiver through the an additional application of the encryption algorithm with the key set to the bitwise 1s complement of the encryption key. This is of great advantage for hardware implementations as both encryption and decryption can be done by the same logic. Triple-ROT13 encrypts data byte by byte. Because of the random-access Michael Richardson mcr@sandelman.ottawa.on.ca [page 2] RFCXXXX April 1, 1999 nature of the encryption algorithm, the data does not have to be decrypted in the same order that it was encrypted. This is an excellent feature in applications where only certain bytes need to be decrypted: random database access, for example. 3. Triple ROT13 3ROT13 like other triple algorithms consists of three passes of ROT13. One pass encryption, a second pass of decryption and a third pass of encryption. Like all triple algorithms, a weak key check must be done. If the first and second keys are equal, then the algorithm breaks down into the single case. An implementation of 3ROT13 MUST pick new keys whenever the first and second keys are equal. 3.1. Keying Material The 3ROT13 encryption algorithm requires three 13 bit subkeys. A parity bit is provided with each subkey, bringing the total to 42 bits. 3.2. Cryptographic Synchronization Because of the stateless nature of the 3ROT13 encryption algorithm, it is not necessary to transmit an IV or similar cryptographic synchronization data on a per packet (or even a per SA) basis. 3.3. Padding 3ROT13 has a block size of 13 bytes, padding is necessary and should be done as described in [ESP] 3.4. Performance The 3ROT13 encryption algorithm is significantly faster than single-DES, RC4 or SEAL, while providing a comparable amount of security. Triple ROT13 is believed to be faster than most of the proposed AES candidates. Hardware implementations can be implemented in far fewer gates, leading to far lower power consumption. 3.5. Test Vectors The following is a set of test vectors to facilitate in the development of interoperable ESP implementations. data = "We believe in rough consensus and running code." data_len = 48 3ROT13_data= "Io Novsofo sx byeqr myxcoxcec Mxn bexxsxq myno." 4. 3ROT13 Operational Requirements ESP_3ROT13 is defined by using 3ROT13 within the context of ESP. This Michael Richardson mcr@sandelman.ottawa.on.ca [page 3] RFCXXXX April 1, 1999 section further defines ESP_3ROT13 by pointing out particular operational parameter requirements. For purposes of IKE key extraction, the key size for this algorithm MUST be fourty-two (42) bits, to facilitate interoperability and to avoid any potential export control problems. To facilitate interoperability, the IV size for this algorithm MUST be zero (0) bits. Padding MAY be included on outgoing packets as specified in [ESP]. 5. Security Considerations If implemented properly, including all weak key checks, the 3ROT13 encryption algorithm offers guarantees that no party other than the sender will ever have knowledge of the plaintext. As stated in [ESP], while the use of encryption algorithms and authentication algorithms are optional in ESP, it is imperative that an ESP SA specifies the use of at least one cryptographically strong encryption algorithm or one cryptographically strong authentication algorithm or one of each. At the time of this writing it is believed that 3ROT13 is legal for use in all parts of the planet earth with the exception of some parts of the Santa Cruz mountains of California. Products using 3ROT13 do not currently fall under the rules of COCOM or Wassenaar treaties. It is, however, illegal to communicate with non-human intelligences using 3ROT13, or communicate technical information about it to them. 6. Intellectual Property Rights Pursuant to the provisions of [RFC-2026], the authors represent that they have disclosed the existence of any proprietary or intellectual property rights in the contribution that are reasonably and personally known to the authors. The authors do not represent that they personally know of all potentially pertinent proprietary and intellectual property rights owned or claimed by the organizations they represent or third parties. 7. Acknowledgments Cheryl Madson is credited with realizing that ROT13 could be made stronger through use of the Encrypt/Decrypt/Encrypt method. Tero Kivinen is credited with identifying the weak key conditions, and wrote the reference implementation for PalmPilot. Tatu Ylonen did the analysis of the number of bits required. 8. References: Michael Richardson mcr@sandelman.ottawa.on.ca [page 4] RFCXXXX April 1, 1999 [RFC-2026] Bradner, S., "The Internet Standards Process -- Revision 3", RFC2026, October 1996. [ESP] Kent, S., Atkinson, R., "IP Encapsulating Security Payload", RFC2406, November 1998. [IKE] Harkins, D., Carrel, D., "The Internet Key Exchange (IKE)", RFC2409, November 1998. 9. Contact information 9.1. Working group The IPSec working group can be contacted via the IPSec working group's mailing list (ipsec@list.tislabs.com) or through its chairs: Robert Moskowitz International Computer Security Association EMail: rgm@icsa.net Theodore Y. Ts'o Massachusetts Institute of Technology EMail: tytso@MIT.EDU 9.2. Author's Address Michael C. Richardson Sandelman Software Works Corp. 152 Rochester Street Ottawa, ON K1R 7M4 Canada Telephone: +1 613 276-6809 EMail: mcr@sandelman.ottawa.on.ca Bruce Schneier President, Counterpane Systems 101 E Minnehaha Parkway Minneapolis, MN 55419 Phone: 612-823-1098 Fax: 612-823-1590 Email: Bruce Schneier Tero Kivinen SSH Communications Security Oy Tekniikantie 12 FIN-02150, ESPOO Tel: +358-9-4354 Email: kivinen@iki.fi Michael Richardson mcr@sandelman.ottawa.on.ca [page 5] RFCXXXX April 1, 1999 10. Appendix: Key derivation /* * Author: Tero Kivinen * * Copyright (c) 1999 Tero Kivinen */ /* * Program: sshisakmp * $Source: /sandel/secure/master/docs/SSW/ietf/rfc-3rot13,v $ * $Author: mcr $ * * Creation : 23:30 Mar 15 1999 kivinen * Last Modification : 00:06 Mar 16 1999 kivinen * Last check in : $Date: 1999/04/21 15:48:18 $ * Revision number : $Revision: 1.1 $ * State : $State: Exp $ * Version : 1.57 * Edit time : 132 min * * Description : 3ROT13 implementation * * * $Log: rfc-3rot13,v $ * Revision 1.1 1999/04/21 15:48:18 mcr * foo * * Revision 1.3 1999/03/15 22:06:59 kivinen * Splited check_for_weak_keys to use check_for_weak_keys_rot13. * Renamed to check_for_weak_keys_3rot13. Splitted key expansion * to split one rot13 key at time. * * Revision 1.2 1999/03/15 21:49:22 kivinen * Added parity. * * Revision 1.1 1999/03/15 21:31:58 kivinen * Created. * * $EndLog$ */ #include #include /* Check for weak key for rot 13 key */ int check_for_weak_keys_rot13(unsigned char *key, int key_nro) { int i, j; /* Check for trivial keys (all zeros, all ones). */ for(j = 0, i = 0; i < 13; i++) j += (key[i] & 0x01) == 0; if (j == 13) { printf("Key %d is weak (all zeros)\n", key_nro); return 0; Michael Richardson mcr@sandelman.ottawa.on.ca [page 6] RFCXXXX April 1, 1999 } for(j = 0, i = 0; i < 13; i++) j += (key[i] & 0x01) == 0x01; if (j == 13) { printf("Key %d is weak (all ones)\n", key_nro); return 0; } if ((j + key[13]) & 1 == 1) { printf("Invalid parity for key %d\n", key_nro); return 0; } return 1; } /* Check for weak keys, and correct parity. */ int check_for_weak_keys_3rot13(unsigned char *key) { int i, j; if (!check_for_weak_keys_rot13(key, 0)) return 0; if (!check_for_weak_keys_rot13(key + 14, 1)) return 0; if (!check_for_weak_keys_rot13(key + 28, 1)) return 0; /* Check for E1, and E2 keys to be same. */ for(j = 0, i = 0; i < 13; i++) j += (key[i] & 0x01) == (key[i + 28] & 0x01); if (j == 13) return 0; return 1; } /* Do the key expansion for the rot13 key. */ void expand_key(unsigned char *key, unsigned char *expanded_key) { int j; /* Initial expansion */ for(j = 0; j < 13; j++) expanded_key[j] = key[j] & ((j < 6) ? 0x01 : 0xff); /* Create expanded key */ for(j = 0; j < 13; j++) { expanded_key[j] ^= ((0x01 ^ (j % 3 == 1)) << 6); expanded_key[j] ^= ((0x01 ^ (j % 3 == 1)) << (((j % 6) > 2) * 5)); expanded_key[j] &= (~1 + (j % 3 != 2)); Michael Richardson mcr@sandelman.ottawa.on.ca [page 7] RFCXXXX April 1, 1999 expanded_key[j] |= (0x01 ^ (j % 3 == 2)); expanded_key[j] ^= ((0x03 ^ ((j % 3 == 0) * 3)) << 2); expanded_key[j] ^= ((0x01 ^ (j % 3 != 2)) << 1); expanded_key[j] ^= expanded_key[j] * (j == 12); } /* Final permutation, make sure expanded key is compatible with 3rot13 standard. */ for(j = 0; j < 2; j++) { expanded_key[j * 6 + 1] |= expanded_key[j * 6 + 4]; expanded_key[j * 6 + 4] |= expanded_key[j * 6 + 1]; expanded_key[j * 6 + 1] &= 0x0f; expanded_key[j * 6 + 4] &= 0x0f; expanded_key[j * 6] |= expanded_key[j * 6 + 5] * (j != 0); expanded_key[j * 6 + 5] |= expanded_key[j * 6] * (j != 0); expanded_key[j * 6 + 3] |= expanded_key[j * 6 + 2] * (j != 0); expanded_key[j * 6 + 2] |= expanded_key[j * 6 + 3] * (j != 0); if (expanded_key[j * 6] == expanded_key[j * 6 + 2]) { expanded_key[j * 6] ^= 0x10; expanded_key[j * 6 + 5] ^= 0x10; } } } /* Split keys to 3 rot13 keys. */ void split_keys(unsigned char *key, unsigned char *split_key[3]) { int i, j; for(i = 0; i < 3; i++) { for(j = 0; j < 13; j++) { split_key[i][j] = key[i * 14 + j]; } } } typedef struct Rot13CipherContextRec { int encrypt; unsigned int s_box[256]; } *Rot13CipherContext; Rot13CipherContext rot13_cipher_allocate( unsigned char key[13], int encrypt) { Rot13CipherContext c; int i, j; c = calloc(1, sizeof(*c)); Michael Richardson mcr@sandelman.ottawa.on.ca [page 8] RFCXXXX April 1, 1999 if (c == NULL) return NULL; c->encrypt = encrypt; for(i = 0; i < 256; i++) c->s_box[i] = i + (key[12] * encrypt); for(i = 0; i < 12; i += 3) { for(j = 0; j < key[i + 1]; j++) { /* Swap s_box[j] with s_box[x + key[i+2]] */ c->s_box[j + key[i]] ^= c->s_box[j + key[i + 2]] ^= c->s_box[j + key[i]] ^= c->s_box[j + key[i + 2]]; } } return c; } void rot13_cipher_transform(Rot13CipherContext c, unsigned char *data, size_t len) { int i; unsigned char d; for(i = 0; i < len; i++) { d = data[i] ^ c->s_box[data[i]]; d ^= (c->s_box[d] >> 8); data[i] = d ^ data[i]; } } void rot13_cipher_deallocate(Rot13CipherContext c) { memset(c, 0, sizeof(*c)); free(c); } int main(int argc, char *argv) { unsigned char *expanded_key[3]; unsigned char *split_key[3]; unsigned char key[1024]; unsigned char data[1024]; Rot13CipherContext e1, d2, e3; size_t len; int i; for(i = 0; i < 3; i++) { split_key[i] = calloc(1, 13); Michael Richardson mcr@sandelman.ottawa.on.ca [page 9] RFCXXXX April 1, 1999 if (split_key[i] == NULL) { fprintf(stderr, "Malloc error, out of memory\n"); exit(1); } expanded_key[i] = calloc(1, 13); if (expanded_key[i] == NULL) { fprintf(stderr, "Malloc error, out of memory\n"); exit(1); } } printf("Key *> "); while (fgets(key, sizeof(key), stdin) != NULL) { if (strlen(key) < 42) { printf("Key too short, must be 42 characters\n"); printf("Key *> "); continue; } if (!check_for_weak_keys_3rot13(key)) { printf("Key is weak key, key rejected\n"); printf("Key *> "); continue; } split_keys(key, split_key); expand_key(split_key[0], expanded_key[0]); expand_key(split_key[1], expanded_key[1]); expand_key(split_key[2], expanded_key[2]); e1 = rot13_cipher_allocate(expanded_key[0], 1); d2 = rot13_cipher_allocate(expanded_key[1], 0); e3 = rot13_cipher_allocate(expanded_key[2], 1); printf("Data *> "); while (fgets(data, sizeof(data), stdin) != NULL) { len = strlen(data); rot13_cipher_transform(e1, data, len); rot13_cipher_transform(d2, data, len); rot13_cipher_transform(e3, data, len); printf("Encrypted data: %s", data); printf("Data *> "); } rot13_cipher_deallocate(e1); rot13_cipher_deallocate(d2); rot13_cipher_deallocate(e3); break; } return 0; Michael Richardson mcr@sandelman.ottawa.on.ca [page 10] RFCXXXX April 1, 1999 } Michael Richardson mcr@sandelman.ottawa.on.ca [page 11]