On Thursday 29 July 2010 12:46:29 Matthew Toseland wrote: > node.db4o.crypt issues: > node.db4o.crypt is encrypted in CTR mode. This is a standard and widely used > mode. It essentially creates a one-time pad, with no feedback, by encrypting > the block number and then XORing that with the plaintext. It is therefore > easy to implement for stuff that needs random access, and secure as long as > you never reuse the sequence number. > However, if we have: > - Defrag using the same key (can happen now, but the old data shouldn't be > recoverable without the other issues) > - Backups using the same key (auto-backups, will happen soon) > - Wandering logs (e.g. BTRFS) > - Data journaling (most modern filesystems have the option) > - Block remapping (flash, disk) > > Then we have the possibility that we have two blocks on disk encrypting > differnet data with the same key and the same sequence number. Which is VERY > BAD, allowing very powerful cryptanalytic attacks: The XOR of the two blocks > of ciphertext will be the same as the XOR of the two blocks of plaintext! A > very similar weakness was used by MI5 in the 60s to decrypt thousands of > soviet messages (reused one-time pads). > > Options: > - Introduce an IV. Store it somewhere in the file e.g. at the beginning, or > maybe duplicated. Change it every time we write the full node.db4o.crypt i.e. > on writing a backup, on defragmenting, on writing from RAM if we are in > full-buffer mode. This eliminates the first problem, but does not deal with > the others. > - Always encrypt a whole block, and introduce an IV for the block. So e.g. we > would divide the file into blocks of 4096 - 32 bytes, add a 32 byte IV at the > beginning of each block, and always read and write an entire block. We could > use a mode with feedback within the block. We could also introduce a checksum > if we wanted to. > - What do other apps do in the same situation? What does TrueCrypt do? Does > it address this issue? It doesn't have to deal with the filesystem issues but > hardware remapping remains a threat, especially with modern flash? > > The first option is likely the easiest, of course. > Current thinking in technical terms:
1. We need a separate key for each file. This requires a header. It should probably be 4K to preserve alignment of the rest of the file. And we can put versioning info in it. The header, including the key, can and should be encrypted with the key from the master keys file. Adding a header will require rewriting the node.db4o.crypt file. Given we have a header we do not necessarily have to rename it, although it might simplify error handling. We will in any case need to rewrite the encrypted file. We might want to defrag beforehand to reduce space usage. 2. CTR mode is not really acceptable, as explained above. Plus, currently we don't use a nonce with it. There are disk-specific encryption modes which have much stronger (and usually provable) security against a wide range of attacks. The main ones are: XEX/XTS: XEX is: C = E ( P xor X ) xor X where X = E ( I ) * a ^ j Where I is the sector number, j is the block number within the sector, X is computed with Galois arithmetic in GF(2^128) (a is a constant e.g. 2). Thus for reading/writing a random block, we need two encryptions, but for reading/writing a block within the same sector as one we just handled, we only need one encryption. If we always read/write a sector, then the cost is the same as ESSIV+CBC. XTS is just XEX with two keys instead of one and ciphertext stealing. Both XTS and XEX are provably secure. XTS is standardised and used by Truecrypt. There is a paper that proves XTS's security while criticising it for using two keys (the original XTS paper apparently assumes that because XEX's security is proven that that must apply to XTS too). The problem is there are no libraries for either XTS/XEX itself or for galois field arithmetic. I can code it (galois multiplication) of course, but I wouldn't want to get it wrong. One possible workaround is to set the sector size equal to the block size. I have not been able to get confirmation from ##crypto that this is safe but it seems fairly clear that the sector thing is an optimisation... ESSIV+CBC: This is CBC mode for a sector (of whatever length) with the IV generated by CTR mode (note that properly implemented CTR mode requires both a key and a nonce). This is very easy to implement. It may not be as well-studied as XTS. Obviously it requires reading or writing one sector at a time, but this isn't necessarily a problem due to caching. It requires one encryption plus one per block. Both XTS and ESSIV+CBC are supported by linux loopback encryption. CMC: This is a more expensive mode that encrypts a sector at once, and does so twice in order to make the whole sector change whenever any word within it changes. It is probably overkill, although if we always write stuff in sectors (which is likely given a caching layer) it may not be much slower than the suggested simplified XEX. It is slightly more complex than XEX but still easy to implement as it doesn't need any wierd math. -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 197 bytes Desc: This is a digitally signed message part. URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20100731/a2935416/attachment.pgp>
