mrb :- "...any cypher will be vulnerable to the multiple-snapshot attack to determine which parts have changed, unless the whole file or volume is re-encrypted whenever something has changed."

Which is correct only if by "file" you are refering to the whole backup not individual user files and importantly a different key is used each time.

However you go on to say,

mrb :- "Of course, that attacker wouldn't know what the changed part contains or contained in the past."

You are making a very dangerous assumption there which is that the change has no context to other events.

First off how about the fact that a very large number of organisations use a "third party" offsite storage facility for their backup tapes...

The tape "owner" assumption is that as the backup is encrypted then it does not matter what the "third party" does with the tape provided it's available if and when required by the owner organisation.

They do not think, as a lot of backup encryption system designers also appear not to, about either "attacks in depth" or about how "Traffic analysis" methods might be applied to the "deltas" of the backups when mapped onto a time line of known events about the target "owner".

Secondly think about SAN and NAS systems with their "snap-shot" modes. They provide a very fine grained set of deltas so even if the volume is encrypted you will be able to roll backwards and forwards easily almost on a file by file basis. And due to efficiency only the key used for the individual file blocks can be changed.

A lot of "full" backup tapes start with almost "time invariant" system files (which are likley to be known quiet accuratly to an attacker) so a simple examination would reveal if the same encryption key had been used from one backup to another (very bad but happens).

The backups then tend to follow exactly the same file system walk each time (so the same files tend to be in the same place each time).

Worse the information about which individual backup tape file and what it relates too, is often recorded in plaintext as part of the tape header etc to aid use in recovery...

Even not having usefull plaintext knowing such things as when the company starts it's financial year end might easily reveal which part of the tape(s) covers the finance dept server etc etc.

A sudden change in the areas known to be used by marketing would be an early indicator of a new campaign and possibly product. Finding this area would be a simple case of rolling back wards from a previous campaign.

With each delta more and more information about what is where on the backups etc will leak from simple "traffic analysis".

Once the various sections are mapped out just monitoring the size of changes is going to provide usefull intel.

So much so that it might reduce the information required for a direct attack to knowing not much more than the text of a letter, and which person typed it up and having a delta or snapshot from the night before and the night after might be all you need to start a known plaintext attack (often possible as due to speed the encryption actually used is effectivly a stream system in older solutions).

I could go on but the simple fact is that a lot of the systems I have looked at are vulnerable in one way or another to "traffic analysis" on their backups and most definatly on SAN/NAS snapshots.

Security of information on storage systems is a very very hard problem when you start looking at it from a slightly higher level than just a one off image of data.

Things like metadata and invariant scripts aide the attacker, and applying traffic analysis methods elicits quite a lot of information.

Doing daft things like using the same key to back up internal only servers with others that have public data storage (mail servers etc) aid attackers by enabaling chosen plaintext attacks.

Oh and if you examin your backup tapes and discover that an attack in depth is possible due to key reuse or it effectivly uses stream encryption then go and find another solution pronto...