Hidden in Plain Sight

From time to time, I’ve talked about looking after the security of data stored on portable devices (like laptops), and have suggested that disk encryption is one tool that can help with this.  Encryption, though, is no panacea for security problems.  Judging by the track records of numerous vendors, encryption is easier to get wrong than to get right; and even when encryption  is done correctly, the data may still be vulnerable to  attacks like the Evil Housekeeper.

Another problem with encryption comes up when one wants not only to conceal the content of the data, but also its existence.  (Consider, for example, the situation of a dissident in a country with an extremely repressive regime.)  It is not difficult to draw a fairly strong inference that an encrypted file is present, because encrypted files typically exhibit much higher entropy than normal files (that is, the sequence of bits in an encrypted file appears “more random” than that in,say, a text file).  Once the authorities conclude that there is encrypted data present, they may be able to resort to measures, legal or otherwise, to obtain the decryption keys.  In some countries, just using encryption may be illegal.

The most common technique for resolving this problem is steganography, meaning concealed writing. A message written in invisible ink, between the lines of an innocuous letter, is a classic example. Another steganographic technique is to embed the bits of a message in the pixel data for an image.  The idea is that, unless someone knows exactly where to look, the presence of a message is unlikely to be noticed.  (The idea of hiding something in plain sight is far from a new one, of course.  It was the central plot device in Poe’s The Purloined Letter, for example.)

The New Scientist has an article about a clever new steganographic method, described in a paper [PDF download available] by four researchers from the US and Pakistan.  The authors have  developed a method of encoding a message that requires no extra data to be stored.

Their technique exploits the way hard drives store file data in numerous small chunks, called clusters. The operating system stores these clusters all over the disc, wherever there is free space between fragments of other files.

The paper discusses implementation of the idea in a FAT file system (the filesystem used by MS-DOS and still usable by Windows and Linux machines, at least), but it can potentially be used with other filesystem types.

Here is a very simple example of the technique.  Suppose we have a message to be hidden that is N bits long.  We also have an innocuous “cover file” which occupies at least N disk clusters.  We find a block of free space on the device that is at least N clusters in length, beginning with an even cluster number if the first bit of the message is 0, and an odd number if the first is 1.  The first cluster of the cover file is written to that cluster.   For the subsequent clusters:

If the next bit in the message is the same as the previous bit, write the next cluster of the cover file in the next sequential cluster; otherwise, skip one cluster, and then write the next cluster of the cover file.

The recipient, who knows the name of the cover file, can then extract the hidden message by looking at the list of cluster allocated to the file.

Different types of files will vary in their suitability as cover files; the more “natural” fragmentation, the better.  The paper describes some statistics gleaned from an actual sample of disk drives (from Windows systems).  As one might expect, files that are generally written all at once, such as executables (.exe) or libraries (.dll or .lib) tend to have relatively few fragments; files like log files tend to have many more fragments, so are potentially better as cover files. Anyone who wants to use the technique will want to study the space allocation algorithms of the filesystem in use, as well.  The paper contains some additional suggestions for variations on the basic technique to adapt it to different environments.

This is an ingenious idea, because it doesn’t write any extra data to the device, providing what the authors call “plausible deniability” that there is anything there at all.  A drawback of the technique is that sending a message requires sending either the physical device, or a disk image copy, to the recipient.  In some circumstances, those actions might in themselves arouse suspicion.  Nonetheless, it’s a potentially useful tool, and another step in the ongoing arms race between those who want to keep secrets, and those who want to uncover them.