В 1643 году Пьер де Ферма предложил метод факторизации. Этот метод позволяет эффективно раскладывать целые числа на простые множители.

Алгоритм шифрования и подписи RSA основывается на том, что факторизация — это задача с высокой сложностью. Открытый ключ RSA содержит составное число (обычно называемое N), которое является произведение двух простых чисел (обычно p и q).

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

Я применил метод факторизации Ферма к большим наборам открытых ключей RSA. И я смог обнаружить небольшое количество уязвимых ключей, которые принадлежали принтерам Canon и Fujifilm (первоначально выпускавшихся под маркой Fuji Xerox). В этих устройствах используется криптографический модуль от компании Rambus.

Что такое метод факторизации Ферма? 

Идея метода состоит в том, что произведение двух простых чисел можно представить в виде N=(A-B)(A+B), где A — это среднее арифметическое двух простых чисел (A=(p+q)/2), а B — это расстояние от A до искомых простых чисел (B=p-a=a-q).

Если простые числа находятся близко друг к другу, то и A близко к квадратному корню из N. Это позволяет определить значение A путем перебора: начать с квадратного корня из N и увеличивать потенциальное значение A на единицу в каждой итерации.

Для каждой итерации мы можем вычислить B^2 = A^2 — N. Если результат является квадратом, то мы угадали A. И теперь можем вычислить p=A+B и q = A-B.

Первоначально Ферма описал этот метод в своём письме, датированным 1643 годом. Текст оригинального письма можно найти в Oeuvres de Fermat, на 256 странице.

Кто пострадавший?

Несколько принтеров серий Fujifilm Apeos, DocuCentre и DocuPrint генерируют самозаверяющие сертификаты TLS с уязвимыми ключами RSA. Информационный бюллетень Fuji содержит список всех затронутых принтеров.

Некоторые принтеры Canon генерируют запрос на подпись сертификаты с помощью уязвимого ключа RSA. Насколько мне известно, это влияет на принтеры серий imageRUNNER и imagePROGRAF. 

Как принтеры Fujifilm, так и принтеры Canon используют криптографический модуль библиотеки Safezone от Rambus. Другие продукты, использующие этот модуль для создания ключей RSA, также могут быть затронуты. Код этой уязвимости — CVE-2022-26320.

Является ли это уязвимостью алгоритма RSA.

Нет, не является. Библиотеки RSA с корректной функцией генерации ключей эта уязвимость не затрагивает.

Как это происходит

Ключ RSA уязвим, если два простых числа p и q находятся близко. Если простые числа генерируются независимо друг от друга и случайным образом, то вероятность того, что они будут близки, ничтожно мала. 

Однако функции генерации ключей RSA могут реализовывать ошибочный алгоритм, например такой:

1. Сгенерировать случайное простое число X;
2. Найти следующее простое число и присвоить его q;
3. Найти следующее простое число и присвоить его p;

Для стандартных размеров ключей RSA разница p и q — тысячи или меньше. Такой алгоритм является уязвимым для метода факторизации Ферма.

Какой должна быть разница простых чисел, чтобы ключ RSA был уязвим?

При обычных размерах ключей RSA в 2048 бит метод ферма со 100 итерациями надежно факторизует числа, где разница p и q меньше 2^517. Другими словами, простые числа, различающиеся только младшими 64 байтами, будут уязвимы. Можно было бы возразить, что 100 итераций — это слишком много, однако алгоритм настолько быстр, что на практике это не будет иметь большого значения.

Могут ли случайно сгенерированные ключи быть уязвимы?

Да, могут. Но для этого необходимо, чтобы они были идентичны, по меньшей мере, в своих старших 500 битах. Вероятность такого исхода — 1:2^500.

Как ты нашел ключи?

Я использовал несколько наборов открытых ключей:

• к которым у меня был доступ;
• которые были предоставлены другими исследователями;
• которые были общедоступны.

Я обнаружил уязвимые ключи Fujifilm в недавних сканированиях TLS-сертификатов Rapid7. Ещё некоторое количество сертификатов я обнаружил в логах Certificate Transparency. Связавшись с их владельцами, я узнал о принтерах Canon.

Как оказалось, все уязвимые сертификаты были относительно недавнего происхождения (2020 год и позже). Я думаю, по этой причине такие уязвимости не были описаны ранее.

Что с SSH?

Скорее всего, уязвимых реализаций SSH, создающих такие ключи, нет. Хотя я и не могу это доказать.

Я проверил несколько больших наборов ключей хоста и пользователя SSH, но ничего не обнаружил.

Затронуты ли PGP/GnuPG/OpenPGP?

Я применил метод к дампу серверов ключей SKS PGP и нашел четыре уязвимых ключа. Однако все ключи были с идентификатором пользователя, который подразумевал, что они были созданы для тестирования.

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

Рекомендации

Если вы используете уязвимое устройство, то убедитесь, что вы обновили их и повторно сгенерировали ключи.

Если внешние пользователи предоставляют вам открытые ключи RSA, то вы можете реализовать проверку на наличие этой уязвимости. Типичный случай — центр сертификации. Я поделился кодом эксплойта с такими центрами и некоторые из них реализовывали проверки в процессе выдачи сертификатов, дабы избежать принятия уязвимых ключей.