Продолжаем решать задания 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 можно с помощью оракула.

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

  • Если оракул отвечает ошибкой «Неверное дополнение», то пробуем следующий байт

  • Если оракул возвращает другой ответ, то мы знаем, что дополнение правильное, а значит (с большой вероятностью) P[15] = 0x01

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:
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), где 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. Значение IV требуется генерировать случайно, но иногда этим пренебрегают и используют ключ в качестве IV. Задание демонстрирует, почему так делать нельзя.

Пусть 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:

  1. Сообщения дополняется до полного блока

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

  3. Последнее значение h является хешем сообщения

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

  1. Подаём на вход оракулу original-message, получаем в ответ h = SHA1(key || original-message || padding)

  2. Начинаем вычисление функцию SHA1 для сообщения key || original-message || padding || new-message || padding но не со значения h_0, а со значения h

  3. В результате получаем верное хеш-значения для сообщения 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


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

Комментарии (0)