Newsgroups: sci.crypt Path: cactus.org!news.dell.com!swrinde!cs.utexas.edu!howland.reston.ans.net! + ix.netcom.com!netcom.com!farid From: farid@netcom.com (Farid F. El-Wailly) Subject: Doing Better than XOR in RC4-like Algorithms Message-ID:Organization: NETCOM On-line Communication Services (408 261-4700 guest) Date: Fri, 11 Nov 1994 21:19:43 GMT Lines: 131 I'd like to suggest a modification of RC4-like algorithms that would make them a little more resistant to the key re-use problem. These algorithms have a random byte generator that is exclusive-or'ed with the cleartext to produce the cyphertext. +----------+ Key ----->| random | | Sequence | +----------+ | v +-----------+ Clear Text ---->| Exclusive |----> Cyphertext (bytes) | or | (bytes) +-----------+ If the same key is used to encrypt two files then cryptanalysis is trivial due to the nature of the exclusive-or. You can cancel out the random sequence by XORing the two cyphertexts together. I suggest instead using a non-linear transformation in place of the exclusive-or, as shown below +----------+ Key ----->| random | | Sequence | +----------+ | v +---+ +-----+ +---+ Clear Text -->| A |---->| XOR |---->| B |-----> Cyphertext (bytes) +---+ +-----+ +---+ (bytes) Where A is a non-linear 8-bit to 8-bit transformation implemented via a table lookup. B is the inverse transformation of A. What is neat is that we may already have a 256 entry table of bytes that can be used for A. In RC4, for example, the "state" table in the key structure can be used. All that is needed is to add another table to the key to implement B, the inverse to the state table A. The inverse table B, "inv", is initialized the same way as "state" and it is automatically the inverse of "state". Maintaining the inverse property is easy. Every time we swap two bytes in "state", we also swap two bytes in "inv" to keep the inverse property. SWAP( state[x], state[y] ) SWAP( inv[state[x]], inv[state[y]] ) Now when we run the algorithm over cyphertext, the A box reverses the final B transformation that was done at the end of encryption, the exclusive-or reverses itself, and the B box reverses the initial A transformation that was done at the beginning of encryption, giving us cleartext. I claim it is very difficult to determine the random sequence or the cleartext given two cyphertexts generated by using the same key on two cleartexts. The following algorithm is based on some C code I saw in this newsgroup a few weeks ago. ++++++++++++++++++++++++++++++++++++++++++++++++++++++ Header file Define the key structure to have two tables state[256] and inv[256]; as well as the two byte variables x and y; Define the prepare_key function prototype; Define the encryption function prototype; Program file Include the header file Define a swap_byte function prototype; Define the prepare_key function it is passed( key_data_ptr, key_data_len, pointer_to_key_struct) { Define the bytes swapByte,index1,index2; state and inv refer to the tables in the key structure x and y are also in the key structure for counter from 0 to 255 by 1 do the following { state[counter] <- counter; inv[counter] <- counter; } x and y(in the key structure), index1, and index2 all get cleared for counter from 0 to 255 by 1 do the following { index2 <- (key_data_ptr[index1] + state[counter] + index2) mod 256 swap_byte state[counter] and state[index2]; swap_byte inv[state[counter]] and inv[state[index2]]; increment index1 modulo the key_data_len; } } Define the encryption function it is passed (buffer_ptr, buffer_len, pointer_to_key_struct) { state and inv refer to the tables in the key structure x and y are also in the key structure for counter from 0 to buffer_len-1 by 1 do the following { increment x modulo 256; add state[x] to y modulo 256; swap_byte state[x] and state[y]; swap_byte inv[state[x]] and inv[state[y]]; set temp to state[x] plus state[y] mod 256; replace buffer_ptr[counter] with inv[state[buffer_ptr[counter]] XOR state[temp]] } } ++++++++++++++++++++++++++++++++++++++++++++++++ Comments? -- Farid F. El-Wailly farid@netcom.com