Cold Siemens

#

Описание: I recently discovered a huge problem in my cryptosystem. Hope it’s SQRe now!

nc cold_siemens.ctfz.zone 1188

import os
import random
from math import log
from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
from secret import flag

TARGET_LEN = 666
left_pad = random.randint(TARGET_LEN // 3, TARGET_LEN // 2)
right_pad = TARGET_LEN - left_pad - len(flag) 
#генерация случайных байтов заданной длины слева и справа от самого флага
flag = os.urandom(left_pad) + flag + os.urandom(right_pad) 

def sqrsqr(x: int, prec: int) -> tuple[int, int]:
    return int(iroot(x * 10 ** (prec * 4), 4)[0]) % 10**prec 


class Server:
    def __init__(self, bl: int, skip: int = 1000):
        self.bl = bl
        self.K = random.randrange(0, 2**self.bl)
        self.cipher = None
        self.key = None
        random.seed(self.K)

    def init_cipher(self, keylen: int):
        alpha = sqrsqr(self.K, prec=keylen)
        alpha_list = list(str(alpha).zfill(keylen))
        random.shuffle(alpha_list)
        self.key = long_to_bytes(int("".join(alpha_list)))

    def encrypt(self, m: bytes) -> bytes:
        keylen = round(log(10 ** len(m)) / log(10))
        self.init_cipher(keylen)
        sc = (len(m) + len(self.key) - 1) // len(self.key)
        return bytes([x ^ y for x, y in zip(m, self.key * sc)])


S = Server(bl=256)

print("Encrypted flag: ", S.encrypt(flag).hex())
while True:
    try:
        msg = bytes.fromhex(input("m: "))
        if len(msg) > 285:
            print("Message to big to encrypt, sorry")
        else:
            print("Encrypted msg: ", S.encrypt(msg).hex())
    except Exception as e:
        print(e)
        exit()

Мы имеем дело с симметричным методом шифрования, который использует дробную часть какого-то большого числа для формирования ключа.

Разберёмся в работе кода

#

Функция sqrsqr возвращает последние prec цифр, 4-го корня из x. Метод init_cipher создаёт ключ для шифрования. Он делает это с помощью применения функции sqrsqr к случайно сгенерированному числу K, а затем перемешивает результат. Метод encrypt шифрует входящее сообщение m используя XOR-операцию.

Пример работы:

Решение

#

Для решения задачи нам необходимо написать код, который будет посимвольно восстанавливать число K, генерировать ключ на его основе и расшифровывать флаг. Разберём по функциям на примере решения Sarkoxed:

Функция find_decimal

#

def find_decimal(key: str, i: int, alpha: list):
    original_counts = [alpha.count(str(i)) for i in range(10)]
    for k in range(0, 100):
        for j in range(2, len(key) + 1, 2):
            tmp = int(key[:j], 16)
            if len(str(tmp)) == i - k:
                tmpalpha = str(tmp).zfill(i)

                diff = [
                    tmpalpha.count(str(i)) - oc for i, oc in enumerate(original_counts)
                ]
                if set(diff) != set([0, 1]):
                    continue
                return tmpalpha

Создается список original_counts, в котором для каждой цифры от 0 до 9 подсчитывается количество её вхождений в списке alpha. Внешний цикл проходит по значениям k от 0 до 99, а внутренний цикл перебирает подстроки строки key, начиная с индекса 2 и увеличивая длину подстроки на 2 (т.е. рассматриваются только чётные длины). Для каждой подстроки происходит преобразование из шестнадцатеричной системы в десятичную. Код проверяет, совпадает ли длина десятичного числа tmp с i - k. Если длина совпадает, создается строка tmpalpha, которая содержит десятичное число, дополненное ведущими нулями до длины i. Создаётся список diff, который содержит разницу между количеством вхождений каждой цифры в tmpalpha и значениями из original_counts. Также происходит проверка на коллизии: set(diff) != set([0, 1]). Если же все условия успешно выполняются, функция возвращает строку tmpalpha.

Функция recover_fractional_part

#

def recover_fractional_part(r, b):
    alpha = []
    #tqdm используется для красивого отображения прогресса выполнения
    for i in tqdm(range(1, b + 1)): 
        r.sendline(b"00" * i)
        key = re.findall(r"Encrypted msg:  (.*)\n", r.recvline().decode())[0]
        alpha_ = list(find_decimal(key, i, alpha))
        assert len(alpha_) == len(alpha) + 1

        for d in alpha.copy():
            if d in alpha_:
                del alpha_[alpha_.index(d)]
            else:
                alpha.append(d)
                break
        else:
            alpha.append(alpha_[0])
    r.close()

    return int("".join(alpha))

b = 285
host, port = "localhost", 1188
r = remote(host, port)
flag = bytes.fromhex(re.findall(r"Encrypted flag:  (.*)\n", r.recvline().decode())[0])
alpha = recover_fractional_part(r, b)
r.close()

Создаётся список alpha для хранения восстановленных значений. На наш сервис отправляется строка, состоящая из нулей, мы получаем ответ и извлекаем зашифрованное сообщение. После чего вызывается функция find_decimal, результат преобразуется в список alpha_. Проверка длины alpha_ гарантирует, что было найдено новое значение. В конце функция возвращает целое число, полученное путем объединения всех элементов списка alpha в строку и преобразования в целое число. То есть мы просто отправляем нули, чтобы получить ключевой поток и восстановить дробную часть.

Основной код

#

Для начала нам придётся немного порассуждать. Если alpha это дробная часть нашего числа, а x это последние цифры (функция sqrsqr в оригинальном кода). Тогда: $$(x + alpha)^4 \approx K $$ $$K - K \approx 0 $$ $$(x + alpha)^4 - (x + alpha)^4\approx 0 $$ $$(x^4 + 4 * alpha * x^3 + 6 * alpha^2 * x^2 + 4 * alpha^3 * x + alpha^4) - K\approx 0 $$ Сведем это к задаче о минимальном векторе. И получим следующую решетку из аналогичной задачи о квадратном корне: $$ \begin{bmatrix} 1 & 0 & 0 & 0 & \lfloor alpha^4 * B \rfloor \\ 0 & 1 & 0 & 0 & \lfloor4 alpha^3 * B \rfloor \\ 0 & 0 & 1 & 0 & \lfloor6 alpha^2 * B \rfloor \\ 0 & 0 & 0 & 1 & \lfloor4 alpha * B \rfloor \\ 0 & 0 & 0 & 0 & B \end{bmatrix} $$

Решетка это подмножество векторов многомерного евклидова пространства, которые образуют дискретную подгруппу относительно операции сложения. Криптография на решётках Мы знаем, что существует линейная комбинация последнего столбика, такая что результирующее число будет недалеко от нуля. Остальные столбики в единицах, так как они будут хранить информацию о коэффициентах многочлена. Они будут примерно около получившегося в последнем столбике нуля. B - точность. Опытным путём можно обнаружить, что нужно примерно 290 знаков алфавита. У нас есть 285, остальные 5 мы можем перебрать (extra). Соответственно: B = 10^(b+extra) = 10^290

extra = 290 - b
for t in tqdm(range(10**extra)):
    B = 10 ** (b + extra)
    alpha_t = alpha * 10**extra + t
    t = Rational(alpha_t) / B
    M = Matrix(
        [
            [1, 0, 0, 0, floor(t**4 * B)],
            [0, 1, 0, 0, floor(4 * t**3 * B)],
            [0, 0, 1, 0, floor(6 * t**2 * B)],
            [0, 0, 0, 1, floor(4 * t * B)],
            [0, 0, 0, 0, B],
        ]
    )

    L = M.LLL()
    tmp = M.solve_left(L[0])
    R = tmp[0] * tmp[1]
    K = int(-tmp[0] * tmp[-1] + R**4)

    def sqrsqr(x: int, prec: int) -> tuple[int, int]:
        return int(iroot(x * 10 ** (prec * 4), 4)[0]) % 10**prec

    m = flag
    keylen = round(log(10 ** len(m)) / log(10))
    random.seed(K)
    alpha_ = sqrsqr(K, prec=keylen)
    alpha_list = list(str(alpha_).zfill(keylen))
    random.shuffle(alpha_list)
    key = long_to_bytes(int("".join(alpha_list)))
    sc = (len(m) + len(key) - 1) // len(key)
    d = bytes([x ^ y for x, y in zip(m, key * sc)])
    if b"CTFZone" in d:
        print(d[d.index(b"CTFZONE") :])
        exit()

Создается матрица M, элементы которой рассчитываются на основе t и B, к ней применяется алгоритм LLL (Lenstra–Lenstra–Lovász), основная цель которого — найти короткие векторы в решетке, созданной на основе данной матрицы, то есть, простыми словами, “уменьшить матрицу”. Рассчитывается число K и происходит генерация ключа на его основе, который затем используется для расшифровки сообщения m с помощью операции XOR. Далее идёт проверка наличия строки “CTFZone” в зашифрованных данных d. Если она найдена, программа выводит данные, начиная с первой найденной позиции. Ура, флаг у нас!

End

#

На этом всё, спасибо за прочтение! Всем хорошего дня, надеюсь вам понравилось!!