XOR256 Stream Encryption with Arcfour PRNG

• Download demo project - 13 Kb

Introduction

The general ideas of the XOR256 encryption/decryption method for the Stream Ciphering case I presented in a previous article with codeproject.com "Some Stream Cipher Encryption/Decryption Algorithms". In that article I used for the generation of the sequence of Pseudo-Random Numbers the Lehmer congruential method. I was criticized for selecting that method because it is considered weak and predictable. In order to improve my encryption method I searched the Internet for some secure Pseudo-Random Number Generators (PRNG) and I found the description of the Arcfour algorithm which seems suitable for my purposes. This algorithm is believed to be fully interoperable with the RC4 algoritm. RC4 is trademark of RSA Data Security, Inc. The most comprehensive description of the Arcfour algorithm I have found on the Internet is at http://www.tillerman.st/ietf/rodney_drafts/draft-kaukonen-cipher-arcfour-01.txt, but information can be found in a lot of other places, just give "Arcfour" to a search engine.

Arcfour Algorithm Description and Implementation

The method implemented in CArcfourPRNG class applies an algorithm here called Arcfour. The implementation has a preliminary Key Setup phase. The key is given as an array of characters (bytes) of maximal length 256.

Preliminary Key Setup:

1. Allocate an 256 element array of 8 bit bytes to be used as an S-box: S[0] .. S[255].
2. Initialize the S-box. Fill each entry first with it's index:

   S[0] = 0; S[1] = 1; etc. up to S[255] = 255;

3. Set j to zero and initialize the S-box with the key like this, repeating key bytes as necessary:

   for(i=0; i<256; i++)
   {
     j = (j + S [i] + key[i % keylen]) % 256;
     //Swapping

     temp = S[i];
     S[i] = S[j];
     S[j] = temp;
   }

4. Initialize i and j to zero.

Random Byte Generation - the pseudorandom byte K is generated:

   i = (i+1) % 256;
   j = (j + S[i]) % 256;
   //Swapping

   temp = S[i];
   S[i] = S[j];
   S[j] = temp;
   t = (S[i] + S[j]) % 256;
   K = S[t];

The CArcfourPRNG class's public interface is:

class CArcfourPRNG
{
public:
  //CONSTRUCTOR

  CArcfourPRNG();
  void SetKey(unsigned char *pucKeyData, int iKeyLen);
  void Reset();
  unsigned char Rand();
//...

};

The Key Setup phase is implemented in the SeyKey() method. The Rand() method is returning the next pseudo-random byte in the sequence. The PRNG can be reset to the initial state using the Reset() method. The class was tested against some known answer tests published on the Internet and the results were identical. This class can also be independently used for other purposes where a PRNG is needed. The usage is easy and an example is given in the following code snippet:

unsigned char aucKey[] = {0x01, 0x02, 0x03, 0x04, 0x05};
CArcfourPRNG oArcfourPRNG;
oArcfourPRNG.SetKey(aucKey, 5);
unsigned char ucRand;
//The first 20 Random Bytes

for(int i=0; i<20; i++)
  cout << "Rand=" << (int)oArcfourPRNG.Rand() << endl;

The XOR256 Stream Ciphering Method Description and Implementation

The usual method applied for Stream Ciphering is to generate a sequence of Pseudo-Random Bytes and to XOR each Stream Byte with the corresponding Pseudo-Random Byte. A known disadvantage of this method is that you cannot use the same key many times because if you have two cipher texts generated by the same key, by XOR-ing those cipher texts you can get the same result you would get by XOR-ing the corresponding plain texts. After that the plain texts could be easily decrypted. My XOR256 method is based on the equation:

cipher[k] = (text[k]^seqX[k] + seq256[k]) % 256  (1)

where the two sequences seqX[k] and seq256[k] are generated by a PRNG. In this way the above mentioned disadvantage is eliminated, so that the same key can be applied many times. Equation (1) can be easily reversed. If we know cipher[k], seqX[k], seq256[k] we can get text[k]:

  if(seq256[k] <= cipher[k]) then
    cipher[k] = cipher[k] - seq256[k]
  else
    cipher[k] = 256 - seq256[k] + cipher[k]
  text[k] = cipher[k] ^ seqX[k]

Let's assume now the scenario for breaking the encryption, considering in equation (1) cipher[k] and text[k] known values and seqX[k], seq256[k] unknown values, than we have 256 possible solutions of the equation, because if for example we fix seq256[k] then we have a unique solution for seqX[k], and seq256[k] can be fixed in 256 possible ways. But we can increase the strength of the method by appling the procedure recursively many times, the number of solutions increasing exponentially with the number of times we apply the procedure:

First Round:
  cipher[k] = (text[k]^seqX[k][0] + seq256[k][0]) % 256
Second Round:
  cipher[k] = (cipher[k]^seq[k][1] + seq[k][1]) % 256
...
NRounds-th Round:
  cipher[k] = (cipher[k]^seq[k][NRounds-1] + seq[k][NRounds-1]) % 256

where the number of iterations (rounds) NRounds is considered a method parameter. It can be shown that in this case the number of solutions is 256^(2*NRounds-1)=2^(8*(2*NRounds-1)). For 5 rounds for example we would have 2⁷² solutions. The difficulty of breaking the encryption resides in the difficulty to computionally manage, using the power of the present computers, the very large number of possible solutions.

Let's consider the plain text text0 text1 ... textk ... which is encrypted in the ciphertext cipher0 cipher1 ... cipherk ... For each stream byte we need to get 2*NRounds random bytes from the PRNG, where NRounds>=1. If k is the current stream position we have:

for(int i=0; i<NRounds; i++)
{
  seqX[k][i] = Rand();
  seq256[k][i] = Rand();
}

We apply the following encryption algorithm:

First Round:
  prev = prev^text[k]
  cipher[k] = (prev^seqX[k][0] + seq256[k][0]) % 256
Second Round:
  cipher[k] = (cipher[k]^seq[k][1] + seq[k][1]) % 256
...
NRounds-th Round:
  cipher[k] = (cipher[k]^seq[k][NRounds-1] + seq[k][NRounds-1]) % 256

with prev initialized to 0 for position k=0. The prev accumulator is used to increase the dificulty of decryption because you cannot easily decrypt the byte at position k in the stream without previously decrypting the bytes at positions 0, 1,...and k-1. For decryption the algorithm is:

NRounds-th Round:
  if(seq256[k][NRounds-1] <= cipher[k]) then
    cipher[k] = cipher[k] - seq256[k][NRounds-1]
  else
    cipher[k] = 256 - seq256[k][NRounds-1] + cipher[k]
  cipher[k] ^= seqX[k][NRounds-1]
...
Second Round:
  if(seq256[k][1] <= cipher[k]) then
    cipher[k] = cipher[k] - seq256[k][1]
  else
    cipher[k] = 256 - seq256[k][1] + cipher[k]
  cipher[k] ^= seqX[k][1]
First Round:
  if(seq256[k][0] <= cipher(k)) then
    cipher[k] = cipher[k] - seq256[k][0]
  else
    cipher[k] = 256 - seq256[k][0] + cipher[k]
  text[k] = cipher[k]^prev^seqX[k][0]
  prev = prev ^ text[k];

also with prev initialized to 0 for position k=0.
The User Interface of the CStreamXOR256 class is:

class CStreamXOR256
{
public:
  //CONSTRUCTOR

  CStreamXOR256(string const& rostrKey, int iRounds);
  //DESTRUCTOR

  virtual ~CStreamXOR256();
  void Reset();
  void Encrypt(string const& rostrIn, string& rostrOut);
  void Decrypt(string const& rostrIn, string& rostrOut);
//...

};

In the constructor CStreamXOR256(string const& rostrKey, int iRounds) you specify the key and the number of rounds, which should be >=1, otherwise an exception is thrown. The Reset() method is resetting the PRNG to the initial state. It should be called before using the same object for decryption. The core of encryption/decryption is done in the methods Encrypt() and respectively Decrypt(). A simple usage example is given below:

try
{
  CStreamXOR256 oStreamXOR256("aaaaaaaa", 9);
  string ostrIn("xxxxxxxx");
  string ostrOut;
  oStreamXOR256.Encrypt(ostrIn, ostrOut);
  oStreamXOR256.Reset();
  ostrIn = "";
  oStreamXOR256.Decrypt(ostrOut, ostrIn);
}
catch(exception& roexception)
{
  cout << roexception.what() << endl;
}

In the project attached to this article a File Encryption/Decryption console application is implemented. To use this application is very easy, for example to encrypt the Readme.txt file using the key "sjehj":

FileCrypt.exe -ksjehj -e ReadMe.txt ReadMe.crp 

and to decrypt it:

FileCrypt.exe -ksjehj -d ReadMe.crp ReadMe.txt

Some command line flags are used to specify the key and the action. The command:

FileCrypt.exe -h

will provide help.

Conclusion

The presented XOR256 stream ciphering method has some advantages over the known XOR> method because it is making possible the reuse of the encryption key. Some disadvantages are that it is slower, involving more computation and also the decryption is slower compared to the encryption. Also the security of the method has not been extensively studied. At this moment I don't know any possible efficient attack. I am very much interested in any feedback from the readers, please e-mail to me!