Skip to content

Latest commit

 

History

History
104 lines (77 loc) · 5.59 KB

README.md

File metadata and controls

104 lines (77 loc) · 5.59 KB

Epiliptic LFSR

Событие Название Категория Сложность
VKA-CTF`2020 Epiliptic LFSR Криптография КМБ

Описание

Автор: unknown

Узнав о криптостойкости эллиптической криптографии, крипто-ефрейтор Вася Пупкин решил создать невзламываемый потоковый шифр, названный ECLFSR-шифр (beta) . Для подтверждения своей правоты, он предоставил нам несколько зашифрованных файлов.

Решение

После просмотра прикрепленных исходных кодов, понимаем, что имеем дело с модифицированным алгоритм шифрования на основе LFSR и эллиптических кривых , который шифрует блоки по два байта, генерируя ключ исходя из текущего состояния регистра и полученного полинома (индексы ячеек, которые будут складываться для получения нового значения). В качестве ячеек в регистре используются точки эллиптической кривой, параметры которой нам известны и являются совсем небольшими, но генерирующую точку G и полином secret_number мы не знаем.

m = 65537
b = 1337
E = EllipticCurve(GF(m), [0, b])
G = E.point((gx, gy))

self.polly = [i for i, x in enumerate(bin_n) if x == '1']
self.state = [inf] * (size - 1) + [G]

Исходя из того, что m всего 17 байт, возникает идея перебрать все возможные комбинации secret_number и генерирующей точки эллиптической кривой. Так как перед использованием secret_number берется по модулю - имеем 65537 х 65537 возможных комбинаций. Далее заметим, что начальное состояние - генерирующая точка G (G + inf = G).

self.state = [inf] * (size - 1) + [G]

Значит, ключ используемый для шифрования первых двух байт файла - координаты y точки G(x, y). Осталось дело за малым - воспользовавшись формулой кривой y^2 = x^3 + b mod m , найти решение уравнения для x.

m = 65537
y = 43315 
b = 1337
for i in range(m):
    if (i**3 + b)%m == y*y % m:
		print(i)
        break
# i = 22868

Теперь возьмем проксоренные первые 10 байт шифротекста и плейнтекста, и попробуем подобрать нужное secret_number.

used_keys = bytearray([169, 220, 169, 220, 169, 220, 87, 37, 4, 1, 87, 37, 169, 220, 169, 220, 87, 37, 4, 1])
for num in range(65537):
    a = eclfsr(num)
    
    cur_keys = bytearray([])
    for i in range(10):
        tmp = int(a.get_next())
        key = bytearray([(tmp//255) % 255, tmp % 255])
        cur_keys += key
    
    if cur_keys == used_keys:
        print(num)
        break
# 41

Получив secret_number можем повторно запустить алгоритм на файле "flag.txt.enc" и получить флаг:

vka{n07_3v3ry7h1n6_15_50_c0mpl1c473d_45_17_533m5_47_f1r57_516h7}

Второй вариант решения

Посмотрим какие ключи использовались для шифрования

with open('Lorem ipsum.txt', 'rb') as file:
	plain_text = file.read()

with open('Lorem ipsum.txt.enc', 'rb') as file:
	enc_text = file.read()

tmp = [a ^ b for a, b in zip(enc_text, plain_text)]
used_keys = [bytes(tmp[i*2:(i+1)*2]) for i in range(len(tmp)//2)]
unequal_keys = set(used_keys)
print(unequal_keys) # {b'\x04\x01', b'W%', b'\xa9\xdc'}

Всего три различных ключа! Тогда почему бы не попробовать каждые два байта зашифрованного флага проксорить на каждый из ключей. Маловероятно, что в результате все 3 ключа после дешифровки дадут символы из [0-9A-z{}_] .

with open('flag.txt.enc', 'rb') as file:
	data = file.read()
	blocks = [data[i*2:(i+1)*2] for i in range(len(data)//2)]

flag = [[] for _ in blocks]
for i, block in enumerate(blocks):
	for key in unequal_keys:
		tmp = bytes([key[0] ^ block[0], key[1] ^ block[1]])
		if bytes([tmp[0]]) in alfa and bytes([tmp[1]]) in alfa: 
			flag[i].append(tmp.decode()) 

print(flag)
# [['vk'], ['a{', '2_'], ['n0'], ['7_'], ['3v'], ['3r'], ['y7'], ['h1'], ['n6'], ['_1'], ['5_', 'f{'], ['50'], ['_c'], ['0m', 'cI'], ['pl'], ['1c', 'bG'], ['47'], ['3d'], ['_4'], ['f{', '5_'], ['17'], ['_5'], ['33'], ['m5'], ['_4'], ['7_'], ['f1'], ['r5'], ['7_', 'd{'], ['51'], ['eL', '6h'], ['7}']]

Спорных позиций всего 7, но они вполне подбираются по смыслу.