Google CTF 2017 Quals: Introspective CRC
Posted 2017/06/21. Last updated 2017/06/21.
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
len(data) == 82
Clearly, the server expects 82 characters. Sending the output of
python -c 'print "A"*82' to the server gives us a different response:
set(data) <= set("01")
OK, so let's send 82 zeros instead:
crc_82_darc(data) == int(data, 2)
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 F2[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.
d=0x308c0111011401440411. Moreover, character "
0" is expressed as
00110000 in binary, while "
00110001. Let the desired value be
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
Rx=∑rx,jXj denote the (polynomial) remainder in the division of
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:
1111110111111011001110001110101000001010101001100111010000100000010011101011100010. Connecting to the server and sending either of these two solutions finally reveals the flag: