Re: Warning! New cryptographic modes!
I believe that mode has been renamed EME2 because people were having a fit over the *. On May 14, 2009, at 12:37 AM, Jon Callas wrote: I'd use a tweakable mode like EME-star (also EME*) that is designed for something like this. It would also work with 512-byte blocks. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Warning! New cryptographic modes!
For what it is worth, in the Tahoe-LAFS project [1] we simply use CTR mode and a unique key for each file. Details: [2] Tahoe-LAFS itself doesn't do any deltas, compression, etc., but there are two projects layered atop Tahoe to add such features -- a plugin for duplicity [3] and a new project named GridBackup [4]. Those upper layers can treat the Tahoe-LAFS as a secure store of whole files and therefore don't have to think about details like cipher modes of operation, nor do they even have to think very hard about key management, thanks to Tahoe-LAFS's convenient capability- based access control scheme. Regards, Zooko [1] http://allmydata.org [2] http://allmydata.org/trac/tahoe/browser/docs/architecture.txt [3] http://duplicity.nongnu.org [4] http://podcast.utos.org/index.php?id=52 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Warning! New cryptographic modes!
On May 11, 2009, at 7:06 PM, silky wrote: How about this. When you modify a file, the backup system attempts to see if it can summarise your modifications into a file that is, say, less then 50% of the file size. So if you modify a 10kb text file and change only the first word, it will encrypt that component (the word you changed) on it's own, and upload that seperate to the file. On the other end, it will have a system to merging these changes when a file is decrypted. It will actually be prepared and decrypted (so all operations of this nature must be done *within* the system). Then, when it reaches a critical point in file changes, it can just upload the entire file new again, and replace it's base copy and all the parts. Slightly more difficult with binary files where the changes are spread out over the file, but if these changes can still be summarised relatively trivially, it should work. To do this, the backup system needs access to both the old and new version of the file. rsync does, because it is inherently sync'ing two copies, usually on two different systems, and we're doing this exactly because we *want* that second copy. If you want the delta computation to be done locally, you need two local copies of the file - doubling your disk requirements. In principle, you could do this only at file close time, so that you'd only need such a copy for files that are currently being written or backed up. What happens if the system crashes after it's updated but before you can back it up? Do you need full data logging? Victor Duchovni suggested using snapshots, which also give you the effect of a local copy - but sliced differently, as it were, into blocks written to the file system over some defined period of time. Very useful, but both it and any other mechanism must sometimes deal with worst cases - an erase of the whole disk, for example; or a single file that fills all or most of the disk. -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Warning! New cryptographic modes!
On Tue, May 12, 2009 at 10:39 AM, Jerry Leichter leich...@lrw.com wrote: On May 11, 2009, at 8:27 PM, silky wrote: The local version needs access to the last committed file (to compare the changes) and the server version only keeps the 'base' file and the 'changes' subsets. a) What's a committed file. I'm thinking an SVN-style backup system. When you're done with all your editing, you just commit the changes to go into the backup. As part of the commit operation, it decides on the amount of changes you've done and whether it warrants an entire re-encrypt and upload, or whether a segment can be done. b) As in my response to Victor's message, note that you can't keep a base plus changes forever - eventually you need to resend the base. And you'd like to do that efficiently. As discussed in my original post, the base is reset when the changes are greater then 50% of the size of the original file. So yes, it does increase the amount of space required locally (not a lot though, unless you are changing often and not committing), Some files change often. There are files that go back and forth between two states. (Consider a directory file that contains a lock file for a program that runs frequently.) The deltas may be huge, but they all collapse! In that specific case, say and MS Access lock file, it can obviously be ignored by the entire backup process. and will also increase the amount of space required on the server by 50%, but you need pay the cost somewhere, and I think disk space is surely the cheapest cost to pay. A large percentage increase - and why 50%? - scales up with the amount of storage. There are, and will for quite some time continue to be, applications that are limited by the amount of disk one can afford to throw at them. Such an approach drops the maximum size of file the application can deal with by 50%. No reason for 50%, it can (and should) be configurable. The point was to set the time at which the base file would be reset. I'm not sure what cost you think needs to be paid here. Ignoring encryption, an rsync-style algorithm uses little local memory (I think the standard program uses more than it has to because it always works on whole files; it could subdivide them) and transfers close to the minimum you could possibly transfer. The cost of not transferring a entirely new encrypted file just because of a minor change. -- noon silky - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Warning! New cryptographic modes!
On May 11, 2009, at 7:08 PM, Matt Ball wrote: Practically, to make this work, you'd want to look at the solutions that support 'data deduplication' (see http://en.wikipedia.org/wiki/Data_deduplication). These techniques typically break the data into variable length 'chunks', and de-duplicate by computing the hash of these chunks and comparing to the hashes of chunks already stored in the system. These chunks provide a useful encryption unit, but they're still somewhat susceptible to traffic analysis. The communication should additionally be protected by SSH, TLS, or IPsec to reduce the exposure to traffic analysis. It's interesting that data-dedup-friendly modes inherently allow an attacker to recognize duplicated plaintext based only on the ciphertext. That's their whole point. But this is exactly the primary weakness of ECB mode. It's actually a bit funny: ECB mode lets you recognize repetitions of what are commonly small, probably semantically meaningless, pieces of plaintext. Data-dedup-friendly modes let you recognize repetitions of what are commonly large chunks of semantically meaningful plaintext. Yet we reject ECB as insecure but accept the insecurity of data-dedup-friendly modes because they are so useful! -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Warning! New cryptographic modes!
How about this. When you modify a file, the backup system attempts to see if it can summarise your modifications into a file that is, say, less then 50% of the file size. So if you modify a 10kb text file and change only the first word, it will encrypt that component (the word you changed) on it's own, and upload that seperate to the file. On the other end, it will have a system to merging these changes when a file is decrypted. It will actually be prepared and decrypted (so all operations of this nature must be done *within* the system). Then, when it reaches a critical point in file changes, it can just upload the entire file new again, and replace it's base copy and all the parts. Slightly more difficult with binary files where the changes are spread out over the file, but if these changes can still be summarised relatively trivially, it should work. -- silky - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Warning! New cryptographic modes!
On Mon, May 11, 2009 at 2:54 PM, Jerry Leichter leich...@lrw.com wrote: On May 11, 2009, at 2:16 PM, Roland Dowdeswell wrote: On 1241996128 seconds since the Beginning of the UNIX epoch Jerry Leichter wrote: I'm not convinced that a stream cipher is appropriate here because if you change the data then you'll reveal the plaintext. Well, XOR of old a new plaintext. But point taken. Sounds like this might actually be an argument for a stream cipher with a more sophisticated combiner than XOR. (Every time I've suggested that, the response has been That doesn't actually add any strength, so why bother- The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Warning! New cryptographic modes!
Jerry Leichter wrote: 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. You specified a good alternative: Encrypted synchronization of a file versioning system: Git runs under SSH. Suppose the files are represented as the original values of the files, plus deltas. If the originals are encrypted, and the deltas encrypted, no information is revealed other than the size of the change. Git is scriptable, write a script to do the job. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Warning! New cryptographic modes!
Jerry Leichter wrote: 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. That is basically what I'm doing in adding encryption to ZFS[1]. Each ZFS block in an encrypted dataset is encrypted with a separate IV and has its own AES-CCM MAC both of which are stored in the block pointer (the whole encrypted block is then checksumed with an unkeyed SHA256 which forms a merkle tree). 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. ZFS already supports gzip compression but only does so on ZFS blocks not on files so it doesn't need to do this trick. The downside is we don't get as good a compression as when you can look at the whole file. ZFS has its own replication system in its send/recv commands (which take a ZFS dataset and produce either a full or delta between snapshots object change list). My plan for this is to be able to send the per block changes as ciphertext so that we don't have to decrypt and re-encrypt the data. Note this doesn't help rsync though since the stream format is specific to ZFS. [1] http://opensolaris.org/os/project/zfs-crypto/ -- Darren J Moffat - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Warning! New cryptographic modes!
On Tue, May 12, 2009 at 10:22 AM, Jerry Leichter leich...@lrw.com wrote: On May 11, 2009, at 7:06 PM, silky wrote: How about this. When you modify a file, the backup system attempts to see if it can summarise your modifications into a file that is, say, less then 50% of the file size. So if you modify a 10kb text file and change only the first word, it will encrypt that component (the word you changed) on it's own, and upload that seperate to the file. On the other end, it will have a system to merging these changes when a file is decrypted. It will actually be prepared and decrypted (so all operations of this nature must be done *within* the system). Then, when it reaches a critical point in file changes, it can just upload the entire file new again, and replace it's base copy and all the parts. Slightly more difficult with binary files where the changes are spread out over the file, but if these changes can still be summarised relatively trivially, it should work. To do this, the backup system needs access to both the old and new version of the file. rsync does, because it is inherently sync'ing two copies, usually on two different systems, and we're doing this exactly because we *want* that second copy. The local version needs access to the last committed file (to compare the changes) and the server version only keeps the 'base' file and the 'changes' subsets. So yes, it does increase the amount of space required locally (not a lot though, unless you are changing often and not committing), and will also increase the amount of space required on the server by 50%, but you need pay the cost somewhere, and I think disk space is surely the cheapest cost to pay. If you want the delta computation to be done locally, you need two local copies of the file - doubling your disk requirements. In principle, you could do this only at file close time, so that you'd only need such a copy for files that are currently being written or backed up. What happens if the system crashes after it's updated but before you can back it up? Do you need full data logging? I think this is resolved by saving only the last committed. Victor Duchovni suggested using snapshots, which also give you the effect of a local copy - but sliced differently, as it were, into blocks written to the file system over some defined period of time. Very useful, but both it and any other mechanism must sometimes deal with worst cases - an erase of the whole disk, for example; or a single file that fills all or most of the disk. -- Jerry -- noon silky - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Warning! New cryptographic modes!
On May 11, 2009, at 8:27 PM, silky wrote: The local version needs access to the last committed file (to compare the changes) and the server version only keeps the 'base' file and the 'changes' subsets. a) What's a committed file. b) As in my response to Victor's message, note that you can't keep a base plus changes forever - eventually you need to resend the base. And you'd like to do that efficiently. So yes, it does increase the amount of space required locally (not a lot though, unless you are changing often and not committing), Some files change often. There are files that go back and forth between two states. (Consider a directory file that contains a lock file for a program that runs frequently.) The deltas may be huge, but they all collapse! and will also increase the amount of space required on the server by 50%, but you need pay the cost somewhere, and I think disk space is surely the cheapest cost to pay. A large percentage increase - and why 50%? - scales up with the amount of storage. There are, and will for quite some time continue to be, applications that are limited by the amount of disk one can afford to throw at them. Such an approach drops the maximum size of file the application can deal with by 50%. I'm not sure what cost you think needs to be paid here. Ignoring encryption, an rsync-style algorithm uses little local memory (I think the standard program uses more than it has to because it always works on whole files; it could subdivide them) and transfers close to the minimum you could possibly transfer. If you want the delta computation to be done locally, you need two local copies of the file - doubling your disk requirements. In principle, you could do this only at file close time, so that you'd only need such a copy for files that are currently being written or backed up. What happens if the system crashes after it's updated but before you can back it up? Do you need full data logging? I think this is resolved by saving only the last committed. If a file isn't committed when closed, then you're talking about any commonly-used system. -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Warning! New cryptographic modes!
I'd use a tweakable mode like EME-star (also EME*) that is designed for something like this. It would also work with 512-byte blocks. Jon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Warning! New cryptographic modes!
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 majord...@metzdowd.com
Re: Warning! New cryptographic modes!
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. 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. 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. -- Viktor. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
