Арьен Ленстра: мы обнаружили 12 720 абсолютно ненадежных 1024-разрядных ключа. Источник: epfl.ch
Арьен Ленстра: мы обнаружили 12 720 абсолютно ненадежных 1024-разрядных ключа. Источник: epfl.ch

Недавно в Интернете был опубликован научный доклад группы видных криптоаналитиков, в котором алгоритм шифрования RSA назван уязвимым. Компания RSA, ныне являющаяся подразделением по информационной безопасности EMC, отреагировала опровержением, заявив, что приведенные в докладе данные указывают не на фундаментальный дефект в самом алгоритме, а скорее на недоработки в его реализациях.

«14 февраля к публикации был представлен научный доклад, утверждающий, что в алгоритме шифрования RSA обнаружена предполагаемая брешь, — говорится в заявлении специалистов RSA. — Проведенный нами анализ показал, что информация из доклада не указывает на существование дефектов в самом алгоритме, а лишь подчеркивает важность его грамотных реализаций, в особенности учитывая взрывной рост числа встроенных систем, подключающихся сегодня к Интернету».

Главный научный сотрудник RSA Ари Джулс полагает, что доклад полезен, так как указывает на «ошибки использования криптопротоколов, совершаемые при генерации случайных чисел». Однако по мнению Джулса, главная идея доклада о том, что сам алгоритм RSA уязвим, неверна: «Замечу, что любой криптографический алгоритм зависит от качества генерации случайных чисел. Если использован неудачный способ их получения, протокол дает сбой. Авторы доклада приходят к выводу о том, что алгоритм RSA может быть менее надежным, чем другие, однако очевидно, что недоработки при этом свойственны не самому RSA, а способу создания ключей».

Джулс отметил, что сегодня в ИТ-индустрии данная проблема прорабатывается, и что корпорация Intel даже реализовала быстрый генератор случайных чисел в своей новой процессорной микроархитектуре Ivy Bridge.

О докладе до его публикации RSA не уведомляли. В официальном заявлении компания не стала оспаривать детали этой работы. Ее авторы — криптографы Арьен Ленстра, Джеймс Хьюз, Максим Ожье, Еппе Бос, Торстен Клейнюнг и Кристоф Вахтер. Доклад озаглавлен «Рон ошибался, а Уит был прав» — отсылка на Рона Ривеста, одного из авторов алгоритма RSA, и видного криптографа Уитфилда Диффи. В ходе подготовки доклада авторы проверили на надежность несколько миллионов цифровых сертификатов стандарта X.509, собранных ими в Web. На основании результатов анализа исследователи пришли к выводу о том, что «1024-разрядный RSA в лучшем случае обеспечивает надежность 99,8%».

Авторы уточняют, что собрали 6,4 млн цифровых сертификатов и PGP-ключей, и в 1% случаев обнаружили совпадающие модули (произведения двух случайных простых чисел, используемых для генерации ключей и входящие в их состав). «Более того, мы обнаружили 12 720 абсолютно ненадежных 1024-разрядных модуля», — сообщают исследователи.

В опровержении специалисты RSA заявляют: «Мы приветствуем исследования такого рода, так как они вносят вклад в развитие технологий безопасности, однако алгоритм RSA доказал свою надежность, выдержав уже немало тщательных проверок, выполнявшихся различными исследователями. Надежность криптографии в большой степени зависит от качества реализации. Генерация истинно случайных чисел лежит в основе практически всех криптографических алгоритмов и протоколов, и должна выполняться грамотно, чтобы не ухудшить надежность шифрования. Проведенный нами анализ указывает на потребность в более тщательном подходе к реализации генераторов случайных чисел, особенно с учетом распространения встроенных систем. Мы не видим конструктивных недостатков в самом алгоритме RSA и призываем всех пользователей криптографии придерживаться только качественных реализаций и оптимальных методов».

Позицию RSA поддержал видный исследователь информационной безопасности Дэн Камински, который в своем блоге опубликовал пост по поводу доклада.

«Ленстра и Хьюс — авторитетные криптографы, — пишет Камински, — которые проделали превосходную обзорную работу, изучив в общей сложности 11,7 млн открытых ключей». Исследователь принципиально отвергает главный тезис доклада: «Не вижу никакой причинно-следственной связи между результатами, которые получили авторы, и главным тезисом этой работы. В целом риск в криптографии определяется в первую очередь не выбором шифра, а особенностями управления ключами. Исследователи нашли 12 720 открытых ключей и примерно 2,94 млн сертификатов с истекшим сроком действия. В докладе не указано количество сертификатов, которым изначально не было причины доверять (так как они были самозаверенными), но говорится о 5,4 млн PGP-ключей.

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

Доклад составлен по итогам обзорной работы, в ходе которой было эмпирически установлено наличие дефектов реализации (найдены 12 720 уязвимых для взлома ключей). Из этого делается вывод о конструктивном дефекте схемы открытого ключа, причем в качестве аргумента используется предположение о том, что таким алгоритмам свойственны ненадежные ключи».

Камински указал, что его не убеждают заключения, к которым пришли авторы доклада: «Не хочу слишком строго судить эту работу, в которой, повторюсь, содержатся ценные данные и их анализ. Я всегда был сторонником сбора эмпирических данных, так как на мой взгляд, специалисты по безопасности исходят из предположений и слухов чаще, чем это хотелось бы признать. Но с другой стороны, не следует пытаться подгонять полученные данные под предположения».