Applying file deltas to an encrypted file

Question

I am developing software that will be used for data backup.

The server will run on Linux. Security in transportation is not an issue (HTTPS or SSH), but the data must be stored encrypted on the server.

The data is not tied to a single computer, so multiple computers should be able to access the same data, if given a key (shared key is acceptable).

The customer should be assured that the data cannot be viewed on the server, either by a curious employee or a hacker. This means that the server should not store the key used to decipher the encryption, but could use it in a transaction if needed.

Being a file server, the network will be saturated, so sending deltas is preferred over sending entire files. The files will also be managed (on the server) by a version control system; whereas the client may or may not have version control. Space is a consideration.

This is what I've come up with:

• Each user has his/her own mount point
• Each mount point will be encrypted
• Files will be decrypted, have the delta applied, then re-encrypted

This sounds a bit inefficient, so I've come here for guidance.

Can file deltas be applied to an encrypted file?

The most important requirements are:

• Data integrity (updates should never break a file)
• Minimize network/storage overhead (conserving CPU/ram would be nice, but not necessary)
• Must be able to be version controlled

Answer 1

Not yet. You are basically describing homomorphic encryption.

Basically you have a file f that you encrypt with function E() notated as E(f).

Now you have delta d which you encrypt with function E() notated as E(d).

You want the new file f' to be equal to f with the delta applied: f'=f+d

Only you dont want to decrypt either E(f) or E(d).

You want E(f) + E(d) = E(f').

And that's homorphic encryption, but it's not ready for production yet. THere are partially homomorphic cryptosystems, but I'm not sure if the file delta would fit into any of the systems. There is one fully homomorphic cryptosystem in development at IBM, but it takes a good amount of computation power and memory and is still slow for large problems.

IBM Research's page on homomorphic encryption http://domino.research.ibm.com/comm/research_projects.nsf/pages/security.homoenc.html

Craig Gentry's PhD Thesis "Fully homomorphic encryption using ideal lattices" This is a break through paper.

Prior to Gentry's thesis there were fully homomorphic systems but those systems could not be made practical. Some existing cryptosystems, RSA for example, are partially homomorphic, meaning that homomorphic operates work for one operation (multiplication for example) but not the other (addition). They also degrade and can only do a limited number of homomorphic operations before causing errors.

Gentry's breakthrough was to establish bootstraping. In my limited understanding, bootstraping establishes a hidden struture capable of maintaining its coherence across operations.

In May of 2011 "Fully Homomorphic Encryption without Bootstrapping" was published bring homomorphic encryption one step closer to real use.

Answer 2

What about keeping the baseline encrypted and unmodified, and encrypting and storing the deltas separately? When a user wants a particular version of the file, they'd need the baseline and all the deltas to that point. This would be pretty close to space-optimal and network-optimal for writes from the perspective of the file server, but would require additional client-side storage and network bandwidth for reads. Then again, once a client is brought current, any future reads are network-optimal as well. The client is free to use additional space to improve performance in ways that should be pretty obvious.

You could also store encrypted delta-sets, where a client with the key merges a few deltas and encrypts the result, as a way to speed up the initial load by the client. This could be done intelligently to do better than the naive approach would lead to, in terms of network and space on writes, and in any case, would be network- and space-efficient on reads.

Tuning is dependent on the characteristics of the app.

Disclaimer: I am just making this up as I go here; I have no idea if I have described someone else's idea or something.

Answer 3

Beside homomorphic cryptosystem (which RSA is partially one), your 2nd requirement may be achievable depending on how you encrypt the data in the first place.

Assuming you use block cipher in ECB mode, then each block is independent of all others. Which means you are free to decrypt and encrypt any single block in isolation. This would allow you to apply the delta to each block nicely. CTR mode is also a possible mode here. For best result, however, I would recommend ESSIV mode. See http://en.wikipedia.org/wiki/Disk_encryption_theory. This all assumes that you know exactly which sector to modify.

Your 1st and 3rd requirements are not really solvable by encryption alone. Think about disk failure half way through the update. Of course the write will fail, procuding an integrity error.

On the other hand, why don't you use encrypted disk (such as dm-crypt) and mount it on demand, modify the files, and finally unmount it?

Answer 4

You have some sensitive local plaintext files, you want to keep a backup copy of (encrypted versions of) those files on some remote server, you have a limited network bandwidth, and you want to set things up so that if the server is compromised by the bad guys, they can't read the plaintext of your files.

That sounds like exactly the situation rsyncrypto was designed to handle:

Sometimes it is necessary to store files on a remote server for backup purposes.

How do you keep the privacy of files stored on a remote server? Encrypt the files prior to sending them. Keep the key locally.

How do you keep the bandwidth usage to a minimum? Use rsync to only transfer the changes.

There is just one problem - the two solutions contradict.

rsyncrypto comes to the rescue.

With rsyncrypto, both objectives can be achieved simultaneously.

-- slightly paraphrased from the rsyncrypto home page

The rsyncrypto algorithm ensures that two almost identical files, when encrypted with rsyncrypto and the same key, will produce almost identical encrypted files. This allows for the low-overhead data transfer achieved by rsync while providing encryption for secure transfer and storage of sensitive data in a remote location.

-- from Wikipedia: rsync variations

Related questions: "Is there an encrypted version control system?" and "How to do rsync-like encrypted backup?"

Answer 5

The primary issue that you need to address is someone compromising the version control system. My impression is that the VCS will be unencrypted as it is responsible for storing the plaintext, but prior to transmission it gets encrypted. If this is not the case than ignore my previous statement. Regardless applying diffs to binary files is quite intensive and causes a huge overhead in terms of space requirements. This can give some extra information

Update to comment

The version control will only be on the server end (git style preferably, but others work too).

My initial comment still stands about it being vulnerable.

The main focus is that I (as the admin) should never be able to read someone else's data

The encryption will handle that, use an algorithm that is lattice based, this is allegedly immune to both classical and quantum algorithms. MIT lattice
description of homomorphic algorithm
I also want to minimize storage space

This is the crux of Disk encryption theory

Answer 6

The main focus is that I (as the admin) should never be able to read someone else's data, but I also want to minimize storage space (if possible).

A very different approach to minimizing storage space, while never entirely trusting the admin of the remote storage server, is discussed in "Is Convergent Encryption really secure?".

Convergent Encryption is designed to allow the remote storage server to de-duplicate common files, without the admin of the storage server ever getting quite enough information to decrypt whatever is in those files (other than the fact that file A is, in fact, the same as file B, and therefore only needs to be stored once).