Специальные простые числа помогают пассивно прослушать протокол обмена ключами Диффи-Хеллмана
Слайд из презентации АНБ
В 2013 году благодаря Эдварду Сноудену в СМИ попали документы АНБ. Среди них — замыленный слайд из презентации, который указывал на возможности АНБ по расшифровке трафика VPN. У АНБ не было причин врать в засекреченной презентации, так что специалисты восприняли эту информацию как свидетельство наличия некоей фундаментальной уязвимости в современных системах криптографии с открытым ключом.
Основы криптографии и реализации алгоритмов пересмотрели ещё раз. Вскоре появились первые предположения. Наиболее вероятным из них было то, что фундаментальная уязвимость скрывается в практической реализации протокола Диффи-Хеллмана. А конкретно в том, что рекомендованная стандартом DSA реализация протокола подталкивает пользователей не вычислять уникальные большие модули p при генерации ключей, а использовать стандартные числа.
Например, вот рекомендованное простое число в RFC 2409.
Так и получилось на практике: до последнего времени 92% самых популярных сайтов HTTPS из списка Alexa использовали два стандартных простых числа. Протокол Диффи-Хеллмана используется также для генерации ключей, которые используются в протоколах SSH, VPN, SMTPS, IPsec и др.
Эти числа считались безопасными при достаточно большой величине простого числа (например, более 1015). Сейчас специалистам из Пенсильванского университета (США), INRIA, CNRS и Университета Лотарингии (Франция) удалось-таки доказать, что не все такие числа безопасны, так что у АНБ действительно есть теоретическая возможность расшифровки HTTPS-трафика. Криптографы на практике продемонстрировали, что специальным образом сконструированное большое простое число при использовании в качестве модуля p при генерации ключей шифрования может выступать в качестве «лазейки» (trapdoor), позволяющей узнать другие, секретные составляющие ключа и, как следствие, расшифровать секретное сообщение.
Вообще говоря, возможность использования большими группами пользователей стандартного простого числа в качестве модуля p вызвала мгновенную критику со стороны экспертов сразу же после публикации в 1991 году стандарта Digital Signature Algorithm (DSA), который предусматривал такую возможность и, фактически, поощрял такую практику.
DSA — криптографический алгоритм с использованием открытого ключа для создания электронной подписи. Подпись создается секретно, но может быть публично проверена. Алгоритм основан на вычислительной сложности взятия логарифмов в конечных полях, то есть дискретного логарифма.
Классической криптографической схемой на основе DSA является схема выработки общего ключа Диффи-Хеллмана. Её криптостойкость основывается на предположительно высокой вычислительной сложности обращения показательной функции. Как предполагали специалисты, алгоритмы вычисления дискретного логарифма имеют очень высокую сложность, которая сравнима со сложностью наиболее быстрых алгоритмов разложения чисел на множители.
Оказывается, это не совсем так. Как показали криптографы, при определённом числе p для 1024-битного ключа можно произвести вычисление дискретного логарифма за вполне обозримое время —, а именно, в 10 000 быстрее, чем теоретически рассчитано для случайных простых чисел. Исследователи сделали это за два месяца на кластере из примерно 3000 процессорных ядер в университетской сети (реальное количество машин менялось в процессе выполнения задачи).
Вопрос только в том, являются ли «стандартные» простые числа такими «лазейками» и откуда они вообще взялись. Теоретически возможно, что предварительные вычисления и составление простых чисел занимались злоумышленники. И тогда мы понимаем, что означает заявление АНБ о возможности расшифровки «триллионов зашифрованных соединений». С вычислительными мощностями в дата-центрах АНБ расшифровка сообщений займёт у них на порядки меньше, чем два месяца.
Возможность внедрения специально подобранного модуля p в стандарт не означает, что АНБ действительно реализовало эту идею. Мы не можем проверить, «хорошими» или «плохими» являются используемые сейчас простые числа, не зная алгоритма, который использует АНБ. Но если это правда, то это будет не первой попыткой АНБ ослабить стандарты публичного шифрования. Ещё не стёрлась из памяти история с генератором «случайных» чисел Dual_EC_DRBG — ГСЧ по умолчанию в RSA BSAFE и Data Protection Manager, среди прочих программ. Как показали документы Сноудена, этот генератор изначально был спроектирован с участием АНБ, чтобы выдавать предсказуемые числа.
Для защиты от потенциальных «лазеек» через специально подобранные простые числа в DSA была предусмотрена возможность выбора простых чисел «виртуально случайным» способом, с публикацией псевдослучайного «посевного значения» (seed value). Но такой возможностью сейчас де-факто практически никто не пользуется. Как уже было сказано, абсолютное большинство сайтов генерирует ключи со стандартными простыми числами, предложенными в документах для общего использования.
Самой простой защитой против возможных уязвимостей в алгоритме шифрования является выбор ключей длиной более 1024 бит, говорят авторы работы. По их расчётам, вычисление для 2048-битного ключа с таким же «ослабленным» простым числом займёт примерно в 16 млн раз больше времени, чем для 1024-битного ключа. Согласно исследованию SSL Pulse, сейчас 27,3% сайтов, использующих SSL, обмениваются ключами длиной в 1024 бита или менее.
В будущем, считают исследователи, для безопасности все простые числа должны публиковаться вместе с посевными значениями.
В общем, надо брать простые числа только из надёжных источников.
