Writing a C++ iostream that uses the RC4 stream cipher. How can I optimize my implementation?

Question

I am implementing a custom iostream (i.e., with read, write, seek and close) which uses the RC4 stream cipher for encryption and decryption. One of the contracts of this stream is that it is bidirectional and calling code needs to be able to arbitrarily seek to any position in the stream before doing any actual reading or writing.

Now because RC4 utilizes a key that relies on all previous swap operations up to a given 'tell' position, how can I incorporate an ability to arbitrarily seek to any position?

Obviously I could seek up to the position of the given seek offset (marked by THIS BIT in the following example), before doing the actual xor-ing transformation process, something like,:

/**
 * @brief called from a stream's read or write function
 * @param in the input buffer
 * @param out the output buffer
 * @param startPosition the current stream position (obtained via the streams
 * tellg or tellp functions for read and write respectively)
 * @param length the number of bytes to transform
 */
void transform(char *in, char *out,
               std::ios_base::streamoff startPosition,
               long length)
{

    // need to reset sbox from member s_box each time this
    // function is called
    long sbox[256];
    for (int i = 0; i<256; ++i) {
        sbox[i]=m_sbox[i];
    }

    // ***THIS BIT***
    // need to run the swap operation startPosition times
    // to get sbox integer sequence in order
    int i = 0, j = 0, k = 0;
    for (int a=0; a < startPosition; ++a) {
        i = (i + 1) % 256;
        j = (j + sbox[i]) % 256;
        swapints(sbox, i, j);
    }

    // now do the actual xoring process up to the length
    // of how many bytes are being read or written
    for (int a=0; a < length; ++a) {
        i = (i + 1) % 256;
        j = (j + sbox[i]) % 256;
        swapints(sbox, i, j);
        k = sbox[(sbox[i] + sbox[j]) % 256];
        out[a] = in[a] ^ k;
    }

}

and then the transform would be called from the read or write of the stream implementation, something like:

MyStream&
MyStream::read(char * const buf, std::streamsize const n)
{
    std::ios_base::streamoff start = m_stream.tellg();
    std::vector<char> in;
    in.resize(n);
    (void)m_stream.read(&in.front(), n);
    m_byteTransformer->transform(&in.front(), buf, start, n);
    return *this;
}    

EDIT: the stream should have no knowledge of how the transformation function works. The transformation function is completely independent and I should be able to freely swap in different transformation implementations.

EDIT: the function swapints looks like this:

void swapints(long *array, long ndx1, long ndx2)
{
    int temp = array[ndx1];
    array[ndx1] = array[ndx2];
    array[ndx2] = temp;
}

The real problem with the above transform function is in its slowness because it has to perform startPosition initial swap operations before the xor transformation-proper is performed. This is very problematic when many seek operations are performed. Now I've heard that RC4 is meant to be quick but my (probably bad implementation) suggests otherwise given the initial set of swap operations.

So my real question is: how can the above code be optimized to reduce the number of required operations? Ideally I would like to eliminate the initial ("THIS BIT") set of swap operations

EDIT: optimizing out the initial sbox setting is probably trivial (e.g. using memcpy as suggested by egur). The important optimization I think is how I can optimize out the loop marked by THIS BIT. Perhaps all those swap ints can be programmed more concisely without the need for a for-loop.

Thanks,

Ben

Answer 1

After some research, it turns out that random access of RC4's key-stream is not possible. See discussion at this link: crypto.stackexchange. A better alternative (as pointed out by Rossum in his comment) is to use a block cipher in counter mode.

What you do in counter mode is to encrypt a sequence of numbers. This sequence is incremental and is the length of the entire stream of data. So, say you want to encrypt 8 bytes of data starting at position '16' of the original data stream using a 64 bit (8 bytes) block cipher.

8 bytes need to be enciphered since you operate over 8-bytes of plain text at a time. Since the position we want to randomly offset to is 16, we essentially encrypt 'block 3' of this number sequence (bytes 0 to 7 == block 1, bytes 8 to 15 == block 2, bytes 16 to 23 == block 3 and so on...)

For example using the XTEA algorithm which encrypts blocks of 8 bytes using a 128 bit key, we'd do something like:

Block 3:

// create a plain text number sequence 
uint8_t plainText[8];
plainText[0] = 16;
plainText[1] = 17;
.
.
.
plainText[7] = 23;

// encrypt the number sequence
uint8_t cipherText[8];
applyXTEATransformation(plainText, cipherText, keyOfLength128Bit);

// use the encrypted number sequence as a 
// key stream on the data to be encrypted
transformedData[16] = dataToBeEncrypted[16] ^ cipherText[0];
transformedData[17] = dataToBeEncrypted[17] ^ cipherText[1];
.
. 
.
transformedData[23] = dataToBeEncrypted[23] ^ cipherText[7];

tldr: I wanted to do random access on RC4 but discovered it isn't possible so used counter mode on an XTEA block cipher instead.

Ben

Answer 2

Change all % 255 to & 0xff, much faster:

i = (i + 1) % 256;

To:

i = (i + 1) & 0xFF;

Edit:

You're wasting a lot of time initializing sbox. You should pass sbox as a parameter to the transform function so the original copy is updated between calls. What you're doing now is initializing it again and again and every time it will take longer since startPosition grows.

void transform(char *in, char *out,
           long length,
           unsigned char* sbox)

The temporary sbox should be a member of the MyStream class. The read function should be:

MyStream&
MyStream::read(char * const buf, std::streamsize const n)
{
    std::ios_base::streamoff start = m_stream.tellg();
    std::vector<char> in;
    in.resize(n);
    (void)m_stream.read(&in.front(), n);

    // init m_TempSbox on first call
    if (m_FirstCall) {
        initTempSbox();
    }

    m_byteTransformer->transform(&in.front(), buf, n, m_TempSbox);
    return *this;
}