Skip to content

Instantly share code, notes, and snippets.

@keltecc
Last active July 25, 2021 18:54
Show Gist options
  • Save keltecc/70f780f5f348e83cda74438384c8e6ec to your computer and use it in GitHub Desktop.
Save keltecc/70f780f5f348e83cda74438384c8e6ec to your computer and use it in GitHub Desktop.
Разбор таска scp-object с таск-бота Летней школы CTF 2021

LetoCTF Taskbot 2021 | scp-object

Описание

Короче, ███████, я тебя [ДАННЫЕ УДАЛЕНЫ] и в благородство играть не буду. Достанешь для меня флаг — и мы [ДАННЫЕ УДАЛЕНЫ].

Файлы

  • challenge.sage
  • output.txt

Решение

Нам выдаётся файл с кодом challenge.sage и его выходные данные output.txt. Рассмотрим подробнее, что делает код.

1. Сначала флаг и ключ шифрования читаются из файлов и передаются в функцию encrypt(), результат которой затем печатается:

def main():
    flag = read_file('flag.txt')
    key = read_file('key.txt')

    result = encrypt(flag, key)

    print(result)

2. Сама функция encrypt() только разбивает входные данные на блоки. Можно сделать вывод, что шифр — блочный, размер блока указан выше:

N = 16

def encrypt(plaintext, key):
    assert len(plaintext) == len(key)

    ciphertext = []

    for i in range(0, len(plaintext), N):
        plaintext_block = plaintext[i:i+N]
        key_block = key[i:i+N]
        ciphertext_block = encrypt_block(plaintext_block, key_block)
        ciphertext.append(ciphertext_block)

    return ciphertext

3. Смотрим в функцию encrypt_block():

def encrypt_block(plaintext, key):
    assert len(plaintext) == len(key) == N

    t = ceil(mean(plaintext + key)) ^ 3
    q = next_prime(t + randint(0, t))
    pol = construct_polynomial(q, plaintext, key)
    ciphertext = encrypt_polynomial(pol)

    return q, ciphertext

Сначала она вычисляет какие-то параметры t и q, а затем строит многочлен на основе блоков флага и ключа.

Здесь и далее используются специфичные для SageMath объекты, но их суть может быть понятна из названия. Например, зная, что plaintext и key — блоки байтов длины N, можно понять, что mean() вычисляет среднее арифметическое всех этих байтов, а ceil(), соответственно, округляет результат вверх. Полученное число t используется для вычисления qпростого числа, чуть большего, чем t. Вероятно, это нужно, чтобы найти какое-либо простое число q, которое будет гарантированно больше, чем все символы во флаге и ключе (но к этому мы ещё вернёмся).

4. Посмотрим в функцию construct_polynomial(), чтобы понять, как составляется многочлен от флага и ключа:

def construct_polynomial(q, plaintext, key):
    F = GF(q)
    P.<x> = PolynomialRing(F)
    Q.<x> = P.quo(x^N - 1)

    r, s = map(Q, map(list, [plaintext, key]))

    return (r / s).lift().change_ring(ZZ)

GF(q) — это конечное поле размера q. Затем над этим полем строится кольцо многочленов, то есть множество всех многочленов, коэффициенты которых лежат в поле GF(q). Следующая строчка P.quo(x^N - 1) означает, что все операции с многочленами мы будем проводить по модулю многочлена x^N - 1.

Мы получили Q — кольцо многочленов, коэффициенты которого не больше q, а сами многочлены не больше x^N - 1. Затем из блоков флага и ключа получаются многочлены r и s: символы используются как коэффициенты. После всего этого мы делим r / s и получаем другой многочлен, коэффициенты которого переводятся в ZZ — обычные целые числа.

5. Теперь у нас есть многочлен pol. Посмотрим в функци encrypt_polynomial(), чтобы понять как он преобразовывается:

from math import cos

R = RealField(4096)

def encrypt_polynomial(pol):
    values = [R(cos(z)) for z in pol]
    keystream = [R(1 + z).sin() for z in range(pol.degree() + 1)]

    return sum(k * v for k, v in zip(keystream, values))

В начале создаётся R — поле действительных чисел с точностью 4096 бит. Действительные числа могут быть бесконечно близко к нулю, поэтому для того, чтобы их хранить в компьютере, может потребоваться бесконечное количество бит. При создании поля можно указать, как много бит числа мы хотим хранить (то есть насколько маленьким оно может быть).

Затем с использованием тригонометрических функций создаются два массива. Сначала вычисляется массив values, в котором i-ый элемент равен косинусу i-ого коэффициента многочлена pol. Далее вычисляется ещё один массив — keystream, в котором элементы равны синусам последовательных чисел от 1 до N + 1 (потому что степень многочлена pol.degree() равна N).

После всего вычисляется скалярное произведение полученных массивов, оно и возвращается функцией как результат шифрования одного блока.


Теперь, когда мы разобрали код, пришло время придумать алгоритм решения.

1. encrypt_polynomial() (пункт 5)

Заметим, что синусы вычисляются у элементов поля методом R.sin(), следовательно, точность полученных чисел будет равна 4096 бит. В отличие от них, косинусы вычисляются встроенной в Python функцией math.cos(), которая работает с типом float и возвращает результат с точностью всего 64 бита. Получается, что элементы values содержат сильно меньше битов данных, чем элементы keystream.

2. construct_polynomial() (пункт 4)

Здесь аналогичная ситуация. У многочленов r и s коэффициенты не больше 8 бит (так как это байты), а размер поля GF(q) в три раза больше: примерно 24 бита. Это вызвано тем, что простое число q примерно равно третьей степени от входных байтов:

t = ceil(mean(plaintext + key)) ^ 3
q = next_prime(t + randint(0, t))

Выходит, что коэффициенты r и s тоже содержат сильно меньше бит данных, чем размер поля q.

3. Как это использовать?

Когда мы встречаемся с ситуацией, когда что-то сильно меньше другого, на ум приходит алгоритм LLL, который уже не первое десятилетие успешно взламывает многие криптографические алгоритмы.

LLL умеет находить кратчайчайший почти ортогональный базис решётки. Что это значит?

Если говорить простыми словами, то решётка — это набор каких-то векторов, которые можно складывать между собой и получать новые вектора. Базис решётки — это множество таких векторов решётки, которые мы никак не можем получить, как бы мы ни складывали другие вектора. Базис решётки образует векторное пространство, при этом одно и то же пространство можно задавать разными базисами:

два базиса

На рисунке выше видно, что базисы (u1, u2) и (v1, v2) образуют одно и то же пространство, но базис (u1, u2) короче и ортогональнее. В данном случае, если бы мы запустили LLL на базисе (v1, v2), он бы смог редуцировать его до (u1, u2).

4. Достаём многочлен pol

Мы можем использовать LLL, чтобы из результата работы функции encrypt_polynomial() (всего одного вещественного числа!) достать массив values — коэффициенты секретного многочлена pol, в котором спрятан флаг. Это возможно из-за того, что неизвестные числа (values) по размеру сильно меньше, чем известные (keystream). Под размером здесь имеется в виду размер в битах, то есть количество информации.

Эта задача похожа на частный случай задачи о сумме подмножеств с низкой плотностью, которую LLL умеет эффективно решать. В теории решёток подобная задача называется задачей нахождения кратчайшего вектора (SVP). Нужно помнить, что LLL не умеет работать с вещественными числами, поэтому их нужно перевести в целые, например, умножив на 2^4096. А затем перевести обратно.

Пример решётки:

пример решётки

Здесь v_i — это числа из массива keystream, а result — результат скалярного произведения.

5. Достаём r и s из многочлена pol

В этом случае нам нужно решить задачу рационального восстановления. Существует лемма Тью, которая утверждает, что для восстановления t = r / s (mod q) необходимо выполнение условия r * s < q / 2. Теперь понятно, зачем q создавалось примерно третьей степени от элементов (пункт 3).

Тот факт, что коэффициенты многочленов r и s сильно меньше, чем порядок всего поля q, позволяет нам снова использовать LLL. Похожая атака используется в криптоанализе алгоритма NTRUEncrypt. В статье на Википедии есть пример решётки:

пример решётки

6. Восстанавливаем флаг

Когда мы получим все многочлены r для каждого блока флага, останется только представить их коэффициенты в виде последовательностей байт и соединить в одну строку. Нужно помнить, что кроме флага в базисе решётки будет содержаться ещё и ключ.

Пример решения: solver.sage

Флаг

LetoCTF{p0lyn0m1aLLL_overdose!!}
#!/usr/bin/env sage
from math import cos
N = 16
R = RealField(4096)
def read_file(filename):
with open(filename, 'rb') as file:
return file.read().strip()
def construct_polynomial(q, plaintext, key):
F = GF(q)
P.<x> = PolynomialRing(F)
Q.<x> = P.quo(x^N - 1)
r, s = map(Q, map(list, [plaintext, key]))
return (r / s).lift().change_ring(ZZ)
def encrypt_polynomial(pol):
values = [R(cos(z)) for z in pol]
keystream = [R(1 + z).sin() for z in range(pol.degree() + 1)]
return sum(k * v for k, v in zip(keystream, values))
def encrypt_block(plaintext, key):
assert len(plaintext) == len(key) == N
t = ceil(mean(plaintext + key)) ^ 3
q = next_prime(t + randint(0, t))
pol = construct_polynomial(q, plaintext, key)
ciphertext = encrypt_polynomial(pol)
return q, ciphertext
def encrypt(plaintext, key):
assert len(plaintext) == len(key)
ciphertext = []
for i in range(0, len(plaintext), N):
plaintext_block = plaintext[i:i+N]
key_block = key[i:i+N]
ciphertext_block = encrypt_block(plaintext_block, key_block)
ciphertext.append(ciphertext_block)
return ciphertext
def main():
flag = read_file('flag.txt')
key = read_file('key.txt')
result = encrypt(flag, key)
print(result)
if __name__ == '__main__':
main()
LetoCTF{p0lyn0m1aLLL_overdose!!}
Jqwd4jbxQJCcC3AWxp4sFcOS8SAieAvd
[(850613, 1.8325117767332078955991616847943234589147974763857795659579199995772601993377771855292859502925864930584736391352022592335517139321246373219164060635651338893460866035364029979199499986454232207327509306693795439246454119704605209377125296128872669015946939161345229247471128450067019406847219202565257169414075188756698478342393435874446671626196931328783305635137667723079699972211594435941037105643917057624412435571850496098790069938525827170630708049567754454526438539772825955463369745596179038765011287002155023628163445334513967770166222910593522089282274922256403718241670228635371242595856189973873003693643746520906512711596986730540629883901213517103486832925324572656437991045770724396904245939499702035143697383626827042225149013707987139335022326968496102202226040019468233138078795938971803681901819992800607586895506672056151601512725990854856421403619719331724102587545619584909675925319704849846249432836729511742354099715847075236461813379527757148835881660254176998057470806666026317988933347261634978181588022314826977950281656493211950459455293034746354602821846638702470453658289563349904360042068510995681975386212018052983507710542633171431825121101370427136964747924727030757410389980671576849778945220739), (1479539, -0.60322827974443472335222089465357189304797818255452740805540857107891663092648605643481305194672533120626617657816215865727981786597972532482322005579837797318997683447723592854945261269783121189919978682981378556619014120109878868781130456994916851535128273579708084390528058531141280750628723667930009164038857084762074366428474757148020078426090978053820697594830830296583506760597711069139568442799610930340392848916035614968258418621443617955837717645416544018400425906775725704236145077364846192451913613288128668416335908559506564558490078293825507734398376370815838018442815043456224900049320204709134855144220279030080170904056106516769166450463679114610387071645734528782110503528891082482096937258436052070051843713108000127131906567678455962323505236267083684173728941261622074451459692065427530271565954810727689348001719258731752232806065388064001721703345279036674193331109453553115500805956134789252763938811890750105272120598003879142711297754408309243515166204711221747598567832975934872626709378792419387787440048645616406958809336215670711845325039324555255473335559082799606202169942508006125424182165280157433345301708321809098974897693872964216746001147919344684381704542928291634988415783703534112783178077355)]
#!/usr/bin/env python3.8
from math import cos
from string import printable
N = 16
bits = 4096
R = RealField(bits)
def recover_block(q, pol):
M_dl = 0 * matrix.identity(ZZ, N)
M_dr = q * matrix.identity(ZZ, N)
M_ul = matrix.identity(ZZ, N)
M_ur = matrix(ZZ, [[0] * N])
for i in range(N):
line = list(pol)
line = line[-i:] + line[:-i]
M_ur = M_ur.stack(vector(ZZ, line))
M = (M_ul.augment(M_ur[1:])).stack(M_dl.augment(M_dr))
# print(M)
L = M.LLL()
# print(L)
for row in L:
for part in [row[:N], row[N:]]:
for candidate in [part, -part]:
possible_flag = bytes(int(z) % 256 for z in candidate)
if all(chr(z) in printable for z in possible_flag):
flag = bytes(possible_flag).decode()
for i in range(len(flag) - 1):
print(flag[i:] + flag[:i])
print()
def recover_polynomial(q, result):
p1 = int(bits * log(2, 10))
p2 = 57
keystream = [R(1 + z).sin() for z in range(N)]
keystream_lifted = [round(z * 10^p1) for z in keystream]
result_lifted = round(result * 10^p1) * 10^p2
M = (matrix.identity(ZZ, N + 1)).augment(vector(ZZ, keystream_lifted + [-result_lifted]))
L = M.LLL()
row = L[0]
sign = row[-2]
values = [float(R(z) / 10^p2) * sign for z in row[:N]]
cache = {}
for x in range(q):
cache[cos(x)] = x
return [cache[value] for value in values]
def main():
with open('output.txt', 'r') as file:
result = sage_eval(file.read())
for q, ciphertext in result:
pol = recover_polynomial(q, ciphertext)
recover_block(q, pol)
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment