Специальные простые числа помогают пассивно прослушать протокол обмена ключами Диффи-Хеллмана


    Слайд из презентации АНБ

    В 2013 году благодаря Эдварду Сноудену в СМИ попали документы АНБ. Среди них — замыленный слайд из презентации, который указывал на возможности АНБ по расшифровке трафика VPN. У АНБ не было причин врать в засекреченной презентации, так что специалисты восприняли эту информацию как свидетельство наличия некоей фундаментальной уязвимости в современных системах криптографии с открытым ключом.

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

    Например, вот рекомендованное простое число в RFC 2409.



    Так и получилось на практике: до последнего времени 92% самых популярных сайтов HTTPS из списка Alexa использовали два стандартных простых числа. Протокол Диффи-Хеллмана используется также для генерации ключей, которые используются в протоколах SSH, VPN, SMTPS, IPsec и др.

    Эти числа считались безопасными при достаточно большой величине простого числа. Сейчас специалистам из Пенсильванского университета (США), 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 бита или менее.

    В будущем, считают исследователи, для безопасности все простые числа должны публиковаться вместе с посевными значениями.

    В общем, надо брать простые числа только из надёжных источников.
    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 11
    • +7
      <чешет за ушком свой 4096-битный ключ>
      • +2
        В общем, надо брать простые числа только из надёжных источников.


        Ага. Из официальных RFC, например. :-D
          • 0
            Эти числа считались безопасными при достаточно большой величине простого числа (например, более 10^15


            Вообще-то 1024 бита это примерно 10^308.

            Добавлю ещё, что основная фишка того ресёрча в том, что они показали существование слабых безопасных простых. Среди произвольных простых найти слабое число для DH (в т.ч. и бэкдор) намного проще.
            • +1
              В общем, надо брать простые числа только из надёжных источников.


              Ну рецепт стар как мир: надо использовать то, что называется 'доказуемая псевдослучайность', например выработка параметров с использованием криптографических функций хэширования с известными входными значениями. Вместе с параметрами публикуете алгоритм выработки и его начальные значения.
              • 0
                DH длиной 1024 и менее сейчас и так не считается безопасным
                • +1
                  Если взгянуть на документ — то там рекомендуют вообще отказаться от алгоритма Диффи-Хеллмана в пользу эллиптических кривых (ECDH).
                  • 0

                    С патентами на эллиптическую криптографии уже всё нормально?

                    • 0
                      Верба-W, КриптоПро и иже с ними никаких проблем с патентами не испытывают…
                      • 0

                        Не думаю, что у этих продуктов основной рынок сбыта это США. Патенты там были американские.

                        • +1
                          Если вы насчет этой заметки — то там есть ссылка на патент — и там есть очаровательная фраза:-
                          Each generated public/private key pair can be verified efficiently to be escrowed properly by anyone. The verification procedure does not use the private key.


                          То есть при верификации вообще не используется закрытый ключ! То есть к эллиптическим кривым данный патент имеет весьма отдаленное отношение…

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.