id: Гость   вход   регистрация
текущее время 02:28 29/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 След.
Комментарии [скрыть комментарии/форму]
— ntldr (21/11/2007 10:12)   профиль/связь   <#>
комментариев: 371   документов: 19   редакций: 20
Свое собственное железо при всем желании делать не получиться. Даже простейший процессор KP580 содержит 2.5 тысячи транзисторов, и из дискретных элементов его собрать представляется затруднительным, как впрочем и проверить всю схему на соответствие спецификациям.
Все что мы можем сделать – это использовать дополнительные проверки и нестандартные методы вычислений (например умножать в цикле по одному биту), и надеяться что специфичный для этих методов бекдор никто встраивать не будет. Правда это уже нездоровая параноя.
Также следует реалистично оценивать свои риски. Зачем кому-то использовать против вас бекдор черезвычайно трудный в создании и использовании, если можно просто прийти к вам домой и вежливо (с помощью утюга и паяльника) попросить у вас любые ваши ключи?
— unknown (21/11/2007 10:12)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
О чём вы спорите? Ну соберите процессор из дискретных элементов.

Это такой многоэтажный шкаф с кучей однотипных плат, с мощным охлаждением, рабочей частотой 1 MHz, который будет сутками генерить ассиметричный ключ?

Типа, назад в 50-е?
— unknown (21/11/2007 10:19)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Также следует реалистично оценивать свои риски. Зачем кому-то использовать против вас бекдор черезвычайно трудный в создании и использовании, если можно просто прийти к вам домой и вежливо (с помощью утюга и паяльника) попросить у вас любые ваши ключи?

Защиту против этого не рассматриваем, как стандартный оффтопик и отход от темы. Рассматриваем идеальный случай, когда если и придут, то спрашивать будет уже нечего или не у кого.
— SATtva (21/11/2007 10:21)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Рассматриваем идеальный случай, когда если и придут, то спрашивать будет уже нечего или не у кого.

Владельца ключа идеально сбила машина? :-)
— unknown (21/11/2007 10:31)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Владельца ключа идеально сбила машина? :-)

Да, как один из классических вариантов, поэтому ключи от владельца перед этим желательно получить незаметно, с помощью закладки в процессоре например.
— sunny (21/11/2007 10:38)   <#>
Коллеги, если владельца ключа сбила машина, то зачем он перед этим голову ломал на тему "как ему зашифровать данные"?
У меня одно предположение – данные нужно сохранить для потомков из далёкого будущего, неуязвимых к атакам наподобие терморектального криптоанализа.
— unknown (21/11/2007 10:51, исправлен 21/11/2007 10:53)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Коллеги, если владельца ключа сбила машина, то зачем он перед этим голову ломал на тему "как ему зашифровать данные"?
У меня одно предположение

Количество вариантов зависит от вашего больного воображения^wразвитой фантазии. Как вам такой вариант:

У владельца ключа может много врагов: например разведка страны "A" хочет убить его до того, как он хочет передать данные разведке страны "Б".

Из-за этого владелец прячется на территории посольства страны "C", которое обеспечивает ему защиту от прослушивания, но он им тоже не верит и держит при себе ноутбук с взрывающимся винчестером, половина пароля на доступ к которому напечатана на быстросгорающей на свету капсуле. Но этого его всё равно не спасает, так противник использует неизвестный метод "Д".
— poptalk (21/11/2007 11:31)   профиль/связь   <#>
комментариев: 271   документов: 13   редакций: 4
Это такой многоэтажный шкаф с кучей однотипных плат, с мощным охлаждением, рабочей частотой 1 MHz, который будет сутками генерить ассиметричный ключ?

Типа, назад в 50-е?

Частоту можно взять и поболее, мы же не в 50-е живём. :-)

Весь фокус в том, что противник подсовывает именно такие данные, где цель должна будет выполнить именно вычисления с этой парой чисел на своём ключе.

Уже понял. Невнимательно читал. Значит, могут взломать только тот ключ, которым я подписываю подложенные документы. Уже легче.
— sunny (21/11/2007 12:06)   <#>
Уважаемый unknown,
Предложенный Вами вариант не соответствует Вашему же условию: "спрашивать нечего или не у кого".

абонент sunny оффтопик закончил
— unknown (21/11/2007 12:27)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Предложенный Вами вариант не соответствует Вашему же условию: "спрашивать нечего или не у кого".

абонент sunny оффтопик закончил

пользователь ключа заблаговременно уничтожил ключ и принял яду :-)

продолжаем без оффтопика...
— unknown (21/11/2007 12:34)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Уже понял. Невнимательно читал. Значит, могут взломать только тот ключ, которым я подписываю подложенные документы. Уже легче.

Сервер может принимать данные, которые шифруются и передаются дальше.
Мало ли какой протокол можно разрушить, если базовые криптографические примитивы выполняются неверно?
— serzh (21/11/2007 13:45)   профиль/связь   <#>
комментариев: 232   документов: 17   редакций: 99
Встраивать такую закладку против одного человека обычно несоизмеримо дорого, но как только мы посмотрим в сторону цели "контроль за обществом", то "насоизмеримо дорого" превращается в черезвычайно дёшево.
Поэтому необходимо развивать общедоступные способы противостояния, т.к. против идивида будут использовать более дешёвые атаки.
— Гость (21/11/2007 21:56)   <#>
Зачем кому-то использовать против вас бекдор черезвычайно трудный в создании и использовании, если можно просто прийти к вам домой и вежливо (с помощью утюга и паяльника) попросить у вас любые ваши ключи?

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

P. S.: Правда, я пока писал уже уязвимость нашёл: человек говорит пароль, в это время мы его проверяем на полиграфе. Если полиграф говорит, что верный – сами вводим его и получаем доступ к информации. Если полиграф говорит что неверный – включаем паяльник.

P. P. S.: Но есть и уязвимость против уязвимости: есть техники противодействия полиграфу, вполне себе эффективные, только тренировка нужна.

Примечание: полиграф в целях обвинения кого-либо в чём либо негласно уже во всю используется, так что техника "пыток на полиграфе" предельно проста в реализации :)
— poptalk (22/11/2007 07:18)   профиль/связь   <#>
комментариев: 271   документов: 13   редакций: 4
Уже понял. Невнимательно читал. Значит, могут взломать только тот ключ, которым я подписываю подложенные документы. Уже легче.

Сервер может принимать данные, которые шифруются и передаются дальше.

Всё-таки данные должны дешифроваться или подписываться. То есть в операции должна участвовать секретная часть ключа, которую злоумышленник и хочет получить.
We now describe the basic idea of the new attack. We assume that the RSA decryption (or signature generation)...


Мало ли какой протокол можно разрушить, если базовые криптографические примитивы выполняются неверно?

Если протокол просто разрушить, то он просто не будет работать. Чтобы атаковать, нужно использовать уязвимости конкретных алгоритмов. Странно, что никто не обсуждает математику атаки.

В общем случае надо проверять результаты вычислений. Никакой производитель процессоров не гарантирует 100% надёжности вычислений, поэтому даже отсутствие закладки проблему не решит.
— Гость (22/11/2007 10:39)   <#>
Никакой производитель процессоров не гарантирует 100% надёжности вычислений
Интересно возможна ли тут встреча теории с практикой – возможен ли процессор настолько простой, чтобы можно было доказать его соответствие своей спецификации, и притом достаточно сложный, чтобы на нём можно было совершать криптографические вычисления (за разумное время)?
На страницу: 1, 2, 3, 4 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3