Definition: steganography - the practice of hiding a secret message so the sender and reciever are the only persons who know the communication exists

How is this useful when you can just encrypt a message and be sure no one but your reciever will be able to read it?

Imagine you are an undercover agent for the United States in a hostile country. It would be foolish to assume that the government is not going to be monitoring not only what people are saying to each other, but also who is talking to who. If you, as an undercover agent, are seen mailing many letters to Washington D.C., it does not really matter what the messages contain. Just the fact that you are communicating with someone is enough information for the enemy to crack down on you. Steganography solves this problem in a way that cryptography can not - in the eyes of the enemy, the message must not even exist.

Physical Steganography vs Digital Steganography

Most of the examples we went over in class (hiding a letter in a hollow cork of a beer barrel, writing messages on the wooden board underneath a wax tablet, etc) are forms of physical steganography. In general, these methods were great for ancient times when electronic mail was not available, but in the modern era waiting a week for your messenger's hair to grow back is not exactly the most time efficient way to communicate secretly. Digital Steganography takes the ideas of message hiding from ancient times and applies them to fundamentals of the digital computer. What the outcome should be is a way to communicate through the internet without anyone ever knowing you are communicating.

An example of Digital Steganography

The most popular form is digital steganography is to hide one form of communication (plaintext, an image, map coordinates) inside of another. As a final project in Computer Science 492: Information Security, I designed and implemented a program that would hide a peice of text inside of an image. I will explain the general idea of how this program works, but if anyone would like to hear more details or see the source code, please feel free to ask me through email/im or after class.

This compressed .rar file contains everything involved in the project, including documentation, source code, and sample inputs.

Also view this powerpoint presentation for a basic introduction to steganography.

More definitions

carrier - peice of data that is going to be hiding the message, ie the digital photo in my project

payload - secret piece of data hidden inside the carrier

package - the carrier after it has had the payload hidden inside it

How does it work?

The first thing to explain in order to understand how this program works is how an image is represented in a computer. After all, there is nothing magical about computers; they are simple symbol manipulators built from the ground up on digital circuitry. When an image is saved on your computer, for example a picture you took with your digital camera, the picture follows a definitive format that can be interpreted by image viewing applications to display a picture on your computer screen. This format is very similar between all types of images (.BMP, .JPG, etc) and it has two major parts. The first part of the format is called the heading, which gives vital data to the application trying to display the picture such as what type of image it is (.BMP, .JPG, etc), how big the picture is (width and height), and many other peices of information. The second peice, which makes up about 99% of an image file, is the picture itself. Every picture is made up of tiny dots of color called pixels, and each pixel is stored in the image file as a number value. Pixels are given their color by 3 components: a value for red, a value for blue, and a value for green (the three primary colors of the light spectrum). The higher the number for each color, the darker the shade of that color is in the pixel. For example, if you have a pixel with values (0 0 255) for red, blue, and green, respectively, then the pixel will have no red, no green, and a heavy shade of green. If you wanted to get purple, you would make the pixel have the values (255 255 0).

The next thing to understand is how a number like 255 is represented in the computer. Numbers in the computer are not represented in base 10, like you use numbers in math. The computer can only understand two things: whether there is electricity present or whether there isn't. This system is called binary, or base 2. A number can only be 0 or 1, and absolutely nothing else. A number like 3 would be represented by 2 binary digits (aka 'bits'), both of them would be set to 1. What would look to most people as 11, would be 3 in base 2, because the right-most one represents the 2^0 place (1) and the left-most bit represents the 2^1 place (2), so the fact that they are both turned on with 1 means you add 2 + 1 and get the value 3 in base 10. The number 30, for example, would be represented by 11110, which is (from left to right) (0 * 2^0) + (1 * 2^1) + (1 * 2^2) + (1 * 2^3) + (1 * 2^4) = 0 + 2 + 4 + 8 + 16 = 30. The number 255 is represented similarly by 11111111, or 8 ones. Everything in your computer is represented in this same form of 0s and 1s. Text in your Microsoft word document, pictures on your cell phone, even a movie you downloaded from Netflix is nothing but a really really long list of 0s and 1s.

After coming to grips with binary number representation, the final thing to comprehend is how these systems can be taken advantage of to give secret communications. If a picture on your computer has a pixel represented by (255 0 0) (or 11111111 00000000 00000000 in binary), it will look red to a human eye when displayed on a screen. Another pixel nearby may have the value (254 0 0) (or 11111110 00000000 00000000 in binary) and will, although the intensity of the redness in the pixel, look exactly the same to the human eye. This miniscule change, which cannot be detected by humans, gives an enourmous opportunity to someone looking for a place to hide a secret message. As I said before, everything in the computer is nothing but 0s and 1s, include a secret message you want to transmit to someone. Each character (letter) of a message is translated into 8 0s and 1s. If we take the right-most bit (called the low order bit) of each pixel in the image, we need 3 pixels in order to hide a letter. We simply truncate off whatever the low order bit was in the color for the original picture, and insert the bit we get from a letter in our secret message in it's place.

I am not sure how clear this explainanation will be to anyone, so please feel free to ask me in person if this concept is poorly explained and I will do my best to elaborate.

Below are some example pictures, with the original picture on the left, and the picture on the right has a secret message embedded in its pixels.

The message: "this is an example of modern digital steganography. this message will be hidden in the low order bits of the pixels in the provided image, and will keep the existence of the message hidden from anyone except the sender and reciever."

samplePGM.pgm - This is the original picture.

baconoutPGM.pgm - This is the picture with the message above embedded in the low order bits of the first couple pixels.

Can you tell the difference? I can't. In order to see the difference first-hand, you can open the image in Notepad. Like I said earlier, everything on your computer is just a long string of 0s and 1s, so there's nothing wrong with having Notepad - a text editor - open an image, you will just get what appears to be jibberish. Below is the first few dozen characters of the original image, pasted from Notepad. It is followed by the same first few dozen characters, but from the image after it has had the message embedded into it:

Text from original picture:    P5 200 200 255 ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ

Text from modified picture:  P5 200 200 255 þþþþþþþþþÿþþÿÿÿÿþÿþÿþÿþþþÿþþÿþþþþÿþþÿþþÿþÿþÿþþÿÿþþÿþþþþþþ

The header for both images is exactly the same. P5 designates that this image is of type .PGM (portable gray map), the two 200s designate that this image is 200 pixels wide and 200 pixels high. The 255 after that specifies that both images are using 8 bits to represent shades of color, or 2^8 = 256 different shades. This is where the similarities between the images end. The original image just had a long string of the character 'ÿ', which is Notepad attempting to interpret the number 255 (white) as a character. In the other image, some of the low order bits were changed from their original 1 (part of the 8 bit string representing the number 255 in base 2) on the far right replaced with a 0, effectively changing the number to 254. This one bit change makes the shade of gray one unit darker, which is completely imperceptible unless you were to blow it up to a rediculous size. When this 254 is interpreted by Notepad, the character 'þ' is shown.

The security of this program relies on the assumption that snoopers will not be opening every image you sent out on the internet with Notepad and inspecting the bits. When running the baconoutPGM.pgm picture through the program again, on decrypt mode, the original message is retrieved from the pixels and printed.

For anyone who is curious, the reason the programs are affiliated with the word "bacon" is because I had originally wrote the program using Baconian Ciphers, and the name stuck even after I moved away from Baconian Cipher.

As a final point, steganography is a really powerful idea and I believe it will become even more powerful in the future. A lot of research and money is being pumped into the field of quantum computing, which effectively uses atoms (yes, atoms as in chemistry class) as the basic building block of a computer, instead of silicon and copper circuitry. If a quantum computer is made, and I believe it is only a matter of time, the speed at which our computers do computations at present day will look like a horse and buggy compared to a sci-fi intergallactic starship. Remember that, no matter how "secure" an encryption algorithm is, the brute force attack is still applicable and WILL crack any cipher, given enough time. If a quantum computer is able to process through several trillion keys every second, modern encryption algorithms will be completely useless. Steganography, however, is a much more creative idea than the mathematics based cryptography, and it takes a human to be able to recognize when there is a hidden message, or when it is just more jibberish.