19.11 // Все ассиметричные алгоритмы могут быть взломаны за одну операцию из-за закладки в процессорах

Один из изобретателей алгоритма RSA и широко известный криптограф Ади Шамир из израильского института Вейцмана, предложил способ атаки, позволяющий мгновенно взломать все системы, построенные на алгоритмах RSA, проблемме вычисления дискретных логарифмов и основаных на проведении вычислений в эллиптических кривых.

Атака основана на предположении, что в процессор внесена закладка, которая выдаёт неверный результат при умножении двух определённых чисел, отличающийся хотя бы на один бит. Чтобы обнаружить эту закладку чисто программным путём, нужно найти эти числа методом перебора всех вариантов умножения, что практически невозможно, так как возможное число пар 64x64-битного умножителя составляет 2¹²⁸.

Обнаружить такой дефект в операции умножения сложная задача и при дорогостоящем физическом исследовании закрытого железа (например процессоров Intel) из-за чрезмерной сложности современных микросхем. Дефект умножителя может быть внедрён также в процессоры мобильных телефонов, смарт-кард и любых устройств, где производятся криптографические вычисления.

Для проведения атаки достаточно знания пары чисел, являющихся секретным ключём дефекта умножителя и всего одного подобранного сообщения.

Вскрытие ассиметричных алгоритмов возможно также при случайном дефекте процессора, не только в процессе его производства, но и эксплуатации, однако тогда он должен быть выявлен на специальном оборудовании.

Шамир приводит вариант вскрытия на примере алгоритма RSA:

Пусть расшифрование или подпись осуществляется на основе китайской теоремы об остатках (CRT). При этом умножаемые числа будут разбиты на слова в соответствии с разрядностью процессора (32 или 64 бита).
Зная n – открытый ключ цели, атакующий вычислит число c, которое будет равно половине разряда и будет гарантированно находиться между секретными множителями p и q для числа n. Например, квадратный корень из n, округлённый до целого значения будет удовлетворять этому условию. Атакующий выбирает сообщение m, эквивалентное c, за исключением младших слов, которые заменяет на специально подобранные a и b и отправляет "отравленное" сообщение получателю.

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

Создатели библиотеки Crypto++ и авторы некоторых реализаций openPGP утверждают, что их программы неподверженны данной атаке, так ак используют дополнительные проверки.

Однако, использование закрытного аппаратного обеспечения ставит под сомнение возможность корректного исполнения на нём криптографических вычислений. В критических случаях для этого необходимо изготовление криптопроцессоров на собственном производстве.

Источник: Cryptome