# 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}`