# GRIC

This is the second challenge from the Crypto section of CTF SG 2021. The challenge needs us to find out the checksum letter when given a 10 digit number.

## Statement

NRIC goes Global!

nc chals.ctf.sg 10101

The server code is provided

## Observation

The basic idea on how the checksum works is that it takes every digit[i], multiply it with constants[i] and sum it together modulo 17 (length of sbox).

Let this final answer be x

Then the checksum letter will be sbox[x].

More formally,

$\texttt{sbox}[( \sum_{i=0}^{9} \texttt{digit[i]} \cdot \texttt{constants[i]})\ \underline{mod} \ 17]$

On every connection to the server, it will random shuffle the sbox and generate random constants.

LEN_GRIC = 10  # For whoever

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)


The server also provided us the ability to query the checksum of a number for 25 times.

To get the flag, we need to answer 100 checksum question randomly generated by the server.

## Solution

First, notice that if we query G1000000000, we can get the value of sbox[constants[0]].

If the value of constants[0] is 1, Then we can restore sbox[1..9] by just querying

sbox[1] = checkSum(G1000000000)
sbox[2] = checkSum(G2000000000)
sbox[3] = checkSum(G3000000000)
...
sbox[9] = checkSum(G9000000000)


Now we have a problem because we can’t retrive sbox[10..16].

But what if the value of constants[1] is also 1?

Then now we got constants[0] = 1 and constants[1] = 1

We can then retrive the content of sbox with just 16 queries.

sbox[1] = checkSum(G1000000000)
sbox[2] = checkSum(G2000000000)
sbox[3] = checkSum(G3000000000)
...
sbox[9] = checkSum(G9000000000)
sbox[10] = checkSum(G9100000000)
sbox[11] = checkSum(G9200000000)
...
sbox[16] = checkSum(G9700000000)


The only one character that is left out will then be sbox[0]

Okay awesome, now we can retrive sbox if constants[0] = 1 and constants[1] = 1.

We can generalize this to constants[i] = 1 and constants[j] = 1. Where i and j not necessarily has to be 0 and 1.

However, we still have no idea what constants[2..16] is.

Therefore we need to have 9 query.

c0 = checkSum(G1000000000) # This has been queried in the previous part
c1 = checkSum(G0100000000)
c2 = checkSum(G0010000000)
c3 = checkSum(G0001000000)
...
c9 = checkSum(G0000000001)


If we have already known the sbox, we can easily retrive back the constants.

constants[0] = sbox.index(c0)
constants[1] = sbox.index(c1)
constants[2] = sbox.index(c2)
constants[3] = sbox.index(c3)
...
constants[9] = sbox.index(c9)


Note that constants[i] = constants[j] if and only if $$c_{i} = c_{j}$$

So the main idea on how to solve this solution is we first query with 10 queries,

c0 = checkSum(G1000000000)
c1 = checkSum(G0100000000)
c2 = checkSum(G0010000000)
c3 = checkSum(G0001000000)
...
c9 = checkSum(G0000000001)


And be hopeful that there will be a pair (i,j) where i != j

such that $$c_{i} = c_{j}$$ , constants[i] = 1 and constants[j] = 1

We can retrive back the sbox and constants with the above method with another 15 queries.

If it fails, we try again and be more hopeful.

It will pass the test in slightly less than 1/17 chance.

Here’s the python code for the complete solution.

from pwn import *

ok = False

sbox = list('ABCDEFGHJKLMRTXYZ')

while (not ok) :
s = 'A'
r = remote('chals.ctf.sg', 10101)
arr = []

for i in range(0,10):
r.recvuntil('\n\n')
r.sendline(b'G')
r.recvline()
r.recvline()
k = 1 << i
gric = 'G' + format(k, '010b')
r.sendline(gric.encode())
c = r.recvline().split()[-1][-1]
if (c in arr):
s = c
ok = True
arr.append(c)

if (not ok):
continue

arr.reverse()

ss = [0, chr(s)]

i1 = arr.index(s)
i2 = i1 + 1 + arr[i1+1:].index(s)

for i in range(2,17):
r.recvuntil('\n\n')
r.sendline(b'G')
r.recvline()
r.recvline()
gric = list('G' + '0'*10)
gric[i1+1] = str(min(i,9))
gric[i2+1] = str(max(i-9,0))
r.sendline("".join(gric).encode())
c = chr(r.recvline().split()[-1][-1])
ss.append(c)

for i in sbox:
if (i not in ss):
ss[0] = i
break

print(ss)

if (ss.count(ss[1]) > 1):
ok = False
continue

constants = [ss.index(chr(i)) for i in arr]

print(constants)

r.recvuntil('\n\n')
r.sendline(b'C')
r.recvline()
for i in range(100):
gric = r.recvline().split()[-1]
count = 0
for j in range(1,11):
count += int(gric[j]) * constants[j-1]
count %= 17
r.sendline(ss[count])
res = r.recvline()
print(res)
if (res.split()[0] == b'Nope,'):
ok = False
r.close()
break

print(r.recvline())
print(r.recvline())


flag : CTFSG{NRIC_m3meS_F0R_GRIC_7eENs}

Updated: