Today, when converting an analog image to digital format, we usually choose between three different ways of representing colors:
LSB insertion modifies the LSBs of each color in 24-bit images, or the LSBs of the 8-bit value for 8-bit images.
The letter 'A' has an ASCII code of 65(decimal), which is 1000001 in binary.
It will need three consecutive pixels for a 24-bit image to store an 'A':
Let's say that the pixels before the insertion are:
Then their values after the insertion of an 'A' will be:
(The values in bold are the ones that were modified by the transformation)
The same example for an 8-bit image would have needed 8 pixels:
Then their values after the insertion of an 'A' would have been:
(Again, the values in bold are the ones that were modified by the transformation)
From these examples we can infer that 1-LSB insertion usually has a 50% chance to change a LSB every 8 bits, thus adding very little noise to the original picture.
For 24-bit images the modification can be extended sometimes to the second or even the third LSBs without being visible. 8-bit images instead have a much more limited space where to choose colors, so it's usually possible to change only the LSBs without the modification being detectable.
The most basic of LSBs insertion for 24-bit pictures inserts 3 bits/pixel. Since every pixel is 24 bits, we can hide
So for this case we hide 1 bit of the embedded message for every 8 bits of the cover image.
If we pushed the insertion to include the second LSBs, the formula would change to:
And we would hide 2 bits of the embedded message for every 8 bits of the cover image. Adding a third-bit insertion, we would get:
Acquiring a data rate of 3 embedded bits every 8 bits of the image.
The data rate for insertion in 8-bit images is analogous to the 1 LSB insertion in 24-bit images, or 1 embedded bit every 8 cover bits.
We can see the problem in another light, and ask how many cover bytes are needed to send an embedded byte.
For 1-LSB insertion in 24-bit images or in 8-bit images this value would be 8/1*8 = 8 Bytes, for 2-LSBs insertion in 24-bit pictures it would be 8/2*8 = 4 Bytes, for 3-LSBs insertion it would be 8/3*8 = 21.33 Bytes.
LSB insertion is very vulnerable to a lot of transformations, even the most harmless and usual ones.
Lossy compression, e.g. JPEG, is very likely to destroy it completely. The problem is that the "holes" in the Human Visual System that LSB insertion tries to exploit - little sensitivity to added noise - are the same that lossy compression algorithms rely on to be able to reduce the data rate of images.
Geometrical transformations, moving the pixels around and especially displacing them from the original grid, are likely to destroy the embedded message, and the only one that could allow recovery is a simple translation.
Any other kind of picture transformation, like blurring or other effects, usually will destroy the hidden data.
All in all, LSB insertion is a very little robust technique for data hiding.
There is no theoretical outstanding mark of LSB insertion, if not a little increase of background noise.
It's very easy, instead, to extract LSBs even with simple programs, and to check them later to find if they mean something or not.
First of all, since it is a so vulnerable technique even for simple processing, LSB insertion is almost useless for digital watermarking, where it must face malicious attempts at its destruction, plus normal transformations like compression/decompression or conversion to analog (printing or visualization)/conversion to digital (scanning).
Its comparatively high data rate can point it as a good technique for steganography, where robustness is not such an important constraint.
Having stated that LSB insertion is good for steganography, we can try to improve one of its major drawbacks: the ease of extraction. We don't want that a malicious attacker be able to read everything we are sending.
This is usually accomplished with two complementary techniques:
In this way, the message is protected by two different keys, acquiring much more confidentiality than before.
This approach protects also the integrity of the message, being much more difficult (we could say at least computationally infeasible) to counterfeit the message.
Anyway, since we don't want our message to be only an encrypted and scrambled message, we must go back to the purpose of making the communication hidden.
The two most important issues in this problems are:
The cover image first of all must seem casual, so it must be chosen between a set of subjects that can have a reason to be exchanged between the source and the receiver.
Then it must have quite varying colors, it must be "noisy", so that the added noise is going to be covered by the already present one. Wide solid-color areas magnify very much any little amount of noise added to them.
Second, there is a problem with the file size, that involves the choice of the format. Unusually big files exchanged between two peers, in fact, are likely to arise suspicion.
Let's calculate, for instance, what the size would be for a 500x300 image (150,000 pixels), quite common for pictures on the Internet, with the different color representations:
Looking at the size, we can see that a 24-bit uncompressed picture is of a quite uncommon size, because it's very strange that the sender didn't compress it, a practice that's widely used and wouldn't have worsened the image quality so much.
To solve this problem, it has been studied a modification to the JPEG algorithm that inserts LSBs in some of the lossless stages or pilots the rounding of the coefficients of the DCT used to compress the image to encode the bits.
Since we need to have small image file sizes, we should resort in using 8-bit images if we want to communicate using LSB insertion, because their size is more likely to be considered as normal.
The problem with 256 colors images is that they make use of an indexed palette, and changing a LSB means that we switch a pixel from a position to an adjacent one. If there are adjacent contrasting colors in the palette, it can happen that a pixel in the image changes its color abruptly and the hidden message becomes visible.
To solve this problem different methods have been studied, like rearranging the palette so that adjacent colors don't contrast so much, or even reducing the palette to a smaller number of colors and replicating the same entry in the table in adjacent positions, so that the difference after the embedding of the message is not visible at all. Moreover for most images the reduction of colors from, for instance, 256 to 32 is hardly visible.
Most of the experts, anyway, advise to use 8-bit grayscale images, since their palette is much less varying than the color one, so LSB insertion is going to be very hard to detect by the human eye.
[JJ98-1]
Previous: still images
Next: spread spectrum
Matteo Fortini