X-MAS CTF 2018 - X^n-MAS Writeup

crypto
,

For this challenge we’re only given a netcat connection and the following description:

Crypto mecha gnomes love random polynomial functions, can you guess what’s hidden in there?

Solution

Connecting to netcat we’re given a modulus and the possibility to evaluate a polynomial at 50 points. The first thing that comes in mind is interpolation: we can retrieve the whole polynomial if the degree is at most 49 (spoiler: it is). In order to do this we use Lagrange’s interpolation method, that basically is: given , then the interpolation polynomial in Lagrange’s form is

Basically all works also with polynomials in the ring. Fortunately, we found out that one of the organizers (Gabies) has, on his github page, a class to work with polynomials in , so using his code we can do the following script to obtain the flag:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
from pwn import *
from Crypto.Util.number import inverse

xy = []

class Polynomial(list):

    def __init__(self,coeffs):
        self.coeffs = coeffs

    def evaluate(self,x,mod):
        val = 0
        for i in range(len(self.coeffs)):
            val = (val + x**i * self.coeffs[i]) % mod
        return val

    def raise_degree(self,x):
        coeffs=[]

        for i in range(x):
            coeffs.append(0)
        for i in range(len(self.coeffs)):
            coeffs.append(self.coeffs[i])
        self.coeffs=coeffs

    def add_to_degree(self,x,y):
        while(len(self.coeffs)<=x):
            self.coeffs.append(0)
        self.coeffs[x]=(self.coeffs[x]+y)%MOD

    def add_poly(self,x):
        while(len(self.coeffs)<len(x.coeffs)):
            self.coeffs.append(0)

        for i in range(len(x.coeffs)):
            self.coeffs[i]=(self.coeffs[i]+x.coeffs[i])%MOD

    def multiply(self,x):
        for i in range(len(self.coeffs)):
            self.coeffs[i]=(self.coeffs[i] * x)%MOD

    def multiply_with_poly(self,p):
        coeffs=Polynomial([])

        for i in range(len(self.coeffs)):
            q=Polynomial(p.coeffs)
            q.raise_degree(i)
            q.multiply(self.coeffs[i])
            coeffs.add_poly(q)
        self.coeffs=coeffs.coeffs

    def calculate_derivative(self):
        p=Polynomial([])
        for i in range(1,len(self.coeffs)):
            p.coeffs.append((self.coeffs[i]*i)%MOD)
        return p

    def compose(self,p):
        P=Polynomial([])
        q=Polynomial([1])
        for i in range(len(self.coeffs)):
            q2=Polynomial(q.coeffs)
            q2.multiply(self.coeffs[i])
            P.add_poly(q2)
            q.multiply_with_poly(p)
        self.coeffs=P.coeffs

    def print_poly(self):
        return self.coeffs

#Lagrange Interpolation part
def Lagrange_Basis_Polynomial(xlist,index):
    l=Polynomial([1])
    for i in range(len(xlist)):
        if(i==index):
            continue
        p=Polynomial([(MOD-xlist[i])%MOD,1])
        p.multiply(inverse((MOD+xlist[index]-xlist[i])%MOD,MOD))
        l.multiply_with_poly(p)
    return l

def Lagrange_Polynomial(xylist):
    xlist=[]
    ylist=[]
    L=Polynomial([])
    for a in xylist:
        xlist.append(a[0])
        ylist.append(a[1])
    for i in range(len(ylist)):
        l=Lagrange_Basis_Polynomial(xlist,i)
        l.multiply(ylist[i])
        L.add_poly(l)
    return L

r = remote("199.247.6.180", 16000)
r.recvuntil("modulo is ")
n = int(r.recvline().decode().split(".")[0])
print(n)
MOD = n
for i in range(50):
    r.recvuntil(":")
    r.sendline(str(i))
    t = int(r.recvline().decode().split(":")[1].rstrip("\n").lstrip(" "))
    print((i,t))
    xy.append((i,t))
print(xy)
coeffs = Lagrange_Polynomial(xy).print_poly()
print(coeffs)
c = ""
for i in range(len(coeffs)):
    print(chr(coeffs[49-i]), end="")