Атака Ферма на RSA / Хабр

В 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 могут реализовывать ошибочный алгоритм, например такой:

Сгенерировать случайное простое число X;
Найти следующее простое число и присвоить его q;
Найти следующее простое число и присвоить его 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