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


Недавно закончился 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$

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

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

На самом деле можно было не перебирать разные 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())




К сожалению, не доступен сервер mySQL