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
комментариев: 271 документов: 13 редакций: 4
Думаю, таким процессором является машина Тьюринга. Все остальные процессоры ей эквивалентны.
А я имел в виду, что процессор ошибается, потому что он физическое устройство, подверженное воздействию теплового движения, радиации, которые могут исказить его работу.
комментариев: 371 документов: 19 редакций: 20
Да, правда только криптографические вычисления на ней будут идти не за разумное время. Но если процессор такой машины легко собрать из дискретных элементов, то что делать с памятью? Вдруг злые шпионы иностранных разведок встраивают в чипы памяти особо хитрожопые бекдоры? А чип памяти вы при всем желании ничем не замените.
комментариев: 11558 документов: 1036 редакций: 4118
Почему, а перфокарты? :-))Дурак я, речь ведь об оперативной памяти.Да ну, сейчас полно RW устройств. Тот же жёсткий диск :)
Ферромагнитные колечки, обмотанные несколькими витками провола! :)
А чип памяти имеет весьма простую логику, состоит из повторяющихся элементов, его и на микроскопе проверить можно.
И со шпионами опыт борьбы имеется.
комментариев: 371 документов: 19 редакций: 20
Ага, жесткий диск вместо оперативной памяти :) И кто сказал что в нем нет бекдора?
Попробуйте набрать еще необходимый для вычислений обьем такой памяти...
комментариев: 271 документов: 13 редакций: 4
Звучит как-то... не очень хорошо, ибо теорему не вычисляют, а доказывают. Вычисления из области арифметики вычетов. Вместо числа в арифметике по модулю p*q можно оперировать остатками от деления на p и на q (если p и q — взаимно простые).
комментариев: 83 документов: 4 редакций: 4
комментариев: 9796 документов: 488 редакций: 5664
Это как раз легко. Например, если подписывается архив или бинарный файл, в конец которого незаметно дописывается блок с a и b.
Платёжные системы. Многопользовательский VPN, сервер с поддержкой SSL: у вас есть один пароль для доступа, но теоретически вы можете получить их все .
Ну и вообще, атака даже с подобранным шифртекстом – это нехорошо.
комментариев: 83 документов: 4 редакций: 4
Увы, вне компетенции, но все равно – это ведь дефект протоколов, а не асимметричного шифрования?
То, что RSA к ней уязвим уже лет 20 известно. Возможно и другие системы.
Насколько помню прочитанное – "негласное правило" пользования RSA гласит: закрытым ключом можно подписывать только выход стойкой хэш функции. Результат расшифрования открытым ключом никогда не должен быть раскрыт. Если соблюдать эти правила, насколько страшна ошибка в процессоре?
комментариев: 9796 документов: 488 редакций: 5664
Я уже высказывал такие же сомнения, а говорили, что прочли все 4 страницы :-)
комментариев: 83 документов: 4 редакций: 4
комментариев: 9796 документов: 488 редакций: 5664
К сожалению, я вовремя не собрал материал по опровержению этой новости. Сейчас собрать ссылки трудно, а поскольку в процессорах разбираюсь явно ещё хуже Шамира, то могу со своими толкованиями сесть в лужу ещё больше него.
По памяти, в общих чертах его заявление признали ошибочным по ряду примерно таких причин, которые сводятся к его незнанию реальной архитектуры современных процессоров и ПО:
Т.е. если закладки в процах и существуют, то совсем не такие (простые), как это представляет Шамир.