Why use steganography?

One thing seldom told about steganography is a well-founded motivation why its use can be very beneficial. The scenario that is almost always given to motivate research in this field goes as follows:

Alice and Bob are locked in a prison, and their behaviour is being monitored by some evil warden. The two inmates are allowed to communicate with each other, but once the warden notices anything strange in their communication, say, some escape plan, he will interrupt any further communication. Since Alice and Bob do want to escape and therefore need some coordination, they must find a way to discuss their plan secretly. Of course, this is impossible using cryptography, because the warden, although he cannot decipher the message, will realise that the encoded message is very suspicious.

So far for theory ... But where in practice does steganography come handy? It's indeed more difficult to use than cryptography because not only do you have to provide a suitable and innocuous-looking cover, but you also have to ensure that there is no direct link between you and the receiver.

I'll give you four reasons why steganography is worth the extra effort and why the theoretical example is indeed not too far fetched in many environments. Note that these examples do not only refer to the standard case where an image is used as cover. Steganography can be quite multifaceted.

1. Most basically, among everyone's inalienable human rights (click here for the UN's Declaration of Human Rights), there are the freedom of speech, religion, thought, and conscience. Furthermore, you have the right to privacy and secrecy of communication. Derived from these, you may conceal whom you talk to, what you are saying and why, in which case steganography suits best, even more than clearly visible cryptography.

2. Many parliaments, even in some democratic countries, have approved laws for telecommunications data retention, among them all member states of the European Union and the Patriod Act-infested United States. This means that at least all your Internet connections are stored for some time without any initial suspicious, effectively reversing the burden of proof. Such procedure is clearly illegitimate, so you have to take action in your own hand to protect yourself from being spied at. Again, steganography helps in this situation as long as you do not send your the cover with the embedded messages directly to the recipient. Even better, use some anonymiser (which is another facette of steganography) like TOR or JAP to stop authorities from examining your data traffic.

3. In other countries, for example, Iran, where any opposition is heavily prosecuted, or Honduras, where ruthless military leaders seized power, the only secure way of digital communication is steganography. Many of them forbid cryptography without official permit by the authorities. Sometimes, you even have to tell them previously what contents you want to encrypt and to hand over the keys. Otherwise, once encrypted data is registered from your computer, you will quickly be visited by the police and might get seriously punished. Human Rights Watch reports a great many such cases in the dictatorships of the Middle East. With secure steganography, you can at least lower this risk to a minimum.

4. Steganography enables you to anonymously inform authorities or the media about scandals without risking your job or reputation. Assume you have discovered that something strange is going on in your company and you want it to be investigated. If you send your message encrypted or even in the clear, it will be detected and you might lose your job. Sometimes, it might be enough for your employer to prove that you have contacted a journalist or the police in order to put you on a "death list". With steganography, you can plausibly deny any communication.

LimeJuice v0.1, steganographic GUI and open-source library

Today, I want to introduce to you LimeJuice, which is not just a steganographic tool like most others. Mainly, it provides four key features:

1. A library implementing a large set of sophisticated steganographic algorithms for various cover types.

2. Another library that handles embedding and extracting into/from suitable cover files.

3. An intuitive graphical user interface for various operating systems, including Debian, Mac OS X, Suse and, currently in a restricted version, Windows, so that you can use the algorithms of LimeJuice like any other stego software.

4. Since LimeJuice is distributed under the terms of GPL, the code is open source. Therefore, you may not only use it, but modify and redistribute it in nearly any thinkable way. Furthermore, being open source guarantees that there are no intentional flaws.

You can find LimeJuice at: http://developer.berlios.de/projects/libstego/

LimeJuice was developed at Oldenburg University in a one-year project between April 2008 and 2009 under the guidance of Dr. Elke Wilkeit at the parallel systems department where I also worked some time after my Diploma degree. The group consisted of eight students and their supervisors. Many of the implemented algorithms are well-known through previous scientific publication.

Most notably, LimeJuice provides - as far as I know - the first public implementation of the highly sophisticated "Perturbed Quantization" algorithm invented at the chair of Jessica Fridrich at Binghampton. Link to the original PQ paper: http://www.ws.binghamton.edu/fridrich/Research/PQ_ACM_journal01.pdf

The project's homepage can be found at: http://parsys.informatik.uni-oldenburg.de/~stego/

Paper: Hiding Information in Retransmission

Written by: W. Mazurczyk, M. Smolarczyk, K. Szczypiorski (all Warsaw, Poland)
Published at: arXiv.org (http://arxiv.org/abs/0905.0363)
Link: http://arxiv.org/ftp/arxiv/papers/0905/0905.0363.pdf

Short summary: The authors present a general approach to hide data in the payloads of network protocol messages. Sender and receiver are network nodes in this case. Instead of acknowledging all successfully received packages, the receiver intentionally omits the confirmation message, so that the sender has to retransmit the package. However, acknowledgments are only omitted when the sender has marked the corresponding packages in a special way. The steganograms are then inserted in the payload fields of the retransmitted packages. The paper concentrates on TCP and its different retransmission modes, but can be applied to other similar protocols. Based on the fact that retransmission occurs quite often, they are able to steganographically transmit several kilobits per second over an 10 MBpS network. The authors try to minimise the detection risk by adding only few intentional retransmissions compared to the number of retransmissions caused by network errors.

Rating: I like the idea in general because the paper goes a way that is unusual in the mainstream of image-based algorithms. Furthermore, I consider this paper worth reading since it provides a comprehensible summary of the authors' ideas. However, I think there are some flaws both in the concept and in the implementation:

1. There must be some direct link between sender and receiver during communication (conceptual).
   
2. The steganographic packets' payload is changed beyond a point that could be explained by network errors (implementation).
3. The transmission statistics of the network are changed (conceptual).

Yet it will cause an adversary quite some trouble to detect such hidden communication, but once he manages observing the relevant network nodes, which should be no problem for secret services, it becomes a lot easier.

What is Steganography?

Steganography is not cryptography

Steganography is the art of hidden communication. In contrast to cryptography, the objective is not only to hide a message's content from an adversary, but to hide a message's very existence. Clearly, hiding existence is a much harder objective to achieve than hiding contents. In science, one considers a cryptosystem to be broken when an adversary, be it theoretically or practically,
can guess the secret key within a reasonable period of time. However, a stegosystem is broken whenever it is possible to decide whether some cover, for example, a JPG image, contains a hidden message with a higher probability than by simply guessing.

Though steganography is far less known than cryptography due to the wide spreading of encryption since the underlying mathematical breakthroughs in the past 50 years, it is in fact a much older technique which was used as early as in the time of ancient Rome and Greece. The reason may be that, with the human mind as the only adversary, hiding is easier than encrypting, which always has to obey a fixed set of rules in order for the recipient to be able to decrypt the message. Moreover, there are lots of possible and suitable stashes in the real world.

Ancient message hiding

Old stories tell that the Romans used slaves to transmit messages steganographically by cutting their hair and tattooing the message upon their heads. When the hair had grown again, the slaves would be sent to the destination. However, such a method seems to be rather inefficient, even from an acient point of view.

Wax tablets where also popular means of steganography: The wax, into which the message was usually carved, was removed from the tablet, then the message was carved into the wood. Afterwards, the tablet was re-filled with molten wax. Other means of steganography, which are even used today by both enthusiasts and secret services, are invisible ink, watermarking, microdots or double bottoms.

Watermarking

Did you know that your home printer is most likely to mark any page you print steganographically, so that type and brand of the printer can be identified? Most of them print some microscopically small dots in one corner of each page, whose color is very close to the paper's and whose layout includes all the important information.

Such procedures are called watermarking, which is a special type of steganography. A secret message is hidden as well, but it is quite uncritical if someone discovers it because its contents are not classified. In some cases, the hider even wants every recipient to be capable of reading the hidden messages if he finds it without knowing the exact hiding algorithm. For example, this applies to many banknotes which contain easily visible watermarks.

Modern steganography

However, what we want is absolute privacy because, in our scenario, there is some evil adversary who, as soon as he detects the presence of a hidden message, will stop us from any further communication and impose severe punishments on us. Within the last 20 years, steganography has emerged from the shadow of the 20th century's cryptographical breakthroughs as a separate science, especially with the fast spreading of digital communication which provides more hiding opportunities than anyone could think of.

In principle, any piece of digital data could be used for hiding purposes. Speaking generally, modern steganography is all about taking a well-known information-carrying protocol, such as the HTTP protocol, injecting some secret data, and sending it to the legitimate receiver, perhaps when he requests a slightly manipulated website using his browser of choice.

Oh, stop!!! Sending it directly to the receiver is very bad because it shows that there is communication between you and someone else which might cause thorough scrutinising of that information channel by your foe. It does not necessarily breach privacy, but it helps.

However, although you might principially use any digital protocol, the most commonly used ones are image formats like JPEG, GIF or PNG. First, they are so common for nearly every purpose that hardly any adversary will take notice. Second, at least on some simple level, it is easy to implement algorithms that don't cause any visible distortion to the original image. Third, images cannot have side-effects on computers' behaviours unlike, for example, the HTTP protocol.

Least-significant bit encoding

The most basic algorithm for hiding a message into an image may be the least-significant bit embedding. Given an image format like bitmaps in which there are a certain number of binary channels to encode colour values, the channel(s) that encode(s) the least-significant summand(s) of each colour value is/are taken to embed the hidden message in binary representation.

In an 8-bit encoding, using only one LSB means that you can replace 12.5 % of the original file with secret information. So the main advantages of this method are the high capacity of the cover and that a human being usually won't see anything suspicious in the manipulated images.

However, image statistics are changed because after embedding, the LSBs look like random in most cases, which they usually aren't in unmanipulated images. Therefore, a lot of people have invented mechanisms to overcome this problem with varying success.

How to prove security?

As we have seen, besides users' unwary behaviour, statistics is the main barrier to creating secure steganography. This is again very different from modern (symmetric) cryptography, where you are mainly dealing with some exotic types of mathematical of fields and vector spaces and only some basic proofs which you have to apply to your mathematical construct.

Proving technical security against unsolicited message detection means that you have to show that, by embedding any message into your cover, you do not change any of the cover's statistics. Or, at least, that you do change statistics only insignificantly enough.

As for me, I haven't yet seen any such formal proof for any practically useful steganographic algorithm. However, such proofs do exist in very restricted models that are unlikely to ever be implemented in a productive tool.

Concerning GE Stego, I cannot conduct such formal proofs either, because the cover complexity is too high, but I can at least argue that some of the main statistics remain unchanged by embedding.

Further reading

I will provide some links to other (longer) introductory texts on steganography in this blog in the near future.

Manual for GE Stego

Why should you use GE Stego?

The objective of GE Stego is to hide messages in KML files so that no-one without the correct password can retrieve nor discover them. By discovery, we mean an adversary's ability to prove a message's presence in a given set of KML files with higher reliability than by throwing dice. This becomes important when you have reason to believe that the mere fact of communication must be kept secret or that finding an encrypted message might cause trouble to you, which is quite likely in undemocratic countries.

How does GE Stego work?

GE Stego takes one or more KML files and embeds your messages in the coordinate values present in these files. By embedding, the coordinates are slightly changed, but do not cause any visible distortion to the objects. Before that, the message is Huffman-encoded and encrypted with AES, for which your password is used, to get a completely random-looking message. Furthermore, all coordinates that do not appear to be sufficiently random as well are discarded.

How to install and run GE Stego?

1. Download the GE Stego ZIP file from this site.
2. Extract its contents wherever you like.
3. Install a recent version of Java (Runtime Environment should be sufficient), if there is none installed currently.
4. Execute GES.jar in the folder where you extracted the ZIP archive.
   

How to embed a hidden message?

1. Create one or more KML files as covers.
2. Add them to the list in the upper part of the GE Stego window.
3. Enter your hidden message or load a text file whose content is to be embedded.
4. Enter a secret key of length 6 or greater.
5. Check the embedding capacity of your files and, in case it is insufficient, add further files.
6. Click the 'Embed' button, after which you will hopefully see a confirmation.

How to extract a hidden message?

1. Add the KML file(s) that carry the message in the upper part of the GE Stego window.
2. Make sure that they are in exactly the same order as during the embedding process.
3. Enter the secret key.
4. Click the 'Extraction' button and the message will be displayed in the second text area or, if nothing was found, an error message will be displayed.
5. Optionally, click the 'Save' button to store the extracted message into a text file.

Some advice to keep your communication secret

GE Stego can ensure that no adversary confronted with a KML file can tell whether it contains a hidden message or not. But there are lots of possible wrong behaviours on your side that could help him. Keep in mind that hidden communication can not only be detected in the media used, but also by the communicants' behaviour. To help you avoid crucial mistakes, here is some behavioural advice for using GE Stego, each with a short reasoning.

1. Never use the same KML file twice for embedding. The adversary may intercept both covers, compare them and find the small deviations, so he will get immediate evidence that secret commuication is taking place.
2. Never use a publicly available cover - always create your own ones. If some KML file is already floating around somewhere in the Internet, the adversary may easily find it and compare it to your cover.
3. Never send a cover directly to the receiver. Direct communication between sender and receiver destroys any secrecy. Rather post your KML files with hidden messages on KML repositories where thousands of other Google Earth enthusiats post their files too.
4. You will need at least one direct communication with the receiver to exchange keys and tell him where and when to find messages. Be careful that this exchange takes place in some save environment, for otherwise the whole following secret communication is uncovered before it really starts. It's best not to use computers or the Internet for that because they are by far more easily to be wiretapped than the real world outside.
5. Try not to establish any further patterns, for they might raise suspicion if not well-reasoned.
6. Never use "strange" cover files that do not seem to have a reasonable semantic, i. e., only use KML files that describe something useful like the course of a certain road or the positioning of a 3D model. If you use arbitrary collections of coordinates, the adversary might question the sense behind that.
7. Another problem lies in obtaining this software without leaving a trace of your download in some server-side protocols that might be stored for a long time and record. If possible, you should try to disguise by using some anonymity tool like JAP, but this only works if many people use the tool at the same time.