19.11 // Все ассиметричные алгоритмы могут быть взломаны за одну операцию из-за закладки в процессорах
Один из изобретателей алгоритма RSA и широко известный криптограф Ади Шамир из израильского института Вейцмана предложил способ атаки, позволяющий мгновенно взломать все системы, построенные на алгоритмах RSA, проблеме вычисления дискретных логарифмов и основанных на проведении вычислений в эллиптических кривых.
Атака основана на предположении, что в процессор внесена закладка, которая выдаёт неверный результат при умножении двух определённых чисел, отличающийся хотя бы на один бит. Чтобы обнаружить эту закладку чисто программным путём, нужно найти эти числа методом перебора всех вариантов умножения, что практически невозможно, так как возможное число пар 64x64-битного умножителя составляет 2128.
Обнаружить такой дефект в операции умножения — сложная задача и при дорогостоящем физическом исследовании закрытого железа (например, процессоров Intel) из-за чрезмерной сложности современных микросхем. Дефект умножителя может быть внедрён также в процессоры мобильных телефонов, смарт-кард и любых устройств, где производятся криптографические вычисления.
Вскрытие асимметричных алгоритмов возможно также при случайном дефекте процессора, не только в процессе его производства, но и эксплуатации, однако тогда он должен быть выявлен на специальном оборудовании.
Для проведения атаки достаточно знания пары чисел, являющихся секретным ключём дефекта умножителя, и всего одного подобранного сообщения. Шамир приводит вариант вскрытия на примере алгоритма RSA:
Пусть расшифрование или подпись осуществляется на основе китайской теоремы об остатках (CRT). При этом умножаемые числа будут разбиты на слова в соответствии с разрядностью процессора (32 или 64 бита). Зная n — открытый ключ цели, — атакующий вычислит число c, которое будет равно половине разряда и будет гарантированно находиться между секретными множителями p и q для числа n. Например, квадратный корень из n, округлённый до целого значения, будет удовлетворять этому условию. Атакующий выбирает сообщение m, эквивалентное c, за исключением младших слов, которые заменяет на специально подобранные a и b, и отправляет "отравленное" сообщение получателю.
Используя дальнейшие вычисления атакующий может извлечь секретный ключ из подписи или зашифрованного сообщения адресата за одну криптографическую операцию.
Первым шагом в вычислении, основанном на китайской теореме об остатках, является редуцирование значения m по модулю p и q.
В соответствии с этим выбором, m будет иметь случайное значение по модулю относительно малого значения p, но останется неизменным по модулю по отношению к большому q. Следующим шагом в RSA-CRT всегда является извлечение квадратного корня редуцированного входного значения по модулю p и q.
Поскольку маловероятно, что a и b останутся в рандомизированном значении m mod(p), вычисление mod p вероятно будет корректным. Таким образом mod q в операции извлечения корня будет содержать шаг, в котором слово a будет умножено на слово b и, в соответствии с нашим предположением, результат умножения будет неверным хотя бы на один бит.
Подразумевая, что оставшиеся из двух вычислений mod p или q будут правильными, окончательный результат двух возведений в степень будет содержаться в одном выходе y, который вероятно будет верным по модулю p, но неверным по модулю q.
Атакующий может завершить свою атаку, тем же путём, каким проводится оригинальная атака на отказ в оборудовании, вычисляя наибольший общий делитель n по отношению к y(e-m), где e – открытая экспонента атакуемого ключа RSA. С очень высокой вероятностью, этот наибольший общий делитель будет являться секретным множителем p от числа n. Это полностью разрушает безопасность ключа.
Создатели библиотеки Crypto++ и авторы некоторых реализаций OpenPGP утверждают, что их программы неподверженны данной атаке, так как используют дополнительные проверки.
Однако, использование закрытого аппаратного обеспечения ставит под сомнение возможность корректного исполнения на нём криптографических вычислений. В критических случаях для этого необходимо изготовление криптопроцессоров на собственном производстве.
Источник: Cryptome
комментариев: 371 документов: 19 редакций: 20
Все что мы можем сделать – это использовать дополнительные проверки и нестандартные методы вычислений (например умножать в цикле по одному биту), и надеяться что специфичный для этих методов бекдор никто встраивать не будет. Правда это уже нездоровая параноя.
Также следует реалистично оценивать свои риски. Зачем кому-то использовать против вас бекдор черезвычайно трудный в создании и использовании, если можно просто прийти к вам домой и вежливо (с помощью утюга и паяльника) попросить у вас любые ваши ключи?
комментариев: 9796 документов: 488 редакций: 5664
Это такой многоэтажный шкаф с кучей однотипных плат, с мощным охлаждением, рабочей частотой 1 MHz, который будет сутками генерить ассиметричный ключ?
Типа, назад в 50-е?
комментариев: 9796 документов: 488 редакций: 5664
Защиту против этого не рассматриваем, как стандартный оффтопик и отход от темы. Рассматриваем идеальный случай, когда если и придут, то спрашивать будет уже нечего или не у кого.
комментариев: 11558 документов: 1036 редакций: 4118
Владельца ключа идеально сбила машина? :-)
комментариев: 9796 документов: 488 редакций: 5664
Да, как один из классических вариантов, поэтому ключи от владельца перед этим желательно получить незаметно, с помощью закладки в процессоре например.
У меня одно предположение – данные нужно сохранить для потомков из далёкого будущего, неуязвимых к атакам наподобие терморектального криптоанализа.
комментариев: 9796 документов: 488 редакций: 5664
Количество вариантов зависит от вашего больного воображения^wразвитой фантазии. Как вам такой вариант:
У владельца ключа может много врагов: например разведка страны "A" хочет убить его до того, как он хочет передать данные разведке страны "Б".
Из-за этого владелец прячется на территории посольства страны "C", которое обеспечивает ему защиту от прослушивания, но он им тоже не верит и держит при себе ноутбук с взрывающимся винчестером, половина пароля на доступ к которому напечатана на быстросгорающей на свету капсуле. Но этого его всё равно не спасает, так противник использует неизвестный метод "Д".
комментариев: 271 документов: 13 редакций: 4
Частоту можно взять и поболее, мы же не в 50-е живём. :-)
Уже понял. Невнимательно читал. Значит, могут взломать только тот ключ, которым я подписываю подложенные документы. Уже легче.
Предложенный Вами вариант не соответствует Вашему же условию: "спрашивать нечего или не у кого".
абонент sunny оффтопик закончил
комментариев: 9796 документов: 488 редакций: 5664
пользователь ключа заблаговременно уничтожил ключ и принял яду :-)
продолжаем без оффтопика...
комментариев: 9796 документов: 488 редакций: 5664
Сервер может принимать данные, которые шифруются и передаются дальше.
Мало ли какой протокол можно разрушить, если базовые криптографические примитивы выполняются неверно?
комментариев: 232 документов: 17 редакций: 99
Поэтому необходимо развивать общедоступные способы противостояния, т.к. против идивида будут использовать более дешёвые атаки.
Потому что можно реализовать схему с неподконтрольной противнику системой самоуничтожения (можно условиться считать, с нужной степенью точности неподконтрольной). Интерфейс такой схемы предлагает использование ключей "доступа" и "уничтожения", причём заблаговременно проверить какой из них какой – нельзя. В этом смысле паяльник паяльником, но у вас всегда будет возможность уничтожить ключ до применения паяльника :)
P. S.: Правда, я пока писал уже уязвимость нашёл: человек говорит пароль, в это время мы его проверяем на полиграфе. Если полиграф говорит, что верный – сами вводим его и получаем доступ к информации. Если полиграф говорит что неверный – включаем паяльник.
P. P. S.: Но есть и уязвимость против уязвимости: есть техники противодействия полиграфу, вполне себе эффективные, только тренировка нужна.
Примечание: полиграф в целях обвинения кого-либо в чём либо негласно уже во всю используется, так что техника "пыток на полиграфе" предельно проста в реализации :)
комментариев: 271 документов: 13 редакций: 4
Всё-таки данные должны дешифроваться или подписываться. То есть в операции должна участвовать секретная часть ключа, которую злоумышленник и хочет получить.
Если протокол просто разрушить, то он просто не будет работать. Чтобы атаковать, нужно использовать уязвимости конкретных алгоритмов. Странно, что никто не обсуждает математику атаки.
В общем случае надо проверять результаты вычислений. Никакой производитель процессоров не гарантирует 100% надёжности вычислений, поэтому даже отсутствие закладки проблему не решит.