Решение cryptopals. Часть 1 / forpes.ru

Главная
Решение cryptopals. Часть 1

Решение cryptopals. Часть 1

20.03.2024 15:47

seregablog 0 681 Источник

Часто при изучении криптографии делают упор на теорию, оставляя практическую часть в стороне. Упражнения Matasano Crypto Challenges cryptopals — это прекрасный вариант подтянуть практические навыки. С одной стороны, начинать можно с минимумом предварительных знаний. С другой стороны, затронуты все важные темы на примере реальных атак.

В этой части рассмотрим блоки заданий 1 и 2.

Блок 1: Basic

Темы: Базовые знания, xor-шифр
Ссылка: https://cryptopals.com/sets/1

Задание 1: Convert hex to base64

Простое подготовительное задание — нужно реализовать стандарт кодирования Base64. Он понадобится в дальнейшем для отображения бинарных данных в читаемом виде.

Задание 2: Fixed XOR

Тоже простое подготовительное задание — нужно реализовать функцию xor для байтовых массивов.

Задание 3: Single-byte XOR cipher

По условию требуется расшифровать текст, зашифрованный xor-шифром с ключом длиной в один байт.
Сначала нужно придумать для расшифрованных данных некую метрику «близости» к английскому тексту. Затем, используя её, определить нужный текст.

В качестве метрики для расшифрованного текста будем использовать функцию:

$M(T) = \sum_{\alpha \in L} (Fr(\alpha) - En(\alpha)) ^ 2$

— текст
— английские буквы, которые присутствуют в тексте
$Fr(\alpha)$ — частота буквы в расшифрованном тексте
$En(\alpha)$ — эталонная частота буквы в английских текстах

Текст, для которого значение метрики минимально, и будет искомым.

Задание 4: Detect single-character XOR

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

Задание 5: Implement repeating-key XOR

Небольшое усложнение Задания 3: теперь для шифрования вместо однобайтового ключа используется ключ из нескольких байтов.

Задание 6: Break repeating-key XOR

Это первое настоящее задание. Нужно расшифровать текст, зашифрованный xor-шифром с многобайтовым ключом.

Решение:

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

Расстояние Хэмминга двух битовый строк — количество бит, в которых эти строки различаются

Расстояние Хэмминга будем использовать как меру «случайности» для битовых строк, так как расстояние Хэмминга для двух строк английского текста в среднем будет отличаться от расстояния для двух случайных строк. Для сравнения строк различной длины будем использовать относительное расстояние Хэмминга, т. е. расстояние, делённое на длину строки.

Для определения длины ключа перебираем возможную длину ключа (по условию длина ключа лежит в пределах от 2 до 40) и считаем относительное расстояние Хэмминга между блоками текста. Длина, при которой получено минимальное расстояние Хэмминга, и будет искомой.

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

Задание 7: AES in ECB mode

Подготовительное задание, нужно расшифровать сообщение, зашифрованное AES-128-ECB. Лучше реализовать режим ECB самостоятельно, а не применять готовые утилиты, потому что он понадобится в дальнейшем.

Задание 8: Detect AES in ECB mode

В задании среди представленных сообщений нужно найти то, которое зашифровано AES-ECB.

AES в режиме ECB шифрует блоки сообщения друг за другом независимо. Если в открытом тексте будет два одинаковых блока, то они также будут одинаковыми и в зашифрованном тексте. Этот недостаток режима ECB и демонстрирует задание. Ищем текст, в котором есть повторяющиеся блоки.

Задание не очень хорошо сформулировано, потому что в тексте, не зашифрованном AES-ECB, тоже могут встречаться повторяющиеся блоки. Решается только за счёт того, что такой текст в задании ровно один.

Блок 2: Block crypto

Тема: Блочные шифры
Ссылка: https://cryptopals.com/sets/2

Задание 9: Implement PKCS#7 padding

Подготовительное задание. Нужно реализовать дополнение PKCS#7. Дополнение работает по простому алгоритму: в конец сообщения добавляется n байтов со значением n. То есть корректными дополнениями являются:

0x01
0x02 0x02
0x03 0x03 0x03
...

Задание 10: Implement CBC mode

Нужно реализовать шифрование AES в режиме CBC, используя результаты Задания 7. Задание знакомит с режимом шифрования CBC.

Формула шифрования:
C_0 = IV
$C_i = E_k(P_i \oplus C_{i - 1})$

Формула расшифрования:
C_0 = IV
$P_i = C_{i - 1} \oplus D_k(C_i)$

Задание 11: An ECB/CBC detection oracle

Это немного усложнённое Задание 8, только теперь нужно различать сообщения, зашифрованные AES-ECB и AES-CBC. Идея та же: у шифра в режиме ECB одинаковые блоки открытого текста после шифрования будут одинаковыми, а в режиме CBC — разными.

Задание 12: Byte-at-a-time ECB decryption (Simple)

Это первое задание, посвящённое настоящей криптографической уязвимости. Оно демонстрирует слабость схемы шифрования:

AES-128-ECB(your_string || unknown_string, key)

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

Решение:

Генерируем сообщение, которое состоит из одинаковых символов, и длина которого на один байт короче, чем полный блок: «AAAA...AA»
Посылаем это сообщение оракулу и получаем шифротекст
Теперь перебираем все возможные байты: дописываем байт в конец сообщения и посылаем полный блок «AAAA...AA», «AAAA...AB», «AAAA...AC», «AAAA...AD»,...
Если байт совпадёт с первым байтом из unknown_string, то будет получен тот же шифротекст, что и на втором шаге
Продолжая действия для остальных символов, полностью восстанавливаем unknown_string

Задание 13: ECB cut-and-paste

Задание демонстрирует, что режим ECB уязвим к атаке замены\удаления блока.

Сначала нужно получить шифротекст блока admin\0xb...\0xb — строка «admin» + дополнение PKCS7 до полного блока. Для этого передаём оракулу email, состоящий из 10 произвольных символов и строки «admin\0xb...\0xb». Тогда блоки открытого текста будут:

email=A...A — 1 блок
admin\0xb...\0xb — 2 блок
&uid=10&role=user — остальные блоки

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

Теперь подаём на вход оракулу произвольный email, состоящий из 13 символов. В результате блоки открытого текста будут:
email=...&uid=10&role= — 1 и 2 блок
user... — 3 блок

В шифротексте заменяем последний блок на ранее полученный зашифрованный блок admin\0xb...\0xb и получаем ответ.

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

Задание 14: Byte-at-a-time ECB decryption (Harder)

Это немного усложнённый вариант Задания 12. Разница в том, что теперь перед текстом добавляется случайная строка. Если длина строки известна, то можно применить атаку из Задания 12, значит основная трудность — это выяснить длину.

Подобно Заданию 9, длину можно определить по дублирующим блокам в шифротексте:

Начинаем передавать тексты «A», «AA», «AAA», ...
В какой-то момент открытый текст будет иметь вид (P - байты начальной строки) PP..PAA|A...A|A....A|,
У шифротекста, сгенерированного на этом открытом тексте, будет два одинаковых блока. Как только это произойдёт, определяем длину
Далее повторяем атаку из Задания 12

Задание 15: PKCS#7 padding validation

В Задании 9 нужно было реализовать дополнение PKCS7, а в этом задании нужно реализовать проверку корректности дополнения. Стоило совместить их.

Задание 16: CBC bitflipping attacks

Задание демонстрирует свойства режима CBC при инвертировании бита в блоке шифротекста:

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

Свойство напрямую следует из формулы для расшифрования в режиме CBC. Сложность задания состоит в том, что нам нужно получить в расшифрованном тексте строку ;admin=true;, но использовать символы «;» и «=» напрямую нельзя, поэтому:

Передаём строку XadminYtrueXAAAA, «X» на месте «;», «Y» на месте «=», «AAAA» — дополнение до полного блока
Изменим биты предыдущего блока шифротекста, чтобы при расшифровании в следующем блоке произошла замена «X»->«;», «Y»->«=»

В этом задании снова излишне сложная подготовительная часть, которая отвлекает от основной идеи.

Код решений на python: https://github.com/seregablog/cryptopals

Мой Телеграм-канал