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

Недавно закончился CTF NeoQuest 2018 ^[1]. Под катом разбор второй части задания про дирижабль, ZeroNet ^[2], регистр сдвига с обратной связью и систему линейных уравнений.

В задании был дан адрес сайта ^[3] в сети 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"xe8Yx9aP5". Результат не очень…
Ещё на сайте есть такая страница: Потыкавшись, можно заметить, что длина шифртекста равна длине открытого текста, а шифрование и дешифрование — это одна и та же операция. Очень похоже на гаммирование, может быть тут тот же алгоритм, которым зашифрован второй секрет?
Сам алгоритм находится в файле 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 обрезается до длины ключа и используется как начальное заполнение. Только в отличии от обычного регистра сдвига с обратной связью ^[4] здесь гамма берётся не с выхода регистра, а с его входа.
Ещё видно, что первые байты гаммы будут шифровать последние байты ОТ… Возвращаемся к 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 бит оказались бы нулевыми.

Автор: Nokta_strigo

Источник ^[5]