6
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ There are random access stream ciphers, such as AES-CTR or Salsa20. But they are problematic since they can easily lead to two-time-pads. I think the closest you're going to get is XTS which needs to encrypt a few bytes close to the data you want to read. $\endgroup$
    – CodesInChaos
    Nov 4, 2013 at 18:31
  • $\begingroup$ The SEAL stream cipher looks what you are looking for. Check the literature to see if it has attacks. $\endgroup$
    – daruma
    Nov 7, 2015 at 10:54

3 Answers 3

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This mode works on multiples of block cipher length . that is what I was trying to prevent not having to read 8 bytes to use 1..Modern ciphers are very complex functions that is probably why database engines do not encrypt their data.. that was why I was trying to achieve, a speed vs security trade of.. :( doesn't it make sense? $\endgroup$
    – CaldasGSM
    Nov 4, 2013 at 18:11
  • $\begingroup$ First of all, your premise is wrong; there are certainly databases that are encrypted. It is possible to encrypt columns as well if this is supported by the db engine. Furthermore, I don't think the complexity of the algorithm is the reason why it isn't deployed much. Other reasons may include: the key management is difficult to get right, the mapping of ciphertext on pre-defined fields is an issue, it is very difficult to perform any operations like search on a encrypted value and then there is the issue of understanding crypto, which is unfortunately not that high for most database engineers $\endgroup$
    – Maarten Bodewes ♦
    Nov 4, 2013 at 18:51
  • 1
    $\begingroup$ @CaldasGSM You do not need to read 16 bytes to use 1. You just need to apply the block cipher on multiples of block cipher length. I.e. you may retrieve say only 2 bytes from the database, but you'll end up having to make usually 1 cipher operation with full cipher block, occasionally 2 (the worst case). Given that in most cases cipher is much faster than database access, you're likely optimizing in wrong place. Think this way: the block size is the natural data unit size of cipher. It being e.g. 16 is better than 1. All modern stream ciphers tend to work on block size larger than 1 char. $\endgroup$
    – user4982
    Nov 4, 2013 at 19:02
  • $\begingroup$ My understanding is that the XTS mode and CTR mode (and all other popular whole-disk encryption modes) does "encrypting and decrypting the same location twice, with the same key." when writing to the disk. Are you seriously saying that all of them are doing it wrong? $\endgroup$
    – David Cary
    Mar 31, 2016 at 20:18
  • $\begingroup$ XTS is often a pretty good solution for whole disk encryption. It is indeed possible to detect with XTS if a block returns to one of its previous values. Still, it is significantly better if attacker has chance to compare against previous snapshots than CTR. However, the original question is about database engine, which is similar but not the same problem than full disk encryption. $\endgroup$
    – user4982
    Mar 31, 2016 at 21:12
4
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.