<- CORCTF

eyes

7 minutes to read

We are given the source code in SageMath that was used to encrypt the flag:

from Crypto.Util.number import bytes_to_long, getPrime

# my NEW and IMPROVED secret sharing scheme!! (now with multivariate quadratics)

with open('flag.txt', 'rb') as f:
    flag = f.read()

s = bytes_to_long(flag)
p = getPrime(len(bin(s)))
print(p)
F = GF(p)
N = 1024

conv = lambda n: matrix(F, N, 1, [int(i) for i in list(bin(n)[2:][::-1].ljust(N, '0'))])  

A = random_matrix(F, N, N)

for i in range(0, N):
    for j in range(0, i):
        A[i, j] = 0
B = random_matrix(F, N, 1)
C = matrix(F, [F(s)])

fn = lambda x: (x.T * A * x + B.T * x + C)[0][0]

L = []
for i in range(7):
    L.append(fn(conv(i + 1)))

print(L)

We also have the output of the script:

1873089703968291141600166892623234932796169766648225659075834963115683566265697596115468506218441065194050127470898727249982614285036691594726454694776985338487833409983284911305295748861807972501521427415609
[676465814304447223312460173335785175339355609820794166139539526721603814168727462048669021831468838980965201045011875121145342768742089543742283566458551844396184709048082643767027680757582782665648386615861, 1472349801957960100239689272370938102886275962984822725248081998254467608384820156734807260120564701715826694945455282899948399224421878450502219353392390325275413701941852603483746312758400819570786735148132, 202899433056324646894243296394578497549806047448163960638380135868871336000334692955799247243847240605199996942959637958157086977051654225700427599193002536157848015527462060033852150223217790081847181896018, 1065982806799890615990995824412253076607488063240855100580513221962298598002468338823225586171107539104635808108356492123167315175110515086192932230998426512947581115358738651206273178867911944034690138825583, 1676559204037482856674710667663849447914859348633288513196735253002541076530170853584406282605482862202276451646974549657672382936948091649764874334064431407644457518190694888175499630744741620199798070517691, 13296702617103868305327606065418801283865859601297413732594674163308176836719888973529318346255955107009306239107173490429718438658382402463122134690438425351000654335078321056270428073071958155536800755626, 1049859675181292817835885218912868452922769382959555558223657616187915018968273717037070599055754118224873924325840103339766227919051395742409319557746066672267640510787473574362058147262440814677327567134194]

Source code analysis

The server a sharing secret scheme (SSS) using matrices over a finite field of order $p$ (a known prime number):

s = bytes_to_long(flag)
p = getPrime(len(bin(s)))  
print(p)
F = GF(p)
N = 1024

First of all, the server creates a random $1024 \times 1024$ matrix $A$ and sets the entries below the main diagonal to $0$:

A = random_matrix(F, N, N)  

for i in range(0, N):
    for j in range(0, i):
        A[i, j] = 0

Then, the server creates a random column vector $B$ of $1024$ entries and $C$ is the flag in decimal format:

B = random_matrix(F, N, 1)  
C = matrix(F, [F(s)])

Finally, the server does some computations and prints out the result:

L = []
for i in range(7):
    L.append(fn(conv(i + 1)))  

print(L)

The function conv represents an integer as a list of bits in reverse order:

conv = lambda n: matrix(F, N, 1, [int(i) for i in list(bin(n)[2:][::-1].ljust(N, '0'))])

So, conv(1) = [1, 0, ..., 0], conv(2) = [0, 1, 0, ..., 0], conv(3) = [1, 1, 0, ..., 0] and so on.

And fn contains a matrix equation:

fn = lambda x: (x.T * A * x + B.T * x + C)[0][0]

In mathematical terms, we can express the above function fn as:

$$ x^T A x + B^T x + C $$

In summary, we are given a total of $7$ results, where we know the $x$ vector in each computation.

Solution

Since the $x$ vector is the output of conv(i + 1), we know that the vector is composed of three bits at the beginning and the rest of entries are $0$. As a result, when computing $x^T A x$, only the top left $3 \times 3$ submatrix matters. The same happens with $B^T x$. So, from now on, $A$ is a $3 \times 3$ triangular matrix, and $x$ and $B$ are column vectors of order $3$.

Let’s say

$$ A = \begin{pmatrix} a & b & c \\ 0 & d & e \\ 0 & 0 & f \end{pmatrix} \qquad B = \begin{pmatrix} g \\ h \\ i \end{pmatrix} $$

And the values of $x$ are:

$$ x \in \left[\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}\right] $$

Let’s do some calculations:

  • x = conv(1):

$$ \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}^T A \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} = (a) \qquad B^T \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} = (g) $$

  • x = conv(2):

$$ \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}^T A \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} = (d) \qquad B^T \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} = (h) $$

  • x = conv(3):

$$ \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}^T A \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} = (a + b + d) \qquad B^T \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} = (g + h) $$

  • x = conv(4):

$$ \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}^T A \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} = (f) \qquad B^T \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} = (i) $$

  • x = conv(5):

$$ \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}^T A \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} = (a + c + f) \qquad B^T \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} = (g + i) $$

  • x = conv(6):

$$ \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}^T A \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix} = (d + e + f) \qquad B^T \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix} = (h + i) $$

  • x = conv(7):

$$ \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}^T A \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} = (a + b + c + d + e + f) \qquad B^T \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} = (g + h + i) $$

At this point, we have all expressions for $x^T A x$ and $B^T x$. We only need to add them along with $C$ (the flag) and we get this system of equations:

$$ \begin{cases} R_1 & = a & & & & & & + g & & & + s \\ R_2 & = & & & + d & & & & + h & & + s \\ R_3 & = a & + b & & + d & & & + g & + h & & + s \\ R_4 & = & & & & & + f & & & + i & + s \\ R_5 & = a & & + c & & & + f & + g & & + i & + s \\ R_6 & = & & & + d & + e & + f & & + h & + i & + s \\ R_7 & = a & + b & + c & + d & + e & + f & + g & + h & + i & + s \\ \end{cases} $$

Where $R_n$ are the $7$ results we get from the output of the server. We can model the above system of equations as a matrix equation:

$$ \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \end{pmatrix} \cdot \begin{pmatrix} a \\ b \\ c \\ d \\ e \\ f \\ g \\ h \\ i \\ s \\ \end{pmatrix} = \begin{pmatrix} R_1 \\ R_2 \\ R_3 \\ R_4 \\ R_5 \\ R_6 \\ R_7 \\ \end{pmatrix} $$

Implementation

We can solve this matrix equation with SageMath:

$ sage -q
sage: p = 1873089703968291141600166892623234932796169766648225659075834963115683566265697596115468506218441065194050127470898727249982614285036691594726454694
....: 776985338487833409983284911305295748861807972501521427415609
sage: F = GF(p)
sage: M = Matrix(F, [[1, 0, 0, 0, 0, 0, 1, 0, 0, 1],
....: [0, 0, 0, 1, 0, 0, 0, 1, 0, 1],
....: [1, 1, 0, 1, 0, 0, 1, 1, 0, 1],
....: [0, 0, 0, 0, 0, 1, 0, 0, 1, 1],
....: [1, 0, 1, 0, 0, 1, 1, 0, 1, 1],
....: [0, 0, 0, 1, 1, 1, 0, 1, 1, 1],
....: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]])
sage: Y = vector(F, [67646581430444722331246017333578517533935560982079416613953952672160381416872746204866902183146883898096520104501187512114534276874208954
....: 3742283566458551844396184709048082643767027680757582782665648386615861, 14723498019579601002396892723709381028862759629848227252480819982544676083848201
....: 56734807260120564701715826694945455282899948399224421878450502219353392390325275413701941852603483746312758400819570786735148132, 2028994330563246468942
....: 43296394578497549806047448163960638380135868871336000334692955799247243847240605199996942959637958157086977051654225700427599193002536157848015527462060
....: 033852150223217790081847181896018, 106598280679989061599099582441225307660748806324085510058051322196229859800246833882322558617110753910463580810835649
....: 2123167315175110515086192932230998426512947581115358738651206273178867911944034690138825583, 16765592040374828566747106676638494479148593486332885131967
....: 35253002541076530170853584406282605482862202276451646974549657672382936948091649764874334064431407644457518190694888175499630744741620199798070517691, 1
....: 32967026171038683053276060654188012838658596012974137325946741633081768367198889735293183462559551070093062391071734904297184386583824024631221346904384
....: 25351000654335078321056270428073071958155536800755626, 1049859675181292817835885218912868452922769382959555558223657616187915018968273717037070599055754
....: 118224873924325840103339766227919051395742409319557746066672267640510787473574362058147262440814677327567134194])
sage: X = M.solve_right(Y)
sage: X[-1]
498813054564388243904582026284763128211187996675052003548247336975880883891366643014569112764868074917765746124723665127785482449631058950191875945870577647245680439099627292248187361743497020009749347138826

Flag

And the last entry of X is $s$, which is the flag in decimal format:

sage: bytes.fromhex(hex(X[-1])[2:])
b'corctf{mind your ones and zeroes because zero squared is zero and one squared is one}\n'