Steganography

CS 463/480 Lecture, Dr. Lawlor

Steganography (covered writing) is a way to make cryptanalysis more difficult, by concealing the fact that a message is being conveyed. The big problem with classic ciphers is if you're always sending or receiving email attachments full of binary data named "la_revolution.txt.aes", the police already have enough to arrest you. But if you're just receiving something innocent looking like lolcat pictures, you might be OK.

There are thousands of places messages could be concealed in digital files, such as inside a hidden compartment in a structured file format like RIFF, but one of the simplest and most common binary files people deal with are image files. Since most image sensors operate at the limit of quantum detection, photon shot noise means the low bits of most images are basically random already.

For example, here's an aurora image I shot in 2013:

Extracted bit 7 of red channel:

Extracted bit 6:

Extracted bit 5:

Extracted bit 4:

Extracted bit 3:

Extracted bit 2:

Extracted bit 1:

Extracted bit 0:

Note that nearly nothing useful is happening in bits 0 and 1 of each pixel. We can thus overwrite the low bits, and our message is not easy to detect by eye.

Note that this does not work if we overwrite the high bits:

Inserted into bit 7:

Inserted into bit 6:

Inserted into bit 5:

Inserted into bit 4:

Inserted into bit 3:

Inserted into bit 2:

Inserted into bit 1:

Inserted into bit 0:

Original image:

There are several complications with this simple technique:

It only works on lossless image formats, like PNG, BMP, or PPM. Lossy image formats like JPEG usually discard exactly the information we're trying to communicate (though you could use specialized DCT-based stego to store data in a JPEG).
Large uniform areas in the secret image bleed through into the output histogram, where they can be detected by the sawtooth pattern in the image value histogram. It's much safer to first encrypt, then stego the data, because then the stego signal appears random. This also prevents Eve from being able to prove that a message even exists.
It's safer to modify only a selected subset of the low bits instead of all of them. Each digital camera sensor, due to fabrication variations, has systematic per-pixel biases in level and gain, which can be used to 'fingerprint' a photo. Overwriting all the low bits will destroy this fingerprint, making it clear the image has been tampered with. Modifying only a small subset is more difficult to detect, as long as the subset is unpredictable (part of the key).

My quick and dirty PPM-binary image format stego source code: Zip or Tar-gzip.