random access stream cipher

Question

Some time ago I was working in a pet project for a type of database engine. And I thought about securing the data in disk with encryption.. and since the main code was already developed.. I had a few requirements..

• a simple stream class that I could hook instead of my file stream had
• to support random access (both read/write at random positions)
• be able to work at any byte position (since the data might not be aligned)
• encrypt/decrypt only the requested data, not the all file,(because the file maybe several MB)
• fast encryption/decryption, since this was for a database system

nowhere on the web I found information about this, or implementation of such code. Normal stream ciphers don't support random access/lookup, and block ciphers require the data to be aligned and in fixed blocks.. So I thought about developing my own. I do know that developing your own encryption is always a bad choice.. but this was kind of theoretical exercise..

So I would like to present you the code.. just to see how far of I am from a security point of view

First the stream is initialized with a password.. but that password is not used for the encryption itself.. it is used as a seed to scramble an array of 256 values in hope of of increasing the key space

public CipherStream(String sKey,Stream oStream) 
{
    _oStream = oStream;
    //initialize key space
    _oVector = new byte[256];
    for(int i = 0; i <= 255; i++)
    _oVector[i] = (byte)i;
    //shuffle the keyspace
    for (int i = 0; i <= 255; i++)//shuffle the box
    {
        //shuffle this item with other
        //other is chosen by char(i) of password
        //and the currently shuffling vector(I)
        // this means that even repeating passwords 'aaaaaa' will produce random results
        int j = ((sKey[i % sKey.Length]) + _oVector[i]) % 256;
        byte cTemp = _oVector[i];
        _oVector[i] = _oVector[j];
        _oVector[j] = cTemp;
    }
}

after this all we have to do is choose the cipher byte for the position we are trying to read/write from.. in my implementation I used xor, witch I know is not the most safe.. but that is can be changed and is not the core of the algorithm..

public override void Write(byte[] buffer, int offset, int count)
{
    long nPosition = this.Position;
    for (int i = offset; i < count; i++)
    {
        byte oPlain = buffer[i];
        byte nKey = GetKey(nPosition);
        byte oCypher = (byte)(oPlain ^ nKey);

        buffer[i] = oCypher;

        nPosition++;
    }
    _oStream.Write(buffer, offset, count);
}

the 'key' to the byte is chosen from the key vector dependently from the position we are trying to access.. calculations are done so that there are no repetitions and the chosen value is as random as possible

private byte GetKey(long nPosition) 
{
    byte nOffset = _oVector[nPosition % _oVector.Length];
    byte nOffset2 = _oVector[(nPosition / (nOffset + 1)) % _oVector.Length];

    int nDif = nOffset - nOffset2;
    if (nDif < 0)
        nDif += 255;
    byte nKey = (Byte)(nDif % 256);

    return nKey;
}

I did try to render the stream as a bitmap.. just so make sure no patterns where obvious.. and did some fine tunning there.. and it seemed ok..

the best I can describe this algorithm is a 'deterministic predictable pseudo-random generator' where I can just ask 'give me the nth random number', and the seed is a 2048 bit vector that is initialized randomly with a password..

how far am I from a solution? Is this completely insecure? or there is not even point of trying because there is no solution for this 'random access stream' problem?

Answer 1

The idea

'deterministic predictable pseudo-random generator' where I can just ask 'give me the nth random number'

is already known, and there are some stream ciphers that work like this (like CTR mode of a block cipher, or the Salsa/ChaCha family of stream ciphers). Usually they don't produce a single byte, but some larger block of consecutive key stream bytes, which is more efficient if you don't have single bytes to encrypt, and (as mentioned by user4982's answer) doesn't restrict you, as you don't have to use all these key stream bytes to encrypt/decrypt your piece of data.

I won't look at your specific cipher (it is too much on the code level for me), but it is probably not a secure one.

The idea itself (even when implemented with an perfectly secure stream cipher) has a problem when used for random access file encryption: You will be having (at several points of time) different pieces of data encrypted with the same piece of keystream, which then leads to the two-times-pad problem, if a potential attacker could look at your encrypted file at different points in time.

You'll need to reencrypt larger blocks with a new initialization vector to avoid this.

Answer 2

How far am I from a solution? Is this completely insecure?

I'm sorry to say, but: This is insecure, because the cipher is not as strong as modern stream ciphers are. The key schedule procedure has some similarities to RC4, but RC4's key schedule is known to be quite weak. The modern stream ciphers currently have much stronger key schedule functions.

there is no solution for this 'random access stream' problem?

There are solutions.

Some stream ciphers have been designed to provide random access stream property. Thus, there are some stream ciphers you can use for this. This is commonly side-effect of parallizability: the stream cipher may allow processing of multiple blocks in parallel thus allowing fast processing.

BTW, some of stream cipher algorithm which can be or cannot be parallelized are mentioned in answer to question "Are there secure stream ciphers that cannot be parallelized"

The most commonly used stream ciphers that can be used in sort of random access mode are 'counter mode' or CTR. This mode works on multiples of block cipher length (usually 16 or 8 bytes). Thus to process specific byte position, it is necessary to process somewhat larger area, from previous multiple of 8 or 16 to next multiple of 8 or 16.

Related Security Considerations

Some word of advice.

Modern ciphers are very complex functions. If you have something simple, it is most likely not secure. Designing a secure cipher takes very extensive amount of work and is something that is very hard to do.

Stream cipher security does not allow encrypting and decrypting the same location twice, with the same key. I.e. if a location within database is rewritten with new value, you will need to use another key and/or another counter value then the first time.

If you intent to be able to use the same key to write same location multiple times with different values, using the same key, you will need different kind of a solution. Disk and flash-based storage often use XTS mode and AES algorithm for storage security. In order to use XTS mode, there needs to be unique mapping from location of database storage to 128-bit tweak used in XTS mode.

The original question only mentions encryption. Usually encryption shall be complemented with integrity and/or authenticity. In some cases, encryption is possible with little or no extension to the length of the data. Integrity and/or authenticity always has cost, it will extend the length of the data. Neither XTS or CTR mode will offer this. There are some other modes like GCM and CCM that do.

Answer 3

Yes, this is completely insecure.

For example, consider the encryption of the first several characters. Here, it's quite likely that nPosition < nOffset+1 for these characters, and so nOffset2 = _oVector[0]. That means that the i-th keystream output is likely to be _oVector[i]-_oVector[0]; that is, given a guess of _oVector[0], you're giving an attacker know knows/guesses the first handful of bytes of _oVector. Given that, the attacker has a good guess of the first handful of bytes of the password (given how your key expansion logic works).

Designing secure cryptosystems is not an job for amateurs. There are existing primitives that can solve this problem. You don't say exactly how your database will use the cryptosystem (e.g. whether you'll be encrypting individual fields, or trying to encrypt the entire database; will be using the same password to encrypt different things; how critical are attacks that modify the ciphertext), so I am hesitant to say 'here's the correct solution to your problem'.