Приветствую, Хабр! Я продолжаю освещать режимы шифрования блочных шифров и сегодня расскажу про режим CTR (Counter), а также разберу решение задачи CTRIME, в которой этот режим используется. При этом в задаче напрямую не используется уязвимость самого режима шифрования, решение будет построено на основе уязвимости CRIME. Впрочем, про уязвимость в CTR я тоже расскажу.

Режим шифрования CTR

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

Как альтернатива блочным шифрам существуют шифры потоковые, которые способны шифровать данные по сути любого объёма. Часто (современные) потоковые шифры устроены так, что они на основе ключа генерируют так называемую "гамму" - поток псевдослучайнх байтов, а дальше эта гамма просто суммируется (xor) с исходным текстом. Так и получается зашифрованное сообщение. По сути надёжность таких шифров полностью зависит от свойств процедуры генерации гаммы и вообще сам по себе шифр можно грубо представить как генератор гаммы.

Хорошие блочные шифры способны выдавать неплохие псевдослучайные последовательности, т.е. зашифрованный текст выглядит очень похожим на случайную последовательность. Отсюда возникла идея - почему бы нам не использовать блочные шифры в качестве генераторов гаммы в потоковом шифре? Кажется, что если у нас есть надёжный блочный шифр, то таким фокусом мы можем получить "бесплатно" потоковый шифр с теми же гарантиями безопасности. К сожалению, не всё так радужно. Нам всё ещё нужно придумать как превратить дискретный выход блочного шифра в непрерывный поток. Именно это и делает режим шифрования CTR (и некоторые другие). И, как мы уже убедились из предыдущих статей, режимы шифрования могут снижать надёжность шифра. Давайте же разбираться что не так с CTR.

CTR работает так:

Для генерации гаммы с помощью блочного шифра шифруется блок Nonce + Counter, где Nonce - то же самое, что IV в других режимах, а Counter - обычный счётчик, который увеличивается на 1 для каждого следующего блока.

В статье я разбераю пример где Nonce и Counter просто "склеиваются" вместе - первую половину блока шифрования занимает Nonce, а вторую Counter. Но вообще есть другие подходы, где Nonce и Counter складываются другими способами (, $\oplus$ , $\cdot$ ,...), у каждого из которых свои проблемы. Конкатенация - самый популярный подход.

Шифрованием каждого блока мы получаем определённую часть гаммы, которую дальше используем для шифрования текста, используя столько байтов, сколько нам нужно. Например, если исполльзовать AES, то один блок гаммы - 16 байт, если надо зашифровать 8 байт, то просто генерируем один блок, используем первые 8 байт, остальные 8 оставляем на будущее. Дальше, допустим, нужно зашифровать 9 байт - используем оставшиеся 8 байт, генерируем второй блок гаммы, используем 1 байт и запоминаем оставшиеся 15 байт. Думаю, что суть вы поняли.

А теперь немного про безопасность. Nonce (вернее, пара (Nonce, Key)) должны быть уникальны в каждой сессии. Иначе это открывает большие дыры в шифровании:

одинаковые открытые тексты, находящиеся на одинаковом смещении относительно начала потока зашифровываются в одинаковые шифротексты. Например, если открытый текст в двух сессиях начинается одинаково с user = admin;, то шифротексты в двух сессиях будут начинаться с одинаковых значений, которые будут соответствовать одинаковым текстам.
если криптоаналитик знает часть одного открытого текста, он может расшифровать все шифротексты на том же смещении. Пусть байты 117-125 в известном криптоаналитику открытом тексте равны $P_{117-125}$ , тогда те же байты в шифротексте в этой сессии будут равны $C_{117-125}$ . Т.к. шифрование - это простое суммирование, можно вычислить часть гаммы для этого участка по формуле $K_{117-125} = C_{117 - 125} \oplus P_{117-125}$ и дальше расшифровывать этот участок шифротекста для любой другой сессии, в которых используется тот же ключ и nonce.

Про практическое использование уязвимости повторяющегося nonce при решении задач можно почитать, например, тут https://ctftime.org/writeup/35876

А я перейду дальше к задаче CTRIME.

Задача

Условие задачи максимально простое. Есть сервер, который может только шифровать переданный текст:

from Crypto.Cipher import AES
from Crypto.Util import Counter
import zlib


KEY = ?
FLAG = ?


@chal.route('/ctrime/encrypt/<plaintext>/')
def encrypt(plaintext):
    plaintext = bytes.fromhex(plaintext)

    iv = int.from_bytes(os.urandom(16), 'big')
    cipher = AES.new(KEY, AES.MODE_CTR, counter=Counter.new(128, initial_value=iv))
    encrypted = cipher.encrypt(zlib.compress(plaintext + FLAG.encode()))

    return {"ciphertext": encrypted.hex()}

К тексту перед шифрованием прикрепляется флаг и (важно!) результат сжимается библиотекой zlib (алгоритм Deflate). Подробно про алгоритм рассказывать не стану, просто отмечу что он умеет сжимать повторяющиеся последовательности бит в более короткую запись. Например, пусть у нас будет такой текст (в битах): 0110 0110 0110 0110. Значение 0110 повторяется 4 раза и мы можем сократить запись до 0100 0110 (здесь 0100 это 4 в двоичной записи, а 0110 - повторяющееся значение). По сути этой записью мы говорим, что значение 0110 повторяется 4 раза и в итоге нам требуется в два раза меньше бит для записи той же информации. Примерно это происходит и в алгоритме Deflate, но несколько сложнее, конечно. Это свойство сокращения сжатого текста при наличии повторяющихся паттернов мы и будем использовать в задаче.

Сначала на практике посмотрим на сжатие, сожмём повторяющийся символ a:

>>> len(zlib.compress(b"a" * 1))
9
>>> len(zlib.compress(b"a" * 2))
10
>>> len(zlib.compress(b"a" * 3))
11
>>> len(zlib.compress(b"a" * 4))
12
>>> len(zlib.compress(b"a" * 5))
11
>>> len(zlib.compress(b"a" * 6))
11
>>> len(zlib.compress(b"a" * 7))
11
>>> len(zlib.compress(b"a" * 100))
12

Видим, что 1 байт сжимается до размера 9 байт! Не очень-то экономно! Потом 2 байта - 10 байт, 3 байта - 11 байт, 4 байта - 12. А вот начиная с 5 повторяющихся символов размер сжатого текста вдруг уменьшается до 11 байт и перестаёт расти при добавлении ещё байт. Даже при сжатии 100 байт получаем всего 12 байт.

Так, хорошо, теперь приблизимся немного к нашей задаче. Предположение будет такое: мы начинаем с шифрования строки crypto{(знаем что флаг начинается с этих символов), к которой будем прикреплять один байт и смотреть растёт ли длина зашифрованного текста. Если текст вырос, то байт скорее всего неправильный, если не вырос - то такой байт есть во флаге, его оставляем. Снова разберём на примере, пусть флагом будет crypto{Fak3_f14g}:

>>> FLAG = b"crypto{Fak3_f14g}"
>>> len(zlib.compress(b"crypto{A" + FLAG))
28
>>> len(zlib.compress(b"crypto{B" + FLAG))
28
>>> len(zlib.compress(b"crypto{F" + FLAG))
27
>>> len(zlib.compress(b"crypto{a" + FLAG))
28

Видим, что при добавлении символа F к строке, длина шифротекста становится меньше, чем при добавлении других символов. Так мы понимаем, что F находится на своём месте, и действительно в нашем тестовом флаге на этом месте стоит символ F. Заметьте, что даже когда мы пробуем символ a, который тоже есть во флаге и следует за F, длина сжатых данных не уменьшается. Это связано с тем, что алгоритм при сжатии ищет повторения в определённом окне бит и символ a не попал в это окно. Т.е. произошло что-то такое:

Снова оговорюсь, что поиск дубликатов в алгоритме не делится ровно так, как у меня нарисовано. Там вообще несколько окон и они бьются не по байтам, а по битам. Но идея примерно такая. Получается, что два символа a не попали в окно, поэтому не сжались.

Теперь мы знаем часть флага crypto{F, чтобы найти следующий символ повторяем перебор:

>>> len(zlib.compress(b"crypto{FA" + FLAG))
28
>>> len(zlib.compress(b"crypto{Fa" + FLAG))
27
>>>

Так делаем для всех остальных символов флага и получаем весь флаг.

Всё, что мы проделали выше на самом деле известная уязвимость - CRIME, или CVE-2012-4929, которую обнаружили в 2012 году в HTTPS. Она позволяла расшифровать куки сайта, получить таким образом токены авторизации и подделать сессию. Но, как видим, одним только HTTPS она не ограничивается. По сути любая комбинация сжатие+шифрование может привести к наличию этой уязвимости в системе.

Теперь давайте попробуем атаковать реальный сервер. Для этого я написал такой скрипт:

import requests
import json


base = "http://aes.cryptohack.org/ctrime/encrypt/"


flag = b"crypto{"

response = requests.get(base + flag.hex())
ciphertext = json.loads(response.content)["ciphertext"]
baseLength = len(ciphertext)

while 1:
	for i in range(32, 128): # Перебираем только печатные символы
		response = requests.get(base + flag.hex() + f"{hex(i)[2:]:0<2}")
		ciphertext = json.loads(response.content)["ciphertext"]
        # Если при добавлении следующего байта длина шифротекста не увеличилась
        # значит мы нашли правильный символ
		if len(ciphertext) == baseLength:
			flag += bytes([i])
			print(flag)
			baseLength = len(ciphertext)
			if i == ord("}"):
				exit()
			break

        # Если мы перебрали все печатные символы, но не нашли нужный символ
        # то останавливаемся. Такое может быть, схема всё таки не идеальная
		if i == 127:
			print("Failed to find another byte. Found flag: " + flag.decode())
			exit()

Запускаем

b'crypto{C'
b'crypto{CR'
b'crypto{CRI'
b'crypto{CRIM'
Failed to find another byte. Found flag: crypto{CRIM

Скрипт нашёл 4 символа и остановился. Попробуем угадать символ самостоятельно. Думаю, что мы можем сделать достаточно сильное предположение, что следующим символом будет либо E, либо e, либо 3, то есть слово будет CRIME, от��ылая к . В скрипте меняем изначальное значение флага с crypto{ на crypto{CRIME и пробуем снова:

b'crypto{CRIME_'
b'crypto{CRIME_5'
b'crypto{CRIME_57'
b'crypto{CRIME_571'
b'crypto{CRIME_571l'
b'crypto{CRIME_571ll_'
b'crypto{CRIME_571ll_p'
b'crypto{CRIME_571ll_p4'
b'crypto{CRIME_571ll_p4y'
b'crypto{CRIME_571ll_p4y5'
b'crypto{CRIME_571ll_p4y5}'

Сервер может отбить соединение из-за количества запросов, чтобы это обойти можно вставить паузу между запросами, или просто запустить скрипт несколько раз, обновляя флаг до последнего известного.

Заключение

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

Cryptohack. Решение CTRIME