[Cryptohack]Stream of Consciousness

6 min readAug 10, 2021

В этой задаче имеем дело с AES в режиме CTR. Этот режим превращает блочный шифр в потоковый, где сам шифр используется как генератор гаммы, а шифрование производится с помощью XOR.

Режим CTR является достаточно надёжным шифрованием (если используется надёжный блочный шифр). Тем не менее, чтобы шифрование было надёжным критически важно использовать уникальное значение Nonce(см. схему выше) в каждой сессии, в противном случае надёжность шифрования падает до уровня OTP с повторяющимся ключом, который, как известно, очень легко взламывается. (Также, конечно, надо не забывать наращивать значение Counter для каждого блока, что в общем-то подразумевается самой схемой.)

Значение Nonce не обязано быть секретным, и даже не должно быть непредсказуемым (в отличие от IV в схеме CBC, например). Атакующий в любом случае не сможет предсказать значение выхода из блочного шифра, не зная ключа. Единственное требование — уникальность.

Поиск уязвимости

Теперь посмотрим на задачу:

В данной задаче мы имеем только одну функцию, которая позволяет нам зашифровать случайное значение из массива строк (в котором также есть флаг) с помощью AES в режиме CTR. Примечательной является строка инициализации шифра:

cipher = AES.new(KEY, AES.MODE_CTR, counter=Counter.new(128))

То есть для каждого вызова функции encrypt() создаётся новый инстанс шифра. Хорошо, теперь посмотрим в документацию модуля Crypto для CTR мода:

Как видим, в функцию new можно передать nonce и начальное значение счётчика — initial_value. Если nonce не передаётся, то будет использовано случайное значение длиной в половину блока (вторая половина блока занята счётчиком, который начинается с 0, если не задан). Таким образом для каждой сессии практически гарантируется создание уникального значения nonce + counter.

Однако есть ещё параметр counter, который можно использовать для создания своего собственного счётчика. Этот параметр принимает объект класса Counter и переопределяет поведение счётчика, отключая параметры nonce и initial_value. В нашей задаче инстанс шифра создаётся без использования nonce и initial_value. А в параметр counter, передаётся результат выполнения функции Counter.new() с параемтром 128.

Посмотрим документацию для функциии Counter.new():

Так, она принимает в первом параметре длину счётчика в битах (в нашем случае 128–16 байт). Также есть опциональные параметры prefix, suffix и initial_value. Значения prefix и suffix фактически являются значением nonce. Тут важно отметить, что если они не передаются, то, в отличие от фукнции Cipher.new, будут использованы пустые значения, а не случайно сгенерированные.

Подытоживая всё вышесказанное, замечаем, что при каждом вызове функции encrypt() будет создаваться новый инстанс шифра, но с одинаковыми параметрами. А значит все тексты будут шифроваться одинаковой гаммой, что и является уязвимостью в данной задаче. Это легко проверить:

Python 3.8.10 (default, Jun  2 2021, 10:49:15) 
[GCC 9.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from Crypto.Cipher import AES
>>> from Crypto.Util import Counter
>>> text = b"1234567890"
>>> key = b"1234567812345678"
>>> cipher1 = AES.new(key, AES.MODE_CTR, counter=Counter.new(128))
>>> cipher2 = AES.new(key, AES.MODE_CTR, counter=Counter.new(128))
>>> cipher1.encrypt(text).hex()
'956e1208eda7ba8e783d'
>>> cipher2.encrypt(text).hex()
'956e1208eda7ba8e783d'

Атака

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

Собрать шифротексты.
Найти первое приближение ключа.
Восстановить ключ побайтово.

Собираем шифротексты

В первую очередь нам необходимо собрать как можно больше зашифрованных данных. Во-первых, потому что у нас всё ещё нет флага, он является элементом в массиве текстов TEXT, а мы получаем случайный элемент при каждом вызове encrypt(). Во-вторых, потому что с большим количеством текстов нам будет проще восстанавливать ключевую гамму. Для сбора шифротекстов используем следующий скрипт:

Здесь мы просто делаем 100 запросов (предполагаем, что этого достаточно, чтобы получить все шифротексты для массива TEXT, это число можно будет увеличить позже) и сохраняем каждый ответ в множестве ciphertexts. Используя множество вместо списка, мы гарантируем отсутствие дубликатов. Дальше просто сохраним все шифротексты в файл.

Всего скрипт собрал 22 значения.

Здесь можно достаточно уверенно сказать, что мы собрали все возможные шифротексты. Если бы в массиве было около 100 или больше элементов, то количество шифротекстов тоже должно было быть близким к 100. Тогда имело бы смысл запустить скрипт на большее количество итераций.

Находим первые байты ключа

Чтобы найти первые байты ключа воспользуемся знанием о флаге. Мы знаем, что флаг начинается со значения crypto{. На всякий случай вспомним, что шифрование производится с помощью операции XOR, а значит: т.к. C = P ^ K, то K = C ^ P. Отсюда следует, что если мы проксорим значение crypto{ с первыми 7 байтами зашифрованного флага, то мы получим первые 7 байт ключа.

Первая проблема — мы не знаем какой из шифротекстов является зашифрованным флагом. Решение: перебрать все 22 значения.

Вторая проблема — как узнать, что мы нашли правильные байты ключа? Ответ: воспользуемся предположением о том, что все тексты в массиве TEXT являются читабельными текстами на английском языке. Значит как только мы найдём правильные 7 байт ключа, первые 7 байт всех текстов смогут быть расшифрованы в читаемый текст.

Воспользуемся следующим скриптом:

Здесь мы просто ксорим первые несколько байт каждого шифротекста с известным нам значением флага, получая таким образом возможный ключ. Далее ксорим все шифротексты с этим ключом, получая возможные открытые тексты. Все варианты расшифровки сохраняем в файл.

Теперь просматривая результаты работы ключа можно заметить, что только один из вариантов полностью расшифровывает все 22 текста в читабельный текст. Если бы такого варианта не нашлось, это могло бы быть знаком того, что мы не получили зашифрованный флаг в шаге 1. Тогда следовало бы повторить оба шага, возможно с большим количеством итераций на первом шаге.

Теперь мы имеем первые байты ключа (1f900f4421748f) и можем приступать к последнему шагу нашего плана.

Побайтовое восстановление ключа (расшифровка флага)

Для побайтового восстановления ключа (или флага) будем использовать следующий скрипт:

Здесь мы просто рассшифровываем начало шифротекста с известным ключом, а ту часть, для которой ключ не известен оставляем зашифрованной. Делаем эту процедуру для всех 22 текстов и выводим результаты на экран.

Теперь самая скучная процедура: нам нужно строить предположения о том во что должен расшифровываться следующий байт шифротекста и на основе этого вычислять следующий байт ключа. Например, есть такой текст:

Known: I shall       Unknown:>I\xf3\xa3\xed<B \xbc\x81\xba5\xf1T-...

Здесь мы можем предположить, что после слова shall, должен быть пробел. Тогда мы берём байт шифротекста > и ксорим его с пробелом, чтобы получить значение байта ключа.

Получаем значение 1e. Добавляем это значение к известному ключу и запускаем скрипт заново.

Здесь очень важно следить за тем, что при добавлении нового байта к ключу все тексты расшифровываются в читабельный текст. Если хотя бы один из текстов расшифровался во что-то бессмысленное — значит мы сделали неправильное предположение и нужно попробовать другое. В нашем случае байт 1e правильно расшифровывает все тексты и мы можем переходить к следующему.

Возьмем текст

Known: It can't       Unknown:\x05\xfe\xb5\xa8hH$\xb7\xd3\xac4...

Здесь тоже предполагаем пробел после can't, значит нужно проксорить байт 05 c 20.

Получаем значение 25 и добавляем к ключу.

Все тексты расшифровались правильно, идём дальше. Возьмём текст

Known: But I wil       Unknown:\xf0\xf0\xfbtH!\xf9\x9b\xaa,\xb7

Предположим что следующий байт должен быть l, чтобы образовалось слово will, тогда ксорим f0 с байтом l. Здесь также стоит отметить, что после слова will скорее всего будет идти пробел, значит мы можем сделать предположение для двух байт сразу.