Обмен ключами: Диффи — Хеллман и его атаки

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

Тема идёт от математики к протоколу. Сначала группа по простому модулю: безопасное простое p, генератор g, порядок q, вычисление общего секрета. Потом — проверка открытых значений: как атака на малую подгруппу обнуляет секрет, если сервер принимает y = 1 или y = p−1. Затем атака «человек посередине» и то, почему без аутентификации обмен ключами бесполезен. Дальше — Полиг — Хеллман и Logjam: как слабая группа и понижение версии ломают протокол целиком. Заканчивается прямой секретностью и тем, как TLS 1.3 заменил классический DH на (EC)DHE с аутентификацией подписями.

Диффи — Хеллман по простому модулю

Схема

Параметры: большое простое p, генератор g подгруппы простого порядка q, где q делит p−1. Алиса выбирает секрет a, Боб — b. Алиса отправляет A = g^a mod p, Боб — B = g^b mod p. Общий секрет: Z = B^a = A^b = g^(ab) mod p ¹.

Для стойкости нужно, чтобы p было «безопасным» простым (p = 2q + 1, q простое) либо чтобы работа велась в подгруппе простого порядка. Размер: 2048 бит и больше для классического DH, 3072 бита для долгоживущих ключей ².

Выбор группы

Стандартные группы описаны в RFC 3526 (модулярные) и RFC 7919 (ffdhe). Использование стандартной группы — не лень, а безопасность: самостоятельно выбранные параметры часто оказываются слабыми, а проверка «это безопасное простое» дорога и легко пропускается.

Проверка значений и малые подгруппы

Атака на малую подгруппу

Если сервер не проверяет присланное y, противник присылает y = 1 или y = p−1. Тогда общий секрет равен 1 или ±1 независимо от секрета жертвы, и противник знает его заранее. Дальше — расшифровать сессию или подделать сообщение.

Защита: проверить 1 < y < p−1 и y^q ≡ 1 mod p. Вторая проверка гарантирует, что y лежит в подгруппе простого порядка q, а не в маленькой подгруппе. Без неё возможны атаки, где противник подбирает y так, чтобы секрет имел мало вариантов ³.

Contribution и «честный» обмен

Протокол должен требовать, чтобы обе стороны внесли вклад: если разрешено y = 1, одна сторона может зафиксировать секрет. Проверки y^q = 1 и y ≠ 1 — часть контракта, а не «дополнительная валидация».

Человек посередине

Атака

Обмен ключами не аутентифицирует стороны. Мэллори встаёт между Алисой и Бобом: с Алисой договаривается о ключе K_1, с Бобом — о K_2, и перешифровывает трафик. Ни Алиса, ни Боб не замечают подмены, если не проверяют аутентичность ключей ⁴.

Схема на рисунке 1.

Защита

Аутентификация: подписи сторон (как в TLS с сертификатами), предварительно разделённый секрет (PSK), привязка к личности через SIGMA или подобные протоколы; систематический разбор таких конструкций есть в справочнике Менезеса, ван Оршота и Ванстоуна ⁸. Ключевое: обмен ключами даёт секретность только против пассивного противника; против активного нужна аутентификация.

Подтверждение ключа и подмена личности

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

Первое — подтверждение ключа (key confirmation): каждая сторона доказывает владение сессионным секретом, например тегом MAC по транскрипту. TLS 1.3 делает это неявно через Finished, который вычисляется из ключа рукопожатия. Этап нужен, потому что без него одна сторона может принять соединение как установленное, тогда как другая его уже прервала.

Второе — устойчивость к unknown key-share: противник подменяет не ключи, а привязку личности, и в результате Алиса уверена, что говорит с Бобом, а Боб — что с Мэллори, при том что сессионный ключ один. Защита — включать в подпись и в вывод ключей не только эфемерные значения, но и идентификаторы сторон, а также роль каждого участника. Если этого не делать, протокол может оказаться стойким к подмене ключа и при этом уязвимым к подмене личности.

Активный противник против пассивного

Разница между пассивным и активным противником — не стилистическая. Пассивный видит обмен и ничего не меняет; для него достаточно стойкости CDH. Активный вставляет свои значения, удаляет сообщения, повторяет их и переупорядочивает; для него нужна модель, в которой протокол проверяет всё, что проверить можно: принадлежность точки, допустимость группы, согласованность версии, наличие подтверждения ключа. Большинство описанных ниже атак — атаки именно активного противника.

Полиг — Хеллман и Logjam

Гладкие порядки

Если p−1 раскладывается на малые простые, дискретный логарифм считается по китайской теореме об остатках: сначала находятся x mod q_i для каждого малого q_i, затем собирается x. Это алгоритм Полига — Хеллмана. Стойкость DH требует, чтобы у p−1 был большой простой множитель ⁵.

Logjam

В 2015 году выяснилось, что многие серверы поддерживают экспортные 512-битные группы, а распространённая 1024-битная группа используется настолько широко, что её предвычисление окупается для хорошо финансируемого противника. Атака понижения версии заставляла клиента согласиться на слабую группу ⁶. Ответ — убрать экспортные шифры и перейти на 2048+ бит или ECDHE.

Прямая секретность

Что это

Прямая секретность (forward secrecy) означает: компрометация долгоживущего ключа не раскрывает прошлые сессии. Достигается тем, что сессионные ключи выводятся из эфемерных значений, которые уничтожаются после использования.

Как проверять

В работе есть записанный трафик двух сессий и «утёкший» долгоживущий ключ Боба. Если протокол использует эфемерные ключи, утечка не помогает расшифровать прошлое; если сессионный ключ выводится из долгоживущего — помогает. Схема на рисунке 2.

Как это сделано в TLS 1.3

TLS 1.3 оставил только (EC)DHE с аутентификацией подписями: эфемерные ключи на каждую сессию, обмен через X25519 или стандартные группы, вывод ключей через HKDF, обязательная проверка всех параметров ⁷. Классический RSA-обмен ключами убран: он не давал прямой секретности. Экспортные группы убраны: они давали Logjam.

Итог: обмен ключами в современном протоколе — это эфемерный DH/ECDH, аутентифицированный подписью, с выводом ключей через KDF и строгой валидацией. Каждый элемент закрывает конкретную атаку из этой темы.

Итоги темы

• Стойкость DH держится на трудности дискретного логарифма и на хорошей группе.
• Без проверки y возможны атаки на малые подгруппы и фиксация секрета.
• Без аутентификации обмен ключами ломается человеком посередине.
• Гладкий p−1 ломается Полигом — Хеллманом; слабые группы и понижение версии дали Logjam.
• Прямая секретность требует эфемерных ключей.
• TLS 1.3 собирает всё вместе: (EC)DHE, подпись, HKDF, валидация.

Литература

1. Diffie W., Hellman M. New Directions in Cryptography. IEEE Transactions on Information Theory, 1976. — исходная идея обмена ключами.
2. NIST. SP 800-56A Rev. 3: Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography. 2018. — требования к группам и проверкам.
3. RFC 7919: Negotiated Finite Field Diffie-Hellman Ephemeral Parameters. 2016. — стандартные группы и их проверка.
4. RFC 8446: TLS 1.3. 2018. — (EC)DHE, аутентификация, вывод ключей.
5. Pohlig S., Hellman M. An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance. 1978. — атака на гладкие порядки.
6. Adrian D. et al. Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. CCS 2015. — Logjam и понижение версии.
7. RFC 7748: Elliptic Curves for Security. 2016. — X25519 для эфемерного обмена.
8. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography, глава 12. — систематическое изложение протоколов обмена ключами.

Дополнительные материалы к апокрифу 11

Вопросы для самопроверки

1. Какую задачу решает обмен ключами?
2. Почему DH не требует общего секрета заранее?
3. Что такое дискретный логарифм и почему он трудный?
4. Зачем нужно безопасное простое?
5. Что даёт проверка y^q ≡ 1?
6. Почему y = 1 опасен?
7. Как работает человек посередине?
8. Какие механизмы аутентификации применимы к обмену ключами?
9. Как Полиг — Хеллман использует гладкость p−1?
10. Что такое понижение версии и как оно связано с Logjam?
11. Что такое прямая секретность?
12. Почему эфемерные ключи нужно уничтожать?
13. Что изменилось в TLS 1.3?
14. Почему X25519 удобен для эфемерного обмена?
15. Что такое PSK и когда он уместен?

Глоссарий темы

Шпаргалка

cp dh_template.py dh.py            && python3 check_dh.py
python3 bob.py &                   # сервер на 127.0.0.1
python3 alice.py                   # клиент
cp mallory_template.py mallory.py  && python3 check_mitm.py
cp ph_template.py ph.py            && python3 check_ph.py
cp fs_template.py fs.py            && python3 check_fs.py

Что почитать и посмотреть

• Diffie, Hellman 1976 — исходная статья.
• NIST SP 800-56A Rev. 3 — требования к схемам и проверкам.
• RFC 7919 — стандартные DH-группы.
• RFC 8446 — TLS 1.3: (EC)DHE, аутентификация, HKDF.
• Pohlig, Hellman 1978 — логарифм при гладком порядке.
• Adrian et al. 2015 — Logjam и реальное состояние DH в Интернете.
• Рекомендации Mozilla по TLS — https://wiki.mozilla.org/Security/Server_Side_TLS.
• Документация cryptography по обмену ключами — https://cryptography.io/en/latest/hazmat/primitives/asymmetric/ec/.

Углубление: почему аутентификация — часть обмена ключами

Обмен ключами гарантирует, что общий секрет знают только две стороны. Но «две стороны» — это те, кто участвовал в обмене, а не те, кем они себя называют. Без аутентификации Мэллори может быть одной из сторон в каждом из двух обменов, и тогда общий секрет знает она.

Отсюда правило проектирования: обмен ключами и аутентификация — один протокол, а не два независимых. В TLS это соединено: сертификат подписывает параметры обмена, и подпись проверяется до вывода ключей. В SSH — свои ключи хоста. В Signal — предварительные ключи и подписи. Разделение «сначала договоримся, потом проверим» оставляет окно для атаки.

Углубление: почему Logjam был возможен

Предвычисление для 1024-битной группы стоит дорого, но если одна и та же группа используется миллионами серверов, затраты окупаются. Logjam показал, что распространённая группа делает атаку экономически осмысленной для крупного противника, а экспортные 512-битные группы ломаются за часы.

Ответ индустрии был трёхчастным: убрать экспортные шифры, запретить группы меньше 2048 бит, перейти на ECDHE и стандартные группы с проверкой. Каждый пункт закрывает свой сценарий, и вместе они убирают класс атак, а не отдельный случай.

Лабораторная работа 11. Обмен ключами и его атаки

• Раздел курса: апокриф 11 «Обмен ключами: человек посередине, Полиг — Хеллман, Logjam»

Введение

«Сейф» договаривается о сессионных ключах по Диффи — Хеллману. Параметры взяты «свои», проверка присланных значений отсутствует, аутентификации нет — «достаточно того, что канал шифруется». Мэллори встаёт посередине и читает всё, а когда разработчик добавляет проверку, выясняется, что группа слабая и логарифм считается по Полигу — Хеллману.

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

Части: DH и параметры, проверка значений, человек посередине, Полиг — Хеллман, прямая секретность.

Цель работы

Научиться оценивать обмен ключами как протокол: какие проверки обязательны, что даёт аутентификация и почему «шифрование канала» не заменяет проверку сторон.

После выполнения работы получится:

• реализовывать DH и проверять безопасность параметров;
• показывать атаку на малую подгруппу и формулировать проверки;
• проводить атаку «человек посередине» и объяснять, почему она работает без аутентификации;
• считать дискретный логарифм по Полигу — Хеллману для гладкого порядка;
• проверять прямую секретность по записанному трафику и утёкшему ключу.

Теоретический минимум

Разделы «Диффи — Хеллман по простому модулю», «Проверка значений и малые подгруппы», «Человек посередине», «Полиг — Хеллман и Logjam», «Прямая секретность» апокрифа 11. Соотношения:

A = g^a mod p;  B = g^b mod p;  Z = B^a = A^b mod p
p = 2q + 1 (безопасное простое), q — простое
проверки: 1 < y < p−1  и  y^q ≡ 1 (mod p)
Полиг — Хеллман: x mod q_i для малых q_i, затем CRT

Перечень оснащения

Ubuntu 24.04, Python 3.10+, cryptography, OpenSSL. Права root не нужны. Все сетевые опыты — только на 127.0.0.1. Архив lr-env.

mkdir -p ~/lab-apocrypha-11 && cd ~/lab-apocrypha-11
unzip ~/lr-env.zip
cp dh_template.py dh.py
python3 check_dh.py

Заготовки копируются в файлы без суффикса _template: dh.py, mallory.py, ph.py, fs.py.

Порядок выполнения работы

В журнале фиксируйте: размер группы, результат проверки y^q ≡ 1, число запросов и время атак, восстановленный секрет. Провал проверки — с причиной: неверная проверка простоты, потерян порядок подгруппы, перепутан генератор.

Часть 1. DH и параметры

Задание

1. Реализуйте is_safe_prime, dh_keypair, validate_public, dh_shared, derive_key.
2. Проверьте на группе RFC 7919, что validate_public отвергает 1 и p−1 и принимает корректное значение.
3. Запустите python3 check_dh.py.
4. Замерьте время возведения в степень для 2048 и 3072 бит. Оцените, сколько занимает полный обмен.
5. Ответьте: почему стандартные группы предпочтительнее «своих» параметров.

Что должно получиться

Работающий DH, проходящий проверки, и замеры, показывающие цену размера группы.

Часть 2. Проверка значений и малые подгруппы

Задание

1. Покажите, что при y = 1 общий секрет равен 1, а при y = p−1 — ±1.
2. Соберите «плохой» сервер, который не проверяет y, и «хороший» с проверкой y^q ≡ 1.
3. Для плохого сервера оцените, сколько вариантов секрета может получить противник, подбирая y в малой подгруппе.
4. Ответьте: почему проверка 1 < y < p−1 недостаточна и нужна проверка порядка.
5. Сформулируйте контракт функции validate_public.

Что должно получиться

Работающая демонстрация фиксации секрета и контракт проверки.

Часть 3. Человек посередине

Задание

1. Запустите чат: python3 bob.py в одном терминале, python3 alice.py в другом.
2. Изучите chatlib.py: где происходит обмен, что именно аутентифицируется.
3. Реализуйте mallory.py: два рукопожатия, перешифрование трафика.
4. Запустите python3 check_mitm.py: противник должен прочитать сообщение.
5. Добавьте аутентификацию (PSK или подпись) и покажите, что атака ломается.
6. Ответьте: почему шифрование канала без аутентификации сторон не защищает от активного противника.

Что должно получиться

Работающая атака, затем её нейтрализация, и понимание, что аутентификация — часть обмена ключами.

Часть 4. Полиг — Хеллман

Задание

1. Изучите ph_data.json: модуль, генератор, открытое значение — и разложение p−1.
2. Реализуйте ph_template.py: для каждого малого простого q_i найдите x mod q_i перебором, затем соберите x по CRT.
3. Запустите python3 check_ph.py: секрет должен восстановиться.
4. Оцените сложность: сумма q_i против √p.
5. Ответьте: почему требование «у p−1 есть большой простой множитель» обязательно, и как Logjam использовал слабые группы.

Что должно получиться

Восстановленный секрет, оценка сложности и вывод о выборе группы.

Часть 5. Прямая секретность

Задание

1. Изучите traffic.json: два сеанса с эфемерными ключами, bob_longterm_leak.json — утёкший долгоживущий ключ.
2. Реализуйте fs.py: попробуйте расшифровать прошлые сессии, используя утечку.
3. Покажите, что при эфемерных ключах утечка не помогает, а при выводе сессионного ключа из долгоживущего — помогает.
4. Запустите python3 check_fs.py.
5. Ответьте: почему прямая секретность требует уничтожения эфемерных ключей после сессии и что произойдёт, если их хранить.

Что должно получиться

Разбор двух сценариев и понимание, что даёт эфемерность.

Журнал работы

Фиксируйте: параметры группы, результаты проверок, число рукопожатий, время Полига — Хеллмана, какие сессии удалось расшифровать. Провал — с причиной.

Контрольные вопросы

1. Как работает DH и на чём держится его стойкость?
2. Что такое безопасное простое и зачем оно нужно?
3. Почему стандартные группы лучше самостоятельно выбранных?
4. Как атака на малую подгруппу фиксирует секрет?
5. Какие проверки открытого значения обязательны?
6. Почему без аутентификации обмен ключами ломается человеком посередине?
7. Как работает Полиг — Хеллман?
8. Что показал Logjam и какой ответ нашли в индустрии?
9. Что такое прямая секретность и как она достигается?
10. Почему классический RSA-обмен ключами убрали из TLS 1.3?
11. Как в TLS 1.3 аутентифицируются стороны?
12. Что произойдёт, если хранить эфемерные ключи после сессии?