How to encrypt a file for random access

Question

I am a programmer familiar with C/C++ and Python. Lately, we got an assignment from a team asking us to work on one of their projects: we need to make a small program to encrypt a large file using symmetric key encryption. We could easily achieve this using AES128 or AES256 in CRT mode.

The catch however is that if a small part of the file is given along with the location of that bytes from the beginning of the file we should be able to decrypt just that piece.

We thought cutting the file into multiple pieces and applying separate generated key for each but the issue is that regarding what we can do if the said part is not exactly a slice of the size we cut it into. Also would like to know if two over lapping such blocks can be handle.

The idea we are currently working on is this:

• We are slicing into 128 bytes each.
• Calculate number of bytes from the last slice. So if we get bytes from 10 to 128. It will be 9.
• Generate a random padding of 9 bytes at the beginning and then decrypt it. Then remove the first 9 Bytes.
• In case multiple slices overlap they are split and the method is repeated.

So, what I would like to know is if this is sensible or if there's a better cipher or algorithm that allows this.

PS:

1. The files will be image files or document files.
2. Only know some basics of cryptography.

Answer 1

The catch how ever is that if a small part of the file is given along with the location of that bytes from the beginning of the file we should be able to decrypt just that piece.

Normal CTR mode encryption allows one to decrypt any block of the file independent of the rest, so no need to invent your own mode. With AES the block size is always 128 bits, so you can start decrypting from any multiple of 16 bytes. You only need to use the correct counter value.

If you need to start from an offset not a multiple of the block size, you will not need the previous bytes in the block to decrypt it correctly, you can just throw away the initial bytes of the keystream, i.e. truncate $AES_k(c)$ to the rightmost bytes.

Answer 2

You basically want a full disk encryption mode for a block cipher; XTS mode seems to be the current standard. In your case each "disk block" is actually a file offset.

Note that using a stream cipher or counter mode is NOT secure if the data is ever modified in the file, as it would violate the cardinal sin of using the same key and initialization vector to encrypt different messages. This is why fancier modes like XTS were created.

CTR mode could be secure if the file were encrypted exactly once per (key,IV) and was then read-only or append-only. However, going that route would involve a massive rewrite and data migration if your requirements ever changed. So find a respected library that implements XTS mode, do not write it yourself as you are not a cryptographer.

Failing that, I would strongly consider punting and using whatever OS-level file or volume encryption system do its job, such as EFS/BitLocker on Windows or eCryptfs/dm-crypt on Linux. All modern OS have such facilities. Even if you might need some platform specific code or configuration, it would be a massive time-saver and isolate the crypto layer from your application.