[Cryptohack] CTRIME

В этом таске у нас CRIME атака на AES в режиме CTR (Counter). Интересной особенностью этого режим является то, что фактически шифрование производится по схеме OTP (one time pad), он же XOR. Таким образом мы получаем самый обычный потоковый шифр с AES в качестве генератора гаммы.

Так как это потоковый шифр, длина данных для шифрования может быть произвольной и не должа быть кратной размеру блока AES.

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

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

Код задачи:

Где уязвимость?

На первый взгляд шифрование выглядит достаточно надёжным: мы не знаем ни ключа, ни инциализирующего вектора (который вобщем-то и не должен быть секретным), а свойства AES позволяют генерировать криптографичесчки безопасную гамму для XORа. Всё здесь хорошо. Но стоит обратить внимание на то, что перед шифрованием данные сжимаются с помощью zlib. Эта библиотека построена вокруг алгоритма DEFLATE. Подробности алгоритма нас особо не интересуют. Более того, в принципе для существования уязвимости сам алгоритм не так важен. Важно лишь свойство алгоритмов сжатия — чем больше повторяющихся данных, тем лучше сжатие. Например:

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.
>>> import zlib
>>> for i in range(1, 21):
...     data = b"a" * i
...     print(len(zlib.compress(data)))
... 
9
10
11
12
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
>>>

Здесь мы сжимаем повторяющуюся букву a, и мы можем заметить, что для первых четырёх повторений цикла, то есть вплоть до aaaa размер сжатых данных увеличивается на 1, при добавлении 1 нового байта, причём размер сжатых данных больше размера сжимаемых данных — это из-за оверхеда алгоритма. Но уже последовательность aaaaa, сжимается в размер на 1 байт меньше, чем предыдущая. Более того, в дальнейшем размер данных не растёт вовсе.

Как найти флаг?

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

>>> import zlib
>>> secret = b"crypto{S0m3_flag}"
>>> len(zlib.compress(b"crypto{n" + secret))
28
>>> len(zlib.compress(b"crypto{S" + secret))
27

Мы отправляем на сервер строку: crypto{n и получаем в ответ 28 байт сжатых данных. Перебирая варианты этого байта мы рано или поздно наткнёмся на S и отправим серверу значение crypto{S и получим в ответ 27 байт сжатых данных. Следует отметить, что мы также можем присылать серверу значения crypto{3, и crypto{0, но размер сжатых данных всё равно будет равен 28 — это связано с особенностью алгоритма, который ищет повторения в небольшом окне бит (не байт). Не будем углубляться в подробности алгоритма, просто отметим, что если мы заметили уменьшение размера данных, то мы нашли следующий неизвестный нам символ флага.

Дальше мы запоминаем этот байт и начинаем пребирать следующий:

>>> len(zlib.compress(b"crypto{Sn" + secret))
28
>>> len(zlib.compress(b"crypto{Sm" + secret))
28
>>> len(zlib.compress(b"crypto{Sk" + secret))
28
>>> len(zlib.compress(b"crypto{S0" + secret))
27

И снова дойдя до символа 0 мы замечаем уменьшение размера сжатых данных.

Так перебирая символ за символом мы дойдём до значения crypto{S0m3. А дальше, какой бы символ мы не подставили, мы всегда будем получать один и тот же размер сжатых данных, даже когда мы ставим правильный символ:

>>> len(zlib.compress(b"crypto{S0n" + secret))
28
>>> len(zlib.compress(b"crypto{S0m" + secret))
27
>>> len(zlib.compress(b"crypto{S0mn" + secret))
28
>>> len(zlib.compress(b"crypto{S0m3" + secret))
27
>>> len(zlib.compress(b"crypto{S0m3n" + secret))
28
>>> len(zlib.compress(b"crypto{S0m3_" + secret))
28

Это опять связано с тем, что алгоритм оперирует сжатием на уровне бит, а не байт, и битовое сжатие может не отразится на размере данных в байтах. В данном случае нам придётся угадать следующий символ, здесь мы явно видим слово some, которое может быть как самостоятельным словом, так и частью составных слов someone, something, somewhere и т.п. Таким образом у нас есть несколько кандидатов на следующий символ: _(вместо пробела), o(или 0), w, t(или 7). Здесь нам нужно выбрать этот символ и продолжить перебор со следующего, если размер сжатых данных начнёт опять “плавать”, то мы выбрали правильный символ. Если нет — стоит попытаться с другим символом. Закрепим символ _.

Дальше перебор продолжается без проблем и мы в итоге получаем весь флаг. Мы знаем, что флаг заканчивается на символе }, значит дальше можно не перебирать.

>>> len(zlib.compress(b"crypto{S0m3_n" + secret))
29
>>> len(zlib.compress(b"crypto{S0m3_m" + secret))
29
>>> len(zlib.compress(b"crypto{S0m3_k" + secret))
29
>>> len(zlib.compress(b"crypto{S0m3_f" + secret))
28
>>> len(zlib.compress(b"crypto{S0m3_fn" + secret))
29
>>> len(zlib.compress(b"crypto{S0m3_fk" + secret))
29
>>> len(zlib.compress(b"crypto{S0m3_fm" + secret))
29
>>> len(zlib.compress(b"crypto{S0m3_fl" + secret))
28
>>> len(zlib.compress(b"crypto{S0m3_fln" + secret))
29
>>> len(zlib.compress(b"crypto{S0m3_flm" + secret))
29
>>> len(zlib.compress(b"crypto{S0m3_fla" + secret))
28
>>> len(zlib.compress(b"crypto{S0m3_flan" + secret))
29
>>> len(zlib.compress(b"crypto{S0m3_flag" + secret))
28
>>> len(zlib.compress(b"crypto{S0m3_flagn" + secret))
29
>>> len(zlib.compress(b"crypto{S0m3_flag}" + secret))
28

Пишем эксплойт

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

Скрипт выглядит следующим образом:

После запуска скрипт дойдёт до строки crypto{CRIM и остановится, не найдя следующий символ.

awawa@awawa-pc:~/Documents$ python3 ctrime_script.py 
b'crypto{C'
b'crypto{CR'
b'crypto{CRI'
b'crypto{CRIM'
Failed to find another byte. Found flag: crypto{CRIM
awawa@awawa-pc:~/Documents$

Это та самая ситуация, когда сжатие в битах не сказалось на размере текста в байтах. Придётся подобрать байт вручную. CRIM — очень похоже на слово CRIME. Тем более таск отностися к уязвимости CRIME, попробуем установить начальное значение флага в crypto{CRIME и запустить скрипт заново. И теперь скрипт находит полный флаг:

awawa@awawa-pc:~/Documents$ python3 ctrime_script.py 
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_'
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}'
awawa@awawa-pc:~/Documents$