Анонсирован проект Phuctor, коллайдер RSA ключей
Введен в строй публичный сервис Phuctor (The RSA Super Collider), позволяющий оценить надежность используемых RSA-ключей и получить сведения о проблемных ключах, используемых в подписях PGP/GPG. Phuctor позволяет оценить потенциальную возможность компрометации закрытого ключа на основании анализа открытого ключа.
Phuctor использует усовершенствованный алгоритм факторизации ключей, предложенный Дэниелем Бернштейном (Daniel J. Bernstein), позволяющий выявить проблемы с генерацией простых чисел, используемых при создании ключей. Система проверяет применение для начальных коэффициентов непростых чисел и выявляет использование в разных ключах одинаковых цикличных коэффициентов (модуль), что может указывать на возможное наличие дубликатов закрытого ключа.
Как правило, проблемы с ключами возникают при использовании ненадежных генераторов случайных чисел для создания ключа, выдающих предсказуемые повторяемые последовательности. В настоящее время в БД проекта уже занесена информация о 1.8 млн модулей. В 858 случаях выявлены дубликаты. Для 222 ключей удалось факторизировать начальные параметры генерации ключа, т. е. фактически для данных ключей можно подобрать закрытый ключ.
Интересно, что среди владельцев скомпрометированных ключей встречаются достаточно известные деятели, например, в списке проблемных ключей присутствуют сотрудники NASA, Red Hat, Apple ([email protected]!), Фонда СПО, IEEE, Intel, Debian (цифровая подпись для репозитория debian.sur5r.net) Отдельно выделяются проблемы с ключами PGP Corporation, используемыми в сервисе обновления ключей ([email protected]) и сервисе каталогов ("PGP Global Directory Verification Key").
Напомним, что в основе шифрования RSA лежит операция возведения в степень по модулю большого числа. В открытом ключе содержится модуль и степень. Модуль формируется на основании двух случайных простых чисел, которые известны только владельцу закрытого ключа. Таким образом наличие открытого ключа и знание одного из начальных простых чисел позволяет полностью восстановить закрытый ключ. В случае если в разных открытых ключах используется один и тот же модуль, то это свидетельствует либо о недостаточном размере энтропии при генерации случайных чисел, либо о наличии бэкдора в определенной реализации GPG.
