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
комментариев: 11558 документов: 1036 редакций: 4118
Раскрутка компилятора не такая уж сложная вещь. Угроза в том, что в связи с общей (не только в России) деградацией образования, людей, которые смогут это сделать, становиться всё меньше, а в связи со всеобщей коммерциализацией им труднее обмениваться идеями (Потому как хочется "хлеба" не только с "маслом", но и с "чёрной икрой" – этот культ "золотого телёнка" скоро всех сожрёт. Некоторые вот лицензию уже меняют...).
комментариев: 232 документов: 17 редакций: 99
комментариев: 271 документов: 13 редакций: 4
комментариев: 371 документов: 19 редакций: 20
http://wasm.ru/toollist.php?list=7#244
Не нужно с чем-то там бороться. Проще просто выбраковывать подозрительные модели и не использовать их.
Для прохождения теста достаточно эмпирически проверить эмулируемый процессор достаточно простой для такой проверки и достаточно производительный для криптовычислений. Если эмулятор не проходит проверку, то соответственно выбраковывается модель аппаратного процессора, если проверка успешная – то криптовычисления проводимые на эмулируемом процессоре работающем на данной аппаратной модели вполне безопасны.
И ещё раз, так как для шифрования/подписи не нужна высокая производительность, то эмулируемый процессор может быть очень простым, понятным и маленьким, а следовательно встраиваемым, например, в виде подключаемой библиотеки.
комментариев: 271 документов: 13 редакций: 4
А написано: "мгновенно взломать все системы"?
А ещё написано:
комментариев: 11558 документов: 1036 редакций: 4118
Так ли уж? На десктопе не нужна, а на сервере, шифрующем оптический канал или несколько тысяч SSL-сессий?
Это делается не для коммерциализации проекта. А то, что ntldr выпускает программу под GPL, допускающей коммерческое использование, Вас не смущает? Давайте не выносить флэйм хотя бы за рамки соответствующей страницы сайта.
комментариев: 371 документов: 19 редакций: 20
Ну это уже крайняя стадия паранои. Теоретически можно и не такое предположить, но практическая сложность такой атаки...
Я в лицензиях не особо разбираюсь, но считаю что если под GPL выпускается большая часть opensource софта, то и мне эта лицензия подойдет.
вполне решаемо, это частности. всё-таки не сравнить с обработкой видео и рендерингом или с аналитическими вычислениями.
комментариев: 9796 документов: 488 редакций: 5664
Естественно, иначе её бы быстро обнаружили. Как раз в 64-битном процессоре её и не подобрать случайно из-за 2(64+64) сочетаний.
Весь фокус в том, что противник подсовывает именно такие данные, где цель должна будет выполнить именно вычисления с этой парой чисел на своём ключе. А по результатам этих вычислений (например по подписи) противник получает закрытый ключ цели. Правда между всем этим лежит хэширование, но у Шамира возможно неполностью раскрыта вся методика, приведён только простейший пример.
Например это данные для финансовой транзакции, раскрывающие ключ платёжной системы; программный пакет, раскрывающий удостоверящий ключ дистрибутива; передача данных в сети TOR, раскрывающая ключ сервера и т.д.
комментариев: 9796 документов: 488 редакций: 5664
Изготовить простую печатную плату можно хоть в домашних условиях (можете собрать даже простейшую видеокарту из деталей), а вот изготовление собственно микросхем, которые туда надо впаять, требует столь дорогого оборудования, что модель в единичном экземпляре будет стоить столь-ко же, сколько и партия в сотню тысяч штук.
Опять же как доверять производителю?