Stegafax -- A Covert Messaging System

R. J. Brown -- Elijah Laboratories Inc.

The stagafax covert messaging system was originally developed for Christian missionaries located in countries where the Christian church must operate underground for fear of reprisals from either the government or activists. It was designed to permit these people to be able to communicate with each other and with their headquarters in the United States without fear of being detected. In certain fundamentalist Islamic nations, detection of this kind of activity will get a foreigner deported, probably after a cruel interrogation and imprisionment period. It will get a Saudi national executed by public decapitation. Steganography can be serious stuff.

A very interesting article appeared just before the September 11, 2001 attacks on the subject of steganography as used with images on the internet. This article, Detecting Steganographic Content on the Internet, also contains a good bibliography.

Cryptography can prevent a message from being understood, but an observer can still see that an encrypted message was sent. Steganography can prevent the real message from being detected. If the need is to prevent the originator or the recipients from being known at all, then this requires additional techniques, which are described in the excellent book Disappearing Cryptography by Peter Wayner, 1996, Academic Press. I know of no other book available to the public that covers this material.

The idea here is to permit the users to communicate using fax transmissions. The actual images being faxed are purely incidental to the covert message being comunicated. Typically, pages of receipts, time cards, invoices, packing slips, bills of lading, etc. make up the apparent transmission, in other words, typical boring innocuous business documents, such as businesses fax among each other every day. The more rumpled and soiled these are the better, as the embedded message will be riding on the "noise" in these images.

If the images are too clean, the little bit of "noise" injected by the steganographic hiding of the message might look suspicious. For this reason, stegafax provides a noise mode to inject additional noise into the image. This tends to look more natural than just a little bit of noise, and is intended to be used when the original fax image is exceptionally clean. An alternative approach would be to spill some coffee on the original, drop it on the floor and step on it with dirty shoes, and crumple it up a few times before running it thru the fax machine. By using fax, we have chosen an already noisy medium, as the pixels are either black or white, and who hasn't complained about the poor quality of many fax transmissions? By embedding a covert message in this medium, we attempt to hide the message in such a way as to thwart government operated traffic analysis techniques, as well as direct evesdropping, such as a wiretap.

The methods used to embed a covert message in a color image file, such as a GIF or JPEG image file, operate by twiddling the least significant bits of the color components of the pixels that make up that image, and when one looks at the noise spectrum of these bits, it becomes subject to suspicion that a covert message could be embedded there. In a fax transmission, on the other hand, the least significant bit is also the most significant bit, as it is a binary image. Noise creeps into fax systems from many places: the quality of the original, the color of the original, dirt on the scanner bar, noise on the phone line, etc. These properties make a noisy transmission less suspect with fax than with a TCP/IP transmitted GIF or JPEG image file. The ablilty to either email the fax, or send it right over the phone lines gives options not available for internet traffic alone, especially in out of the way locations.

The typical usage of stegafax involves preparing a message, typically a short text message, and compressing it with gzip, then encrypting this message with either pgp or gpg. This compressing and encryption is an important step, as it makes the message smaller, and also makes it more random. It also make the message unintelligable to anyone who is able to extract it by defeating the steganography.

Next, a set of pages for the fax images are choosen. These are run thru a conventional fax machine and sent to the fax modem on the computer. These fax images are then converted to Portable Bit Map (PBM) format using g3topbm. These PBM images are then fed thru stegafax in encode mode, along with the compressesed and encrypted secret message, and a secret key is chosen. This key is used to seed the psuedo-random number generator that determines which pixels in the fax raster will contain the message. The result is a set of PBM files that contain the steganographically embedded secret message. These files are then converted back into fax images using the pbmtog3 tool. The PBM files may be previewed with xv. These new fax images are then set to the desired recipient, either as an attachment to an email, or directly over the phone lines as a seemingly normal fax transmission. In either case, an evesdropper will only observe a normal fax image of boring and mundane business documents, not the hidden secret message that is really the reason for the transmission.

Once the fax images have been sent, the recipient takes these images, one per page of the fax transmission, and converts them into PBM files. These PBM files are then fed into the stegafax program in decode mode, along with the same secret key that was used to encode them. Thus we are using a form of symetric cryptography, where the secret key must be known to the transmitting and receiving parties. How this key is distributed and revoked is a matter beyond the scope of this document, but suffice it to say that the subject has been well studied in the literature. Consult Bruce Schneier's Applied Cryptography for more information on the subject. After the decode operation, the hidden message will be extracted from the fax image. This message must then be decrypted and uncompressed to render it legible again.

Unfortunately, this was all written back in 1998 for Linux, and a lot has changed since then, particularly the Gnu gcc compiler and the g++ runtime library, together with the associated include files. The usual bit-rot has set in, and the program no longer compiles under Red Hat Linux 8.0, so you will need to tweak it accordingly if you plan to use it with a modern Linux system. Obviously, using it with other systems should be possible, but even more tweaking will be needed. Using it so that a message can be sent from one kind of originating system to a different kind of receiving system is even more problematic, as cryptographically secure random number generators are usually somewhat dependent upon the hardware they are running on, especially for the initial seed. You may want to look at the random number generator used with the blowfish algorithm, which is part of openSSL.

At any rate, here are the source files involved. If you want to give it a try, go ahead and get these sources and twiddle with them until you get it working on your system, then either send and receive messages with a friend running the same setup, or do the additional work to make sure that the random number generation is the same for all the systems you plan to use it with. Finally, run some tests to evaluate the cryptographic security of your changes. If you are using this in a situation where important information is at stake, or where human lives may be at stake, be sure you test everything very well!

Obviously, for the convenience of non-technical users, all this should be wrapped up in a set of scripts, and interfaced to a GUI, perhaps using tcl/Tk. Such a GUI shell should provide an easy way to specify the plaintext file, the key it is to be encrypted with, the set of fax image files, and the key that drives the steganographic embedding of the cyphertext into the fax images, and a simple way to specify the set of resulting files. Means should be provided to specify how the fax images should be sent, either as email attachments, or as a fax transmission over the fax modem. Likewise, similar facilities should be provided for the decoding of received fax images. This GUI shell should provide way to view the fax images, both before and after encoding, and to view received fax images as well. If, after viewing an image, either before of after encoding, the user decides that it looks somewhat suspicious, he should be able to perform noise injection into that image and re-encode the message into it.

Source FilesInclude files
permuted_sample.C permuted_sample.H
prng.C prng.H

Elijah Laboratories Inc. logo Elijah Laboratories Inc. logo

© 2002 Elijah Laboratories Inc.

Web page design by Robert J. Brown.
Last modified: Sat May 3 00:55:19 CDT 2003