Basic Steganography
Chapter Ninety-Three
Syllabus topic Module 2, "Basic steganography"
Pages 338 to 341 of 378
In one line
Least significant bit hiding puts one bit of a message into the lowest bit of each pixel, where a change of one in 256 is invisible.
In the wording you can write in an examination: steganography conceals the existence of a message by embedding it in a carrier whose alteration is imperceptible. In least significant bit hiding the message bits replace the lowest-order bit of successive samples of a digital carrier, typically the pixels of an image. The capacity is one bit per sample, the distortion is at most one unit per altered sample, and the method is detectable by statistical analysis of the low-order bits.
Why the lowest bit
A greyscale pixel is a number from 0 to 255. Its lowest bit contributes 1.
Changing it changes the shade by one part in 256. No eye sees it, and most displays cannot show it.
And every pixel has one, so an image of a million pixels carries a million bits, which is 125 kilobytes.
That is the whole idea. The carrier has more precision than anybody uses, and the unused precision is storage.
The method
To hide. Turn the message into bits. For each bit in turn, take the next pixel, clear its lowest bit, and set it to the message bit.
To recover. Read the lowest bit of each pixel in turn, group them into bytes, and stop at a terminator.
The terminator matters. Without it the reader does not know where the message ends and reads the carrier's own low bits as text. This implementation appends a zero byte, which is why the message may not itself contain one.
The method, run
"""Least significant bit hiding, on a small greyscale image the program makes."""
WIDTH, HEIGHT = 16, 16
def carrier():
"""A smooth gradient, so that a changed bit is invisible to the eye."""
return [((x * 7 + y * 11) % 200) + 28 for y in range(HEIGHT) for x in range(WIDTH)]
def hide(pixels, message):
bits = "".join(format(b, "08b") for b in message.encode("ascii")) + "0" * 8
if len(bits) > len(pixels):
raise ValueError("carrier holds %d bits, message needs %d" % (len(pixels), len(bits)))
out = list(pixels)
for i, bit in enumerate(bits):
out[i] = (out[i] & ~1) | int(bit)
return out
def read(pixels):
bits = "".join(str(p & 1) for p in pixels)
out = bytearray()
for i in range(0, len(bits) - 7, 8):
byte = int(bits[i:i + 8], 2)
if byte == 0:
break
out.append(byte)
return out.decode("ascii")
MSG = "GUDHALEKHYA"
plain = carrier()
stego = hide(plain, MSG)
print("carrier: %d by %d greyscale, %d pixels, %d bits of capacity"
% (WIDTH, HEIGHT, len(plain), len(plain)))
print("message: %r, %d bytes, %d bits with the terminator"
% (MSG, len(MSG), 8 * len(MSG) + 8))
print("capacity used: %.1f%%" % (100 * (8 * len(MSG) + 8) / len(plain)))
print()
print("the first sixteen pixels, before and after")
print(" before " + " ".join("%3d" % p for p in plain[:16]))
print(" after " + " ".join("%3d" % p for p in stego[:16]))
print(" change " + " ".join("%3d" % (s - p) for p, s in zip(plain[:16], stego[:16])))
print()
changed = sum(1 for p, s in zip(plain, stego) if p != s)
biggest = max(abs(s - p) for p, s in zip(plain, stego))
print("pixels changed: %d of %d" % (changed, len(plain)))
print("largest change in any pixel: %d (out of a 0 to 255 range)" % biggest)
print("recovered message: %r" % read(stego))
print("round trip correct:", read(stego) == MSG)
print()
print("and the detection: the low bits of a natural image are not uniform")
def low_bit_balance(pixels, n):
ones = sum(p & 1 for p in pixels[:n])
return ones, n - ones
for name, px in (("carrier", plain), ("stego ", stego)):
ones, zeros = low_bit_balance(px, 96)
print(" %s first 96 low bits: %d ones, %d zeros" % (name, ones, zeros))
print()
try:
hide(plain, "X" * 40)
except ValueError as e:
print("a message too large is refused:", e)Basic Steganography
carrier: 16 by 16 greyscale, 256 pixels, 256 bits of capacity
message: 'GUDHALEKHYA', 11 bytes, 96 bits with the terminator
capacity used: 37.5%
the first sixteen pixels, before and after
before 28 35 42 49 56 63 70 77 84 91 98 105 112 119 126 133
after 28 35 42 48 56 63 71 77 84 91 98 105 112 119 126 133
change 0 0 0 -1 0 0 1 0 0 0 0 0 0 0 0 0
pixels changed: 44 of 256
largest change in any pixel: 1 (out of a 0 to 255 range)
recovered message: 'GUDHALEKHYA'
round trip correct: True
and the detection: the low bits of a natural image are not uniform
carrier first 96 low bits: 48 ones, 48 zeros
stego first 96 low bits: 32 ones, 64 zeros
a message too large is refused: carrier holds 256 bits, message needs 328Reading the output
A 16 by 16 image is 256 pixels and therefore 256 bits of capacity. The message is 11 bytes, 96 bits with the terminator, so 37.5 per cent of the capacity is used.
Forty-four pixels changed out of 256, not 96. That is because a bit only changes a pixel when it differs from the bit already there, and about half the time it agrees. The expected number of changes is half the bits used, which is 48, and 44 is what this carrier gave.
The largest change to any pixel is 1, on a range of 0 to 255. That is the imperceptibility claim, measured.
Basic Steganography
And the round trip is checked, not assumed.
The detection, measured
The last block is the reason least significant bit hiding is not used where it matters.
The carrier's first 96 low bits are 48 ones and 48 zeros. That is what a smooth gradient gives: the low bit alternates with the gradient.
The stego image's are 32 ones and 64 zeros. The message's bits are ASCII text, whose bytes all begin with a zero bit and whose letters are concentrated in a narrow range, so its bit stream is not balanced.
So the alteration is visible in the statistics although it is invisible to the eye. A detector does not look at the picture; it counts the low bits and asks whether they look like the low bits of an image of that kind.
And that is the general principle worth stating. An embedding that does not match the carrier's own statistics is detectable however small it is, and the field of steganalysis is the business of finding such mismatches. Modern methods therefore embed in a way that preserves the expected statistics, at the cost of capacity.
Capacity, and its limits
One bit per sample is the simple version. Using two bits per pixel doubles the capacity and quadruples the maximum distortion, to 3 out of 255, which is still nearly invisible and is much more detectable.
And the carrier must be large. Hiding a message of n bytes needs at least 8n plus 8 samples. A 100 kilobyte message needs an image of more than 800,000 pixels.
The refusal at the end of the output is the check that must exist. A message too large for its carrier must be rejected, and an implementation that silently truncates it has produced a message the recipient cannot read and given no warning.
What steganography is NOT
It is not encryption. The message is in the carrier in plain form. Anyone who suspects the method reads it.
So it is used WITH encryption, as [Concealment and Coded Messaging] sets out: encipher first, then embed, so that discovery of the embedding yields ciphertext.
It is not robust. Recompressing the image, resizing it, or converting it to a lossy format destroys the low bits and the message with them. Least significant bit hiding survives only a lossless channel, and most channels are not.
And it is not new. The Arthaśāstra's information carried "under the pretext of taking in musical instruments" is the same idea with a different carrier, as is the signs made in temples. What is new is the carrier's precision, which is what makes the modern version high-capacity and invisible.
Basic Steganography
The comparison with the classical methods
| The Arthaśāstra's concealment | Least significant bit hiding | |
|---|---|---|
| Carrier | an object, an occasion, a gesture | the unused precision of a digital sample |
| Capacity | one prearranged meaning | one bit per sample, so kilobytes |
| Detection | by a suspicious observer | by counting the low bits |
| Robustness | survives handling | destroyed by recompression |
| Needs prior agreement | yes, the sign's meaning | yes, the method and the terminator |
The last row is the one they share, and it is the standing problem of all concealment: both parties must agree on the method before any message is sent, which is the key distribution problem of [Symmetric Encryption] in a different coat.
Quick revision
- LSB hiding replaces the lowest bit of each sample with a message bit. Capacity one bit per sample; distortion at most one unit.
- A terminator is required, or the reader cannot tell where the message ends.
- About half the bits change a pixel, because half the time the bit already agrees.
- Detection is by statistics, not by eye: the carrier's low bits were balanced 48 to 48 and the stego image's were 32 to 64.
- An embedding that does not match the carrier's own statistics is detectable however small it is.
- It is not encryption, it is not robust to recompression, and a message too large must be refused rather than truncated.
- Both parties must agree the method in advance, which is key distribution in another form.
Test yourself
1. Why is the lowest bit chosen, and what is the capacity of a one-megapixel greyscale image?
Because changing it alters the value by one part in 256, which is imperceptible. The capacity is one bit per pixel, so about a million bits, which is 125 kilobytes.
2. Why did 96 message bits change only 44 pixels?
Because a message bit only changes a pixel when it differs from the bit already in the lowest position, which happens about half the time. The expected number of changes is half the bits used.
3. How is least significant bit hiding detected, and what does that tell you about designing a better method?
By counting the low-order bits and comparing their distribution with what a carrier of that kind should have; here the balance moved from 48 ones in 96 to 32. It tells you that an embedding must preserve the carrier's own statistics, which costs capacity.
4. Why must steganography be combined with encryption, and in what order?
Because the hidden message is in plain form and is readable by anyone who suspects the method. Encipher first and then embed, so that discovering the embedding yields only ciphertext.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.