id: Гость   вход   регистрация
текущее время 09:31 26/02/2021
Владелец: unknown (создано 19/11/2007 10:48), редакция от 23/11/2007 09:08 (автор: unknown) Печать
Категории: криптография, политика, шифрование с открытым ключом, атаки, побочные каналы, спецслужбы
https://www.pgpru.com/Новости/2007/ВсеАссиметричныеАлгоритмыМогутБытьВзломаныЗаОднуОперациюИз-заЗакладкиВПроцессорах
создать
просмотр
редакции
ссылки

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


 
На страницу: 1, 2, 3, 4 След.
Комментарии [скрыть комментарии/форму]
— SATtva (19/11/2007 11:47)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4094
Элегантно. Очередной камень в огород аппаратных средств шифрования. Или где там заводик можно прикупить? :-)
— unknown (19/11/2007 12:08)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Очередной камень в огород аппаратных средств шифрования.

Равно как и программных, выполняющих умножение на обычном процессоре (он ведь закрытый). Можно конечно вводить всякие дополнительные проверки, но нельзя быть полностью уверенным в том, какие ещё сюрпризы могут быть там теоретически припрятаны.
— unknown (19/11/2007 12:11)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Или где там заводик можно прикупить? :-)

АНБ разрешило как-то документалистам снять несколько мимолётных кадров про свой подземный заводик, где они делают криптооборудование для собственных нужд, начиная с процессоров и заканчивая всеми остальными деталями собственной сборки. О стоимости проекта ничего не сообщалось.
— флинт (19/11/2007 12:11)   <#>
Могут ли такие закладки сказываться на криптовычмслениях проводимых на эмулируемых процессорах (например, bochs)?
— SATtva (19/11/2007 12:16)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4094
О стоимости проекта ничего не сообщалось.

Они открыто отчитываться и не обязаны, все затраты заложены в секретные бюджетные статьи Пентагона.
— unknown (19/11/2007 12:29)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Могут ли такие закладки сказываться на криптовычмслениях проводимых на эмулируемых процессорах (например, bochs)?

Результат умножения он всё равно будет брать от основного проца, ну разрядность поменяет или ещё что, но это можно предсказать.

И не факт, что не существует других способов внесения закладок или атак, нацеленных спечиально на эмуляторы процессоров (против особо упорно сопротивляющихся) :-)
— ntldr (19/11/2007 13:30)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
В 32х битных процессорах по умолчанию идет работа с 32х битными частями (если в реализации алго не используется mmx), поэтому проверить умножение можно брутфорсом. Для 64 и 128 битных операций mmx и sse этого сделать уже нельзя :(

Ну что, займемся распределенной проверкой процессоров на вшивость? Могу накатать прогу которая это делает.
— флинт (19/11/2007 14:04)   <#>
хм, тогда выходит можно осуществить проверку проводя тесты в упрощённом эмуляторе на котором планируется производить вычисления?



По моему, это зависит только от эмулятора. Эмуляторы с полным эмулированием процессора (насколько помню, bochs из их числа) врядли могут быть подвержены 'не' специфичным атакам и закладкам.

Конечно, придётся безбожно платить производительностью (не сравнимой даже с популярными vm), но с этим можно смириться. Мысль выглядит заманчивой, если учесть что эмулятор может быть предельно простым и встраиваемым.
— ent1 (19/11/2007 14:37)   <#>
Это мне напоминает историю со знаменитой "ошибкой" в первом пентиуме! Пентиум написал целиком, 086, 286, 386sx, 386dx, 486sx, 486dx, 486dx2, 486dx4 уже изрядно надоели... тогда.

Там как раз и была ошибка вычислений с пл. точкой из-за двух неверных (или пропущеных, не помню) предвычисленных констант. Интел тогда долго отказывалась менять проци. Не было ли это первым шагом на пути таких "хардверных" закладок?

Я даже не стал избавляться от одного компа с таким процом, оставил. Теперь можно попробовать оценить влияние той ошибки.
— ntldr (19/11/2007 15:03)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
Не обязательно юзать эмуляторы. Достаточно просто переписать реализацию крипто так, чтобы операция умножения не использовалась. Только имхо делать это нет никакого смысла, так как можно придумать целый ряд других атак производимых с помощью закладок в процессоре. Например возможно создать закладку в команде rep movsb позволяющую исполнить произвольный код путем передачи специально сформированого сообщения по любому возможному канале (через сеть, в файле, и.т.д.). Как вы от этого собираетесь защищаться? Переделывать ОС так чтобы она не использовала rep movsb?
Имхо это война с ветряными мельницами.
— Гость (19/11/2007 23:12)   <#>
Нужно изобретать и внедрять недорогую технологию производства микросхем, пусть маломощных, но с "открытыми исходниками", (например печатать их на принтере специальными чернилами :).
— ntldr (19/11/2007 23:26, исправлен 19/11/2007 23:30)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
Зачем же, есть старенькие советские процессоры KP580ВМ80, можете собрать себе криптодевайс на таком и пользоваться им. Уж в эту древность никакие бекдоры точно не догадались вставить... Кстати, принципиальная схема этого процессора открыта, что позволяет надеяться на его полную изученость и документированость.
— serzh (19/11/2007 23:42)   профиль/связь   <#>
комментариев: 232   документов: 17   редакций: 99
Пришло время задуматься над "Открытым аппаратным обеспечением".
— Гость (20/11/2007 14:21)   <#>
Нужно изобретать и внедрять недорогую технологию производства микросхем, пусть маломощных, но с "открытыми исходниками", (например печатать их на принтере специальными чернилами :).

Так проблема-то намного жёстче!
Проблема состоит в том, что даже имея открытую полную спецификацию на процессор нельзя проверить удовлетворяет ли он указанной спецификации в силу того что нельзя перебрать все возможные варианты входов и выходов... технически нельзя, как тут неции сказали. Так что, если вы лично не присутствовали на всех стадиях проектирования и производства процессора, а также на всех проектированиях и стадиях создания оборудования для изготовления процессора, а также ... <рекурсия n->inf выреана> то вы ни в чём не можете быть уверенным. Да, в перспективе, вы, может быть, сможете проверить процессор на наличие какой-то совершенно конкретной закладки... но ведь их число едва ли ли счётно, вряд ли когда будет создан универсальный тест, позволяющий проверить то, что "это железо делает то и только то что указано в документации". Да и если есть неочевидные закладки, их можно и задокументировать под видом того что "пока ещё разберутся... что это закладка".
— Гость (20/11/2007 15:27)   <#>
нельзя проверить удовлетворяет ли он указанной спецификации в силу того что нельзя перебрать все возможные варианты входов и выходов...
Не надо перебирать все входы-выходы. Существуют методики верификации программ. Кремниевый компилятор тоже программа. А процессор для шифрования нужен совсем простенький. Так что не факт, что так уж всё плохо.
На страницу: 1, 2, 3, 4 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3