dxdt.ru: занимательный интернет-журнал

В работе исследователей, которые обнаружили уязвимость TLS Logjam, обсуждается возможность вычисления системами АНБ дискретного логарифма в некоторых группах, используемых в различных реализациях алгоритма Диффи-Хеллмана. (Задача дискретного логарифмирования, для правильно выбранных параметров, является вычислительно трудной, на этой трудности и основана практическая полезность протокола Диффи-Хеллмана.) Например, в решениях VPN, использующих IPsec (а это распространённая практика), для генерации общего ключа служат группы, заданные в рекомендациях (RFC). То есть, параметры известны заранее, это позволяет сильно ускорить процесс вычисления логарифма, выполнив предварительные вычисления.

АНБ, в теории, могло построить особый компьютерный кластер. В его основе – специализированные вычислители (ASIC), которые оптимизированы для выполнения конкретной задачи (вычисление арифметической структуры заданной группы). Если использовать современные технологии микроэлектронного производства, то узкоспециализированных вычислительных ядер в небольшом элементе кластера (в размере сервера типа blade, скажем) можно разместить тысячи (вспомните про современные видеокарты: там тысячи ядер, составляющих графический процессор, размещаются на одной небольшой плате). Предварительные вычисления для дискретного логарифмирования хорошо распараллеливаются. Миллионы ядер, допустим, позволяют вычислять структуру группы для 1024-битного модуля за год. После того, как предварительные вычисления сделаны, можно очень быстро (за минуты) раскрывать секретные ключи, полученные по протоколу Диффи-Хеллмана, из записанного трафика. А “предвычислитель” может заняться другой группой, потратив на неё ещё год, – это не так страшно, потому что одни и те же параметры в Сети действуют десятилетиями.

Повторюсь: группы, которые использует большинство узлов VPN, известны заранее – они внесены в рекомендации, их всего несколько (три-пять, в зависимости от протокола). Соответственно, при необходимости расшифровки трафика, записанные снифером параметры отправляются в центр обработки данных АНБ, там из них вычисляют ключ, возвращают его обратно на перехватывающий узел и – всё, теперь можно в пассивном режиме читать IPsec VPN. Именно такая схема обозначена на слайдах из презентаций АНБ. В общем-то, выглядит всё логично: бюджеты большие, а превращение некоторой их части в суперкомпьютер, раскрывающий хотя бы половину трафика VPN, – такое несложно обосновать, просто сравнив возможности “до и после”. Ситуация с прослушиванием в режиме онлайн становится возможной не потому, что алгоритм плохой, а потому, что повсеместно используются рекомендуемые параметры алгоритма (это известная схема, которая всегда служила источником напряжённости в спорах о том, какую и “чью” криптографию нужно применять). Интересно, кстати, что если VPN-трафик скрывает какие-то весьма ценные данные, но узлы используют нестандартные настройки, то трафик можно записать, потратить год времени на вычисление конкретных ключей – ну, чтобы оборудование не простаивало, – и потом расшифровать трафик, нивелировав всю прогрессивную секретность.

(Меня попросили простыми словами объяснить, как работают методы считывания секретных ключей через побочные излучения и наводки, например через измерение электрических параметров ноутбука, как продемонстрировано в недавней работе Genkin, Pipman, Tromer. Думаю, что описание достаточно интересно и для публикации на dxdt.ru, тем более, что в нём, на мой взгляд, есть наблюдения, полезные для понимания деталей работы современных реализаций RSA и принципов разработки криптографического ПО.)

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

Основная идея использования излучений и наводок для создания канала утечки состоит в том, чтобы при помощи анализа тех или иных параметров научиться определять внутреннее состояние атакуемой системы, с привязкой к некоторой временной шкале. (Это верно даже для тривиального случая, когда “защищаемая” информация по недосмотру просто транслируется в эфир.)

Но недостаточно научиться лишь различать внутренние состояния системы, измеряя внешние параметры – нужно ещё суметь сопоставить эти состояния со значением проводимых системой операций. То есть, грубо говоря, провести “декодирование” или раскрытие сигнала. В случае с программным обеспечением, выполняющим криптографические вычисления, векторы атак направлены в сторону различий в использовании ресурсов для реализации тех или иных операций. Хрестоматийный пример: реализация умножения чисел, занимающая разное время в зависимости от значений сомножителей.

Кстати, именно наличие побочных каналов утечек задаёт совершенно другие требования к архитектуре криптографического ПО: его разработчики не только должны отлично владеть программированием как таковым, но и в деталях понимать особенности исполнения программного кода аппаратным обеспечением; это, естественно, кроме досконального знания криптографических алгоритмов. Одной из фундаментальных задач при разработке криптографического ПО является создание такого кода, для которого действовал бы принцип неразличимости “внешним наблюдателем” проводимых над разными операндами низкоуровневых операций между собой и между операндами. В том числе, принцип должен действовать для такого наблюдателя, который может изменять данные, поступающие на вход функций криптобиблиотеки (см. ниже). Поэтому разработка качественных криптобиблиотек представляет собой обособленный вид магии, сильно отличающийся от других направлений программирования. Разобраться в этой магии чрезвычайно сложно, ещё сложнее – научиться её применять.

Перейдём к конкретному примеру, описанному в исходной работе: получение ключа RSA при помощи измерения электрического потенциала на корпусе (“земле”) ноутбука. (В работе речь идёт также о криптосистеме ElGamal, но принцип атаки совершенно аналогичен, поэтому мы будем рассматривать только случай RSA.) RSA использует операцию возведения в степень, и для шифрования, и для расшифровывания. Напомню, что секретной в RSA является расшифровывающая экспонента, обратная к шифрующей экспоненте. Последняя входит в состав открытого ключа, наряду с модулем (большим числом, задающим конечное множество чисел, в котором осуществляются операции для данного ключа). RSA работает с очень большими числами (2048 бит и более). Арифметические операции над ними, если их осуществлять “в лоб”, занимали бы слишком много времени, даже при работе на самых мощных компьютерах. К счастью, известно большое число оптимизаций, сводящих умножение (возведение в степень) больших целых чисел RSA к некоторому разумному количеству операций. Эти оптимизации всегда являлись проводником для возникновения побочных каналов утечек. Они же используются и в этот раз.

Итак – секретной частью ключа RSA является расшифровывающая экспонента. Это целое число. Достаточно большое. В компьютерной памяти, естественно, оно представлено в двоичном виде. Операции с ним также осуществляются, грубо говоря, побитно – это одна из оптимизаций для быстрого умножения. После того, как исследователи определили, что можно различить исполняемые центральным процессором компьютера серии одних и тех же операций, измеряя потенциал на его корпусе, осталось найти такие зацепки в программном коде, которые позволили бы, на основе этих измерений, различать единицы и нули шифрующей экспоненты. Здесь и кроется основная задумка работы. Зацепки удалось найти в части кода GpuPG, осуществляющей умножение: здесь для 1 и 0 шифрующей экспоненты выбирались разные ветки кода, исполнение которых, при определённых условиях (см. ниже про шифротекст), оставляло разные следы в измеряемом канале утечки.

В RSA шифруемое/расшифровываемое сообщение также представляет собой большое целое число (по длине записи соответствующее длине ключа). При шифровании это число (сообщение) возводится в степень, соответствующую открытой экспоненте. Для дешифрования служит обратная, секретная экспонента. То есть, для того, чтобы наблюдать операции с секретным ключом, атакуемая система должна расшифровывать сообщения – возводить полученные числа в степень, используя соответствующий фрагмент кода GnuPG. А чтобы исследователи могли увидеть биты секретной экспоненты, нужно чтобы возводимые числа (а точнее – одно число) имели специальный вид. Использование специального шифротекста называется “атакой с подобранным шифротекстом”. В рассматриваемом случае – это основная зацепка: если система работает с другими шифротекстами, извлечь ключ описанным способом невозможно.

Подобранный шифротекст вовсе не обязан быть каким-то осмысленным сообщением. Это просто число. Значение этого числа подбиралось по параметрам открытого ключа RSA таким образом, чтобы при обработке внутри низкоуровневых функций GnuPG для нулевых битов секретной экспоненты получались промежуточные значения одного из операндов, содержащие в своем представлении большое число нулевых элементов (промежуточных произведений), а для битов секретной экспоненты, которые равны единице – нулевых элементов было бы мало. Это довольно тонкое наблюдение, очередной раз подтверждающее, что если реализация криптосистем в программном коде – штука, обладающая многими гранями сложности, то работа криптоаналитика с этими системами больше напоминает рыбалку: собирая снасти, никогда точно не знаешь, что поймаешь.

Выбрать правильный шифротекст, из-за особенностей реализации RSA, не представляло особого труда: подходит значение m – 1, где m = pq – модуль ключа, который, как известно, равен произведению двух простых чисел p и q. Значение модуля является открытым. (В секрете держится только разложение на p и q. Несмотря на то что, строго говоря, для расшифровывания сообщения нужно знать только расшифровывающую экспоненту, значения p и q сохраняются, чтобы в дальнейшем использовать их для оптимизации умножения при расшифровывании сообщений.)

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

Ещё раз остановлюсь на ключевых моментах: побочные излучения и наводки есть практически всегда; для их использования в качестве канала утечки нужно научиться по измеряемым физическим параметрам (электрический потенциал, звуковое давление, что-то ещё) различать внутренние состояния атакуемой системы; для извлечения полезной информации при атаках на конкретное ПО требуется также правильно сопоставить различным внутренним состояниям логические этапы работы используемой криптосистемы.

И рекомендую почитать исходную работу (PDF).

Есть такой российский криптографический стандарт хэш-функции – ГОСТ Р 34.11-2012. На днях стартовал открытый конкурс научно-исследовательских работ, посвящённых анализу криптографических качеств этой хэш-функции. Популяризируют российскую (советскую) криптографию, и популяризируют, надо заметить, весьма кстати: сейчас второй полюс в мировом криптографическом инструментарии не помешает. При этом “гостовские” алгоритмы пока что сильно проигрывают более широко известным “западным” в степени исследованности академическим сообществом.

(Призы конкурса Streebog весьма приличные: первая премия – 500 тыс. руб.)

В продолжение темы аппаратных закладок: интересная работа Georg T. Becker, Francesco Regazzoni, Christof Paar и Wayne Burleson (по ссылке – PDF). Предложен метод внедрения аппаратных закладок (“троянов”) путём изменения легирующего состава (dopant), добавляемого в вещество, составляющее транзистор. В результате меняется тип проводимости, что влияет на электрические характеристики схемы.

Преимущество метода в том, что созданные с его помощью троянские модификации микросхем практически невозможно обнаружить, “топологически” исследуя кристал по слоям при помощи электронного микроскопа (или другого оборудования): не добавляется новых элементов, изменённые транзисторы на снимках выглядят так же, как и штатные. Более того, “троянская” схема успешно проходит процедуры контроля качества.

В роли одного из практических примеров обсуждают модификацию аппаратного генератора случайных чисел Intel. Корректировка поведения транзисторов, изменяющая свойства регистров, сводит вполне корректную интеловскую схему генерации (псевдо)случайных чисел к фиксированному исходному ключу и небольшому количеству песевдослучайной энтропии. То есть, всё можно раскрыть простым перебором. Степень желаемой сложности перебора задаётся атакующим. Так, штатно работающий генератор выдаёт сложность 2^128, модификация позволяет сократить её до, например, 2^32 (доступно для перебора). Для непосвящённого в атаку аналитика, контролирующего качество элементной базы, результаты выглядят вполне себе добротно. Изменения не обнаруживаются и встроенной в схемотехнику системой самопроверки. Примерно такой подход снижения сложности перебора ключей, кстати, обсуждается в записке о гипотетической системе прослушивания TLS. Думаю, не нужно напоминать, что оборудование Intel весьма распространено.

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

Статья про технологию DANE, которую я написал для “Открытых систем”, появилась в общем доступе на сайте – почитайте.

“Серьезности ситуации придает то, что наличие валидного сертификата и соответствующего закрытого ключа, например для домена example.com, позволяет перехватывать и полностью «прослушивать» пользовательский HTTPS-трафик к сервисам, работающим под этим именем, путем организации атаки типа «человек посередине» с подменой сетевого узла. При этом браузер пользователя не будет выдавать никаких предупреждений, полагая, что соединение устанавливается с доверенным сайтом.”

UPDATE (06.05.13) – статья доступна. UPDATE (03/06/13): по неясной мне причине, статью опять убрали в доступ по подписке. Окей, ладно, это право издателя.

В свежем журнале “Открытые системы” моя статья про технологию DANE (доступ по подписке). Напомню, что DANE – это весьма полезное улучшение для систем безопасности, действующих в Интернете: cуть DANE состоит в публикации дополнительной информации об использовании SSL-сертификатов при помощи DNS, защищённой DNSSEC.

(Я часто писал про DANE на dxdt.ru.)

На stat.nic.ru – очередное обновление: большая статья с результатами исследования веб-технологий, используемых в Рунете, и их сравнением с международным сегментом Сети (тему в RU-CENTER ведёт Артемий Ломов). Данных много, поясняющего текста тоже немало. Рекомендую всем, кому интересно, как сейчас устроен рунетовский веб. Исследование, вообще говоря, уникальное.

Оказывается, “сверхсветовые” нейтрино детектировали ещё и используя другое оборудование, независимое от OPERA. Выводы вот такие:

Таким образом, ICARUS прямо опровергает данные OPERA и подтверждает ожидания теории относительности.

(По ссылке – заметка Игоря Иванова с подробностями, опять рекомендую.)

Помните про “сверхсветовые” нейтрино, которые обсуждались осенью? На сайте ЦЕРНа вчера появилось обновление, касающееся этого эксперимента. Сообщают о том, что дополнительные проверки-перепроверки выявили два возможных направления, которые могли привести к ошибке измерений (а могли и не привести к ошибке, да; более того, там разные оценки есть: ошибка могла быть как в сторону увеличения измеренной величины, так и в сторону уменьшения). Насколько можно понять из краткого сообщения, речь идёт о контуре, связанном с обработкой отметок времени GPS – обе потенциальных проблемы кроются в нём. Измерять уровень возможных искажений планируют только в мае. Ждём, в общем, что там “лазеры покажут”.

Многие интересуются научно-техническими деталями того, как нашли и вскрывали “подлёдное” озеро Восток, и что это за озеро такое вообще. Читать об этом нужно в блоге Игоря Иванова: там две заметки с описаниями сейсмограмм и другими интересными пояснениями.

Без самолётов и радаров, как вы понимаете, тоже не обошлось.

Пять лет назад я упоминал про скандал, связанный с журналом Topology: тогда редакционная коллегия этого научного журнала отказалась участвовать в его подготовке. Так вот, борьба с издательской компанией Elsevier активно продолжается. Сейчас на специально созданной странице собирают подписи тех учёных, кто решил отказаться от сотрудничества с Elsevier в знак протеста. Протест связан с тем, что издатель завышает цены на доступ к журналам (да, нездоровая коммерция в науке последние годы крепнет) и навязывает библиотекам “подписные пакеты”, не позволяя выбрать только реально нужные издания (понятно, что пакеты при этом тоже недешёвые). Ещё одна причина недовольства, которую часто называют, в том, что Elsevier поддерживает всякие мутные начинания в области ограничения обмена информацией, типа нашумевшего SOPA.

На страничке акции, озаглавленной The Cost of Knowledge, уже собрано более 1370 подписей, и это число быстро растёт.