4
$\begingroup$

Is there a safe way to do crypto that will always produce the same result for a given input?

My use case is transferring deltas of huge files, to a backup server. The backup server has no knowledge of what's in the byte stream (and it shouldn't).

In order to transfer only the changed parts of the file, any block that hasn't changed would need to return the same cyphertext. This allows the server and client to detect identical ranges which don't need to be transferred again (pretty much how rsync works).

I've been looking at a CTR cypher, but as far as I understand I'd need to reuse the IV over time to end up with equally encrypted blocks, which is obviously a no-go.

Is this even possible, or am I violating some basic principle of crypto here?

$\endgroup$
2
  • 6
    $\begingroup$ 1) AES-SIV 2) convergent encryption AKA message locked encryption AKA content-hash-key (CHK). Be sure to include a convergence secret, to avoid the confirmation and learning the remaining information attacks $\endgroup$ Commented Aug 28, 2014 at 15:56
  • 2
    $\begingroup$ Also, you may wish to look into the architecture of tarsnap, which was designed to efficiently solve content-aware deduplication of encrypted backups. $\endgroup$ Commented Aug 28, 2014 at 18:21

1 Answer 1

4
$\begingroup$

Some cryptographers feel that the ultimate goal for an encryption scheme is semantic security or, even better, perfect security.

An encryption scheme that supports de-duplication also allows the backup server -- and the attacker, who we assume steals every backup tape that the server sysadmins send to the off-site backup location -- to detect which parts have changed and which parts stay the same. Such an encryption scheme is, by definition, not semantically secure. I don't see how to build an encryption scheme that supports de-duplication without leaking the fact that two different chunks of plaintext are identical, which apparently makes all such schemes vulnerable to a "learn the remaining information attack", a kind of chosen-plaintext attack. (I hear "the BEAST attack" is related.).

Other cryptographers feel that host-proof protocols are so useful that it may be worth deliberately building encryption algorithms that support de-duplication and other useful features. They argue that deliberately designing an algorithm to be non-semantically secure -- i.e., allowing the attacker to know that one piece of plaintext is the same as some other piece of plaintext, "leaking" that information to an attacker -- is not a big deal if the amount of information leaked is very small.

"Doing deduplication ... leaks information..., but this leakage is often small enough to be ignored entirely." -- Looking for cryptographic secure hash algorithm(s) that produces identical root hash for differently sliced hash list

There already exist a few crypto algorithms that support de-duplication:

  • Tarsnap divides files into variable-length chunks of average size 64 kB. (Colin Percival mentions this in a blog post; I believe the exact details are in the tarsnap "chunkify.c" program text).

  • rsyncrypto divides files into variable-length chunks of average size 4 kB.

  • Content hash keying, also called convergent encryption, uses chunks the size of the entire file (at least in the Tahoe 0.9.0 implementation).

  • ... any others?

It can be proven that the smaller the chunks are, the more information leaks to the attacker. If the chunks are 1 character, the result is a simple substitution cipher, as used in cryptoquotes which are easily completely broken by amateur cryptotographers every day. Two-character chunks are more difficult to break, but the Playfair and four-square cipher can still be completely broken with pencil-and-paper techniques. With chunks of 128 bits and longer -- other than the attacks mentioned above that are inherent to deduplication-friendly encryption -- there doesn't seem to be any known attack against de-duplication-friendly encryption that is feasible with current technology.

"always produce the same result for a given input?"

It is unclear what you are asking. Are you searching for:

  • deterministic encryption always produces the same ciphertext when given the same key and the same plaintext, but (in general) completely different ciphertext with any other key and the same plaintext. The rsyncrypto and Tarsnap systems do this, which means that the server cannot do de-duplication when two different people try to backup the same file; de-duplication only happens when the same person backs a file that is the same (or very similar) to a previous file from that same person.

  • convergent encryption always produces the same ciphertext when given the same plaintext, no matter who encrypts it. When 100 different people try to back up the same file, the server only needs to store 1 copy of (the encrypted version of) that file.

With convergent encryption, the "learn the remaining information attack" can be an offline attack -- once the attacker gets an encrypted file, the attacker can make any number of guesses limited only by the speed of the attacker's computer.

Systems that use deterministic encryption -- even if they don't use convergent encryption -- are less vulnerable to a "learn the remaining information attack", but not immune. With deterministic encryption, the "learn the remaining information attack" is an online attack: the attacker can make guesses limited by how often he can trick the person that has the encryption key into encrypting those guesses on behalf of the attacker. Tricking a person into encrypting some plaintext chosen by the attacker is inherently going to be slower than an offline attack, and there are many ways to rate-limit such an attack to even slower rates.

How hard is it to trick a person into using his secret key to encrypt guesses supplied by the attacker? Easier than you might think -- cryptanalysts at Bletchley Park doing "gardening", BEAST, CRIME, and BREACH show that chosen-plaintext attacks (CPA) are not only theoretically possible, but have have been shown to be practical. The BEAST, CRIME, and BREACH attacks allow an attacker to recover secret authentication cookies, even though the attacker never learns the encryption keys, and the encryption itself (AES encryption, with ephemeral keys generated by Diffie-Hellman key exchange) is arguably not broken.

Further reading:

$\endgroup$
2
  • $\begingroup$ Great answer. It's definitely deterministic encryption I was looking for.You're right on leaking info, but if data is encrypted with a user key (which implies that identical data for different users encrypts in a completely different way), isn't the only way to make a match (attack the deduplication) by using the original key? In which case it's broken anyway :-) $\endgroup$ Commented Sep 2, 2014 at 11:11
  • $\begingroup$ Yes, a system that lets the attacker get the encryption key -- is broken. However, there is a way to attack the deduplication, even if the attacker doesn't know the original key. $\endgroup$
    – David Cary
    Commented Sep 2, 2014 at 15:27

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.