Two images, one bit apart

Backdoor CTF 2016 Lossless: data hidden in a PNG pixel difference

Two PNG files look the same to the eye. Subtracting them reveals a small block of pixels whose values differ by one, and that block is a 7-bit ASCII message.

Hexfield editorial

EventBackdoor CTF 2016
CategoryForensics, stegano
Points100
TechniqueImage difference, LSB
Forensics100 pts
  1. 01

    Inspect

    Two PNG files, original.png and encrypted.png, appear identical, which means the information lives in pixel values or in the file structure.

  2. 02

    Hypothesize

    PNG compression is lossless, so a one-bit change in a pixel survives and can carry a message invisible to the eye.

  3. 03

    Test

    Running ImageMagick compare produces a difference image with a small marked region in the upper left corner.

  4. 04

    Solve

    The region is a 49 by 7 black and white matrix, read as 7-bit ASCII columns, which decodes to the flag text.

Byte-pair digram of a PNG file with a faint diagonal and scattered dense cells typical of deflate-compressed scanlines
The digram of a PNG shows the near-uniform spread of deflate output, with the structure living in the headers and chunk boundaries.

The two files

The Lossless task in Backdoor CTF 2016 is a 100-point forensics challenge tagged as steganography. The story is thin: someone hid a secret in a PNG and tried to distract the reader. The attachment is two files, original.png and encrypted.png. Opened in an image viewer they look the same, down to the last visible detail. That observation is the first piece of reasoning. Identical appearance with different file bytes means the change is either small enough to be invisible or stored somewhere a viewer never displays.

A quick structural look rules out the second option. A PNG file starts with the eight-byte signature 89 50 4E 47 0D 0A 1A 0A, followed by chunks that each hold a four-byte big-endian length, a four-byte type, the data and a CRC32 over type and data. The mandatory chunks are IHDR for dimensions and color type, one or more IDAT chunks with the image data, and IEND. Listing the chunks with pngcheck -v or exiftool shows whether text chunks (tEXt, zTXt, iTXt) or private ancillary chunks carry anything extra. In this task the interesting differences are in the decoded pixels, not in metadata.

Why a one-bit change survives

IDAT data is a zlib stream: a two-byte header, a DEFLATE body and an Adler-32 checksum. Before compression, each scanline is passed through one of five filters (None, Sub, Up, Average or Paeth) that store each byte as a difference from a prediction. This is purely reversible, so the format is lossless. Decoding gives back the exact original sample for every pixel.

That property is what makes the least significant bit a convenient hiding place. Each channel of a typical image holds a value from 0 to 255, and flipping bit 0 shifts a color by one level. Such a shift is imperceptible, yet the bytes inside the compressed stream change completely, because DEFLATE reacts to any difference in its input. A byte-level comparison of the two files therefore shows a mess, while a pixel-level comparison shows exactly which pixels were touched. The comparison has to happen after decoding.

Subtracting the images

ImageMagick makes the pixel-level comparison a single command.

compare original.png encrypted.png difference.png

By default the output keeps the base image faded and paints every differing pixel in red. In the resulting file a distinct rectangle appears in the upper left corner and nowhere else. A numeric check agrees: compare -metric AE reports the number of differing pixels, and the count is small. The same result can be had in Python with Pillow, which also gives the bounding box of the change directly.

from PIL import Image, ImageChops

a = Image.open("original.png").convert("RGB")
b = Image.open("encrypted.png").convert("RGB")
diff = ImageChops.difference(a, b)
print(diff.getbbox())

Anything outside that box is identical. Inside it, a pixel either carries a difference of one or none, which makes the region a binary picture.

Reading the matrix

Cleaning the difference up in GIMP, with a threshold so that changed pixels turn black and unchanged ones white, exposes a grid of 49 by 7 cells. Seven is the telling number. Seven bits is the width of an ASCII code, and printable ASCII never needs the eighth bit. The grid is therefore 49 characters, each written as a column of seven bits.

The first column begins with the bits 10, which places it in the range 0x40 to 0x5F, the capital letters. The remaining columns begin with 11, the range 0x60 to 0x7F, which holds the lowercase letters. Columns of 0100000 stand for the space character, 0x20. That distribution, one capital letter followed by lowercase text and spaces, matches an ordinary sentence and confirms that the bit order was read correctly.

Turning pixels into text

One workable route rotates the matrix by 90 degrees counterclockwise so each character becomes a row, exports it as a 24-bit BMP, and then reads the pixel bytes as a hex dump. Black pixels appear as 00 00 00 and white ones as ff ff ff, so a replacement of the first with 1 and the second with 0 yields a bit string. Grouping into sevens and converting each group to a character finishes the job.

Two details commonly cause trouble in this approach. BMP rows are padded to a multiple of four bytes, so a seven-pixel row of 21 bytes carries three extra bytes of padding that must be removed before grouping. BMP also stores rows from the bottom up, which reverses the row order. A direct read of pixel values with Pillow avoids both, since it returns the pixels in display order. If the first decoded character is not a capital letter, the matrix needs a flip or a different rotation.

What transfers to other challenges

When two files are supposed to be the same, subtract them. Difference images expose least-significant-bit embedding, tiny watermarks and edited regions in one step. Check the chunk list first, then the pixels. A channel-wise bit plane view, which shows each bit of each color separately, finds the cases where only one image is provided and no original exists. The same logic of comparing something against its expected form appears in the CRC task from the same contest, where the checksum plays the role of the second file. For the mechanics of how compressed image data looks at byte level, see the guide to compression and encryption.

Questions readers ask

Why does lossless compression matter for this challenge?

A lossless format reproduces every pixel value exactly. A lossy format such as JPEG would round away a change of one in a color channel. Because PNG keeps it, a message in the least significant bits survives saving, copying and conversion between lossless formats.

What does the least significant bit change look like?

Flipping the lowest bit of an 8-bit channel changes its brightness by one step out of 255. The result is far below what human vision can tell apart, so the two images look the same even though a pixel-wise difference is not zero.

Could the data have been in a PNG chunk instead?

Yes, text and custom chunks can carry payloads, and tools such as pngcheck and exiftool list them. Here the two files differ in pixel data, which is why a visual or numeric difference finds the message while a chunk listing does not.

New to capture the flag? Formats, teams and a first-month plan in one place.

Read the CTF guide