Curve Logic
Задание
Наши разведчики нашли в пустоши заброшенный сервер, который остался от тех, кто создавал системы безопасности еще до Великой Войны. Он принимает числа и выполняет какие-то сложные расчеты. Если твой ввод будет правильным, сервер откроет доступ к засекреченной информации. Постарайся, нам очень нужны эти данные!
Решение
Подключение для выполнения данного задания происходит по Netcat.
Для выполнения задания был дан файл с исходным кодом сервиса:
import socket
import os
from random import *
from Crypto.Util.number import *
from Crypto.PublicKey import ECC
from threading import Thread
flag = f"ptech2024{{{os.getenv('flag')}}}\n"
def generate_curve():
nbit = 521
key = ECC.generate(curve='P-521')
order = ECC._curves['NIST P-521'][2]
Q = key.pointQ
O = ECC.EccPoint(Q.x, Q.y, curve='p521').point_at_infinity()
return nbit, order, Q, O
def check_number(n, nbit):
return n.bit_length() == nbit and bin(n)[2:].count('1') >= nbit // 2 + 1
def decimal(n, nbit, order, O, Q):
try:
n = int(n)
except:
return -1
if check_number(n, nbit):
R, P, counter = O, Q.copy(), 0
for bit in bin(n)[2:][::-1]:
if bit == '1':
R = R + P
counter += 1
P = P.double()
counter += 1
if 406 * counter >= 522 * nbit:
break
if R == Q * n and n < order:
return 1
else:
return 0
else:
return -2
def binary(bin_n, nbit, order, O, Q):
try:
bin_n = [int(i) for i in bin_n.split(',')]
flag = all(0 <= i <= 1 for i in bin_n) and len(bin_n) == nbit
except:
return -1
if flag:
R, P, counter, i, n = O, Q.copy(), 0, 0, 0
for bit in bin_n[::-1]:
if bit != 0:
n += 2 ** i * bit
R += P
counter += 1
P = P.double()
counter += 1
i += 1
if 594 * counter >= 600 * nbit:
break
if n.bit_length() == nbit and n < order and R == Q * n:
return 1
else:
return 0
else:
return -2
def handle_client(conn, addr):
print(f"New connection from {addr}")
try:
nbit, order, Q, O = generate_curve()
hello_message = "This super computer uses elliptic curves for its calculations.\nEnter the decimal representation of the number or its binary form to begin the calculation\n1 - decimal or 2 - binary:\n"
conn.sendall(hello_message.encode())
mode = conn.recv(1024).decode().strip().lower()
if mode == '1':
conn.sendall("Enter decimal number:\n".encode())
n = conn.recv(4096).decode().strip()
result = decimal(n, nbit, order, O, Q)
if result == -2:
conn.sendall("Number does not satisfy the requirements\n".encode())
elif result == -1:
conn.sendall("Input is not integer\n".encode())
elif result == 0:
conn.sendall("Wrong number,the calculations failed\n".encode())
elif result == 1:
conn.sendall(f"Calculations completed successfully. There is your flag: {flag}\n".encode())
elif mode == '2':
conn.sendall("Enter binary form of number separated by commas:\n".encode())
B = conn.recv(4096).decode().strip()
result = binary(B, nbit, order, O, Q)
if result == -2:
conn.sendall("Number does not satisfy the requirements\n".encode())
elif result == -1:
conn.sendall("Input is not correct\n".encode())
elif result == 0:
conn.sendall("Wrong number,the calculations failed\n".encode())
elif result == 1:
conn.sendall(f"Calculations completed successfully. There is your flag: {flag}\n".encode())
else:
conn.sendall("Choice is not correct\n".encode())
except Exception as e:
print(f"Error in session with {addr}: {e}")
finally:
conn.close()
def server_get_connections():
server_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
server_socket.bind(('0.0.0.0', 52152))
server_socket.listen(5)
print(f"Server started. Listening port 52152 ....")
while True:
conn, addr = server_socket.accept()
client_thread = Thread(target=handle_client, args=(conn, addr))
client_thread.start()
if __name__ == '__main__':
server_get_connections()
После краткого анализа кода становится понятно, что в данном задании использованы операции на эллиптической кривой P-521.
Если вы не знаете, как работают эллиптические кривые, и зачем они нужны, прочитать про это можно здесь и здесь.
При подключении к сервису пользователю доступно меню с выбором десятичной или двоичной формы ввода.
This super computer uses elliptic curves for its calculations.
Enter the decimal representation of the number or its binary form to begin the calculation
1 - decimal or 2 - binary:
Определим, в каком случае пользователю будет выдан флаг. Из анализа кода становится понятно, что для этого необходимо, чтобы переменная result была равна 1.
elif result == 1:
conn.sendall(f"Calculations completed successfully. There is your flag: {flag}\n".encode())При этом result является результатом работы функций для обработки ввода пользователя в десятичной или двоичной форме.
result = decimal(n, nbit, order, O, Q)
...
result = binary(B, nbit, order, O, Q)Рассмотрим отдельно логику функций, используемых для обработки десятичного и двоичного ввода. Начнем с функции для десятичного ввода:
def decimal(n, nbit, order, O, Q):
try:
n = int(n)
except:
return -1
if check_number(n, nbit):
R, P, counter = O, Q.copy(), 0
for bit in bin(n)[2:][::-1]:
if bit == '1':
R = R + P
counter += 1
P = P.double()
counter += 1
if 406 * counter >= 522 * nbit:
break
if R == Q * n and n < order:
return 1
else:
return 0
else:
return -2Разберемся с параметрами, передаваемыми в эту функцию. Параметры order, Q и O являются параметрами эллиптической кривой и генерируются ранее в коде. Параметр nbit также задан в коде. Параметр n является числом в десятичной форме, введенным пользователем.
nbit = 521
order = ECC._curves['NIST P-521'][2]
Q = key.pointQ
O = ECC.EccPoint(Q.x, Q.y, curve='p521').point_at_infinity()В первую очередь в данной функции происходит проверка ввода пользователя на соответствие некоторым условиям с помощью функции check_number. Проанализировав код данной функции, прийдем к выводу о том, что ввод пользователя должен быть числом длиной nbit (в нашем случае 521) и должен содержать более nbit // 2 + 1 единиц в двоичном представлении (в нащем случае 261).
def check_number(n, nbit):
return n.bit_length() == nbit and bin(n)[2:].count('1') >= nbit // 2 + 1Если ввод пользователя прошел проверку, то происходит определение некоторых параметров. Параметр R приравнивается точке на бесконечности, а параметр P - точке Q, сгенерированной для эллиптической кривой. Также задается счетчик counter, равный нулю.
R, P, counter = O, Q.copy(), 0Далее происходит обработка введенного пользователем числа. При этом число рассматривается побитово в обратном порядке (от младшего бита к старшему). Если бит равен 1, то к точке R прибавляется точка P и значение счетчика counter увеличивается на 1. При этом независимо от значения бита происходит удвоение точки P и увеличение счетчика counter на 1. Когда выполняется условие 406 * counter >= 522 * nbit, то перебор битов числа останавливается.
for bit in bin(n)[2:][::-1]:
if bit == '1':
R = R + P
counter += 1
P = P.double()
counter += 1
if 406 * counter >= 522 * nbit:
breakПотом происходит проверка условия:
if R == Q * n and n < order:
return 1Для получения флага необходимо, чтобы рассчитанная точка R была равна сложению точки Q с самой собой n раз. Вспомним, что n - это введенное пользователем числом в десятичной форме. Также n равно сумме степеней двойки на местах единичных бит. Добавление Q к R происходит только, если бит n равен 1. Таким образом, для выполнения данного условия необходимо, чтобы при рассмотрении числа по битам было пройдено все число.
Так как перебор битов останавливается, когда выполняется условие 406 * counter >= 522 * nbit, то при значении counter равном 670 перебор будет остановлен. При этом, чтобы пройти все число длиной 521 бит с минимум 261 единицей (условие для прохождения первой проверки) необходимо прибавить counter 782 раза. Соответственно, не получится пройти такое число целиком. Из этого можно сделать вывод о том, что при выборе десятичного ввода пользователю не удастся получить флаг.
Рассмотрим работу функции для двоичного ввода пользователя:
def binary(bin_n, nbit, order, O, Q):
try:
bin_n = [int(i) for i in bin_n.split(',')]
flag = all(0 <= i <= 1 for i in bin_n) and len(bin_n) == nbit
except:
return -1
if flag:
R, P, counter, i, n = O, Q.copy(), 0, 0, 0
for bit in bin_n[::-1]:
if bit != 0:
n += 2 ** i * bit
R += P
counter += 1
P = P.double()
counter += 1
i += 1
if 594 * counter >= 600 * nbit:
break
if n.bit_length() == nbit and n < order and R == Q * n:
return 1
else:
return 0
else:
return -2В данном случае также длина введенного числа должна быть равна 521 бит, однако НЕТ УСЛОВИЯ ДЛЯ МИНИМАЛЬНОГО КОЛИЧЕСТВА ЕДИНИЦ!
flag = all(0 <= i <= 1 for i in bin_n) and len(bin_n) == nbitПомимо параметров R, Q и counter, заданных аналогично случаю с десятичным вводом, вводится переменные n и i для сборки числа, введенного пользователем, в десятичном виде.
R, P, counter, i, n = O, Q.copy(), 0, 0, 0Сложение точек на кривой в данном случае происходит также, как и в случае с десятичным вводом пользователя. Побитовый перебор будет завершен, когда выполнится условие 594 * counter >= 600 * nbit. Таким образом предельное значение counter будет равно 527.
for bit in bin_n[::-1]:
if bit != 0:
n += 2 ** i * bit
R += P
counter += 1
P = P.double()
counter += 1
i += 1
if 594 * counter >= 600 * nbit:
breakДля получения флага необходим пройти следующее условие:
if n.bit_length() == nbit and n < order and R == Q * n:
return 1То есть для получения флага необходимо пройти все биты числа, введенного пользователем. Так как в данном случае нет условия на минимальное количество единиц в числе и предельное значение counter равно 527, а длина числа 521 бит, то пользователь может ввести число, содержащее до 6 единиц.
Выполним ввод такого числа, пользователь получит флаг:
This super computer uses elliptic curves for its calculations.
Enter the decimal representation of the number or its binary form to begin the calculation
1 - decimal or 2 - binary:
2
Enter binary form of number separated by commas:
1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
Calculations completed successfully. There is your flag: ptech2024{17d2c5ab414a641c1620623cb5b8cd081f6e749f}