В этой задаче имеем дело с 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
скорее всего будет идти пробел, значит мы можем сделать предположение для двух байт сразу.
Получаем байты 9c
и d0
, добавляем их к ключу и расшифровываем.
Таким образом продолжаем до тех пор, пока длины ключа не хватит для расшифровки флага.