Let's assume I have an 18GB database that is backed up nightly by dumping the database and then encrypted using a modern algorithm such as AES-256. This database has a daily update of rate of approximately 5%.

The storage medium the backups are saved on support block level de-duplication. I'm interested in knowing how this would impact the de-dupe rates of the backup partition.

  • 3
    You probably have to know the de-dupe rates beforehand to measure impact. Duplication of encrypted content should be approximately equal to duplication rates of random bits. So birthday paradox where N is the size of the block. – tylerl Jul 24 '13 at 5:42
  • How do you encrypt? Which mode? And what's the nature of your data? – CodesInChaos Jul 24 '13 at 7:15
  • @tylerl: Oh definitely. To do a real quantitative analysis then yes, that information is required. This was a more theoretic question so I could have generic conversations with storage and/or DB people. Presumably before the analysis occurred. – Scott Pack Jul 25 '13 at 14:00

Deduplication works on detection of identical files or blocks of data. Such duplicates occur only with negligible probability in random data, and properly encrypted data ought to be indistinguishable from randomness. Encryption is there to ensure confidentiality and this includes, in particular, hiding from any eavesdropper whether two source data files are identical or not.

In that sense, deduplication can work on encrypted files only if the encryption model is weakened. This is not a light decision: in the case of your database, showing which "blocks" have changed and which have not can be quite revealing on what you did with your database in the meantime. The generic term is traffic analysis. The Wikipedia page lists several famous military cases; traffic analysis is also very good at predicting business tactics of competitors (e.g. noticing in advance preparations for release of new major products).

Assuming that you want to do block-level deduplication, despite the possible leaks alluded to above, there are good ways and bad ways to do it. First you need to split the input data into block-sized chunks, actually a bit smaller because of the need for an extra per-block header (for IV and a MAC). Each block will be encrypted separately. Now the tricky part is that for deduplication to work, the same block data must be reencrypted identically if it did not change between invocations -- so it must reuse the IV. Reusing IV value is a sin; it is deadly when using modes like CTR and in particular its modern derivatives GCM and EAX. The solution here is an IV computed with a one-way function from the block offset in the file, and its contents; the one-way function should be "random looking", and be keyed, because otherwise attackers could try exhaustive search on the data itself, matching with the block IV.

The following scheme should be safe (within the weakened model) but this would require some careful analysis:

  • There are two keys K1 and K2 (possibly derived from a single master key with a Key Derivation Function.

  • For block number i, with data d, compute IV = HMAC(K1, i || d) (the IV is the result of HMAC/SHA-256 over the concatenation of i and the data d, using K1 as key -- truncate the IV to its first 128 bits).

  • Encrypt d with AES, using the IV from previous step and key K2, in CBC mode.

  • Put the IV and the encryption result together in a block-size chunk.

This uses CBC and MAC-and-encrypt, which is "not ideal" as far as cryptography is concerned, but hey, weakened model. You get what you ask for.

Edit: Important note: though some HMAC is being used here, this does not guarantee integrity of the block data. You may use the IV for decryption and then recompute the IV and see if it matches the one in the file; this will prevent generic alterations, but an active attacker could still replace a block with an older version of this same block. If you need some integrity check on your backups, do the following: in addition to any encryption and MAC described above, compute a MAC or a signature on the complete file and verify that before using the backup (if you are restoring a backup, then I assume that you will read it completely anyway, so you could have the MAC or signature verification "for free").

  • This is pretty great. I find this pretty dang helpful. – Scott Pack Jul 25 '13 at 14:01

Deduplication loves patterns in the data, good crypto hates patterns in the output. It follows then that dedupe before encrypt is going to produce better dedupe results.

I'm going to assume you have multiple nightly backup copies of the database, and it's primarily the dedupe effectiveness across those you are interested in.

Certain block cipher modes will propagate changes forward (e.g. CBC): a single difference in the first block of the input will result in (almost certainly) a completely different output. Bad for dedupe.

If the chosen encryption localises changes in the input to the same block or blocks (give or take) in the output, then dedupe can be effective.

Block cipher counter modes (CTR, XTS) do not have this propagation property, thus solving problems with random access and parallel/concurrent encryption and decryption. (Synchronous stream ciphers also localise changes in input.)

A changed IV/nonce/salt (you are using a random salt or IV, right?) will (almost certainly change) every single block. Bad for dedupe.

If you really want to sacrifice some security, you should measure your dedupe performance using a fixed IV or salt with AES-256 in CTR mode to see what the dedupe benefit is.

To summarise:

It depends exactly on which mode of AES is in use, worst case for dedupe is if you're either using CBC or a random IV/salt for each backup: there will be (near) zero dedupe gain.

If you're using CTR or XTS modes, and a static IV (not a good plan in general, and definitely not with CTR mode), then you should see reasonable gains.

You'll (almost) never get the same gain compared with unencrypted files: if you have large runs of zeroed or identical blocks (not uncommon in databases) these will not appear as such in the encrypted output (unless you're using something silly like ECB mode). The best you can hope for is dedupe between backup files approaching 95% (and dedupe within each encrypted backup file approaching 0%).

See these for how this and similar problems are solved:

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.