VolgaCTF 2015 TLSB

The question:

tlsb
There must be a hidden message somewhere.
stego

Hints
  1. 2 bpp. That's incredible.
  2. 2x3 matrix embedding.
  3. Jessica Fridrich would solve this task easily.

    So, where to begin.

    So the first place to look is the lsb, so extracting them with a little python I don't see anything that I can use, either anything looking like a text string, or any sections that seem to differ.

    The first clue says it's 2 bpp, now each pixel has 3 channels, so I spent some time looking at two lsb's from each channel, but that didn't lead anywhere, so then I did some digging into how you might encode 2 bits in 3 bits of data.

    The only way I could come up with was Hamming weights which is basically the count of set bits:

                R G B  Hamming weight
                0 0 0     0 = 00
                0 0 1     1 = 01
                0 1 0     1 = 01
                1 0 0     1 = 01
                0 1 1     2 = 10
                1 0 1     2 = 10
                1 1 0     2 = 10
                1 1 1     3 = 11

    I played with this a little, but wasn't able to come up with anything that in a few ways but couldn't quite come up with anything that really looked like a solution

    There's definitely something funny going with the lsb, just looking almost all of them are either 00 or 11, it doesn't help me get an answer, but it indicates something funny is going on, back to goolge!

    The second clue mentioned Matrix embedding, and the third mentioned Jessica Fridrich, which lead me to a few papers including these:

    I spent some time digging through these, and I'll confess to having a hard time with the maths notations, which made it hard going understanding exactly how these would help when dealing with our image.

    However when I gave up on actually getting the underlying theory (Bookmarked for later!) I went back to google looking for sample implementations of some of what they're talking about, the real breakthrough came from: F5 a Steganographic algorithm which is quite a nice Power Point deck discussing different ways of embedding data into images but with a much more programmer accessible notation, again mostly based on jpegs but fortunatly including slide 15 which states:

                x1 == a1 ^ a3, x2 == a2 ^ a3 - no modification required
                x1 != a1 ^ a3, x2 == a2 ^ a3 - flip a1
                x1 == a1 ^ a3, x2 != a2 ^ a3 - flip a2
                x1 != a1 ^ a3, x2 != a2 ^ a3 - flip a3

    This is basically saying you can encode two bits of data into three source bits by only modifying one bit from each pixel (at worst) in the cover image (which is pretty darn cool!)

    The slide refers to the more general cases for hiding x bits of data in y bits of cover, which was what I was trying and failing to grasp from the Math papers I suspect, but that's not the issue, because this is the 3x2 case we're already looking for!

    So this means that our output bits following this scheme would be:

                x1 = (r & 1) ^ (b & 1)
                x2 = (g & 1) ^ (b & 1)

    So coded this up and searched for strings or the png header and still failed to find anything.

    I was trying to do some side by side comparisons and actually printed the output from this and was surprised (and excited) to see that almost all the bits were zero!

    So I tried to split them based on rows and columns to see if the ones that were set made a pattern, but was surprised to see that all the bits were at the start of each row...

    A quick look at my code and I realised I was traversing columns not rows, a quick conversion and suddenly I've found that all the ones are in the first 15 rows of the file, and there's no big gaps! I've got something out!

    but what? file doesn't regcognise it, although the way it looks as text reminds me of other png's I've seen...

    Looking at the bits of the header it's very close to being a png header, with only alternate bits set wrong, a little trial and error lead me to:

    x1 = (r & 1) ^ (g & 1)
    x2 = (g & 1) ^ (b & 1)

    Run that through my inspection code and I see a whole png header, right from the start of the file! a quick export and we've got a valid output!

    The result image is just white with some black text {xor_trick_reduces_overall_distortion}

    Source for the final run:

    from PIL import Image
    im = Image.open("stego.png") #Can be many different formats.
    #im = Image.open("original.jpeg")
    pix = im.load()
    limx, limy = im.size
    
    red_bits = []
    green_bits = []
    blue_bits = []
    
    counter = 0
    last_1 = (0,0,0)
    bits = [0,0,0,0,0,0,0,0]
    recovered_bits = []
    chars = []
    for y in xrange(limy):
        for x in xrange(limx):
            r, g, b = pix[x,y]
    
            red_bits.append(r&1)
            green_bits.append(g&1)
            blue_bits.append(b&1)
    
            x1 = (r & 1) ^ (g & 1)
            x2 = (g & 1) ^ (b & 1)
    
            recovered_bits.append(x1)
            recovered_bits.append(x2)
    
            bits[counter % 8] = str(x1)
            bits[(counter % 8) + 1] = str(x2)
    
            counter += 2
    
            if counter % 8 == 0:
                chars.append(chr(int(''.join(bits),2)))
    
            if(x1 != 0 or x2 != 0):
                last_1 = (x,y,len(chars))
    
    recovered = ''.join(chars[:last_1[2]+1])
    
    png_header = "\x89\x50\x4e\x47\x0d\x0a\x1a\x0a"
    png_bits = []
    
    for c in png_header:
        for i in xrange(8):
            png_bits.append((ord(c) & pow(2, 7 - i)) >> 7 - i)
    
    from termcolor import colored
    
    print "Image Dimentions: (%i x %i)" % (limx, limy)
    print "Last Data: (x,y) = (%i, %i) - output length = %i" % last_1
    
    print "Length of png header bits %i" % len(png_bits)
    
    print "Hunting..."
    matched = 0
    matched_best = 0
    for i in xrange(len(red_bits)):
        if red_bits[i] ^ blue_bits[i] == png_bits[matched] and green_bits[i] ^ blue_bits[i] == png_bits[matched+1]:
            matched += 2
            if matched > matched_best:
                matched_best = matched
                print "matched %i bits starting at %i" % (matched, i - ((matched / 2) - 1))
        else:
            matched = 0
    
    print "PNG header:"
    for x in png_bits:
        print x,
    print 
    
    print "Red:"
    for x in red_bits[:len(png_bits)]:
        print colored(str(x), 'red'),
    print 
    
    print "Green:"
    for x in green_bits[:len(png_bits)]:
        print colored(str(x), 'green'),
    print 
    
    print "Blue:"
    for x in blue_bits[:len(png_bits)]:
        print colored(str(x), 'blue'),
    print 
    
    print "====== Based on XOR ======"
    
    print "PNG:"
    Toggle = True
    for x in png_bits:
        print colored(str(x), 'red') if Toggle else colored(str(x), 'blue'),
        Toggle = not Toggle
    print 
    
    print "Recovered:"
    Toggle = True
    for x in recovered_bits[:len(png_bits)]:
        print colored(str(x), 'red') if Toggle else colored(str(x), 'blue'),
        Toggle = not Toggle
    print
    print "======= Bytes ======="
    print "PNG:"
    print [bin(ord(x))[2:].zfill(8) for x in png_header]
    print "Recovered:"
    print [bin(ord(x))[2:].zfill(8) for x in recovered[:len(png_header)]]
    print "Bits by val"
    
    print "Writing output to out.png..."
    
    with open('out.png', 'wb+') as f:
        f.write(recovered)
    
    print "Done!"