id: Гость   вход   регистрация
текущее время 23:09 14/11/2024
Владелец: unknown (создано 19/11/2007 10:48), редакция от 23/11/2007 09:08 (автор: unknown) Печать
Категории: криптография, политика, шифрование с открытым ключом, атаки, побочные каналы, спецслужбы
http://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 (20/11/2007 15:47, исправлен 20/11/2007 15:50)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Ещё в 84-м году в классической работе fileReflections on Trusting Trust было показано, что бэкдор может быть внедрён не только в исходный текст программы (где его можно отловить при аудите), но и в объектный код на этапе компиляции. Затрояненный компилятор может троянить и другие компиляторы при bootstrap'е систем, которые, в свою очередь, будут троянить обычные программы, а поскольку машинный код никто читать не будет, "закладка" может бесконечно долго оставаться необнаруженной.

The moral is obvious. You can't trust code that you did not totally create yourself... No amount of source-level verification or scrutiny will protect you from using untrusted code... As the level of program gets lower, these bugs will be harder and harder to detect. A well-installed microcode bug will be almost impossible to detect.
— Гость (20/11/2007 17:12)   <#>
Затрояненный компилятор

Раскрутка компилятора не такая уж сложная вещь. Угроза в том, что в связи с общей (не только в России) деградацией образования, людей, которые смогут это сделать, становиться всё меньше, а в связи со всеобщей коммерциализацией им труднее обмениваться идеями (Потому как хочется "хлеба" не только с "маслом", но и с "чёрной икрой" – этот культ "золотого телёнка" скоро всех сожрёт. Некоторые вот лицензию уже меняют...).
— Гость (20/11/2007 17:21)   <#>
машинный код никто читать не будет
Ну почему, есть любители. А если объяснить проблему, то очень даже будут.
— serzh (20/11/2007 18:36)   профиль/связь   <#>
комментариев: 232   документов: 17   редакций: 99
Для проверки можно попробывать протестировать на выходные данные случайно выбраные процессоры разных производителей и одной архитектуры. В результате можно несколько снизить вероятность закладки.
— poptalk (20/11/2007 18:38)   профиль/связь   <#>
комментариев: 271   документов: 13   редакций: 4
О чём вы спорите? Ну соберите процессор из дискретных элементов.
— ntldr (20/11/2007 18:59)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
Уж лучше эмулятор созданый так, чтобы против него не могли работать универсальные атаки. Ну а от специфических атак вам внешний криптопроцессор не поможет, ибо бекдор в CPU может искажать результаты передаваемые им на ПК.
— Гость (20/11/2007 21:08)   <#>
Не совсем в тему, но может быть интересно тем, кто собирается перекомпилировать, например, TCWDE.
Вам, возможно, неизвестно, что MS линкер любит пошалить и запихивает в PE-файл (между стабом DOS и началом PE-заголовка) какой-то "мусор". Что же это за "мусор"? Так вот, туда попадает слово "Rich" + compid (!!!) вашей машины, поксоренный определенным ключом!

http://wasm.ru/toollist.php?list=7#244
— флинт (20/11/2007 22:05)   <#>
Думал, что проанализируют мою мысль, но кажеться её не поняли.

Не нужно с чем-то там бороться. Проще просто выбраковывать подозрительные модели и не использовать их.

Для прохождения теста достаточно эмпирически проверить эмулируемый процессор достаточно простой для такой проверки и достаточно производительный для криптовычислений. Если эмулятор не проходит проверку, то соответственно выбраковывается модель аппаратного процессора, если проверка успешная – то криптовычисления проводимые на эмулируемом процессоре работающем на данной аппаратной модели вполне безопасны.

И ещё раз, так как для шифрования/подписи не нужна высокая производительность, то эмулируемый процессор может быть очень простым, понятным и маленьким, а следовательно встраиваемым, например, в виде подключаемой библиотеки.
— poptalk (20/11/2007 22:34)   профиль/связь   <#>
комментариев: 271   документов: 13   редакций: 4
Или я чего-то не понимаю... Закладка проявляет себя только один раз из 2^128 умножений. Значит, и вероятность того, что эти числа проскочат в вычислениях, 2^-128. Авось пронесёт. :-)

А написано: "мгновенно взломать все системы"?
— Гость (20/11/2007 23:01)   <#>
А написано: "мгновенно взломать все системы"?

А ещё написано:
Для проведения атаки достаточно знания пары чисел, являющихся секретным ключём дефекта умножителя, и всего одного подобранного сообщения.
— SATtva (21/11/2007 07:23)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
"Reflections..." я привёл в качестве аналогии. Если мы [потенциально] имеем закладку в процессоре, то справедливо допустить, что другие процессоры, разработанные с применением данного, также могут получить бэкдор. Мало кто в наши дни делает что-то только на чертёжном кульмане своими руками.

И ещё раз, так как для шифрования/подписи не нужна высокая производительность

Так ли уж? На десктопе не нужна, а на сервере, шифрующем оптический канал или несколько тысяч SSL-сессий?

Некоторые вот лицензию уже меняют.

Это делается не для коммерциализации проекта. А то, что ntldr выпускает программу под GPL, допускающей коммерческое использование, Вас не смущает? Давайте не выносить флэйм хотя бы за рамки соответствующей страницы сайта.
— ntldr (21/11/2007 07:49)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20

Ну это уже крайняя стадия паранои. Теоретически можно и не такое предположить, но практическая сложность такой атаки...

Я в лицензиях не особо разбираюсь, но считаю что если под GPL выпускается большая часть opensource софта, то и мне эта лицензия подойдет.
— Гость (21/11/2007 08:19)   <#>


вполне решаемо, это частности. всё-таки не сравнить с обработкой видео и рендерингом или с аналитическими вычислениями.
— unknown (21/11/2007 09:34)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Закладка проявляет себя только один раз из 2^128 умножений. Значит, и вероятность того, что эти числа проскочат в вычислениях, 2^-128. Авось пронесёт. :-)

Естественно, иначе её бы быстро обнаружили. Как раз в 64-битном процессоре её и не подобрать случайно из-за 2(64+64) сочетаний.


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

Например это данные для финансовой транзакции, раскрывающие ключ платёжной системы; программный пакет, раскрывающий удостоверящий ключ дистрибутива; передача данных в сети TOR, раскрывающая ключ сервера и т.д.
— unknown (21/11/2007 09:43, исправлен 21/11/2007 10:07)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Для ассиметричной криптографии нужны мощные процессоры. Именно поэтому в 8-битных микроконтроллерах или смарт-картах используется ключ максимум 1024 бита или вычисления на эллиптических кривых.

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

Опять же как доверять производителю?
На страницу: 1, 2, 3, 4 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3