eyes
7 minutos de lectura
Se nos proporciona el código fuente en SageMath que se usó para cifrar la 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)
También tenemos la salida del script:
1873089703968291141600166892623234932796169766648225659075834963115683566265697596115468506218441065194050127470898727249982614285036691594726454694776985338487833409983284911305295748861807972501521427415609
[676465814304447223312460173335785175339355609820794166139539526721603814168727462048669021831468838980965201045011875121145342768742089543742283566458551844396184709048082643767027680757582782665648386615861, 1472349801957960100239689272370938102886275962984822725248081998254467608384820156734807260120564701715826694945455282899948399224421878450502219353392390325275413701941852603483746312758400819570786735148132, 202899433056324646894243296394578497549806047448163960638380135868871336000334692955799247243847240605199996942959637958157086977051654225700427599193002536157848015527462060033852150223217790081847181896018, 1065982806799890615990995824412253076607488063240855100580513221962298598002468338823225586171107539104635808108356492123167315175110515086192932230998426512947581115358738651206273178867911944034690138825583, 1676559204037482856674710667663849447914859348633288513196735253002541076530170853584406282605482862202276451646974549657672382936948091649764874334064431407644457518190694888175499630744741620199798070517691, 13296702617103868305327606065418801283865859601297413732594674163308176836719888973529318346255955107009306239107173490429718438658382402463122134690438425351000654335078321056270428073071958155536800755626, 1049859675181292817835885218912868452922769382959555558223657616187915018968273717037070599055754118224873924325840103339766227919051395742409319557746066672267640510787473574362058147262440814677327567134194]
Análisis del código fuente
El servidor un esquema de compartición de secretos (SSS, sharing secret scheme) utilizando matrices sobre un cuerpo finito de orden $p$ (un número primo conocido):
s = bytes_to_long(flag)
p = getPrime(len(bin(s)))
print(p)
F = GF(p)
N = 1024
En primer lugar, el servidor crea una matriz aleatoria $A$ de dimensión $1024 \times 1024$ y pone a $0$ las entradas debajo de la diagonal principal:
A = random_matrix(F, N, N)
for i in range(0, N):
for j in range(0, i):
A[i, j] = 0
Luego, el servidor crea un vector columna aleatorio $B$ de $1024$ entradas y $C$, que es la flag en formato decimal:
B = random_matrix(F, N, 1)
C = matrix(F, [F(s)])
Finalmente, el servidor hace algunos cálculos e imprime el resultado:
L = []
for i in range(7):
L.append(fn(conv(i + 1)))
print(L)
La función conv representa un entero como una lista de bits en orden inverso:
conv = lambda n: matrix(F, N, 1, [int(i) for i in list(bin(n)[2:][::-1].ljust(N, '0'))])
Así, conv(1) = [1, 0, ..., 0], conv(2) = [0, 1, 0, ..., 0], conv(3) = [1, 1, 0, ..., 0], y sucesivamente.
Y la función fn contiene una ecuación matricial:
fn = lambda x: (x.T * A * x + B.T * x + C)[0][0]
En términos matemáticos, podemos expresar la función fn como:
$$ x^T A x + B^T x + C $$
En resumen, se nos dan un total de $7$ resultados, donde conocemos el vector $x$ en cada cálculo.
Solución
Dado que el vector de $x$ es la salida de conv(i + 1), sabemos que el vector está compuesto por tres bits al principio y el resto de las entradas son $0$. Como resultado, al calcular $x^T A x$, solo la submatriz de $3 \times 3$ de arriba a la izquierda importa. Lo mismo ocurre con $B^T x$. Entonces, de ahora en adelante, $A$ es una matriz diagonal de $3 \times 3$, y $x$ y $B$ son vectores columna de dimensión $3$.
Digamos que
$$ A = \begin{pmatrix} a & b & c \\ 0 & d & e \\ 0 & 0 & f \end{pmatrix} \qquad B = \begin{pmatrix} g \\ h \\ i \end{pmatrix} $$
Y los valore de $x$ son:
$$ 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] $$
Vamos a hacer algunos cálculos:
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) $$
En este punto, tenemos todas las expresiones de $x^T A x$ y $B^T x$. Solo necesitamos sumarlos junto con $C$ (la flag) y obtenemos este sistema de ecuaciones:
$$ \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} $$
Donde $R_n$ son los $7$ resultados que obtenemos de la salida del servidor. Podemos modelar el sistema de ecuaciones anterior como una ecuación matricial:
$$ \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} $$
Implementación
Ahora podemos resolver esta ecuación matricial con 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
Y la última entrada de X es $s$, que es la flag en formato decimal:
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'