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

Продолжаем решать задания 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

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

Источник: https://habr.com/ru/articles/803077/

Вернуться к списку

Интересные статьи

Что такое «хорошо» и что такое «плохо» в NiFi. Часть 3

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

Как сделать удобную дизайн-систему. Цвета. Часть 1

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

Неочевидные уязвимости онлайн сервисов. Часть первая

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

Data Science vs COVID-19_Часть 3

Всем привет. Выходим на финишную прямую: сегодня финальная статья о том, какие ответы может дать data science о прогнозировании COVID-19. Первая статья здесь. Вторая здесь. Сегодн...

Автоматизация Для Самых Маленьких. Часть Вторая. Дизайн сети

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