Google CTF 2017 Quals: Introspective CRC

Posted 2017/06/21. Last updated 2017/06/21.

Introduction

This past weekend, I participated in Google's 2017 CTF Qualifiers as the captain of the Oxford team, Ox002147. This was quite likely the hardest CTF we've done, but we still did well, placing 59/1977. I wanted to share the solutions to some of the problems I solved, starting with a crypto one, called "Introspective CRC". The description merely says:

We saw https://shells.aachen.ccc.de/~spq/md5.gif and were inspired. Challenge running at selfhash.ctfcompetition.com:1337

The link is to an animated GIF that shows its own MD5 hash, but the challenge does not have any source code. Time to explore!

Understanding the Task

I connected to the server using nc selfhash.ctfcompetition.com 1337, and gave it some data (seen in red):

Give me some data: AAA Check failed. Expected: len(data) == 82 Was: 3

Clearly, the server expects 82 characters. Sending the output of python -c 'print "A"*82' to the server gives us a different response:

Expected: set(data) <= set("01") Was: set(['A'])

OK, so let's send 82 zeros instead:

Expected: crc_82_darc(data) == int(data, 2) Was: 1021102219365466010738322L 0

Right, so the CRC-82/DARC of what we send (interpreted as ASCII) needs to match what we send interpreted as a binary integer.

Exporing the CRC

A Cyclic Redundancy Check (CRC) is, broadly speaking, the remainder of a polynomial division, typically over the polynomial ring F₂[X], so that coefficients are interpreted mod 2. In other words, the data to be checked is expressed as a binary number, whose bits are then interpreted as the coefficients of the polynomial to be divided. For example, the binary number 0b1011 would be interpreted as the polynomial X3 + X1 + 1. The divisor used is typically expressed as a number d, and a width W, with the actual polynomial being D=(1 << W) | d. Note: there are some intricacies with whether inputs and outputs need to be modified by XORing or swapping bits and bytes, but they are tangential to this high level discussion, and are only reflected in the code linked below.

For CRC-82/DARC, W=82 and d=0x308c0111011401440411. Moreover, character "0" is expressed as 00110000 in binary, while "1" as 00110001. Let the desired value be a=aW-1aW-2...a0, where ai∈{0,1}. Let bi denote the exponent to which the LSB of ai corresponds, which is the only difference in the two characters. With Pi=Xbi, the polynomial corresponding to the desired value Pa is related to the polynomial corresponding to the all 0s string by the following equation: Pa=P0 + ∑aiPi, where the equation holds in F2[X].

Let Rx=∑rx,jXj denote the (polynomial) remainder in the division of Px by D. Then the same equation as above holds: Ra=R0 + ∑aiRi. This is a polynomial equality, and Ra=∑aiXi by assumption, so for 0 ≤ i ≤ W, the following holds:

ai=r0,i + ∑ajrj,i, where the sum is over j=0,...,W-1. This equation on the coefficients is now an equation that holds in F2, i.e., modulo 2. We just now simply need to solve this system of equations!

Putting It All Together

In CTFs, solving a problem quickly is more important than the quality of code. For that reason, I decided to take a mixed approach in my coding. At first, I calculated the remainders in Python, using the pwntools library that the problem was likely also using, and which contains an implementation of crc_82_darc that I could dig into and understand. As I didn't readily find a Python library that can solve systems of linear equations in a field other than the real numbers, I decided to solve the equations in Mathematica, and then verify the solution in Python. My code is on my Github, and is sufficiently well-commented. The polynomials are setup by replicating the pwntools code, and the code ensures that the bit ordering is respected.

Solving the problem in Mathematica reveals that the equations are under-specified, so there are, in fact, two possible solutions: 1010010010111000110111101011101001101011011000010000100001011100101001001100000000 and 1111110111111011001110001110101000001010101001100111010000100000010011101011100010. Connecting to the server and sending either of these two solutions finally reveals the flag: CTF{i-hope-you-like-linear-algebra}!