Encrypting text file line by line with stable encryption

Question

I want to store files in a secure manner (i.e. no one should be able to decrypt the contents of the file without the secret key) but I also want a diff tool to be able to show me which lines changed (let's assume that you can't learn anything about the content of the file by seeing which lines have changed).

The idea is to encrypt each line individually and convert the result to hex or BASE64 and then write each line into one file. A line with a certain content should always return the same output, no matter where it is in the file.

Specifically, I want a version control tool like Git or Mercurial to be able to efficiently handle the files as text. At the same time, a (self written) UI should be able to show a decrypted diff without the need of decrypting the data inside of the version control tool (git diff would show me the line numbers which I could then decrypt in my app to display them myself).

Is that possible? Do you know where I can find more information how to do this?

Answer 1

Yes, it's possible. Encrypting each line independently, like you suggest is the way to go.

Most likely you will want to use a symmetric encryption algorithm independently for each line – i.e. have a new unique IV/nonce per line. That's the simplest to implement. However, it means every line is up to 128 bits longer. If you can't live with that, you practically have to either sacrifice some security (e.g. use ECB mode without semantic security) or have changes to one line affect nearby lines as well.

One question to consider is whether to use authenticated encryption to guard against an attacker being able to modify the file. This is usually the way to go, but if you have something that ensures integrity at a higher level in your setup (signed tags/commits, say), you could afford to skip it.

For authenticated encryption you need to further decide whether you want a single MAC for the whole file (slower, since it needs to be recalculated after every modification) or one per line (which takes even more space).

---

In practice, I would go with AES for encryption. (Either 128-bit or 256-bit keys – doesn't matter much in practice.)

1. If you can live with the extra space it requires, the absolute simplest from an implementation standpoint (when you have a library that supports it), is to use AES in GCM mode. You get both encryption and authentication in one, and the only requirement for IVs is uniqueness. Each line will be up to 256 bits longer (when using 128 bits for both IV and auth. tag).

2. If you have authentication already, I would go with AES CTR. If you know the file will never have more that $2^k$ lines through its lifetime (counting each version of each line) you could store a $k$-bit value per line instead of a full 128-bit IV. You will need to make sure you never reuse a counter value in any case, including different "forks" of the file.

3. If you need a MAC for the file, you can do the above and append an HMAC.

Answer 2

You may be better off encrypting the file using normal file encryption, and then encrypting the diff that goes with the file, except for the line numbers included in the diff. You could also extract the line number changes from the diff in advance. Otherwise you will have to keep track of the lines, and make sure that the nonces used for each line stay identical.

Also, due to the nature of encryption/decryption, small changes (e.g. to indentation) will result in huge changes in the ciphertext. Even if you use something like CTR mode encryption, you will have to reencrypt changed lines with a different nonce.

Regardless, you will of course convey a lot of information about the plaintext, but that's more or less inherent if you want to perform diffs on the ciphertext.

---

All in all, this could be harder than you might imagine at first glance.

Answer 3

"Specifically, I want a version control tool like Git or Mercurial to be able to efficiently handle the files ... I need an efficient way to preserve the edit history."

The rsyncrypto tool can help version control tools efficiently handle small changes to files, but in bigger chunks than one-line-at-a-time. The rsyncrypto is designed to encrypt files (using standards such as AES encryption as much as possible) such that

two almost identical files, such as the same file before an after a change, when encrypted using rsyncrypto and the same key, will produce almost identical encrypted files.

When you temporarily decrypt a file, change a few bytes, and then re-encrypt a file, Git or Mercurial will see:

• without encryption: a few bytes of changes
• with the proposed line-by-line encryption: a few lines of changes
• with rsyncrypto: a few kbytes of changes
• with most other good encryption tools: pretty much the entire file is different

Perhaps rsyncrypto is close enough that you could use it as-is, or perhaps you could use it with a small amount of tweaking.