Warning! New cryptographic modes!

[Jerry Leichter]

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 majordomo at metzdowd.com