id: Гость   вход   регистрация
текущее время 19:17 28/03/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 След.
Комментарии [скрыть комментарии/форму]
— poptalk (22/11/2007 15:54)   профиль/связь   <#>
комментариев: 271   документов: 13   редакций: 4
Никакой производитель процессоров не гарантирует 100% надёжности вычислений

Интересно возможна ли тут встреча теории с практикой – возможен ли процессор настолько простой, чтобы можно было доказать его соответствие своей спецификации, и притом достаточно сложный, чтобы на нём можно было совершать криптографические вычисления (за разумное время)?

Думаю, таким процессором является машина Тьюринга. Все остальные процессоры ей эквивалентны.

А я имел в виду, что процессор ошибается, потому что он физическое устройство, подверженное воздействию теплового движения, радиации, которые могут исказить его работу.
— ntldr (22/11/2007 16:38)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20

Да, правда только криптографические вычисления на ней будут идти не за разумное время. Но если процессор такой машины легко собрать из дискретных элементов, то что делать с памятью? Вдруг злые шпионы иностранных разведок встраивают в чипы памяти особо хитрожопые бекдоры? А чип памяти вы при всем желании ничем не замените.
— SATtva (22/11/2007 16:43, исправлен 22/11/2007 16:46)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
А чип памяти вы при всем желании ничем не замените.

Почему, а перфокарты? :-)) Дурак я, речь ведь об оперативной памяти.
— Гость (22/11/2007 17:15)   <#>
А чип памяти вы при всем желании ничем не замените

Да ну, сейчас полно RW устройств. Тот же жёсткий диск :)
перфокарты
Ферромагнитные колечки, обмотанные несколькими витками провола! :)

шпионы иностранных разведок встраивают в чипы памяти...

А чип памяти имеет весьма простую логику, состоит из повторяющихся элементов, его и на микроскопе проверить можно.
И со шпионами опыт борьбы имеется.
— ntldr (22/11/2007 17:30)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20

Ага, жесткий диск вместо оперативной памяти :) И кто сказал что в нем нет бекдора?

Попробуйте набрать еще необходимый для вычислений обьем такой памяти...
— Гость (22/11/2007 17:55)   <#>
И кто сказал что в нем нет бекдора?
Вы :)). Жесткий диск – это почти машина тьюринга, а
процессор такой машины легко собрать из дискретных элементов
Можно даже магнитный барабан! ;-)
— poptalk (22/11/2007 18:46)   профиль/связь   <#>
комментариев: 271   документов: 13   редакций: 4
Первым шагом в вычислении китайской теоремы об остатках

Звучит как-то... не очень хорошо, ибо теорему не вычисляют, а доказывают. Вычисления из области арифметики вычетов. Вместо числа в арифметике по модулю p*q можно оперировать остатками от деления на p и на q (если p и q — взаимно простые).
— cooshoo (23/11/2007 09:15)   профиль/связь   <#>
комментариев: 83   документов: 4   редакций: 4
Я еще раз перечитал все четыре страницы, но не нашел одного момента – для подобного механизма вскрытия нужно, чтобы абонент бездумно подписал закрытым ключом сфабрикованный текст или бездумно расшифровал сфабрикованный текст открым ключом и выдал результат "на гора". Не знаю протоколов различных автоматизированных систем, но вроде GnuPG подобным маразмом не страдает.
— unknown (23/11/2007 10:22)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
нужно, чтобы абонент бездумно подписал закрытым ключом сфабрикованный текст

Это как раз легко. Например, если подписывается архив или бинарный файл, в конец которого незаметно дописывается блок с a и b.

или бездумно расшифровал сфабрикованный текст открым ключом и выдал результат "на гора". Не знаю протоколов различных автоматизированных систем

Платёжные системы. Многопользовательский VPN, сервер с поддержкой SSL: у вас есть один пароль для доступа, но теоретически вы можете получить их все .

Ну и вообще, атака даже с подобранным шифртекстом – это нехорошо.
— cooshoo (23/11/2007 15:04)   профиль/связь   <#>
комментариев: 83   документов: 4   редакций: 4
Это как раз легко. Например, если подписывается архив или бинарный файл
Хэш от архива или бинарного файла.
Платёжные системы. Многопользовательский VPN, сервер с поддержкой SSL
Увы, вне компетенции, но все равно – это ведь дефект протоколов, а не асимметричного шифрования?
Ну и вообще, атака даже с подобранным шифртекстом – это нехорошо.
То, что RSA к ней уязвим уже лет 20 известно. Возможно и другие системы.
Насколько помню прочитанное – "негласное правило" пользования RSA гласит: закрытым ключом можно подписывать только выход стойкой хэш функции. Результат расшифрования открытым ключом никогда не должен быть раскрыт. Если соблюдать эти правила, насколько страшна ошибка в процессоре?
— unknown (23/11/2007 16:08)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Насколько помню прочитанное – "негласное правило" пользования RSA гласит: закрытым ключом можно подписывать только выход стойкой хэш функции. Результат расшифрования открытым ключом никогда не должен быть раскрыт. Если соблюдать эти правила, насколько страшна ошибка в процессоре?

Я уже высказывал такие же сомнения, а говорили, что прочли все 4 страницы :-)
— cooshoo (23/11/2007 19:07)   профиль/связь   <#>
комментариев: 83   документов: 4   редакций: 4
а говорили, что прочли все 4 страницы :-)
Да... ТщательнЕе нужно быть...
— unknown (10/02/2013 19:46, исправлен 10/02/2013 20:24)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

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


По памяти, в общих чертах его заявление признали ошибочным по ряду примерно таких причин, которые сводятся к его незнанию реальной архитектуры современных процессоров и ПО:


  1. Может какие-то древние малоразрядные процы и хранили какие-то константы и процедуры для ускоренного умножения, но на современных процах умножение выполняется простой инструкцией сдвига, которая используется ещё много для чего. Так что непонятно, как там закладка будет определять, что с этим сдвигом делают.
  2. Умножение больших чисел с помощью сдвига можно разбивать на шаги и оптимизировать разными способами и применять для этого различающиеся алгоритмы, так что предсказать, что будет в каждой програмной реализации сложно.
  3. Джон Каллас (PGP) и др. заявляли, что ещё до этой новости у них в программах результат умножения проверялся для защиты от случайных сбоев и ошибок.

Т.е. если закладки в процах и существуют, то совсем не такие (простые), как это представляет Шамир.

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