Gric

The challenge is to predict 100 checksums in a row. The algorithm for computing a checksum is:

constants = [0] * LEN_GRIC
sbox = list('ABCDEFGHJKLMRTXYZ')
def setup():
    global constants, sbox
    constants = [random.randint(0, 17) for x in range(LEN_GRIC)]
    random.shuffle(sbox)

def get_checksum(n): return sbox[sum(map(lambda x: int(x[0]) * int(x[1]), zip(n, constants))) % len(sbox)]

This algorithm is a rather simple linear checksum. It multiplies each digit by a random coefficient, then the final result is taken mod \(17\) and a random sbox is looked up to figure which letter corresponds to the checksum.

The difficulty here lies in the fact we can only get 25 checksums before the server refuses to give anymore to us.

Solution

We can assign each letter a number from \(0\) to \(16\) and each constant as a variable. Notice that for each checksum request, for instance \(G0123456789A\), we get an equation of the form \(0c_0+1c_1+\dots+9c_9=A\), which are linear equations that have no constant term. This tells us that we are interestd in finding the kernel of some matrix. Furthermore since everything is done modulo \(17\), our matrix elements are in \(\mb F_{17}\).

We can represent each equation as a row of a matrix \(M\), where the first \(10\) columns are our input digits and the rest of the columns are \(0\) except the column that is the checksum letter, where we assign \(-1=16\pmod{17}\). This gives us a \(25\) by \(27\) matrix that we are interested in finding the right kernel. This can easily be done in sage:

sage: M.right_kernel()
Vector space of degree 27 and dimension 4 over Finite Field of size 17
Basis matrix:
[ 1 12 15 10  7  5 10  1  0 16  0  3  0  7 10  5  0  2 15 16  6 11  0  4  9  8 12]
[ 0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0]

Here we immediately see the unknown coefficients have a unique solution \(c_i\), but some of the letters are interchangable with each other (the last 3 vectors). Importantly, we can use the fact that there is a bijective map between the letters and numbers in \(\mb F_{17}\), this yields \(3!=6\) possible solutions in this case. As there are very little permutations possible, we can simply try several timse and we will eventually get the flag.

Note that we can arbitrarily multiply our solutions by any number. However since the constants and letters are changed accordingly, the output will remain the same.

Wow you did it. Congratulations! Here flag!
CTFSG{NRIC_m3meS_F0R_GRIC_7eENs}

The solution script can be found at solve.py and the script to compute the kernel can be found at ker.sage

GRIC

Checksum

Solution