Neoquest 2018: «Дирижабль? Ага!»

Andy21.03.2018

27 Время чтения: 4 мин.

Недавно закончился CTF NeoQuest 2018. Под катом разбор второй части задания про дирижабль, ZeroNet, регистр сдвига с обратной связью и систему линейных уравнений.
В задании был дан адрес сайта в сети ZeroNet, на котором развёрнут чат. Т.к. в ZeroNet содержимое сайта скачивается на локальный компьютер, то погрепав по папке с сайтом, я нашёл первый ключ, а так же encrypted_storage.json:

{ "encrypted_storage": [ { "secret_name": "SiteName", "secret_value": "84a303b9f188b0", "date_added": 1519915207692 }, { "secret_name": "SiteAddress", "secret_value": "e68cd4a46ee074121a040a6188d3f6d495f24480fc0e08b0d45d8fba875d9fd38e88", "date_added": 1519915235730 }, { "secret_name": "AdminUsername", "secret_value": "0d9ef480aa", "date_added": 1519915256867 }, { "secret_name": "AdminCert", "secret_value": "4b95e6dfd893b37293fe041188cd6d8da5af08d4fb80b0", "date_added": 1519915282130 }, { "secret_name": "SecondKey", "secret_value": "c73ab54b91c6099b0f0081ea9124e2f50e846f6fc674046b3b41a86048ae3e27b04d354c9b9786a158f9722821005362bcfae8d6c0a261addb0b2ef8e16fbdfc851b82e0829d", "date_added": 1519915320471 } ]
}

Видимо, нам нужно расшифровать «secret_value». Можно заметить, что длина шифртекста для AdminUsername 5 байт. Возможно открытый текст — «admin»? Если это шифр гаммирования, то мы можем получить 5 байт гаммы и проверить подходят ли они к другим «секретам». Проверяем на первых 5 байтах SiteName, получаем b"\xe8Y\x9aP5". Результат не очень…

Ещё на сайте есть такая страница:

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

Сам алгоритм находится в файле js/lfsr.js. Гамма в нём генерируется функцией

 function genKeyStream(key, iv, length) { var res = [] var state_len = bitLength(key) var state = iv.mod(bigInt(1).shiftLeft(state_len)) for (var i = 0; i < length; i++) { var next_byte = 0 for (var j = 0; j < 8; j++) { var next_bit = bitCount(state.and(key)) % 2 next_byte = (next_byte >>> 1) | (next_bit << 7) state = state.shiftRight(1).or(bigInt(next_bit).shiftLeft(state_len - 1)) } res.push(next_byte) } return res.reverse() }

Это регистр сдвига с обратной связью. Длина регистра равна длине ключа, расположение отводов задаётся ключём. IV обрезается до длины ключа и используется как начальное заполнение. Только в отличии от обычного регистра сдвига с обратной связью здесь гамма берётся не с выхода регистра, а с его входа.

Ещё видно, что первые байты гаммы будут шифровать последние байты ОТ… Возвращаемся к encrypted_storage.json, берём гамму от «admin» и расшфировываем ей последние 5 байт SiteName: «oChat» — уже совсем другой результат! Расшифровываем конец строки SiteAddress — видим, что в строке записан «1NeoChatZK4DxZJdg5WwocwxcUppA1eJgL» — адрес сайта. Длина этой строки 34 байта, т.е. у нас есть первые 34 байта (272 бита) гаммы.
В принципе шифрование с помощью регистров сдвига уже давно не считается стойким, но всё-таки имея только небольшой кусок гаммы его так просто не сломаешь… Но у этого шифра есть небольшое отличие от «классики» — гамма берётся со входа регистра. Подумав над этим, можно понять что после L = len(key) итераций IV будет полностью «вытеснен» из регистра сдвига, а всё внутреннее состояние (заполнение регистра) будет равно последним L битам гаммы. Тогда для всех $i \geq L$ можно записать такое уравнение:

$G_{i-1}* K_{L-1} + G_{i-2}* K_{L-2} + ... + G_{i-L}* K_{0} = G_i$

где:
$inline$ — i-ый бит гаммы
$inline$ — i-ый бит ключа
$inline$ — длина ключа
$inline$ — логическое И
$inline$ — исключительное ИЛИ (XOR)
Решив систему из L таких уравнений можно найти ключ. А зная ключ и внутреннее состояние (последние L бит гаммы) можно генерировать столько гаммы, сколько нужно! Что бы система имела не больше одного решения в ней должно быть не меньше L линейно независимых уравнений. Т.е. в правой части будут стоять $inline$ для $i \in [L, 2L - 1]$ . Значит мы сможем решить задачу если длина ключа не больше чем $inline$ бит.

Для решения пришлось написать функцию, которая решает систему по методу Гаусса, т.к. все найденные готовые функции решали всё в поле действительных или комплексных чисел, а не на множестве (0, 1) с операциями AND и XOR. Дальше я перебирал разные значения L, если система оказывалась совместной, я проверял будут ли следующие биты гаммы, сгенерированные таким ключём, совпадась с известными мне. Совпадение нашлось для $inline$ . Через пару минут ключ был засчитан!

На самом деле можно было не перебирать разные L, а сразу записать систему из 134 уравнений с 134 неизвестными, просто у ключа первые 6 бит оказались бы нулевыми.

Код решения

from hashlib import sha1 N_ct = 70 * 8
N = 0x22 * 8
O_hex = "D7 C2 B1 CB 2D 88 15 66 40 4F 3E 25 F0 89 BC B0 F2 C7 13 F7 93 6D 7F C8 B7 08 FF CA C6 6C FA 99 E9 C4".replace(" ", "")
O_int = int(O_hex, 16)
O = [int(c) for c in bin(O_int)[2:]]
O.reverse()
O_full = O_int ct = int("C7 3A B5 4B 91 C6 09 9B 0F 00 81 EA 91 24 E2 F5 0E 84 6F 6F C6 74 04 6B 3B 41 A8 60 48 AE 3E 27 B0 4D 35 4C 9B 97 86 A1 58 F9 72 28 21 00 53 62 BC FA E8 D6 C0 A2 61 AD DB 0B 2E F8 E1 6F BD FC 85 1B 82 E0 82 9D".replace(" ", ""), 16) def solve_linear_eq(A): """A[l, l+1]""" l = len(A) assert len(A) + 1 == len(A[0]) for j in range(l): for i in range(j, l): if A[i][j] == 1: break A[j], A[i] = A[i], A[j] for i in range(l): if i != j and A[i][j] == 1: for k in range(l + 1): A[i][k] ^= A[j][k] for i in range(l): for j in range(l): if i != j and A[i][j] == 1 or i==j and A[i][j] == 0: return None return [A[i][-1] for i in range(l)] def preapare_linear_eq(L): A = [] for n in range(L, 2*L): A.append([]) for i in range(0, L): A[-1].append(O[n-L+i]) A[-1].append(O[n]) return A def gamma(K): O_full = O.copy() L = len(K) for n in range(N, N_ct): s = 0 for i in range(0, L): s ^= O_full[n - L + i] & K[i] O_full.append(s) return O_full def check_key(K): for n in range(L, N): s = 0 for i in range(0, L): s ^= O[n - L + i] & K[i] if s != O[n]: return False return True found = 0
not_found = 0
for L in range(8, N//2): A = preapare_linear_eq(L) K = solve_linear_eq(A) if K is not None and check_key(K): found += 1 print(L, K) O_full = gamma(K) O_full_int = 0 O_full.reverse() for O in O_full: O_full_int = (O_full_int << 1) + O pt = O_full_int ^ ct pt = pt.to_bytes(70, "big") print(pt) break else: not_found += 1 print(sha1(pt).hexdigest())

Теги