Newsgroups: sci.crypt

Subject: Re: Doing Better than XOR in RC4-like Algorithms
Date: 19 Nov 1994 01:24:23 -0000
Organization: Delphi Internet Services Corporation
Lines: 128
Message-ID: <3ajk47$>
NNTP-Posting-Host: (Farid F. El-Wailly) writes:

>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.

Hmmm.  I don't think the modification you suggest would make it safe
to re-use the key.  With known plaintext in one message, an attacker could
still build a "codebook" that allowed decryption of matching bytes in 
the other message.  Also, I suspect that enough known plaintext in several
messages using the same key stream would allow recovery of the 8-bit 
substitution table.

>               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.

I think using a substitution table this way is probably not a bad idea.  
However, it should definitely not be anything internal to the stream cipher
being used, since that would leave a real possibility of introducing new 
weaknesses that weren't there in the normal stream cipher.  (Ie, for your 
RC4 example, you might be able to learn something about the table entries 
from this system that weren't reveaB$Qsg;zGt

>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

>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]]
>         }               
>    }



>Farid F. El-Wailly