Saturday, 31 January 2009

deniable encryption

In a faraway land inhabited by elves, an evil emperor who hated butterflies decided to make it illegal for anyone to possess images of butterflies. It didn't make any difference whether the depicted butterflies were real or imaginary. Members of the anti-butterfly squad would track down butterfly lovers, and seize and investigate their computers hoping to find offending material. This post describes how elves in that faraway land armed themselves against this, so that they might continue to indulge in their predilection for butterflies, without bothering anyone nor being bothered by the evil emperor's thugs.

Traditionally, electronic data is protected from prying eyes by encryption. Encryption turns useful data (plaintext) into a form that is useless and looks like gobbledygook (ciphertext). The gobbledygook can only be turned back into the original data with the same key that was used to encrypt the data in the first place (symmetric encryption).

In the old days, butterfly lovers used to encrypt their images to keep them secret. However, the evil emperor's thugs then started to throw people in dungeons for the mere offence of not revealing their keys. The elves therefore turned to an ingenious invention called deniable encryption, which allowed them to argue plausibly that there was no key, or more precisely with regard to what will follow, to argue that there was only one key, when in reality there were two. The first key encrypted and decrypted allowed images of, say, ladybugs and the second key was used for forbidden images of butterflies. Of course the elves would deny the existence of that second key when asked.

Now let's see how this works in more detail. The technique is most effective where it is applied on an entire device, let's say an external harddrive of 500 GB. A tool is used to turn the complete storage space into gobbledygook. (Warning: all existing information on it is thereby irretrievably erased!) Then either one or two keys are fixed. With the first key one can store encrypted images of ladybugs at the beginning of the harddrive, say in the first 1 GB. Optionally, with a second key one can store encrypted images of butterflies in the remaining 499 GB. The entire contents of the harddrive now looks like gobbledygook if one doesn't know either key, and if one knows one of the keys one can only access the corresponding part of the storage space, and one cannot tell whether the other key exists at all.

Whenever the anti-butterfly squad would stop by, an elf would first claim that his harddrive was broken: "Look, the damn thing doesn't even mount!" He would usually be believed by the underpayed, understaffed, undermotivated and virtually illiterate goons, but when they were in a particularly tenacious mood and kept putting pressure on him, the elf felt he didn't have any other choice but to reveal the first key (and only the first key) to them, and that was the end of it: "Okay, so far I've only stored 1 GB of images yet on my 500 GB harddrive, so what? And I encrypted the ladybug images because I was embarrassed about liking ladybugs, and didn't want my friends to find out. Butterflies?! I don't know nothing of no butterflies!"

The most popular tool realising deniable encryption is TrueCrypt, which is an industrial-strength application available for Windows, Mac and Linux. Each of the two keys allows access to a volume, which behaves just like any other filesystem, consisting of directories and files. The two volumes are, for obvious reasons, called the outer volume and the hidden volume, respectively. Depending on the operating system, one should follow the relevant instructions on the TrueCrypt website, to install the tool and to turn an arbitrary harddrive (which can also be a thumbdrive) into an encrypted device.

Important is that the outer volume should only be modified in a protected mode, which requires both passwords to be entered. The reason is that otherwise the hidden volume might become damaged by being overwritten. For normal usage this is not a problem, as the contents of the outer volume merely serves as decoy, and will normally be fixed once and for all, while one may regularly want to add material to the hidden volume. Conversely, there is no risk of the hidden volume overwriting the outer volume, because the hidden volume 'knows' how much storage space is available to it, which is fixed when the volumes are created, while the outer volume for obvious reasons 'knows' nothing of the inner volume.

Further remarks:
  • Elves knew that suitable keys had to be long and not consist of words from any dictionary, because such keys would be too easy for the anti-butterfly squad to guess.
  • The butterfly images were best directly copied from the source (e.g. a fellow elf's harddrive) onto the encrypted volume. This is because any material temporarily stored on an unencrypted harddrive might leave residual traces. Similarly, viewing of the images was best done without copying them to unencrypted memory.
  • With all of the above precautions, the anti-butterfly squad might still find evidence in the logs of a computer that an elf had played a file called extreme-butterfly5.avi. This might cause some embarrassment, even if the filename didn't constitute proof that the video had in fact been about butterflies. (In mentioned evil empire, the mere accusation of a butterfly-related crime was enough to wreck an elf's career, marriage and reputation, not to mention the risk of being lynched by vigilantes, encouraged by the emperor's vile propaganda.) The best solution was to erase log files regularly. This may be rather difficult for Microsoft operating systems, which are utterly hopeless pieces of crap when it comes to security and privacy (see e.g.: "Defeating Encrypted and Deniable File Systems: TrueCrypt v5.1a and the Case of the Tattling OS and Applications"). For Linux however, it is easy to write a script to remove all log files upon logout. To determine which files and directories to remove, the home directory should be scrutinised, especially the filenames starting with a period. Another issue is the /tmp/ directory, which can often be cleared automatically upon logout by choosing appropriate personal settings.
  • Further, privacy settings of browsers can be made to erase browsing history, cache, cookies, etc., upon exit.
  • Also elves who were not into butterflies preferred to use deniable encryption for all their data, because the paranoid emperor ended up seeing butterflies in the most harmless grocery lists.
  • Full-disk encryption with plausible deniability solves the problem of securely storing information, but not of how to confidentially exchange data with others. This requires more care, and in particular public-key encryption via e.g. PGP (GPG on Linux). One can even stay anonymous by using the TOR network and related tools (see the links at Citizen Lab).

No comments: