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
