Interesting research from iSEC Partners on attacking the weakened Bitlocker design in Windows 8 has corollaries for the problem of trying to apply full-disk encryption to protect cloud storage. Last year we sketched out a series of experiments on trying to create private storage by combining existing full-disk encryption (FDE) scheme with standard cloud storage providers such as Dropbox or Google Drive. The simplest design is creating a virtual disk image (VHD) backed by an ordinary file, syncing that file to the cloud, mounting the VHD as drive and enabling Bitlocker-To-Go on the volume same way one could enable it on a USB thumb-drive.
As noted these prototypes suffer from an intrinsic problem: FDE provides confidentiality but not integrity. Encryption alone stops the cloud storage service from finding out what is stored, but will not prevent them from being able to make changes. (Or for that matter, unauthorized changes by adversaries on the network path between user and cloud provider. That attack vector was more clear with an alternative design involving iSCSI targets stored in the cloud. iSCSI has no transport level security, unlike the SSL-based sync used by most cloud storage services.) Because there is no redundancy in FDE, any ciphertext will decrypt to something even after it has been tampered with. Granted, the resulting garbled plaintext may cause trouble further up in the application layer. For example in the case of an encrypted VHD, if the file-system structures stored on disk have been corrupted, the VHD will no longer mount correctly as an NTFS volume. Perhaps the file-system is intact but the first few hundred bytes for a particular file have been scrambled, with the result that it is no longer recognized as the correct type, because file formats typically have a fixed preamble. Other file formats such as text are more resilient, but they could end up with corrupted data in the middle resulting from incorrect decryption.
It’s clear such attacks can result in random data corruption. Less clear is whether controlled changes can be made to an encrypted volume to achieve more dangerous outcomes. iSEC research demonstrates such an outcome against Bitlocker in Windows 8. While their proof-of-concept works against a local boot volume, the same techniques would apply to disk images stored in the cloud, although it will be more difficult to reproduce the attack for reasons described in the next post.
Critical to this exploit is a weakening of Bitlocker in Windows 8. Recall that block ciphers are designed to encrypt a fixed amount of data at a time. For example AES operates on 16 bytes at a time. To encrypt larger amounts of plaintext requires choosing a mode of operation—a way to invoke that single-block encryption repeatedly as a blackbox until all of the data has been processed. The naive way of doing this, namely encrypting each block independently, is known as electronic codebook or ECB mode. It has significant drawbacks, dramatically illustrated with the penguin pictures. Cipher-block chaining or CBC mode does a better job of hiding patterns in plaintext such as repeated blocks by mixing one block into the encryption of the next one. But CBC still does not provide integrity. In fact it becomes easier to modify ciphertext to get desired changes. With ECB mode attackers are usually limited to replacing blocks with other known plaintext blocks. By contrast CBC mode allows getting full control over any block by making changes to the preceding one. More specifically, any difference XORed into the preceding block will result in the same difference XORed into the plaintext when current block is decrypted. This capability comes with a caveat: the decryption of that preceding block is corrupted and replaced with junk that we can not control in the general case.
For these reasons simple block cipher modes are combined with a separate integrity check. Alternatively one can use authenticated encryption modes such as GCM, which also compute an integrity check along the way while processing plaintext blocks. Because disk-encryption schemes can not add an integrity check— encryption of one disk sector must fit in exactly one sector— they have to defend against these risks by alternative means. The original version of Bitlocker in Vista used a reversible diffuser dubbed Elephant to “mix” the contents of a sector before encryption, such that errors introduced in decryption will be amplified across the entire sector unpredictably, instead of being neatly confined to single blocks. While Elephant was an ad hoc design, later theoretical treatments of the subject in the literature introduced the notion of narrow-block ciphers and “wide-block ciphers to properly capture this intuitive notion: difficult to make controlled changes across a large chunk of plaintext, much larger than the block size of the underlying primitive such as AES. IEEE Security in Storage Working Group then standardized a number of modes such as XTS that have provable security properties based on assumptions about the underlying block cipher.