1

I'm going to need to store a whole bunch of encrypted files. Groups of them have very similar content. I would like to optimize the space required using compression, but no encryption algorithm I found is suitable for this. There is, however, a tool out there that is able to do this: rsyncrypto. The license makes it impossible for me to use it, though, and I don't have the expertise to study its implementation and write my own. What I'm looking for is any ready to use encryption algorithm that does the same thing: give similar output for similar input, given that the same key is used. The reduced encryption strength is acceptable.

4
  • 1
    Is there something stopping you from compressing the files first, and then encrypting them? No proper encryption algorithm can be compressible, because by definition the output of encryption must be indistinguishable from random noise in order to not disclose information about the files' original contents. And of course no compression algorithm can compress truly random data - that's proven information theory.
    – Borealid
    Feb 13, 2012 at 19:11
  • @Borealid Yes, the files separately arrive in encrypted form at the location where they are stored and are not to be decrypted there. I know that I will have to sacrifice security to some extent, but that's acceptable. Feb 13, 2012 at 19:17
  • Can the similar content be shifted or does it occur at a fixed offset in each file? Feb 13, 2012 at 19:28
  • @CodeInChaos I will be storing daily copies of multiple files. I would like to store not much more than the changes. Between two files, what remained unchanged should generally be at the same position. Feb 13, 2012 at 19:38

1 Answer 1

0

The algorithm used by rsyncrypto is described at: http://rsyncrypto.lingnu.com/index.php/Algorithm

The essence is that divides the file into blocks based on some local, translation invariant criteria, and then encrypts the blocks separately.

The algorithm doesn't look very complicated, and you should be able to implement it in a few hours.


If the same content stays at the same offset in a file, you can get away with an even simpler algorithm:

Divide the file into constant sized blocks (say 64KiB), and encrypt those blocks separately using CBC. Or just use a mode designed for disk-encryption like XTS.

4
  • Your second suggestion would probably work for my purpose. Makes me wonder, though, why rsyncrypto had to reinvent the wheel. Feb 13, 2012 at 19:48
  • @tvdien rsyncrypto supports shifted data. If a block reoccurs at a different offset, it still gets recognized as similar. This means they can't simply use XTS or constant sized blocks. Feb 13, 2012 at 20:23
  • XTS would completely not accomplish what you want, because part of the encryption key is based on the logical location of the block. So two encrypted blocks with identical contents would (almost assuredly) produce unrelated ciphertext.
    – Borealid
    Feb 14, 2012 at 13:36
  • @Borealid if you read the comments on the question, you'll see that for the OP's problem detecting similar content at the same offset is enough. He doesn't need translation invariance. "Between two files, what remained unchanged should generally be at the same position." Feb 14, 2012 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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