Решение cryptopals. Часть 226.03.2024 20:00

Продолжаем решать задания cryptopals. В этой части рассмотрим блоки заданий 3 и 4.

Первая часть
Вторая часть

Блок 3: Block & stream crypto

Темы: Блочные шифры, генераторы случайных чисел
Ссылка: https://cryptopals.com/sets/3

Задание 17: The CBC padding oracle

Задание знакомит с классической (но от этого не менее актуальной) атакой «Oracle Padding Attack» на режим CBC блочного шифра. Она позволяет восстановить открытый текст, имея только зашифрованный текст и доступ к оракулу, проверяющему корректность дополнения.

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

Результат будет примерно такой:

text = CBC.decrypt(ciphertext);  # расшифрование
if (!is_padding_correct(text)) {  # проверка дополнения
        Error('incorrect padding');
    }
return unpad(text);  # снятие дополнения

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

Идея атаки
Расшифрование в режиме CBC проводится по следующему правилу:
$P_i = C_{i - 1} \oplus D_k(C_i)$

Обозначим I_i = D_k(C_i) , тогда $P_i = C_{i - 1} \oplus I_i$
Если I_i известно, то легко расшифровать сообщение (поскольку $C_{i - 1}$ известно). А узнать I_i можно с помощью оракула.

Пусть мы хотим расшифровать блок шифротекста. Расшифровывать будем побайтово, начиная с последнего байта.
Построим блок у которого байты B[0],...,B[14] заполним случайными значениями, а последний байт будем перебирать и отправлять сообщение B || C оракулу.

Если оракул отвечает ошибкой «Неверное дополнение», то пробуем следующий байт
Если оракул возвращает другой ответ, то мы знаем, что дополнение правильное, а значит (с большой вероятностью)

$P[15] = B[15] \oplus I[15]$ , тогда
$I[15] = B[15] \oplus P[15] = B[15] \oplus 0x01$
т. е. мы получаем I[15] , а значит можем восстановить байт исходного текста.

Для двух байтов правильное дополнение будет 0x02, 0x02 .
Чтобы восстановить I[14] мы формируем блок :
B[0],...,B[13] — произвольные значения
$B[15] = I[15] \oplus 0x02$
Теперь перебираем B[14] и посылаем на вход оракулу сообщения вида B||C . Когда оракул не выдаст ошибку, вычисляем $I[14] = B[14] \oplus 0x02$

Продолжая эту процедуру, получаем исходный текст.

Задание 18: Implement CTR, the stream cipher mode

В задание нужно реализовать режим шифрования CTR. Этот режим превращает блочный шифр в поточный.

Шифрование в режиме CTR происходит по правилу:
$C_i = P_i \oplus E_k(counter_i)$ , где — счётчик

Задание 19–20: Break fixed-nonce CTR

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

Задание 21: Implement the MT19937 Mersenne Twister RNG

Ещё одно подготовительное задание, требуется реализовать генератор псевдослучайных чисел Вихрь Мерсенна.

Задание 22: Crack an MT19937 seed

Задание демонстрирует, что начальное заполнение ГПСЧ должно быть труднопредсказуемым. Например, текущее время — не лучший выбор. Решение состоит в переборе начального заполнения, начиная от текущего времени.

Задание 23: Clone an MT19937 RNG from its output

Нужно восстановить состояние ГПСЧ Вихрь Мерсена на основе последовательности его выходов.
Для этого нужно реализовать операции, обратные реализованным в Задании 21. Задание демонстрирует, что Вихрь Мерсена не является криптографически стойким: достаточно последовательности из 624 чисел, чтобы полностью восстановить начальное состояние генератора.

Задание 24: Create the MT19937 stream cipher and break it

Нужно реализовать поточный шифр на основе Вихря Мерсена и взломать его.
Ключом такого шифра является начальное заполнение ГПСЧ. Поскольку значение маленькое, всего 16 бит, находим его простым перебором.

Блок 4: Stream crypto and randomness

Темы: MAC, хеш-функции
Ссылка: https://cryptopals.com/sets/4

Задание 25: Break «random access read/write» AES CTR

По условию дан оракул, который, который позволяет изменять текст, зашифрованный в режиме CTR:

edit(ciphertext, key, offset, newtext)

Нужно получить открытый текст.

Передаём в функцию edit текст newtext, состоящий только из нулей и равный по длине шифротексту. Так как шифрование идёт в режиме CTR, в ответ получаем гамму шифрования и расшифровываем текст.

Задание 26: CTR bitflipping

Задание демонстрирует что происходит с режимом CRT при изменении бита в зашифрованном тексте.

Решение аналогично решению для режима CBC (Задание 16). В режиме CTR каждый бит расшифровывается по формуле
$P = C \oplus K$
Поэтому если инвертировать бит в шифротексте, то он будет также инвертирован в расшифрованном тексте.

Задание 27: Recover the key from CBC with IV=Key

В режиме CBC используется два значения: ключ и инициализирующий вектор . Значение требуется генерировать случайно, но иногда этим пренебрегают и используют ключ в качестве . Задание демонстрирует, почему так делать нельзя.

Пусть IV=K . Рассмотрим шифротекст из трёх блоков: первый и третий одинаковый, а второй состоит полностью из нулей. C || 0 || C . После расшифрования в режиме CBC имеем:
$P_1 = IV \oplus D_k(C) = K \oplus D_k(C)$
$P_2 = C \oplus D_k(0)$
P_3 = D_k(C)
Тогда $P_1 \oplus P_3 = K$ — ключ шифрования найден.

Задание 28: Implement a SHA-1 keyed MAC

Ещё одно подготовительное задание. Нужно реализовать схему MAC:

MAC = SHA1(key || message)

Хеш-функцию SHA-1 стоит реализовать с нуля, это пригодится в следующих заданиях.

Задание 29–30: Break a SHA-1 keyed MAC using length extension

Задание демонстрирует уязвимость схемы MAC:

MAC = SHA1(key || message)

Алгоритм работы хеш-функции SHA-1:

Сообщения дополняется до полного блока
Блоки обрабатываются друг за другом функцией сжатия $h_i = H(m_i, h_{i-1}), h_0 = const$
Последнее значение является хешем сообщения

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

Подаём на вход оракулу original-message, получаем в ответ h = SHA1(key || original-message || padding)
Начинаем вычисление функцию SHA1 для сообщения key || original-message || padding || new-message || padding, но не со значения , а со значения
В результате получаем верное хеш-значения для сообщения key || original-message || padding || new-message

Задание 30 полностью аналогичное, только вместо SHA1 используется хеш-функция MD4.

Задание 31–32: Implement and break HMAC-SHA1 with an artificial timing leak

Задание знакомит с понятием timing-атак на примере HMAC.

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

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

Больше интересного у меня в Телеграм-канале