RSS Блог "След бит"
Подписаться
Факторизация RSA-ключей «короткого рукава» с полиномами
Исследователи обнаружили, что некоторые частные ключи RSA имеют биты, сильно смещенные в сторону 0, что можно обнаружить и факторизовать быстро. Вместе с Ханно Бёком из проекта badkeys они нашли сотни уникальных ключей с этим свойством и проанализировали исторические данные, чтобы отслеживать проблему во времени. Шаблон битов 0 в этих ключах часто высоко структурирован, что позволяет разработать полиномиальную криптоаналитическую технику для использования этого шаблона. Исследователи выявили два шаблона модулей RSA с повторяющимися блоками битов 0, при этом один шаблон остался необъяснённым, а другой был отслежен до несоответствия типов в коде больших целых чисел в старых версиях программного обеспечения CompleteFTP для передачи файлов. Ошибка CompleteFTP также генерировала уязвимые короткие ключи DSA, и исследователи восстановили 603 уникальных частных ключа RSA и 74 ключа DSA из интернет-сканирований. Проект badkeys - это открытый сервис, который проверяет открытые ключи на наличие известных уязвимостей, и, выполнив поиск в наборе реальных ключей, исследователи обнаружили большое количество ключей в дикой природе с этими шаблонами. Исследователи обратным инжинирингом обнаружили уязвимость CompleteFTP и обнаружили, что она была вызвана несоответствием между размером сегментов и размером вывода генератора случайных чисел. Уязвимость была устранена после того, как команда CompleteFTP выпустила обновление, которое автоматически проверяет уязвимые ключи и оповещает пользователя, если ключ необходимо регенерировать. Исследователи также разработали технику факторизации целых чисел, представляя их как полиномы, которую можно использовать для факторизации общих модулей RSA. Обнаружение этих уязвимостей подчеркивает важность практических исследований и необходимость постоянного мониторинга криптографических реализаций для выявления и устранения потенциальных слабостей.
