Техническое: протокол Диффи-Хеллмана, АНБ и конечные группы

BirdВ продолжение заметки про сеансовые ключи TLS, генерируемые по протоколу Диффи-Хеллмана (DH). Этот протокол, в классическом случае, работает на “обычной” конечной группе (современный вариант использует группу точек эллиптической кривой – см. ниже). Группа DH задаётся единственным числом – модулем. Это обязательно большое простое число. На практике веб-серверы так настроены, что используют ту или иную типовую группу (или типовой модуль, что эквивалентно). Модуль не является секретным. То есть, известна группа, используемая большинством веб-серверов, поддерживающих DH (для Рунета это более 60% веб-серверов). Эта группа является 1024-битной, что не так много.

Вся практическая полезность DH строится на сложности задачи дискретного логарифмирования (отыскания по известным A,G такого e, что A = G^e). Так вот, один из моментов, на который обратили внимание авторы атаки на TLS Logjam, состоит в том, что если у вас много ресурсов, то, в теории, для 1024-битной группы можно уже сейчас предвычислить её арифметические структуры, потратив пару лет работы суперкомпьютера и сохранив результаты в специальных таблицах. После этого вычислять дискретный логарифм можно достаточно быстро (за часы, а возможно, даже в режиме онлайн), особенно, если вы используете специальную многопроцессорную систему. Это означает, что можно расшифровать записанный ранее трафик TLS-сессий (а также других протоколов, использующих DH). Дело в том, что сеансовый ключ, если вы умеете отыскивать дискретный логарифм, элементарно вычисляется из ключа DH, который передаётся в открытом виде. Предвычислить нужную структуру можно только для известной группы, поэтому важно, чтобы TLS-серверы использовали типовые параметры. При этом, для тех, у кого ресурсов мало (кто не является специализированным агентством, например), группа остаётся вполне стойкой.

Лирическое отступление: как упоминалось выше, есть современная разновидность DH, работающая на группе точек эллиптической кривой – ECDH. Этот протокол также распространён в современных реализациях TLS. Из-за особенностей групповой операции на эллиптической кривой, отыскание дискретного логарифма в такой группе сложнее, поэтому, во-первых, можно использовать более короткие ключи, и, во-вторых, использовать общую кривую. На практике самый распространённый случай – кривая secp256r1, предлагающая 256 бит. Естественно, на ум сразу приходят теории о том, что АНБ известна пара-тройка секретных теорем, которые позволяют резко уменьшить вычислительную сложность дискретного логарифмирования на кривой secp256r1 (которая, кстати, в АНБ и сконструирована).

Самое занятное, что если группу классического DH в TLS легко поменять – модуль и генератор передаются в сообщении сервера и могут быть любыми, – то для эллиптических кривых всё сильно сложнее: параметры здесь фиксированы заранее, клиент и сервер могут договориться только о самой кривой, выбрав её из ограниченного списка. Для эллиптической криптографии уже находили эффективные оптимизации: например, существуют так называемые суперсингулярные кривые, на которых дискретное логарифмирование оказывается разрешимым на практике. (Поэтому данный тип кривых нельзя применять в качестве основы для “классического” ECDH или алгебраически родственной криптосистемы ECDSA; что, кстати, не означает неприменимость этих кривых в криптографии вообще – предложены алгоритмы электронной подписи, использующие именно суперсингулярные кривые, но это другая история.) В общем, если вы умеете “логарифмировать” на эллиптической кривой, то ECDH точно также теряет надёжность, а памяти для хранения оптимизации, вполне возможно, требуется меньше (из-за меньшей разрядности группы).

()

Похожие записки:



Далее - мнения и дискуссии

(Сообщения ниже добавляются читателями сайта, через форму, расположенную в конце страницы.)

Комментарии читателей блога: 6

  • 1. 14th August 2015, 11:47 // Читатель Roman написал:

    А вы не могли бы в конце подобных статей писать ваши рекомендации о том, какие ключи надо генерировать, чтобы не попадать под подобный вид атак?

    В идеале хотелось бы получить “правильную” консольную команду от вас.

    Заранее спасибо.

  • 2. 14th August 2015, 12:15 // Александр Венедюхин ответил:

    Постараюсь писать. Параметры для протокола Диффи-Хеллмана можно сгенерировать силами OpenSSL:

    $ openssl dhparam -out dhparams.pem 2048

    – генерируется 2048-битный модуль.

  • 3. 15th August 2015, 01:52 // Читатель Шурик написал:

    “использующие именно суперсингулярные кривые”

    А ведь это как раз интересно.

  • 4. 15th August 2015, 12:18 // Читатель Z.T. написал:

    Apache 2.4.7 сам выбирает модуль DH по размеру ключа RSA (http://blog.ivanristic.com/2013/08/increasing-dhe-strength-on-apache.html).

  • 5. 15th August 2015, 13:58 // Александр Венедюхин ответил:

    > Apache 2.4.7 сам выбирает модуль DH по размеру ключа RSA

    Да, и выбирает он из типовых модулей (правда, они все должны быть длиннее 1024 бит).

  • 6. 15th August 2015, 22:08 // Александр Венедюхин ответил:

    > А ведь это как раз интересно.

    Да, это самый современный раздел эллиптической криптографии, особенно привлекательный потому, что соответствующие криптосистемы претендуют на “квантовую” стойкость – то есть, нет эффективных взламывающих алгоритмов, работающих на квантовом компьютере. Проблема в том, что это довольно сложная область математики (между прочим, связанная с доказательством Великой теоремы Ферма). Формулировки алгоритмов, конечно, проигрывают классическому DH в доступности изложения. В основном из-за того, что оперируют “экзотическими” для современной прикладной математики объектами. Кстати, несколько лет назад была предложена криптосистема SIDH – Supersingular Isogeny Diffie-Hellman. Она использует изогении эллиптических кривых – это, грубо говоря, особые отображения (морфизмы) точек одной кривой в другую, сохраняющие заданные отношения. Есть совсем свежие предложения и по схемам электронной подписи. Может, я когда-нибудь соберусь и – смогу об этом написать подробную заметку.