I'm looking for a file encryption algorithm (or library) that supports
efficient random access to the cleartext. That is, given an encrypted
file, I need to be able to repeatedly read arbitrary byte-ranges from
the cleartext with as little overhead as possible.
What you are asking is highly dependent on the encryption primitive. You can't have arbitrary access to the plaintext without decrypting the ciphertext on each access. To reduce overhead you can decrypt the whole file once, cache it, and use it afterwards or, depending on the encryption scheme, store the minimum required amount of parameters needed to decrypt the needed information. For example, (secure)block ciphers chain all previous blocks prior to the encryption of the current one. Thus it is sufficient to know the output of the previous one(and the key) in order to decrypt the current block. Knowing the length of the block, the initialization vector(if used) and the decryption key you can store the outputs of each block. Unfortunately, in the case of AES, this does not reduce storage requirements(as you will be storing data with the length of the whole plaintext). However, depending on the segments of the file being used you can estimate a usage probability and cache the plaintext only for those entries. Practically, it is difficult to implement due to the (very) likely different offsets of useful plaintext and blocks.
This clearly isn't rocket science: I imagine one would do it by
breaking the file into fixed-size chunks and encrypting each chunk
with a symmetric cipher like AES. I'd need to use a different key for
every block (derived by combining a master key and the block offset?),
and I'd want an in-memory LRU block cache for performance. But it's
fiddly enough that I'd much rather use an existing library than design
it myself and run the risk of getting something disastrously wrong.
A makeshift solution would look like:
# Split the file into separate files of 1000 bytes each, suffixed by _bigFile
split -b 1000 bigFile.tar.gz --additional-suffix=_bigFile
# Encrypt each file using aes256 cbc(with salt)
for fl in *_bigFile; do $ openssl enc -aes-256-cbc -salt -in "$fl" -out "$enc""$fl"; done
# Decrypt each file
for fl in `ls "$enc"`; do openssl enc -aes-256-cbc -d -in "$enc""$fl" -out "$dec""$fl"
If I did have to design this myself, my main question would be key
derivation: is it safe to derive each block's key from a master key
and the block offset -- something like SHA2(masterkey || offset) -- or
do I need to generate a random key for each block? (If the latter,
those keys will need to be stored in the file, which makes it a bit
trickier to keep the file chunks on filesystem block foundaries
No, it is not safe, as getting the key from block i(i is an index to that block) would allow retrieving all remaining keys n - i where n is the number of keys(blocks) and 0 <= i < n. Key management complexity also increases with the number of blocks. It is safe to use a single key for all of them(as you would if you would encrypt/decrypt the file entirely).