PNG Merge

From YobiWiki
Jump to navigation Jump to search

How many images in this PNG?

This is a Poc (Proof of Concept) to create a PNG file that contains different images somehow entangled together.
The original idea is from @reversity who proposed us a hand-crafted PoC.
There was no available script to play with so @angealbertini and I tried to reverse-engineer it :-)
The idea is that PNG data can be interpreted depending on the Color Type among other types as RGB values (color type =2) or as indexed values (color type =3) together with a palette (PLTE).
RGB PNG (color type =2) can legitimately contain a PLTE, from the specs:

If present, it provides a suggested set of from 1 to 256 colors to which the truecolor image can be quantized if the viewer cannot display truecolor directly.

Which means nowadays that a PLTE in a RGB image will be systematically ignored!
So just by changing the color type byte (typically the 25th byte) from 2 to 3 (and the IHDR CRC) we can change completely the way the image is displayed.

To craft such image, we need a RGB image, an indexed image and the corresponding palette which, we'll see, can also contain an image!

Literate programming

This code, also available on Github TODO can do the job: {{#fileanchor: mergeRGBi.py}} 

#!/usr/bin/env python
# Ange Albertini, Philippe Teuwen, BSD Licence, 2014
# Based on Dominique Bongard original idea

# Should we restrict scanline filters to 0 only?
# Needed e.g. for Gimp under Windows
# Side effect is presence of black diagonals in results
SLF_FIX=False

This SLF_FIX refers already to an obscure problem in Gimp under Windows but let's ignore it for now.
_pngread and _pngmake are two helper functions to... read and make PNG structures and handle them as list of chunks: {{#fileanchor: mergeRGBi.py}} 

import struct, sys, zlib, binascii

_MAGIC = "\x89PNG\x0d\x0a\x1a\x0a"
_crc32 = lambda d:(binascii.crc32(d) % 0x100000000)

def pngread(f):
    """gets a file, returns a list of [type, data] chunks"""
    assert f.read(8) == _MAGIC
    chunks = []
    while (True):
        l, = struct.unpack(">I", f.read(4))
        t = f.read(4)
        d = f.read(l)
        assert _crc32(t + d) == struct.unpack(">I", f.read(4))[0]
        chunks += [[t, d]]
        if t == "IEND":
            return chunks
    raise(BaseException("Invalid image"))

def pngmake(chunks):
    """returns a PNG binary string from a list of [type, data] PNG chunks"""
    s = [_MAGIC]
    for t, d in chunks:
        assert len(t) == 4
        s += [
            struct.pack(">I", len(d)),
            t,
            d,
            struct.pack(">I", _crc32(t + d))
            ]
    return "".join(s)

Usage will be 

mergeRGBi.py rgb.png ncol.png result.png

So RGB input chunks are stored in rgb, indexed image input chunks are stored in nc (for N colors) {{#fileanchor: mergeRGBi.py}} 

fnrgb, fnnc, fnout = sys.argv[1:4]
with open(fnrgb, "rb") as frgb:
    rgb = pngread(frgb)
with open(fnnc, "rb") as fnc:
    nc = pngread(fnc)

For simplicity, we only support inputs with the minimum number of chunks: IHDR, possibly one PLTE (even for rgb, in case we're reusing a previous PoC file), one single IDAT, and IEND.
We extract width and height of rgb and nc. {{#fileanchor: mergeRGBi.py}} 

assert len(rgb) == 3 or len(rgb) == 4 # IHDR [PLTE] IDAT IEND
assert len(nc) == 4 # IHDR PLTE IDAT IEND
wrgb, hrgb = struct.unpack(">LL", rgb[0][1][0:0 + 4 * 2])
wnc, hnc   = struct.unpack(">LL", nc[0][1][0:0 + 4 * 2])

We also support only unfiltered PNGs. A PNG is made of compressed horizontal scanlines starting with a "filter type" byte according to a "filter method" but as of today only "filter method 0" is standardized with 5 different types of filter, the first one, 0, means the identity function: Filt(x) = Orig(x).
Once decompressed, scanlines are streams of bytes of size=(width*3)+1 for rgb with 3 bytes per pixel and of width+1 for indexed nc.
To embed nc in rgb we must make sure its IDAT contains same or less bytes than rgb IDAT. {{#fileanchor: mergeRGBi.py}} 

print "RGB dimensions:", wrgb, hrgb
print "RGB IDAT:", ((wrgb*3)+1)*hrgb
print "idx dimensions:", wnc, hnc
print "idx IDAT:", (wnc+1)*hnc
assert ((wrgb*3)+1)*hrgb >= (wnc+1)*hnc

Let's decompress scanlines from IDAT {{#fileanchor: mergeRGBi.py}} 

px_rgb  = [ord(i) for i in zlib.decompress(rgb[1 if len(rgb) == 3 else 2][1])]
px_nc = [ord(i) for i in zlib.decompress(nc[2][1])]

We extract the palette from nc and count the number of colors (as rgb triplets). By safety we check all indexes are indeed in the range of palette colors. The we convert the palette into a list of rgb triplets. {{#fileanchor: mergeRGBi.py}} 

# Initial palette
palin = nc[1][1]
# Number of colors in initial palette
n=len(palin)/3
assert n >= max(px_nc)+1
print "PLTE", n, "colors"
# Convert palette into list of rgb triplets
palin = [palin[i:i+3] for i in range(0, len(palin), 3)]

We can also allow the script to take an extra image as palette. We'll see later that it gives the freedom to put also an image in the palette itself!
So usage becomes: 

mergeRGBi.py rgb.png ncol.png result.png [palette.png]

If there is a palette image, it must respect the same constraints as nc and it must be a 16x16 image using the same palette as nc.
All colors present in the palette must be present in the image that will become the new palette.
Ideally all colors should be present in each of the 16 lines of the new palette to avoid too large distortions in the final RGB result. {{#fileanchor: mergeRGBi.py}} 

# New palette
if len(sys.argv)>4:
    # We got a file as new palette
    fnpal = sys.argv[4]
    with open(fnpal, "rb") as fpal:
        pal = pngread(fpal)
    assert len(pal) == 4 # IHDR PLTE IDAT IEND
    assert 16, 16 == struct.unpack(">LL", pal[0][1][0:0 + 4 * 2])
    assert nc[1][1] == pal[1][1]
    px_pal = [ord(i) for i in zlib.decompress(pal[2][1])]
    # Remove scanlines
    for i in xrange(16):
        px_pal.pop(i*16)
    # We need all palette colors
    for i in xrange(n):
        assert i in px_pal
    palout = [palin[i] for i in px_pal]

If we don't provide a new palette, then it will be constructed from the original small palette and it will be extended to cover all 256 possible indexes so we'll have the possibility to tweak rgb pixels towards indexes of wanted colors without too much distortion, again.
Original palette is mutated when duplicated to avoid traditional LSB-based stegano scanners, so indexes of same color won't have always the same LSB. {{#fileanchor: mergeRGBi.py}} 

else:
    palout=[]
    paltmp=palin
    for i in xrange((256/n)+1):
        palout+=paltmp
        # mutate original palette
        paltmp=paltmp[1:]+paltmp[:1]
    palout=palout[:256]

So now how the rgb IDAT is distorted to map to nc? Each r, g, b byte is interpreted as an index when the color type byte is forced =3 and the corresponding color is given by the palette. We've see above that we tried to extend the palette to all 256 possible values by repeating the same colors regularly. So now we need a function that given a starting R or G or B value to be interpreted as index and a desired color, returns the closest index pointing to that color. Special attention must be taken when we're dealing with the start of a scanline, the filter byte, because theoretically it can only be between 0 and 5. And it cannot change otherwise we're changing the applied filtering. Unless rgb and nc have very compatible dimensions, a color byte of rgb can match a filter byte of nc or vice versa. Practically, most applications accept a filter byte >5 and will interpret it as a 0, which gives us some flexibility. But as said earlier, Gimp under Windows is one of the applications complaining about filter byte>5, therefore this SLF_FIX to force filter bytes=0, but this will display unsightly black lines in the counterpart. {{#fileanchor: mergeRGBi.py}} 

def find_closest_idx(col, idx, palette, scanline_rgb=False, scanline_nc=False):
    off=0
    if scanline_rgb:
        assert idx == 0 or idx>=5
    if SLF_FIX and (scanline_rgb or scanline_nc):
        return 0
    assert col in palette[5 if scanline_rgb else 0:]
    if scanline_nc and 0<=idx<5:
        return 0 if idx < 3 else 5
    while abs(off) < len(palette):
        if (idx+off == 0 or (5 if (scanline_rgb or scanline_nc) else 0) <= idx+off < len(palette)) \
          and col == palette[idx+off]:
            return idx+off
        else:
            off = -off if off>0 else -off+1

Now all we have is to go over nc pixels and merge them into rgb data. {{#fileanchor: mergeRGBi.py}} 

for i, j in enumerate(px_nc):
    # integrate n-col indexes in RGB values, watch out RGB scanlines
    px_rgb[i]=find_closest_idx(palin[j],px_rgb[i], palout,
                               scanline_rgb=(i % (3 * wrgb + 1)) == 0,
                               scanline_nc=(i % (wnc + 1)) == 0)

And we're done! We can pack everything in a PNG. {{#fileanchor: mergeRGBi.py}} 

px_final = "".join([chr(i) for i in px_rgb])

outchunks = [
    ["IHDR", rgb[0][1]],
    ["PLTE", ''.join(palout)],
    ["IDAT", zlib.compress(px_final, 9)],
    ["IEND", ""]
    ]

with open(fnout, "wb") as fout:
    fout.write(pngmake(outchunks))

To make analysis easier, we can generate a PNG with the color type patch to see the indexed version. As some applications don't appreciate more bytes than needed in IDAT (as libpng) we truncate IDAT too. {{#fileanchor: mergeRGBi.py}} 

outchunks[0][1] = outchunks[0][1][:9] + "\3" + outchunks[0][1][10:]
# Fix size
outchunks[0][1]=struct.pack(">LL", wnc, hnc)+outchunks[0][1][0 + 4 * 2:]
# Optional step: truncate IDAT to make libpng happy:
outchunks[2][1] = zlib.compress(px_final[:(wnc+1)*hnc], 9)
with open("_" + fnout, "wb") as fout:
    fout.write(pngmake(outchunks))
# To debug IDAT:
#with open("_IDAT_" + fnout, "wb") as fout:
#    fout.write(px_final[:(wnc+1)*hnc])

Usage

[{{#filelink: mergeRGBi.py}} mergeRGBi.py is available for download here] 

mergeRGBi.py rgb.png ncol.png result.png [palette.png]

It merges a n-color indexed PNG into a RGB PNG.
To find back the indexed PNG, one has to change color=2 -> color=3 in the IHDR, which is already done in secondary output _resultat.png.
Original palette is mutated when duplicated to avoid traditional LSB-based stegano scanners.
But you can provide your own 16x16 PNG to be used as palette. It must have the same palette as the indexed PNG and make sure each line contains each color to avoid too large adjustments in RGB PNG.
Note that libpng will complain about the indexed PNG because IDAT is larger than needed, try e.g. Gimp.

RGB PNG requirements:

  • IHDR+IDAT+IEND
  • scanline filters=0

n colors PNG requirements:

  • IHDR+PLTE+IDAT+IEND
  • scanline filters=0

IDAT size <= RGB IDAT size, i.e. (wnc+1)*hnc <= ((wrgb*3)+1)*hrgb

palette PNG requirements:

  • IHDR+PLTE+IDAT+IEND
  • scanline filters=0
  • 16x16
  • same palette as n colors PNG
  • image must use all colors

To verify and get one single IDAT, you can do: 

pngchunks foo.png
advpng -z -0 foo.png
advpng -z -3 foo.png
pngchunks foo.png

Note that if you're in a situation where you need to use SLF_FIX, one way to avoid it is to use a n colors PNG with width exactly = 3*width of RGB PNG.
In that case, scanline filter bytes of rgb and nc will coincide and you won't get dark diagonals, you even don't need to activate this option anymore.
E.g. you can choose rations such as x/y~=1/(3*x/y) => x/y~=1/sqrt(3) => x/y ~ 0.577
So one can use a RGB PNG of 200x350 pixels (x/y ~ 0.571) and a n-color indexed PNG of 600x350 pixels

Examples

Going further?

We managed to put 3 images into 1, could we do better?
Maybe :-)
One can draw e.g. a skyline in the image histogram.
See http://www.joshmillard.com/2007/10/04/retro-histo-making-an-image-fit-your-histogram/ and http://www.ironicsans.com/2007/09/idea_the_histogram_as_the_imag.html
But the method would have to be integrated without destroying our careful rgb values<>indexes correspondences...

Retrieved from "https://wiki.yobi.be/index.php?title=PNG_Merge&oldid=9220"