On May 11, 2009, at 5:13 PM, Victor Duchovni wrote:

On Mon, May 11, 2009 at 02:16:45PM -0400, Roland Dowdeswell wrote:

In any case, there are obvious, well-understood solutions here:  Use
counter mode, which propagates changes by a single block of the
cryptosystem.  Or use any other stream cipher mode.  (An interesting
question is whether there's a mode that will recover from insertions
or deletions.  Perhaps something like:  Use counter mode.  If two
consecutive ciphertext bytes are 0, fill the rest of the ciphertext
block with 0's, jump the counter by 65536, and insert a special block
containing the new counter value.)

I'm not convinced that a stream cipher is appropriate here because
if you change the data then you'll reveal the plaintext.

Indeed. If the remote copy is a "backup", and the local file-system
supports snaphots, then it is far better to arrange for the remote
backup to always be a copy of a local snapshot, and to compute the rsync "delta" between the local copy of the remote snapshot and a newer snapshot
locally, and then rsync the delta. Sure, snapshot file-systems are not
yet universal, but given disk size and file-system trends, I would base
encrypted remote backups on a foundation that assumed the existence of
local before/after images.
If you have a snapshot file system, sure, you can use it. Caching checksums and using a write barrier (like fsevents in MacOS) would also work.

Any such system will eventually build up either a huge number of small deltas, or deltas that are close to the size of the underlying files (i.e., eventually most things get changed). So you also need a way to reset to a new base - that is, run an rsync as you do today. Thus, while this is certainly a good optimization, you still need to solve the underlying problem.

A cipher that produces largely identical cipher-text for largely identical
plaintext in the face of updates, inserts and deletes, is unlikely to
be particularly strong.
Consider first just updates. Then you have exactly the same problem as for disk encryption: You want to limit the changes needed in the encrypted image to more or less the size of the change to the underlying data. Generally, we assume that the size of the encrypted change for a given contiguous range of changed underlying bytes is bounded roughly by rounding the size of the changed region up to a multiple of the blocksize. This does reveal a great deal of information, but there isn't any good alternative. (Of course, many file types are never actually changed in place - they are copied with modifications along the way - and in that case the whole thing will get re-encrypted differently anyway.)

The CBC IV reset should not be too disasterous if the IV is an encrypted
block counter under a derived key. Drive encryption basically does the
same thing with 512 byte blocks. This fails to handle inserts/deletes
that are not multiples of the "chunk" size.
It's curious that the ability to add or remove blocks in the middle of a file has never emerged as a file system primitive. Most file system organizations could support it easily. (Why would you want this? Consider all the container file organizations we have, which bundle up segments of different kinds of data. A .o file is a common example. Often we reserve space in some of the embedded sections to allow for changes later - patch areas, for example. But when these fill, there's no alternative but to re-create the file from scratch. If we could insert another block, things would get easier.)

Given that file systems don't support the operation, disk encryption schemes haven't bothered either.

To support insertions or deletions of full blocks, you can't make the block encryption depend on the block position in the file, since that's subject to change. For a disk encryptor that can't add data to the file, that's a killer; for an rsync pre-processor, it's no big deal - just store the necessary key-generation or tweak data with each block. This has no effect on security - the position data was public anyway.

To handle smaller inserts or deletes, you need to ensure that the underlying blocks "get back into sync". The gzip technique I mentioned earlier works. Keep a running cryptographically secure checksum over the last blocksize bytes. When some condition on the checksum is met - equals 0 mod M - insert filler to the beginning of the next block before encrypting; discard to the beginning of the next block when decrypting. Logically, this is dividing the file up into segments whose ends occur at runs of blocksize bytes that give a checksum obeying the condition. A change within a segment can at most destroy that segment and the following one; any other segments eventually match up. (The comparison algorithm can't have anything that assumes either block or segment offset from beginning of file are significant - but I think rsync already handles that.) Yes, this leaks *something* about the plaintext which is hard to pin down, but it seems much less significant than what you've already given up to allow local cleartext changes to produce local ciphertext changes.
                                                        -- Jerry

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com

Reply via email to