4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Yes, what you suggest is possible. Are you after suggestions for which algorithms to choose or after a practical implementation? The latter is off topic for this site. $\endgroup$ – otus Jun 30 '14 at 12:49
  • $\begingroup$ I first need some pointers how to get started: Suggestions for algorithms which are well suited for this purpose and things like that so I can start asking implementation questions on SO without getting downvoted. $\endgroup$ – Aaron Digulla Jun 30 '14 at 12:56
  • $\begingroup$ AES-SIV - tools.ietf.org/html/rfc5297 - is an appropriate algorithm to use in this case. $\endgroup$ – user2398029 Jul 5 '14 at 20:25
  • $\begingroup$ @louism: That sounds very promising but I couldn't find any information about the actual implementation. The link just gives an overview (unlike other RFCs). $\endgroup$ – Aaron Digulla Jul 7 '14 at 14:35
  • $\begingroup$ Check out github.com/cryodex/siv-rb for a Ruby extension, which wraps around a C implementation by Dan Harkins. $\endgroup$ – user2398029 Jul 8 '14 at 21:32
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That sounds like I should save the IV/nonce along with the line data. Otherwise, how would I get the same value again when I encode the lines a second time? My gut feeling is that creating the IV/nonce from the line content is a bad idea, right? $\endgroup$ – Aaron Digulla Jun 30 '14 at 13:48
  • $\begingroup$ Ah, I just realized you answered the "save IV with line" part in point #1 above. $\endgroup$ – Aaron Digulla Jun 30 '14 at 13:50
  • $\begingroup$ @AaronDigulla, exactly. You can't really derive it from the line content because you don't know the content before decrypting. (Also because that would lead to collisions on equal lines.) $\endgroup$ – otus Jun 30 '14 at 13:50
  • $\begingroup$ Thanks. As for the k-bit value in #2 above: Can I use a plain counter for this? Or does it have to be random? $\endgroup$ – Aaron Digulla Jun 30 '14 at 13:51
  • 1
    $\begingroup$ @owlstead: Not everyone visiting this site knows as much about encryption as people who hang around here, so adding links often helps. $\endgroup$ – Aaron Digulla Jul 1 '14 at 10:17
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't think I have the time or energy to change the source code of Git or Mercurial. But maybe a better solution would be to hook into Mercurial and encrypt the changesets themselves. $\endgroup$ – Aaron Digulla Jul 1 '14 at 11:46
  • $\begingroup$ If you can get away with encryption on a higher level (e.g. the entire DB) than that would be much easier to implement. But yeah, that depends on the use case and attack scenarios. $\endgroup$ – Maarten Bodewes Jul 1 '14 at 11:56
  • $\begingroup$ I have plain text files and I need an efficient way to preserve the edit history. So encoding individual lines currently looks like the way to go since then, I can use the standard tool chain for everything else. $\endgroup$ – Aaron Digulla Jul 1 '14 at 12:55
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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