Автор: keltecc
Я реализовал алгоритм обмена ключами, чтобы безопасно передавать данные по сети, но он не работает. Эти спецификации слишком сложные, я запутался в коде и не могу найти ошибку. Сможете помочь мне исправить её?
nc HOST 17171
Изучим выданный файл с исходным кодом. Сервер реализует протокол Диффи-Хеллмана для получения общего секретного ключа, затем шифрует этим ключом флаг и отправляет нам полученный шифртекст. Проблема в том, что алгоритм реализован с ошибкой: сервер не отправляет свой публичный ключ клиенту. Из-за этого клиент просто не может получить общий секретный ключ, и, следовательно, расшифровать флаг.
Рассмотрим подробнее, как сервер генерирует общий секрет:
# 1. выбирает случайное число от 2 до p - 1
# это ПРИВАТНЫЙ ключ сервера
x = randrange(2, p)
# 2. принимает число от клиента
# это ПУБЛИЧНЫЙ ключ клиента
h = int(input())
# 3. вычисляет h^x (mod p)
# это общий ключ, который должен получиться у обеих сторон
shared = pow(h, x, p)
# 4. проверяет, что shared не равен 1 и -1 (mod p)
assert 1 < shared < p - 1, 'invalid shared key'Чтобы расшифровать флаг, нам нужно угадать shared, который получился у сервера. Заметим, что параметр g вообще не используется, всё зависит от числа h, которое мы отправляем серверу. Перебрать все возможные значения x не получится (их почти что p штук), поэтому нам бы хотелось как-то сократить этот диапазон.
Представим, что у нас нет последней проверки (4). В этом случае, если отправить h = 1, то shared также будет равен 1. Если отправить h = -1 (mod p) = p - 1, то shared будет равен либо 1, либо -1, в зависимости от чётности числа x. Таким образом мы смогли бы сократить перебор до двух чисел, но проверка не даёт нам этого сделать.
Вспомним, что такое порядок элемента в группе. Для числа g его порядок — это такое наименьшее число k, что g^k == 1 (mod p) (также это число k называют порядком подгруппы, образованной элементом g). Как нам это поможет? Можно заметить, что для чисел, бо́льших k, результаты "зациклятся":
g^k == 1 (mod p)
g^(k + 1) == g (mod p)
g^(k + 2) == g^2 (mod p)
...
g^(k + i) == g^i (mod p)
Это значит, что если мы хотим перебрать все возможные числа, которые могут получиться при возведении числа g во все возможные степени, нам надо перебрать только k возможных чисел:
g^1, g^2, g^3, ..., g^k
Других чисел при возведении g в степень по модулю p получиться просто не может.
Можно заметить, что наибольший возможный порядок числа g равен p - 1 — это подгруппа, содержащая все возможные числа от 1 до p - 1 (в частности, об этом говорит малая теорема Ферма). Что, если мы найдём такое число h, что его порядок будет равен какому-то маленькому числу k? В этом случае shared = h^k (mod p), и нам нужно будет перебрать всего k различных чисел.
Чтобы его найти, нам поможет теорема Коши. Она говорит о том, что если порядок группы делится на простое число k, то такая группа содержит элементы порядка k. Как мы помним, порядок нашей группы равен p - 1 (так как она содержит p - 1 элементов). Следовательно, нам нужно найти какой-то небольшой простой делитель k числа p - 1, и затем найти элемент порядка k.
Можно разложить p - 1 на множители любым способом, например сайтом factordb.com. Отправляем туда число p - 1 и получаем результат:
1031220398...62<309> = 2 · 348419 · 1479856722...49<303>
Как мы видим, полностью разложить число он не смог, но нам достаточно того, что он нашёл. В разложении есть два простых числа:
- Число
2. Элемент с таким порядком мы уже видели — это-1 (mod p), но он не проходит проверку (4) - Число
348419. Выглядит как то, что мы искали, осталось найти элемент с таким порядком
Зафиксируем k = 348419. Возьмём какое-то случайное число g и посчитаем:
h = g ^ ((p - 1) / k) (mod p)
Если h == 1, то g "плохой", и нам нужно попробовать другой g, Иначе, если h > 1, мы получили нужный элемент порядка k. Как это проверить? Посчитаем h^k (mod p):
h^k == (g ^ ((p - 1) / k)) ^ k == g ^ ((p - 1) / k * k) == g ^ (p - 1) == 1 (mod p)
h^(k + 1) == h^k * h = ... = 1 * h = h (mod p)
...
h^(k + i) == 1 * h^i == h^i (mod p)
Как мы видим, степени снова "зациклились", а значит возможных результатов возведения в степень всего k штук. Следовательно, если отправить h на сервер в качестве нашего публичного ключа, мы сможем получить k различных вариантов числа shared = h^x (mod p). А это уже можно эффективно перебрать.
Заметим, что сервер шифрует не только флаг, а целое сообщение:
f'[?] Here is your flag: {flag}'Так как размер блока AES равен 16 байт, мы можем сравнивать первые 16 байт расшифрованного текста с этим сообщением, чтобы найти верный общий ключ.
Пример решения: solver.py
Эта атака называется атакой заключения в малую подгруппу.
LetoCTF{1mp0ss1bl3_d1ff13_h3llm4n_4tt4ck}