Завершаем решение cryptopals. В этой части рассмотрим блоки заданий 5 и 6, которые посвящены криптографии с открытым ключом.

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

Блок 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

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

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

, тогда $k = 1^{ab} \bmod p = 1$
, тогда $k = p^{ab} \bmod p = 0$
, тогда $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 отличается от оригинального главным образом тем, что значение не зависит от , а значит и от пароля. Это позволяет атакующему посередине использовать произвольное в качестве ответа на запрос клиента, а затем в режиме офлайн осуществлять перебор пароля по словарю.

Задание 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 — хеш исходного сообщения

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

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

Пакет представляется в виде числа
Подписывается 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
Вторая часть демонстрирует, что нельзя использовать предсказуемые значения — это приводит к раскрытию секретного ключа

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

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

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

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

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

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

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

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

Случай $g = 0 \pmod p$ :
В этом случае проверка любой подписи для любого сообщения будет верной, потому что
$r = g ^ k \pmod p = 0$
$v = g^{u_1} y^{u_2} = 0$
И всегда совпадает с
Случай $g = 1 \pmod p$ :
В этом случае можно составить такую подпись, которая будет подходить к любому тексту:
— любое число
$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 числа. Используя этот оракул, нужно расшифровать число. Задание игрушечное, но очень полезное для понимания следующего.

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

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

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

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

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

Задание 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 с параметрами , , . Длина в байтах равна .

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

Сообщение превращается в целое число 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$ , так как имеет вид 0x00 0x02 0x00 ... 0x00
$m_0 \ge 3B$ , так как имеет вид 0x00 0x03 0x00 ... 0x00

Зная , мы можем для некоторого составить сообщение
$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$
$\frac{2B + rn}{s} \le m_0 \le \frac{3B + rn}{s}$
Что даёт новые ограничения для m_0 . Эти ограничения уточняют исходное ограничение $2B \le m_0 \le 3B$
Повторяя этот процесс, получаем единственно возможное значение m_0 .

Решение

Полагаем . Ищем такое, что сообщение $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}$ — это значение используем как отправную точку
Получаем ограничения для : $\frac{2B + rn}{s_1} \le m_0 \le \frac{3B + rn}{s_1}$
Строим пересечение полученных ограничений с текущими ограничениями

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

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

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

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

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