Crypto mecha gnomes love random polynomial functions, can you guess what’s hidden in there? Server: nc 199.247.6.180 16000

When connected to the server it reply with a welcome message:

Hello to the most amazing Christmas event. The X^n-Mas! You can send at most 50 requests to the server. The modulo is 1705110751. Good luck!

Then we can ask to the server to compute for some x the value f(x), for example:

Enter a integer:0 The output is: 125

Enter a integer:1 The output is: 3458

Enter a integer:2 The output is: 26558034

All the numbers written are modulo 1705110751 and the inserted integer should be in the range [0, 1705110750].

Fortunately we see that if reconnect to the server all the values, including the modulo, remain the same, so the limit of 50 requests is only fictitious, as we can reopen the connection and ask the value for more x.

Now let’s start to do some math!

The random polynomial function is in the form:

f(x) = c_0*x^0 + c_1*x^1 + c_2*x^2 + ... + c_d*x^d (mod 1705110751)

For some degree d and we want to retrieve all the values of c_i.

Now we have that :

f(x) = c_0

f(1) = c_0 + c_1 + c_2 + ... + c_d

f(2) = c_0 + 2^1*c_1 + 2^2*c_2 + ... + 2^d*c_d

(Note that c_0 is equal to 125 the ASCII-code of }, so we are in the right path!)

We can create the matrix d X d called M = [M_1, M_2, M_3, ..., M_d] where:

M_i = [i^0, i^1, i^2, i^3, ..., i^d]

and create the vector b = [f(1), f(2), f(3), ..., f(d)] with the asked values to the server.

To retrieve all the coefficients we have to solve the system M * c = b, so it’s enough to invert M and multiply it by b (c = M^-1 * b).

Using the sagemath library for python we found that the coefficients are:

(125, 115, 97, 109, 116, 115, 105, 114, 104, 67, 95, 121, 114, 114, 51, 109, 95, 52, 95, 117, 111, 121, 95, 104, 115, 49, 119, 95, 51, 87, 123, 83, 65, 77, 45, 88, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

The function has degree 36, and after converting all the coefficients to their ASCII values we finally recover the flag!

The flag is X-MAS{W3_w1sh_you_4_m3rry_Christmas}

Python code:

#!/bin/env python2.7

from pwn import *
from sage.all import *
import gmpy

r = None
MAX_QUERY = 50
qc = 0

def query(num):
  global qc
  global r
  if qc % MAX_QUERY == 0:
    r = remote("199.247.6.180", 16000)
    l1 = r.recvline()
    l2 = r.recvline()
    l3 = r.recvline()
  qc += 1
  r.recvuntil("Enter a integer:")
  r.sendline(str(num))
  r.recvuntil("he output is: ")
  return int(r.recvline().strip())

modulo = 1705110751
lun = 50
M = []


# Create the matrix M
for i in range(1, lun+1):
  p = [pow(i, x, modulo) for x in range(0, lun)]
  p.append(query(i))
  M.append(p)

# Separate M' = [ M | b ]
n1 = len(M[0])-1
M = M[0:n1]
b = [t[n1] for t in M]
M = [t[0:n1] for t in M]

# Invert the matrix M
inv = Matrix(IntegerModRing(modulo), M).inverse()

# Solve the linear system
sol = inv*vector(b)

# Convert coefficient to ascii
sol = "".join([chr(o) for o in sol][::-1])

print(sol)