On Sunday I happened to notice that Google have taken down the challenges from their 2018 CTF competition, replacing the site with a notice about the imminent arrival of the 2019 one. This prompted me to revisit a couple of the challenges that I’d made progress on, but hadn’t completed, and with a little bit of cheating I’ve managed to finish them.
Proprietary Format
Proprietary Format
Last time I’d spent quite a lot of time on this one and was convinced that I must be close to solving it. I’d come to the conclusion that this was a custom image format. The data starts with this:
47 43 54 46 58 02 00 00 90 01 00 00 03 00 00 00 |GCTFX...........|
I’d then guessed that it broke down as:
| Data | Description | Value |
|---|---|---|
| 47 43 54 46 | Identifying magic number | GCTF |
| 58 02 00 00 | Image width | 600 |
| 90 01 00 00 | Image height | 400 |
| 03 00 00 00 | Number of channels | 3 |
I’d also spotted a pattern in the rest of the hex dump that was reinforcing my belief that this was an image format, and that was also leading me to believe that it might be using a form of run-length encoding. There were columns of low values, which occasionally stopped and stepped over one column before continuing.
Looking closer I could see that the data was mostly grouped into blocks of four bytes, with each block consisting of a low value byte followed by three higher value bytes. The pattern only changed when the low value byte was 0x0f, when that happened there would be an extra low value byte and then the pattern would continue. I was thinking that the low values bytes might be encoding a run-length and that the following bytes would be the R, G and B value to repeat. Then the 0x0f could be an escape to indicate that another byte needs to be read to encode a longer run.
Unfortunately there were several things that didn’t make sense with this:
- Why would it only use half of the bits in the length byte before flagging an escape to read another byte?
- There were a few places where there were two back to back runs of the same colour, they should have been encoded in the same run.
- No matter how I played around with the encoding of the lengths I couldn’t get the right amount of data out. I was getting around half of what I needed for a 600x400x3 image.
I wasn’t getting any further with this revisit, so it was time to cheat and look for some clues, so I took a look at LC↯BC’s write-up here: https://ctftime.org/writeup/10335.
Reading that I could see that not having access to the network service (which I’d also not actually noticed) was a big handicap. But while it was a bit more of a hint than I was really after, the description of how the low value bytes in the input data represented quadrants was more than enough information to allow me to write my own decoder.
Those low value bytes that are only using the bottom four bits are indicating how to traverse a quad-tree. Each bit represents one of the four quadrants. If the bit is set then it indicates that the decoder should recurse into that quadrant, dividing it into its own four quadrants. If the bit is not set then the entire quadrant should be filled with the RGB colour that follows the byte.
That also explains why there is no RGB data after a 0x0F byte. That has all four bits set, so the decoder should recurse into all of the quadrants and not fill any of them, so no colour is needed.
Here’s my implementation of a decoder:
#!/usr/bin/python
import sys, struct
import numpy as np
def fill(colour, output, x, y, size):
for i in range(x, x + size):
for j in range(y, y + size):
output[i, j] = colour
def recurse(input, output, x, y, size):
quads = ord(input.read(1))
colour = 0
if quads != 15:
colour = (colour << 8) + ord(input.read(1))
colour = (colour << 8) + ord(input.read(1))
colour = (colour << 8) + ord(input.read(1))
if size > 1:
s2 = size/2
if quads & 1:
recurse(input, output, x + 0, y + 0, s2)
else:
fill(colour, output, x + 0, y + 0, s2)
if quads & 2:
recurse(input, output, x + s2, y + 0, s2)
else:
fill(colour, output, x + s2, y + 0, s2)
if quads & 4:
recurse(input, output, x + 0, y + s2, s2)
else:
fill(colour, output, x + 0, y + s2, s2)
if quads & 8:
recurse(input, output, x + s2, y + s2, s2)
else:
fill(colour, output, x + s2, y + s2, s2)
else:
fill(colour, output, x, y, 1);
return
with open(sys.argv[1]) as input:
with open(sys.argv[2], 'wb') as output:
magic, width, height = struct.unpack('4sII', input.read(12))
print "Magic: %s" % magic
print "Width: %s" % width
print "Height: %s" % height
size = max(width, height)
size = 1 << (size - 1).bit_length()
data = np.zeros(shape=(size, size), dtype=np.int32)
recurse(input, data, 0, 0, size)
for i in range(0, height):
for j in range(0, width):
colour = data[j, i]
output.write(chr((colour >> 0) & 0xff))
output.write(chr((colour >> 8) & 0xff))
output.write(chr((colour >> 16) & 0xff))
The decoder script writes out a raw RGB image that can then be opened in gimp to reveal the flag.
Tape
Tape
For this one we get given a data file, a tiny ARM binary and the hint “We’ve found this priceless, old magnetic tape in our archives. We dumped the contents, but the data is corrupted and we can’t read it. We only have this old tape reader tool, but source code was lost long ago. The program has only 944 bytes, so reversing it should be trivial, right?”
I hadn’t spent much time on this one the first time around. It looked interesting and the description of corrupted data on a tape was invoking memories of PAR files when downloading stuff from newsgroups. I was thinking that we’d probably have to reverse engineer and then implement an error correction algorithm. I’d not actually considered that we could run the provided binary. If I had then I’d have realised that I couldn’t be right, because why didn’t this binary already correct the data?
But, still thinking this was the case, and that I was unlikely to be able to reverse out an error correction scheme just from the corrupt data file, I started by trying to disassemble the binary. I’d recently downloaded a copy of Ghidra to play with, so I loaded it up and then spent a couple of hours constantly flicking backwards and forwards between the disassembly and an ARM reference manual. My complete lack of knowledge of ARM assembly really wasn’t helping, and I was become increasingly convinced that Ghidra wasn’t actually showing me most of the code.
So… time for another hint… This time I took a look at the write up by Galhacktic Trendsetters: https://galhacktictrendsetters.wordpress.com/2018/07/01/google-ctf-2018-tape/.
My first surprise was in the first couple of paragraphs
cat FLAGZ.DAT | qemu-arm tapereader
Oh! You can run it! If I’d realised that I’d probably have tried stepping through the live code in a debugger. Oh, well, I’ll have to remember that trick for next time.
I read enough of their write-up to discover that the data file is divided into 80 byte lines, each of which are followed by an 8 byte checksum. Each line after the first is also XOR’d with the previous line, which has the unfortunate effect of propagating the corruption from earlier lines into the same columns of all subsequent lines. I also saw them mention that their brute force attempt had failed. That seemed like a good place to stop reading.
Now I had a good idea how to proceed… I needed to find a way to use the 64-bit CRC checksums from each line to fill in the blanks from the corruption. Knowing that brute force was apparently not going to work, but not knowing why, the first thing that I wanted to do was make my own attempt at brute forcing it. Then hopefully I’d get to understand why it can’t work.
Luckily the corrupt characters are really easy to spot, they all have the high bit set, putting them outside the range of ASCII characters. This makes a brute force decoder pretty simple. A recursive function can look for a bad character and loop trying all possible replacements, whilst also recursively calling itself to find and replace further bad characters on the line. Once all bad characters land on their correct replacement then the CRC will match the expected one and we’ve got the fixed text.
Here’s the code for that basic brute force decoder:
#!/usr/bin/python
import sys, struct
polynomial = 0xC96C5795D7870F42
table = [0] * 256
def populateTable():
for i in xrange(256):
crc = i
for j in xrange(8):
if crc & 1:
crc >>= 1
crc ^= polynomial
else:
crc >>= 1
table[i] = crc
def crc64(s, crc=0):
for c in s:
crc = table[(crc & 0xff) ^ ord(c)] ^ (crc >> 8) & 0xFFFFFFFFFFFFFFFF
return crc
def fix(expectedCRC, line, offset):
index = -1
for i in range(offset, len(line)):
if ord(line[i]) < 0x20 or ord(line[i]) > 0x7f:
index = i
break
if index != -1:
offset = index
for c in range(0x20, 0x80):
newLine = line[:offset] + chr(c) + line[offset+1:]
if crc64(newLine) == expectedCRC:
return (True, newLine)
if offset + 1 < len(newLine):
success, newLine = fix(expectedCRC, newLine, offset + 1)
if success:
return (True, newLine)
return (False, line)
populateTable()
prevLine = None
with open(sys.argv[1]) as input:
while True:
line = input.read(80)
if len(line) < 80:
break
expectedCRC = struct.unpack('Q', input.read(8))[0]
if prevLine:
line = ''.join([chr(ord(c) ^ ord(prevLine[i])) for i,c in enumerate(line)])
calculatedCRC = crc64(line)
if calculatedCRC != expectedCRC:
print 'X',line, hex(expectedCRC), hex(calculatedCRC)
success, line = fix(expectedCRC, line, 0)
calculatedCRC = crc64(line)
print 'F',line, hex(expectedCRC), hex(calculatedCRC)
else:
print 'O',line, hex(expectedCRC), hex(calculatedCRC)
prevLine = line
This starts off doing a reasonable job, at first there’s one error per line and it flies through these. Then it changes to two errors per line and it slows down a little. Then three errors per line and it slows down a lot, but continues to work… until after about five or six minutes when it runs into this line:
: Anyway, this was interesting, but if you want more, go read goo.gl����������
OK, now I know why brute forcing isn’t going to work… one error has a worst case of 96 guesses (using characters 0x20 to 0x7f), two errors… 9,216 guesses, three… 884,736, ten… 6×1019!
Forcing it to skip that line then reveals the line that we need:
: You probably just want the flag. So here it is: CTF{dZXi����ߘ��јP����������
That’s not good, although it’s not as bad as it first looks. It’s just another 10 corrupt characters, the other 10 are just propagating down from the previous line. So to get the flag I needed to find a way to decode two lines, each with 10 unknown characters.
I couldn’t see any way other than brute force that would allow me to work through the string from front to back, and be able to fix the corrupt characters. The only information available to use was the checksum, and that had no relationship to the first bad characters, it was only valid at the end of the string.
As the one place that the checksum was valid was at the end, I started to wonder whether I could work backwards. Could a CRC be reversed?
While researching this idea, I ran into this blog post entitled Reversing CRC. That post is mostly talking about how to alter data to make it match an existing CRC, but there was one paragraph that jumped out at me:
“Crc basicly takes the hash, moves it 1 byte to the right (dropping one byte) and xor-ring it with the table entry. The nice thing about normal CRC is that the first byte of a table entry is unique for that entry.”
Calculating a CRC uses a 256 entry lookup table, with the core update function looking like this:
crc = table[(crc & 0xff) ^ c] ^ (crc >> 8)
To update a CRC for another byte of input data, the bottom byte of the current CRC is XOR’d with the new character, and this value is used to select a table entry to use. That table value is then XOR’d with the existing CRC shifted down 8 bits. This means that the top byte of the new CRC comes entirely from the table entry. Not only does it come entirely from the table entry, but each table entry has a unique top byte, so it uniquely identifies the table entry that was used.
The first thing that I could do with this was implement a reverse CRC function, that given an existing CRC and the last input character, would give me the previous CRC from before the character was added. This would then allow me to rewind the CRC that was given for each line back to one of the corrupt characters. By doing that I would have a CRC that was related to the corrupt character rather than a CRC that was only relevant at the end of the whole string.
The CRC rewinding function is surprisingly simple. Given a string, CRC and number of characters to remove, it returns the shortened string and new CRC:
def rewindCRC(crc, s, count):
for step in range(count):
for i, x in enumerate(table):
if x >> 56 == crc >> 56:
upperBytes = ((crc ^ x) & 0xFFFFFFFFFFFFFFL)
bottomByte = ord(s[-1]) ^ i
crc = (upperBytes << 8) | bottomByte
break
s = s[:-1]
return (crc, s)
Now I had the CRC that was generated by the input of the last corrupt character, so there was now at least some relationship between the CRC and the unknown character, but could I do anything with that?
I eventually noticed that you don’t actually need the characters to identify the successive table entries that were used. When rewinding a CRC I was using the character to generate the bottom byte of the previous CRC, but it’s the top byte that’s used to identify the next table entry. This meant that if I skipped generating the bottom byte, I could identify 8 table entries before the non-populated bytes propagated to the top byte, stopping me from continuing.
So, now I could rewind the known CRC until it hit the last corrupt character in the string, and then I could identify the table entries that were used when updating the CRC for the previous eight characters, but I still couldn’t identify what those characters were.
Then I spotted the last piece of the puzzle. If I could work out which table entries were used all the way back past the corrupt characters to a known good character, then I could work forward… Given the CRC of the known good prefix string up to the first corrupt character, and given the index of the table entry that was used, there is only one possible input character!
c = (prefixCRC & 0xff) ^ table[tableIndex]
With this I could calculate eight consecutive unknown characters, provided there was no other corruption in the string, which meant that I could calculate the correct CRC for the last character before the corruption, and the correct CRC for the first character after the corruption.
This won’t work if the corrupt characters aren’t back to back in the string, but luckily the corruption in the problematic strings was consecutive. There was just the small issue of there being ten unknowns, not eight. But the solution to that was easy, just brute force the first two characters, which takes less than 10,000 guesses, then calculate the remaining eight.
Once I’d seen how this could work, it was just a case of writing the new decoder script… and ironing out all the bugs… but once that was done, it worked! It decoded the whole file in under 5 seconds.
Actually, that’s not quite true. It turns out that brute forcing the first two characters can lead to multiple solutions that arrive at the correct end-of-line CRC. Luckily after only a few attempts of getting the script to skip the bad solutions, it did find the correct answer.
Here’s the full script:
#!/usr/bin/python
import sys, struct
polynomial = 0xC96C5795D7870F42
table = [0] * 256
def populateTable():
for i in xrange(256):
crc = i
for j in xrange(8):
if crc & 1:
crc >>= 1
crc ^= polynomial
else:
crc >>= 1
table[i] = crc
def crc64(s, crc=0):
for c in s:
crc = table[(crc & 0xff) ^ ord(c)] ^ (crc >> 8) & 0xFFFFFFFFFFFFFFFF
return crc
def findLastBadChar(s):
for i, c in enumerate(reversed(s)):
if ord(c) < 0x20 or ord(c) > 0x7f:
return len(s) - i - 1
return -1
def findFirstBadChar(s, startOffset):
for i in range(startOffset, len(s)):
if ord(s[i]) < 0x20 or ord(s[i]) > 0x7f:
return i
return -1
def rewindCRC(crc, s, count):
for step in range(count):
for i, x in enumerate(table):
if x >> 56 == crc >> 56:
upperBytes = ((crc ^ x) & 0xFFFFFFFFFFFFFFL)
bottomByte = ord(s[-1]) ^ i
crc = (upperBytes << 8) | bottomByte
break
s = s[:-1]
return (crc, s)
def findConstants(crc):
constants = []
for count in range(8):
for i, x in enumerate(table):
if x >> 56 == crc >> 56:
constants.append(i)
crc = ((crc ^ x) & 0xFFFFFFFFFFFFFFL) << 8
break
return constants[::-1]
def fix(expectedCRC, s, startOffset, constants, firstConstantOffset):
while True:
firstBadCharOffset = findFirstBadChar(s, startOffset)
if firstBadCharOffset == -1:
break
constantIndex = firstBadCharOffset - firstConstantOffset
if constantIndex >= 0:
prefixCRC = crc64(s[:firstBadCharOffset])
c = (prefixCRC & 0xff) ^ constants[constantIndex]
if c < 0x20 or c > 0x7f:
return (False, s)
s = s[:firstBadCharOffset] + chr(c) + s[firstBadCharOffset + 1:]
if s.startswith(': Anyway, this was interesting, but if you want more, go read goo.gl'):
if not s.startswith(': Anyway, this was interesting, but if you want more, go read goo.gl/'):
return (False, s)
elif s.startswith(': You probably just want the flag. So here it is: CTF{dZXi!'):
return (False, s)
elif s.startswith(': You probably just want the flag. So here it is: CTF{dZXi6'):
return (False, s)
elif s.startswith(': You probably just want the flag. So here it is: CTF{dZXi:'):
return (False, s)
elif s.startswith(': You probably just want the flag. So here it is: CTF{dZXi?'):
return (False, s)
elif s.startswith(': You probably just want the flag. So here it is: CTF{dZXi@'):
return (False, s)
if crc64(s) == expectedCRC:
return (True, s)
else:
for c in range(0x20, 0x80):
test = s[:firstBadCharOffset] + chr(c) + s[firstBadCharOffset + 1:]
if crc64(test) == expectedCRC:
return (True, test)
if firstBadCharOffset + 1 < len(test):
success, test = fix(expectedCRC, test, firstBadCharOffset + 1, constants, firstConstantOffset)
if success:
return (True, test)
return (False, s)
return (False, s)
def fixLine(expectedCRC, line):
lastBadCharOffset = findLastBadChar(line)
truncatedCRC, truncatedStr = rewindCRC(expectedCRC, line, len(line) - lastBadCharOffset - 1)
constants = findConstants(truncatedCRC)
success, fixed = fix(truncatedCRC, truncatedStr, 0, constants, lastBadCharOffset - (len(constants) - 1))
fixed += line[lastBadCharOffset + 1:]
return fixed
populateTable()
prevLine = None
with open(sys.argv[1]) as input:
while True:
line = input.read(80)
if len(line) < 80:
break
expectedCRC = struct.unpack('Q', input.read(8))[0]
if prevLine:
line = ''.join([chr(ord(c) ^ ord(prevLine[i])) for i,c in enumerate(line)])
calculatedCRC = crc64(line)
if calculatedCRC != expectedCRC:
line = fixLine(expectedCRC, line)
print line
prevLine = line
Recent Comments