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

Условия задач: https://cryptopals.com/
Код решений на python: https://github.com/seregablog/cryptopals

Блок 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)$ для расшифрованного текста будем использовать функцию:
$$ M(T) = \sum_{\alpha \in L} (Fr(\alpha) - En(\alpha)) ^ 2 $$

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

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

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

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

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

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

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

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

Решение:

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

Определение:

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

Пример:

Для строк 0011 и 1010 расстояние будет равно 2, так как в них различаются первый и четвёртый бит.

∎

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

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

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

Пример:

Пусть текст ‘Burn’ и длина ключа равна 3, тогда блоки будут:
(‘B’, ’n’) – шифруются первым байтом ключа
(‘u’) – шифруется вторым байтом ключа
(’n’) – шифруется третьим байтом ключа

∎

Такой шифр мы уже взламывали в Задании 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”->"="

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

Блок 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$ на оракулу.

Если оракул отвечает ошибкой “Неверное дополнение”, то пробуем следующий байт $B[15]$
Если оракул возвращает другой ответ, то мы знаем, что дополнение правильное, а значит (с большой вероятностью) $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$, где $C$ – бит шифротекста, $P$ – бит открытого текста, $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:

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

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

По заданию нужно получить верный MAC для сообщения
key || original-message || padding || new-message,
имея MAC для сообщения
key || original-message

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

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

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

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

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

Блок 5: Diffie-Hellman and friends

Темы: Протокол Диффи-Хеллмана, SRP
Ссылка: https://cryptopals.com/sets/5

Задание 33: Implement Diffie-Hellman

Подготовительное задание, которое знакомит с протоколом Диффи-Хеллмана для выработки общего сессионного ключа.

Задание 34: Implement a MITM key-fixing attack on Diffie-Hellman with parameter injection

Задание демонстрирует вариант атаки “человек посередине” в протоколе Диффи-Хеллмана.
Рассмотрим, какой общий ключ $key$ получается в результате. При нормальном выполнении протокола $key = g^b \bmod p$, но из-за противника посередине A думает, что $B=p$, поэтому
$s = B^a \bmod p = p^p \bmod p = 0$
В этом случае сессионный ключ имеет предсказуемое значение, благодаря чему M может расшифровывать сообщения.

Задание 35: Implement DH with negotiated groups, and break with malicious “g” parameters

Задание демонстрирует, что происходит с протоколом Диффи-Хеллмана при неудачном выборе параметра $g$.

Генерация сессионного ключа для участника A:
$k = B^a \bmod p = (g^b)^a \bmod p = g^{ab} \bmod p$

$g = 1$, тогда $k = 1^{ab} \bmod p = 1$
$g = p$, тогда $k = p^{ab} \bmod p = 0$
$g = p - 1$, тогда $k = {(p - 1)}^{ab} \bmod p = p - 1$ или 1

Во всех случаях значение сессионного ключа легко предсказуемо.

Задание 36: Implement Secure Remote Password (SRP)

Подготовительное задание, нужно реализовать протокол Secure Remote Password.

Задание 37: Break SRP with a zero key

Задание демонстрирует уязвимость протокола SRP в случае, если клиент использует значение $A=0\pmod N$.
В этом случае $s = (Av^u)^{b}\pmod N = 0$, и ключ будет иметь предсказуемое значение $Hash(s) = Hash(0)$.

Задание 38: Offline dictionary attack on simplified SRP

Приведённый в задании “упрощённый” протокол SRP отличается от оригинального главным образом тем, что значение $B$ не зависит от $v$, а значит и от пароля. Это позволяет атакующему посередине использовать произвольное $B$ в качестве ответа на запрос клиента, а затем в режиме офлайн осуществлять перебор пароля по словарю.

Задание 39: Implement RSA

Подготовительное задание, нужно реализовать криптосистему RSA.

Задание 40: Implement an E=3 RSA Broadcast attack

Задание демонстрирует Broadcast attack на систему RSA с небольшим $e=3$.

Если одно и то же сообщение было зашифровано на трёх различных публичных ключах RSA, то:
$c_1 = m^3 \pmod{n_1}$
$c_2 = m^3 \pmod{n_2}$
$c_3 = m^3 \pmod{n_3}$

Это система линейных сравнений по модулю, которую можно решить с помощью Китайской теоремы об остатках и найти $m^3 \pmod{n_1n_2n_3}$ . Извлекая кубический корень из полученного решения, получаем исходное сообщение.

Блок 6: RSA and DSA

Тема: Атаки на RSA и DSA
Ссылка: https://cryptopals.com/sets/6

Задание 41: Implement unpadded message recovery oracle

Задание демонстрирует мультипликативное свойство RSA:
Если $c = m^e$, то
$(s^e * c)^d \pmod n = s * m$
Это свойство можно использовать, чтобы получить от сервера подпись для сообщения, которое напрямую не передавалось. По сути это простой протокол слепой подписи.

Задание 42: Bleichenbacher’s e=3 RSA Attack

Задание посвящено атаке Bleichenbacher на PKCS1.5 RSA с $e = 3$.

Формат сообщения PKCS1.5
Cообщение PKCS1.5 имеет вид вид:
0x00 0x01 0xff 0xff ... 0xff 0xff 0x00 ASN HASH, где
ASN – служебная информация, определяющая хеш-функцию
HASH – хеш исходного сообщения

Длина сообщения в байтах должна быть равна длине модуля $n$ (это обеспечивается нужным количеством байтов 0xff).

Подпись сообщения
Подписанный пакет формируется так:

Пакет представляется в виде числа $m$
Подписывается RSA: $s = m^d \pmod n$

Проверка подписи
При проверке подписи сообщения подпись снимается $m = s^e \pmod n$, затем проверяется хеш исходного сообщения.

Атака
Атака становится возможной из-за ошибки при реализации разбора сообщения.

Алгоритм разбора с ошибкой:

Найти байты 0x00, 0x01
Найти следующий за ними байт 0x00
Разобрать ASN, узнать длину хеша
Получить нужное количество байт хеша
Сверить хеш

Ошибка состоит в том, что не проверяется ни длина сообщения, ни корректность заполнения. Поэтому сообщения вида 0x00 0x01 0x00 ASN.1 HASH SOMEBYTES также будут успешно разобраны парсером.

Чтобы подделать подпись, необходимо получить такое сообщение, чтобы при возведении в куб оно имело вид 0x00 0x01 ... 0x00 ASN.1 HASH SOMEBYTES.

Составляем сообщение 0x00 0x01 0x00 ASN.1 HASH 0x00...0x00
Извлекаем из него кубический корень

Задание 43: DSA key recovery from nonce

Задание состоит из двух частей:

Первая часть – реализация протокола DSA
Вторая часть демонстрирует, что нельзя использовать предсказуемые значения $k$ – это приводит к раскрытию секретного ключа

Если $k$ известно, то секретный ключ легко вычислить:
$x = (r^{-1} \pmod q * (k * s - h)) \pmod q$

В задании $k$ лежит в отрезке $[1, 2^{16}]$, поэтому находим его перебором.

Внимание: в задании $r$ и $s$ указаны в десятичной системе счисления, в то время как остальные числа – в шестнадцатеричной.

Задание 44: DSA nonce recovery from repeated nonce

Задание демонстрирует, что нельзя использовать повторяющиеся значения $k$ для различных сообщений при использовании подписи DSA – это приводит к раскрытию секретного ключа.

Если $k$ одинаковые, то $r = g^k \pmod p \pmod q$ также будут одинаковые. Находим в файле два сообщения с одинаковым $r$
Рассчитываем $k = (m_1 - m_2) * (s_1 - s_2)^{-1} \pmod q$
Рассчитываем $x$ по известному $k$, как в Задании 43

Задание 45: DSA parameter tampering

Задание показывает, что важно тщательно проверять параметры, которые используются в подписи DSA.

Случай $g = 0 \pmod p$:
В этом случае проверка любой подписи для любого сообщения будет верной, потому что
$r = g ^ k \pmod p = 0$
$v = g^{u_1} y^{u_2} = 0$
И $v$ всегда совпадает с $r$
Случай $g = 1 \pmod p$:
В этом случае можно составить такую подпись, которая будет подходить к любому тексту:
$z$ – любое число
$r = y ^ z \pmod p \pmod q$
$s = r z^{-1} \pmod q$

Тогда при проверке: $v = g^{u_1} y^{u_2} = y^{u_2} = y^{rw} = y^{rr^{-1}z} = y^z = r$

Задание 46: RSA parity oracle

Дан оракул, который определяет чётность зашифрованного с помощью RSA числа. Используя этот оракул, нужно расшифровать число. Задание игрушечное, но очень полезное для понимания следующего.

Пусть $m$ – исходное число
$E(m) = c = m^e \pmod n$ – зашифрованное число

Мы можем получить зашифрованный текст для сообщения $2m$:
$c’ = c * 2^e \pmod n = (2m)^e \pmod n = E(2m)$

Подаём это сообщение на вход оракулу:

Если ответ, что число нечётное, значит сообщение превосходит $n$ (так как $n$ – нечётное, остаток без превышения должен быть нечётным), а значит $m \ge n / 2$
Если ответ чётное, значит $m \le n / 2$

Изначально известно, что $0 \le m \le n$. Повторяя эту операцию для $4m$, $8m$,… находим $m$.

Задание 47-48: Bleichenbacher’s PKCS 1.5 Padding Oracle

Это задание сложнее, чем все остальные вместе взятые. Требуется реализовать атаку, описанную в статье “Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1”, Daniel Bleichenbacher.

Формат PKCS
Используется RSA с параметрами $e$, $d$, $n$. Длина $n$ в байтах равна $k$.

Структура сообщения PKCS:
0x00 0x02 PAD 0x00 DATA, где:
0x00 0x02 – фиксированное начало
PAD – заполнение случайными ненулевыми байтами
0x00 – нулевой байт, признак начала данных
DATA – данные
Общая длина сообщения равна в точности $k$.

Сообщение превращается в целое число $m_0$ и шифруется $c = m_0^e \pmod n$.

Описание атаки
Атака возможна из-з недостатка реализации расшифровки и разбора сообщения PKCS. Она заключается в том, что парсер сразу выдаёт какую-то особую ошибку, если первые два байта сообщения не равны 0x00 0x02. Это позволяет атакующему получить информацию о первых байтах сообщения.

Обозначим $B =$ 0x00 0x01 0x00 ... 0x00 , в десятичной форме $B = 2^{8(k-2)}$
Так как в сообщении $m_0$ первые два байта равны 0x00 0x02, то известно, что

$2B \le m_0$, так как $2B$ имеет вид 0x00 0x02 0x00 ... 0x00
$m_0 \ge 3B$, так как $3B$ имеет вид 0x00 0x03 0x00 ... 0x00

Зная $c$, мы можем для некоторого $s$ составить сообщение
$c_1 = m_1^e \pmod n = (m_0 * s)^e \pmod n = c * s^e \pmod n$
Если сообщение $c_1$ не вызывает ошибки, то первые два байта в $m_1 = c_1 ^ d \pmod n$ равны 0x00 0x02, значит $2B \le m_1 \le 3B$, следовательно
$2B \le m_0s - rn \le 3B$, для любых целых $r$ и
$\frac{2B + rn}{s} \le m_0 \le \frac{3B + rn}{s}$
Что даёт новые ограничения для $m_0$. Эти ограничения уточняют исходное ограничение $2B \le m_0 \le 3B$
Повторяя этот процесс, получаем единственно возможное значение $m_0$.

Решение

Полагаем $M = ([2B, 3B])$. Ищем $s_1$ такое, что сообщение $c_1 = s_1^e * m_0 \pmod n$ не вызовет ошибки.
В силу того, что $r = \frac{m_0s_1 - m_1}{n}$, $r \le \frac{3Bs_1 - 2B}{n} =\frac{3Bs_1}{n}$. И чтобы $r \ge 1$ должно выполняться $s_1 > \frac{n}{3B}$ – это значение $s_1$ используем как отправную точку
Получаем ограничения для $m_0$: $\frac{2B + rn}{s_1} \le m_0 \le \frac{3B + rn}{s_1}$
Строим пересечение полученных ограничений с текущими ограничениями

Далее возможны три случая:

$M$ состоит из более чем одного отрезка. В этом случае мы находим значение $s_{i + 1} > s_i$, получаем ограничения для $m_0$ и переходим на шаг 3.
$M$ состоит ровно из одного отрезка, который состоит из одной точки. Тогда $m_0$ найдено
$M$ состоит ровно из одного отрезка $[a, b]$. Тогда применяется оптимизация поиска:
находим $s_i$ такое, что $\frac{2B + r_in}{b} \le s_i \le \frac{3B + r_in}{a}$ (при этом $r_i \ge \frac{2bs_{i - 1} - 2B}{n}$). Получаем ограничения для $m_0$ и переходим на шаг 3.

Блок 1: Basic#

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

Задание 2: Fixed XOR#

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

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

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

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

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

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

Блок 2: Block crypto#

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

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

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

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

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

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

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

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

Блок 3: Block & stream crypto#

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

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

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

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

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

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

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

Блок 4: Stream crypto and randomness#

Задание 25: Break “random access read/write” AES CTR#

Задание 26: CTR bitflipping#

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

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

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

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

Блок 5: Diffie-Hellman and friends#

Задание 33: Implement Diffie-Hellman#

Задание 34: Implement a MITM key-fixing attack on Diffie-Hellman with parameter injection#

Задание 35: Implement DH with negotiated groups, and break with malicious “g” parameters#

Задание 36: Implement Secure Remote Password (SRP)#

Задание 37: Break SRP with a zero key#

Задание 38: Offline dictionary attack on simplified SRP#

Задание 39: Implement RSA#

Задание 40: Implement an E=3 RSA Broadcast attack#

Блок 6: RSA and DSA#

Задание 41: Implement unpadded message recovery oracle#

Задание 42: Bleichenbacher’s e=3 RSA Attack#

Задание 43: DSA key recovery from nonce#

Задание 44: DSA nonce recovery from repeated nonce#

Задание 45: DSA parameter tampering#

Задание 46: RSA parity oracle#

Задание 47-48: Bleichenbacher’s PKCS 1.5 Padding Oracle#