Разбор таска baby-diffie-hellman с таск-бота Летней школы CTF 2021

!README.md

LetoCTF Taskbot 2021 | baby-diffie-hellman

Описание

Я реализовал алгоритм обмена ключами, чтобы безопасно передавать данные по сети, но он не работает. Эти спецификации слишком сложные, я запутался в коде и не могу найти ошибку. Сможете помочь мне исправить её?

nc HOST 17171

Файлы

• server.py

Решение

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

Рассмотрим подробнее, как сервер генерирует общий секрет:

# 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}

server.py

#!/usr/bin/env python3.8

from random import randrange
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad


p = 0x92d9c4cebe39e2182b2e781047320548d5dbb0471e8f62ad1f39255c6c32e38849a69e8bae661266f115686235093ae69c479787600afce8a940127d07bd28e5f26dda53d89640088558f63a42e6007c50558af642d70b2e533576a1c6c0f285a2fa94c22eea2586c253bd86804a8e7abfc3f299f5d2e1da13daed627a0db877
g = 0x2b4c217b740edb9b2491b9d7f5efaf32f3fee67b682d6e3802eb3a7fb1956073885f4a49725b543f292d6bb32af11af929b11a2deffac180f1b1ad95594bc813a26a1f70d0407a371603e06ed4418302952bf907e30979c0910ffed1ca146af3c3a223440186fd06249a85831a4ab73788ed4e90fc29a9d8875e842027bcfc22


def key_exchange() -> bytes:
    while True:
        x = randrange(2, p)
        if pow(g, x, p) > 1:
            break

    # print("[*] My public key:")
    # print(pow(g, x, p))

    print(f"[?] Please, input your public key:")
    shared = pow(int(input()), x, p)
    assert 1 < shared < p - 1, 'invalid shared key'
    
    return md5(shared.to_bytes(128, 'big')).digest()


def main(flag):
    print(f'[*] Hi!')

    key = key_exchange()
    cipher = AES.new(key, AES.MODE_ECB)
    encrypt = lambda m: cipher.encrypt(pad(m.encode(), AES.block_size)).hex()
    print(f'[+] Passed key exchange. Switching to encrypted mode...')

    print(encrypt(f'[?] Here is your flag: {flag}'))
    return


if __name__ == '__main__':
    try:
        with open('flag.txt', 'r') as file:
            flag = file.read().strip()

        main(flag)
    except Exception as e:
        print(f'[-] {e}')

solver.py

#!/usr/bin/env python3.8

from pwn import remote
from random import randrange
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad


p = 0x92d9c4cebe39e2182b2e781047320548d5dbb0471e8f62ad1f39255c6c32e38849a69e8bae661266f115686235093ae69c479787600afce8a940127d07bd28e5f26dda53d89640088558f63a42e6007c50558af642d70b2e533576a1c6c0f285a2fa94c22eea2586c253bd86804a8e7abfc3f299f5d2e1da13daed627a0db877


def main(io):
    factor = 348419
    assert (p - 1) % factor == 0
    plaintext = b'[?] Here is your flag:'[:AES.block_size]
    
    while True:
        h = pow(randrange(1, p), (p - 1) // factor, p)
        if 1 < h < p - 1:
            break
    
    io.recvline()
    io.recvline()
    io.sendline(str(h).encode())
    io.recvline()
    ciphertext = bytes.fromhex(io.recvline().strip().decode())

    for x in range(factor):
        key = md5(pow(h, x, p).to_bytes(128, 'big')).digest()
        cipher = AES.new(key, AES.MODE_ECB)
        if ciphertext.startswith(cipher.encrypt(plaintext)):
            print(unpad(cipher.decrypt(ciphertext), AES.block_size))
            break
    
    return


if __name__ == '__main__':
    with remote('0.0.0.0', 31337) as io:
        main(io)