Warning! New cryptographic modes!

[Jerry Leichter]

I recently stumbled across two attempts to solve a cryptographic  
problem - which has lead to what look like rather unfortunate solutions.

The problem has to do with using rsync to maintain backups of  
directories.  rsync tries to transfer a minimum of data by sending  
only the differences between new and old versions of files.  Suppose,  
however, that I want to keep my backup "in the cloud", and I don't  
want to expose my data.  That is, what I really want to store is  
encrypted versions of my files - and I don't want the server to be  
able to decrypt, even as part of the transfer.  So what I do is  
locally encrypt each file before trying to sync it.  However, using  
CBC (apparently the only acceptable mode of operation), any change in  
the file itself propagates to changes to the rest of encrypted file,  
so rsync has to transfer the whole rest of the file.  The obvious  
thing to do is to use a mode that doesn't propagate errors - at least  
not too far.

This issue has been faced in the rsync world for compressed filesi n  
the past:  If I try to minimize both byte transfers and space on the  
remote system by compressing files before sending them, any adaptive  
compression algorithm will tend to propagate a single-byte change to  
the end of the file, forcing a big transfer.  The fix that's come be  
be accepted - it's part of all recent versions of gzip (--rsync- 
friendly option, or something like that) is to simply reset the  
compression tables every so often.  (The actual algorithm is a bit  
more clever:  It resets the algorithm whenever some number of bits of  
a rolling checksum match a constant.  This allow resynchronization  
after insertions or deletions.)

Given this history, both murk (http://murk.sourceforge.net/) and  
rsyncrypto (http://sourceforge.net/projects/rsyncrypto/) seem to do  
the same basic thing:  Use CBC, but regularly reset the IV.  Neither  
project documents their actual algorithm; a quick look at the murk  
code suggests that it encrypts 8K blocks using CBC and an IV computed  
as the CRC of the block.  There also seems to be some kind of  
authentication checksum done, but it's not entirely clear what.

So here we have it all:  A new cryptographic mode, documented only in  
C code, being proposed for broad use with no analysis.

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.)
                                                        -- Jerry


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com