This past weekend, I played in PlaidCTF 2015 with Men in Black Hats. We placed a respectable 17th in the end which, despite being far from the 1st place we'd hoped for, still didn't prevent me from having a ton of fun. I was involved in solving a few different challenges, but the one I'd like to take the time to write up is actually one I didn't solve for us: "PNG Uncorrupt".

For this challenge, we're given a corrupted PNG file and told that we need to view it to receive the flag. I thought this was a really interesting programming problem, so I took a stab at it myself after the competition ended. file can't even recognize that it's a PNG, which isn't good for us:

$ file corrupt_735acee15fa4f3be8ecd0c6bcf294fd4.png
corrupt_735acee15fa4f3be8ecd0c6bcf294fd4.png: data

Using pngcheck, we can see that the file may have been corrupted by an incorrect translation of 0x0D 0x0A pairs (the "CRLF" line endings that Windows/DOS uses for newlines) to simply 0x0A (the "LF" line endings that *nix systems tend to use instead):

$ pngcheck -v corrupt_735acee15fa4f3be8ecd0c6bcf294fd4.png
File: corrupt_735acee15fa4f3be8ecd0c6bcf294fd4.png (1188435 bytes)
  File is CORRUPTED.  It seems to have suffered DOS->Unix conversion.
ERRORS DETECTED in corrupt_735acee15fa4f3be8ecd0c6bcf294fd4.png

It turns out that this problem is common enough that the authors of the PNG format designed the 5th and 6th bytes of the PNG header to detect it. The other nice thing is that each chunk contains a 4-byte CRC at the end. Using the CRC values and the overall format of a PNG, we can determine which chunks are missing data. We also have an idea of which data is missing because we know how the file was likely transformed.

I broke my solution down into 5 steps:

1. Read the corrupted PNG into memory.
2. Slice the PNG into individual chunks.
3. Determine which chunks are invalid due to CRC and/or length errors.
4. Fix each invalid chunk with a combinatoric, brute-force approach.
5. Re-assemble the uncorrupted PNG and write it to disk.

I then implemented my solution in ruby:

#!/usr/bin/env ruby

require "zlib"

abort "Usage: #{__FILE__} <input_file> <output_file>" if ARGV.size < 1

File.open(ARGV.shift, "rb") do |input|
    File.open(ARGV.shift, "wb") do |output|
        # read file into memory
        file = input.read()
        puts "[+] Read file of size #{file.length}"

        # correct header if necessary
        if file[4] != "\r"
            file.insert(4, "\r")
        end
        output.write(file[0..7])

        # find all chunks via text search of type (finding them via size may not work due to corrruption)
        offsets = []
        ["IHDR", "PLTE", "IDAT", "IEND", "sBIT", "pHYs", "tEXt"].each do |type|
            file.scan(type) do |match|
                offsets << (Regexp.last_match.offset(0)[0] - 4)
            end
        end
        offsets.sort!
        offsets << file.length

        # attempt to fix all broken chunks
        i = 0
        while i < (offsets.length - 1) do
            # get the chunk out of the file
            chunk = file[offsets[i]..(offsets[i+1]-1)]
            size = chunk[0..3].unpack("L>")[0]  # first 4 bytes are chunk's size
            type = chunk[4..7]  # next 4 bytes are chunk's type
            crc = chunk[-4..-1].unpack("L>")[0]  # last 4 bytes are chunk's CRC

            # only process incorrect chunks
            if Zlib.crc32(chunk[4..-5]) == crc  # CRC only checks type + data
                output.write(chunk)
                i += 1
            else
                # ensure we are actually missing bytes in the chunk
                missing = size - (chunk.length - 12)
                if missing == 0
                    puts "[!] Cannot fix broken #{chunk[4..7]} chunk @ 0x#{offsets[i].to_s(16)}: No missing bytes!"
                    output.write(chunk)
                    i += 1
                    next
                elsif missing < 0
                    puts "[!] Cannot fix broken #{chunk[4..7]} chunk @ 0x#{offsets[i].to_s(16)}: Incorrect size!"
                    output.write(chunk)
                    i += 1
                    next
                else
                    puts "[*] #{chunk[4..7]} @ 0x#{offsets[i].to_s(16)} is missing #{missing} bytes"
                end

                # check all combinations of added bytes to see if we can fix the chunk
                linefeeds = []
                chunk.scan("\n") do |lf|
                    linefeeds << Regexp.last_match.offset(0)[0]
                end
                possibilities = linefeeds.combination(missing)
                if possibilities.count <= 0
                    puts "[!] Cannot fix broken #{chunk [4..7]} chunk @ 0x#{offsets[i].to_s(16)}: No valid solutions!"
                    output.write(chunk)
                    i += 1
                    next
                else
                    puts "[*] Trying all #{possibilities.count} possible ways to make CRC 0x#{crc.to_s(16)} match..."
                end

                # try and fix the chunk if it's possible
                success = false
                possibilities.each do |combo|
                    new = chunk.dup
                    offset = 0
                    combo.each do |i|
                        new.insert(i + offset, "\r")
                        offset += 1
                    end
                    if Zlib.crc32(new[4..-5]) == crc
                        puts "[+] Fixed broken #{chunk[4..7]} chunk @ 0x#{offsets[i].to_s(16)}"
                        output.write(new)
                        success = true
                        break
                    end
                end
                if not success
                    puts "[!] Cannot fix broken #{chunk [4..7]} chunk @ 0x#{offsets[i].to_s(16)}: No valid solutions!"
                    output.write(chunk)
                end
                i += 1
            end
        end
    end
end

When you run the script, you get the following output:

As you can see, it's a screenshot from StarCraft II. The flag is in the chat box: flag{have_a_wonderful_starcrafts}.

I really liked this challenge because it represented a problem that one could plausibly need to solve outside of a CTF (bad FTP transfers will sometimes cause a transformation like this, for example). Often, CTF challenge writers come up with very "unrealistic" problems (see: most pwnables). I'm guilty of this myself. Challenges like this that break the mold by being both accessible and "realistic" are awesome and I encourage others to use this as an example of great challenge design.