# 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!

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 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.

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 `0`s 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}`!