Thanks to Bryan G. Olson's continued attacks on the Sapphire Stream Cipher, I have come up with the Sapphire II Stream Cipher. Thanks again to Bryan for his valuable help. Bryan's "differential" attack relies on both of these facts: 1. By continual reorigination of a black box containing a keyed version of the Sapphire Stream Cipher, it is possible to find a set of input strings that differ only in the first two (or possibly three) bytes that have identical output after the first three (or possibly four) bytes. The output suffixes so obtained will not contain the values of the permutation vector bytes that _differ_ because of the different initial bytes encrypted. 2. Because the five index values are initialized to constants that are known by the attacker, most of the locations of the "missing" bytes noted in the above paragraph are known to the attacker (except for those indexed by the ratchet index variable for encryptions after the first byte). I have not yet figured out if Bryan's attack on the original Sapphire Stream Cipher had complexity of more or less than the design strength goal of 2^64 encryptions, but some conservative estimations I made showed that it could possibly come in significantly less than that. (I would probably have to develop a full practical attack to accurately estimate the complexity more accurately, and I have limited time for that). Fortunately, there is a way to frustrate this type of attack without fully developing it. Denial of condition 1 above by increased alteration of the state variables is too costly, at least using the methods I tried. For example, doubling the number of index variables and the number of permutation vector items referenced in the output function of the stream cipher provides only doubles the cost of getting the data in item 1, above. This is bad crypto-economics. A better way is to change the output function such that the stream cipher output byte is a combination of two permutation vector bytes instead of one. That means that all possible output values can occur in the differential sequences of item 1, above. Denial of condition 2 above, is simpler. By making the initial values of the five index variables dependent on the key, Bryan's differential attack is defeated, since the attacker has no idea which elements of the permutation vector were different between data sets, and exhaustive search is too expensive. Do the above changes make another attack possible? Have I really stopped the class of attacks mentioned above? I invite you to analyze this cipher further, both as an encryption algorithm and as a hash generator. ***************************************************************************** THE SAPPHIRE II STREAM CIPHER The Sapphire Stream Cipher is designed to have the following properties: * Be useful for generation of cryptographic check values as well as protecting message privacy. * Accept a variable length key. * Strong enough to justify _at least_ a 64 bit key for balanced security. * Small enough to be built into other applications with several keys active at once. * Key setup fast enough to support frequent key change operations but slow enough to discourage brute force attack on the key. * Fast enough to not significantly impact file read & write operations on most current platforms. * Portable among common computers and efficient in C, C++, and Pascal. * Byte oriented. * Include both ciphertext and plain text feedback (for both optimal data hiding and value in creation of cryptographic check values). * Acceptable performance as a pure pseudorandom number generator without providing a data stream for encryption or decryption. * Allow _limited_ key reuse without serious security degradation. HISTORY AND RELATED CIPHERS The Sapphire Stream Cipher is very similar to a cipher I started work on in November 1993. It is also similar in some respects to the alledged RC-4 that was posted to sci.crypt recently. Both operate on the principle of a mutating permutation vector. Alledged RC-4 doesn't include any feedback of ciphertext or plain text, however. This makes it more vulnerable to a known plain text attack, and useless for creation of cryptographic check values. On the other hand, alledged RC-4 is faster. The Sapphire Stream Cipher is used in the shareware product Quicrypt, which is available at ftp://ftp.csn.net/mpj/qcrypt10.zip and on the Colorado Catacombs BBS (303-772-1062). There are two versions of Quicrypt: the exportable version (with a session key limited to 32 bits but with strong user keys allowed) and the commercial North American version (with a session key of 128 bits). A variant of the Sapphire Stream Cipher is also used in the shareware program Atbash, which has no weakened exportable version. The Sapphire II Stream Cipher is a modification of the Sapphire Stream Cipher designed to be much more resistant to adaptive chosen plaintext attacks (with reorigination of the cipher allowed). OVERVIEW The Sapphire Stream Cipher is based on a state machine. The state consists of 5 index values and a permutation vector. The permutation vector is simply an array containing a permutation of the numbers from 0 through 255. Four of the bytes in the permutation vector are moved to new locations (which may be the same as the old location) for every byte output. The output byte is a nonlinear function of all 5 of the index values and 8 of the bytes in the permutation vector, thus frustrating attempts to solve for the state variables based on past output. On initialization, the permutation vector (called the cards array in the source code below) is shuffled based on the user key. This shuffling is done in a way that is designed to minimize the bias in the destinations of the bytes in the array. The biggest advantage in this method is not in the elimination of the bias, per se, but in slowing down the process slightly to make brute force attack more expensive. Eliminating the bias (relative to that exhibited by RC-4) is nice, but this advantage is probably of minimal cryptographic value. The index variables are set (somewhat arbitrarily) to the permutation vector elements at locations 1, 3, 5, 7, and a key dependent value (rsum) left over from the shuffling of the permutation vector (cards array). KEY SETUP Key setup (illustrated by the function initialize(), below) consists of three parts: 1. Initialize the index variables. 2. Set the permutation vector to a known state (a simple counting sequence). 3. Starting at the end of the vector, swap each element of the permutation vector with an element indexed somewhere from 0 to the current index (chosen by the function keyrand()). The keyrand() function returns a value between 0 and some maximum number based on the user's key, the current state of the permutation vector, and an index running sum called rsum. Note that the length of the key is used in keyrand(), too, so that a key like "abcd" will not result in the same permutation as a key like "abcdabcd". ENCRYPTION Each encryption involves updating the index values, moving (up to) 4 bytes around in the permutation vector, selecting an output byte, and adding the output byte bitwise modulo-2 (exclusive-or) to the plain text byte to produce the cipher text byte. The index values are incremented by different rules. The index called rotor just increases by one (modulo 256) each time. Ratchet increases by the value in the permutation vector pointed to by rotor. Avalanche increases by the value in the permutation vector pointed to by another byte in the permutation vector pointed to by the last cipher text byte. The last plain text and the last cipher text bytes are also kept as index variables. See the function called encrypt(), below for details. PSUEDORANDOM BYTE GENERATION If you want to generate random numbers without encrypting any particular ciphertext, simply encrypt 0. There is still plenty of complexity left in the system to ensure unpredictability (if the key is not known) of the output stream when this simplification is made. DECRYPTION Decryption is the same as encryption, except for the obvious swapping of the assignments to last_plain and last_cipher and the return value. See the function decrypt(), below. C++ SOURCE CODE FRAGMENT The original implimentation of this cipher was in Object Oriented Pascal, but C++ is available for more platforms. /* sapphire.h -- Interface for the Saphire II stream cipher. Dedicated to the Public Domain the author and inventor (Michael Paul Johnson). This code comes with no warranty. Use it at your own risk. Ported from the Pascal implementation of the Sapphire Stream Cipher 9 December 1994. Added hash-specific functions 27 December 1994. Made index variable initialization key-dependent, made the output function more resistant to cryptanalysis, and renamed to Sapphire II Stream Cipher 2 January 1995. unsigned char is assumed to be 8 bits. If it is not, the results of assignments need to be reduced to 8 bits with & 0xFF or % 0x100, whichever is faster. */ class sapphire { // These variables comprise the state of the state machine. unsigned char cards[256]; // A permutation of 0-255. unsigned char rotor, // Index that rotates smoothly ratchet, // Index that moves erratically avalanche, // Index heavily data dependent last_plain, // Last plain text byte last_cipher; // Last cipher text byte // This function is used by initialize(), which is called by the // constructor. unsigned char keyrand(int limit, unsigned char *user_key, unsigned char keysize, unsigned char *rsum, unsigned *keypos); public: sapphire(unsigned char *key = NULL, // Calls initialize if a real unsigned char keysize=0); // key is provided. If none // is provided, call initialize // before encrypt or decrypt. ~sapphire(); // Destroy cipher state information. void initialize(unsigned char *key, // User key is used to set unsigned char keysize); // up state information. void hash_init(void); // Set up default hash. unsigned char encrypt(unsigned char b = 0); // Encrypt byte // or get a random byte. unsigned char decrypt(unsigned char b); // Decrypt byte. void hash_final(unsigned char *hash, // Copy hash value to hash unsigned char hashlength=20); // Hash length (16-32) void burn(void); // Destroy cipher state information. }; /* sapphire.cpp -- the Saphire II stream cipher class. Dedicated to the Public Domain the author and inventor: (Michael Paul Johnson). This code comes with no warranty. Use it at your own risk. Ported from the Pascal implementation of the Sapphire Stream Cipher 9 December 1994. Added hash pre- and post-processing 27 December 1994. Modified initialization to make index variables key dependent, made the output function more resistant to cryptanalysis, and renamed to Sapphire II 2 January 1995 */ #ifdef UNIX #include #include #else #include #endif #include "sapphire.h" unsigned char sapphire::keyrand(int limit, unsigned char *user_key, unsigned char keysize, unsigned char *rsum, unsigned *keypos) { unsigned u, // Value from 0 to limit to return. retry_limiter, // No infinite loops allowed. mask; // Select just enough bits. retry_limiter = 0; mask = 1; // Fill mask with enough bits to cover while (mask < limit) // the desired range. mask = (mask << 1) + 1; do { *rsum = cards[*rsum] + user_key[(*keypos)++]; if (*keypos >= keysize) { *keypos = 0; // Recycle the user key. *rsum += keysize; // key "aaaa" != key "aaaaaaaa" } u = mask & *rsum; if (++retry_limiter > 11) u %= limit; // Prevent very rare long loops. } while (u > limit); return u; } void sapphire::initialize(unsigned char *key, unsigned char keysize) { // Key size may be up to 256 bytes. // Pass phrases may be used directly, with longer length // compensating for the low entropy expected in such keys. // Alternatively, shorter keys hashed from a pass phrase or // generated randomly may be used. For random keys, lengths // of from 4 to 16 bytes are recommended, depending on how // secure you want this to be. int i; unsigned char toswap, swaptemp, rsum; unsigned keypos; // If we have been given no key, assume the default hash setup. if (keysize < 1) { hash_init(); return; } // Start with cards all in order, one of each. for (i=0;i<256;i++) cards[i] = i; // Swap the card at each position with some other card. toswap = 0; keypos = 0; // Start with first byte of user key. rsum = 0; for (i=255;i>=0;i--) { toswap = keyrand(i, key, keysize, &rsum, &keypos); swaptemp = cards[i]; cards[i] = cards[toswap]; cards[toswap] = swaptemp; } // Initialize the indices and data dependencies. // Indices are set to different values instead of all 0 // to reduce what is known about the state of the cards // when the first byte is emitted. rotor = cards[1]; ratchet = cards[3]; avalanche = cards[5]; last_plain = cards[7]; last_cipher = cards[rsum]; toswap = swaptemp = rsum = 0; keypos = 0; } void sapphire::hash_init(void) { // This function is used to initialize non-keyed hash // computation. int i, j; // Initialize the indices and data dependencies. rotor = 1; ratchet = 3; avalanche = 5; last_plain = 7; last_cipher = 11; // Start with cards all in inverse order. for (i=0, j=255;i<256;i++,j--) cards[i] = (unsigned char) j; } sapphire::sapphire(unsigned char *key, unsigned char keysize) { if (key && keysize) initialize(key, keysize); } void sapphire::burn(void) { // Destroy the key and state information in RAM. memset(cards, 0, 256); rotor = ratchet = avalanche = last_plain = last_cipher = 0; } sapphire::~sapphire() { burn(); } unsigned char sapphire::encrypt(unsigned char b) { // Picture a single enigma rotor with 256 positions, rewired // on the fly by card-shuffling. // This cipher is a variant of one invented and written // by Michael Paul Johnson in November, 1993. unsigned char swaptemp; // Shuffle the deck a little more. ratchet += cards[rotor++]; swaptemp = cards[last_cipher]; cards[last_cipher] = cards[ratchet]; cards[ratchet] = cards[last_plain]; cards[last_plain] = cards[rotor]; cards[rotor] = swaptemp; avalanche += cards[swaptemp]; // Output one byte from the state in such a way as to make it // very hard to figure out which one you are looking at. last_cipher = b^cards[(cards[ratchet] + cards[rotor]) & 0xFF] ^ cards[cards[(cards[last_plain] + cards[last_cipher] + cards[avalanche])&0xFF]]; last_plain = b; return last_cipher; } unsigned char sapphire::decrypt(unsigned char b) { unsigned char swaptemp; // Shuffle the deck a little more. ratchet += cards[rotor++]; swaptemp = cards[last_cipher]; cards[last_cipher] = cards[ratchet]; cards[ratchet] = cards[last_plain]; cards[last_plain] = cards[rotor]; cards[rotor] = swaptemp; avalanche += cards[swaptemp]; // Output one byte from the state in such a way as to make it // very hard to figure out which one you are looking at. last_plain = b^cards[(cards[ratchet] + cards[rotor]) & 0xFF] ^ cards[cards[(cards[last_plain] + cards[last_cipher] + cards[avalanche])&0xFF]]; last_cipher = b; return last_plain; } void sapphire::hash_final(unsigned char *hash, // Destination unsigned char hashlength) // Size of hash. { int i; for (i=255;i>=0;i--) encrypt((unsigned char) i); for (i=0;i