Talk Topic: Steganographic Encodings
David Wittenberg, Brandeis University
October 10, 2007

Abstract
Steganography (hidden writing) predates cryptography (secret writing) as a method of hiding information. The first known uses were described by Herodotus around 480 BCE, and there are reports of both sides using steganography during World War II.

For most of its history, steganography consisted of thinking of new hiding methods and hoping that no one else thought to look in those places. In 2000, Moskowitz, Longdon, and Chang changed the basic model of steganography to be closer to the standard model of cryptography. Instead of trying to pick a method of communicating which others are unlikely to look for, the steganographer now assumes that the steganalyst knows what steganographic system is in use, and tries to make it impossible to distinguish objects with hidden data from unmodified objects without knowledge of the steganographic key.

LSB (least significant bit) encoding is a steganographic technique to hide data in the low order bits of an image. On the assumption that the low order bits are essentially random (since they're at the limit of the camera's sensitivity), one simply replaces those bits with the message one wishes to send. Moskowitz et al. point out that most pictures have areas where the low order bits are clearly non-random, so if those bits are replaced with (apparently) random bits, the replacement is easily detected. We show that this attack can be avoided by not embedding data in areas which appear too regular.

Later, other attacks on LSB encoding were based on the observation that even the low order bits which appear random when viewed alone correlate with the higher order bits. Several groups have showed how to detect steganography using this fact. We describe additive LSB encoding, which avoids detection by all methods of searching for correlation which we are aware of.

We introduce XLSB, which combines block selection with additive LSB encoding to avoid both methods of detection without complicating the decoder. We give test results showing that several steganalysis techniques do not detect XLSB.

This talk is self-contained, and assumes no steganographic background.