Недавно закончился CTF NeoQuest 2018. Под катом разбор второй части задания про дирижабль, ZeroNet, регистр сдвига с обратной связью и систему линейных уравнений.
В задании был дан адрес сайта в сети ZeroNet, на котором развёрнут чат. Т.к. в ZeroNet содержимое сайта скачивается на локальный компьютер, то погрепав по папке с сайтом, я нашёл первый ключ, а так же encrypted_storage.json:
Видимо, нам нужно расшифровать «secret_value». Можно заметить, что длина шифртекста для AdminUsername 5 байт. Возможно открытый текст — «admin»? Если это шифр гаммирования, то мы можем получить 5 байт гаммы и проверить подходят ли они к другим «секретам». Проверяем на первых 5 байтах SiteName, получаем b"\xe8Y\x9aP5". Результат не очень…
Ещё на сайте есть такая страница:
Потыкавшись, можно заметить, что длина шифртекста равна длине открытого текста, а шифрование и дешифрование — это одна и та же операция. Очень похоже на гаммирование, может быть тут тот же алгоритм, которым зашифрован второй секрет?
Сам алгоритм находится в файле js/lfsr.js. Гамма в нём генерируется функцией
Это регистр сдвига с обратной связью. Длина регистра равна длине ключа, расположение отводов задаётся ключём. IV обрезается до длины ключа и используется как начальное заполнение. Только в отличии от обычного регистра сдвига с обратной связью здесь гамма берётся не с выхода регистра, а с его входа.
Ещё видно, что первые байты гаммы будут шифровать последние байты ОТ… Возвращаемся к encrypted_storage.json, берём гамму от «admin» и расшфировываем ей последние 5 байт SiteName: «oChat» — уже совсем другой результат! Расшифровываем конец строки SiteAddress — видим, что в строке записан «1NeoChatZK4DxZJdg5WwocwxcUppA1eJgL» — адрес сайта. Длина этой строки 34 байта, т.е. у нас есть первые 34 байта (272 бита) гаммы.
В принципе шифрование с помощью регистров сдвига уже давно не считается стойким, но всё-таки имея только небольшой кусок гаммы его так просто не сломаешь… Но у этого шифра есть небольшое отличие от «классики» — гамма берётся со входа регистра. Подумав над этим, можно понять что после L = len(key) итераций IV будет полностью «вытеснен» из регистра сдвига, а всё внутреннее состояние (заполнение регистра) будет равно последним L битам гаммы. Тогда для всех можно записать такое уравнение:
где:
— i-ый бит гаммы
— i-ый бит ключа
— длина ключа
— логическое И
— исключительное ИЛИ (XOR)
Решив систему из L таких уравнений можно найти ключ. А зная ключ и внутреннее состояние (последние L бит гаммы) можно генерировать столько гаммы, сколько нужно! Что бы система имела не больше одного решения в ней должно быть не меньше L линейно независимых уравнений. Т.е. в правой части будут стоять для . Значит мы сможем решить задачу если длина ключа не больше чем бит.
Для решения пришлось написать функцию, которая решает систему по методу Гаусса, т.к. все найденные готовые функции решали всё в поле действительных или комплексных чисел, а не на множестве (0, 1) с операциями AND и XOR. Дальше я перебирал разные значения L, если система оказывалась совместной, я проверял будут ли следующие биты гаммы, сгенерированные таким ключём, совпадась с известными мне. Совпадение нашлось для . Через пару минут ключ был засчитан!
На самом деле можно было не перебирать разные L, а сразу записать систему из 134 уравнений с 134 неизвестными, просто у ключа первые 6 бит оказались бы нулевыми.
В задании был дан адрес сайта в сети 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-ый бит гаммы
— i-ый бит ключа
— длина ключа
— логическое И
— исключительное ИЛИ (XOR)
Решив систему из L таких уравнений можно найти ключ. А зная ключ и внутреннее состояние (последние L бит гаммы) можно генерировать столько гаммы, сколько нужно! Что бы система имела не больше одного решения в ней должно быть не меньше L линейно независимых уравнений. Т.е. в правой части будут стоять для . Значит мы сможем решить задачу если длина ключа не больше чем бит.
Для решения пришлось написать функцию, которая решает систему по методу Гаусса, т.к. все найденные готовые функции решали всё в поле действительных или комплексных чисел, а не на множестве (0, 1) с операциями AND и XOR. Дальше я перебирал разные значения L, если система оказывалась совместной, я проверял будут ли следующие биты гаммы, сгенерированные таким ключём, совпадась с известными мне. Совпадение нашлось для . Через пару минут ключ был засчитан!
На самом деле можно было не перебирать разные 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())
VampiRUS
А можно код посмотреть?
Nokta_strigo Автор
Добавил в конец статьи. Выкладываю почти в неизменном виде, просьба за стиль не осуждать ;-)
VampiRUS
Спасибо.