If you are a member of a dissident faction in a repressive regime, where encryption is as illegal as the data it protects, what use is encryption?

The problem here is known as "Rubber-Hose cryptanalysis" - why attack an encryption system with large amounts of computing power, when you can beat the password out of your suspect? In a more likely scenario, a court order could force decryption of any computer files, if it can be reasonably assumed that you have the key. The Fifth Amendment that protects against self-incrimination is not much use against laws such as the RIPA in different countries.

The solution is steganography - hiding one set of information within another. It then becomes impossible for anyone to prove that the hidden information exists, let alone order you to hand over keys.

Although normally done on individual files, the principal can be applied at the filesystem level. It becomes possible to design a filesystem for which proving the existence of any specific file is impossible, unless you know it exists and you have the file's password.

The basic principle is that an entire partition is filled with random data. Random/pseudo-random information is theoretically indistinguishable from encrypted data, so you can put an encrypted file anywhere on the partition and it is effectively impossible to pinpoint, unless you already know it's location.

The file's location is encoded as a secure hash function of the file and directory names, along with the password supplied. The lookup table1 would be pre-filled with random data like so:

Hash/garbage | block/random number
-------------+--------
VYHERBISVZCF | 65454
FDDBUKTYNBVC | 10379
QKZHARSOYFUP | 94192
...           ...
and so on.

The location would then be inserted at random in the above table, at which point it looks like any other entry. The file would then be further encrypted, using a similar secure hash to the one used above, to get the key.

The problem with hiding files immediately on creation is that it is impossible to avoid overwriting them in subsequent operations with different passwords2. At this point things get awkward because of the birthday paradox, generally demonstrated by the fact that to have a greater than fifty percent chance that two people in a room share the same birthday, only 23 people need be in the room.

Roughly speaking, the effect is that for a partition with space for a million files, you will probably start having non-empty blocks overwritten after only a thousand files have been written. These are termed "collisions".

The partial solution to collisions is to write each block multiple times at random places in the filesystem. Then, the chance of all blocks containing the same information being over-written decreases.

However, it is inevitable that blocks containing encrypted information will be over-written. This is an unavoidable property of stego filesystems: that as the number of write operations increases, so does corruption of the stored information.

Despite these problems, there is a steganographic filesystem available for Linux, called StegFS. This was done as a research project, and is based on (and maintains compatibility with) the ext2 filesystem.

The steganographic filesystem was first proposed by Ross Anderson, Roger Needham and Adi Shamir of Cambridge University (England), Microsoft Research, and the Weizmann Institute of Science respectively, in a paper entitled "The Steganographic File System".

Footnotes:
1: If my file system terminology is hideously wrong, please /msg!
2: Thanks to lj for the correction, who correctly points out:

Stegfs can safely write to the disk without overwriting any level that it has the password for. This doesn't protect the filesystem when it is locked up, nor does it protect any layers that aren't opened yet from being overwritten.

Sources:
http://www.mcdonald.org.uk/StegFS/
http://www.apache-ssl.org/disclosure.pdf
http://www.cl.cam.ac.uk/ftp/users/rja14/sfs3.pdf
http://www.sans.org/infosecFAQ/covertchannels/steganography2.htm

Log in or registerto write something here or to contact authors.