AES против осциллографа

Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!

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

Введение

В 2007 году компания Nvidia представила первую версию CUDA — программно-аппаратную архитектуру параллельных вычислений, позволяющую использовать графические ускорители для большего класса задач, нежели только рендеринг изображений. Переведя свои графические процессоры из разряда GPU в разряд GPGPU (General Purpose GPU), Nvidia сделала массивно-параллельные вычисления доступнее для широкого круга задач. В частности, видеопроцессоры оказались применимы к задачам шифрования, и разработчики криптографических библиотек воспользовались возможностью ускорить вычисления. К сожалению, как и любые электронные устройства, видеокарты излучают электромагнитные волны, и характер этого излучения зависит от конкретных действий графического процессора. Пристальное наблюдение за таким излучением позволило группе ученых из UCAS взломать шифр AES, узнав значение секретного ключа.

Краткое напоминание

Прежде чем перейти непосредственно к атаке, нелишним будет вспомнить основы CUDA и AES:

CUDA

CUDA (Compute Unified Device Architecture) — это программно-аппаратная архитектура параллельных вычислений, предложенная компанией Nvidia для своих графических процессоров общего назначения. Давайте посмотрим на CUDA с двух различных ракурсов.

С точки зрения программиста

При написании программ, использующих CUDA, программист имеет дело со следующими сущностями:

Программист сам определяет число потоков в блоке и блоков в сетке, исходя из особенностей решаемой задачи. Подробнее про программирование с использованием CUDA можно узнать здесь и тут.

Для эффективного управления описанными сущностями необходимо понимать, как они связаны с аппаратной реализацией GPGPU.

С точки зрения CUDA

С точки зрения CUDA, GPGPU выглядит следующим образом (на этот раз движемся снизу вверх):

Ещё одна важная особенность работы GPGPU, не выраженная столь явно, связана с исполнением блоков. Каждый блок исполняется группами по 32 нити (warp). Внутри такой группы все потоки выполняют одну инструкцию над разными данными, то есть реализуют так называемую SIMT-архитектуру (Single Instruction Multiple Threads).

Более полное описание архитектуры GPGPU можно найти в Белой книге, на Вики и в официальной документации. Полезным может показаться и это обсуждение.

Для понимания атаки предоставленного описания должно быть достаточно.

AES

Advanced Encryption Standard (AES), также известный как Rijndael — популярный симметричный алгоритм блочного шифрования. Он оперирует блоками данных длины 128 бит при длине ключа 128, 192 или 256 бит. Так как атака демонстрировалась на шифровании с длиной ключа 128 бит, пока уберем прочие размеры из рассмотрения и сфокусируемся на алгоритме для длины ключа 128 бит.

AES-128 представляет входной блок текста в виде матрицы S размером 4 на 4 байта, называемой состоянием (state), и 11 раз последовательно применяет к нему следующие операции:

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

AddRoundKey(0)

for (i = 1; i <= 10; i += 1) {
    SubBytes()
    ShiftRows()
    MixColumns()
    AddRoundKey(i)
}

SubBytes()
ShiftRows()
AddRoundKey(11)

В качестве финального замечания необходимо отметить, что все сложения и умножения производятся в конечном поле GF(2^8) . Простыми словами, сложение двух байтов эквивалентно применению к ним операции ИСКЛЮЧАЮЩЕЕ-ИЛИ, которую мы будем обозначать символом $\oplus$ .

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

Говоря об AES, нельзя не упомянуть пьесу про AES, в частности — акт третий, сцена вторая.

Описание атаки

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

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

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

Физические основы

В основе атаки лежит наблюдение за ближним полем — электромагнитным излучением в области, удаленной от источника не более, чем на $1/2\pi$ длины волны. Авторы заметили, что существует явная связь между операциями, выполняемыми GPGPU, и видом электромагнитного поля, излучаемого видеокартой. Результатом одного измерения является набор точек, снятых с электронного осциллографа и характеризующих зависимость напряжения исследуемого поля от времени для последнего раунда шифрования. Каждое такое измерение имеет одинаковое число точек, синхронизированных по времени. В дальнейшем мы будем называть эти точки отсчетами.

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

Кэш-коллизии

В качестве операции, надежно генерирующей различимые сигналы, авторы рассматривают одновременную кэш-коллизию (Simultaneous Cache Collision, SCC). В процессе исполнения все потоки, принадлежащие одной warp-группе, могут обратиться к данным, находящимся в одной (происходит SCC) или различных (SCC не происходит) кэш-линиях. При этом генерируемый электромагнитный сигнал будет различаться.

Заметим, что длина кэш-линии GPGPU архитектуры Fermi, рассматриваемой в данной работе, составляет 128 байтов. Размер же таблицы SBoxLUT, используемой на этапе SubBytes, составляет 256 байтов, то есть для размещения таблицы в памяти требуется две кеш-линии, по одной на первую и вторую половину. Отсюда же видно, что наличие SCC говорит об обращении всеми потоками к SBoxLUT по индексам либо из диапазона $D_1 = \{0~..~127\}$ , либо из $D_2 = \{128~..~255\}$ .

Атака

Обработка данных утечки

Рассмотрим последний раунд шифрования текста. Он описывается следующим уравнением:

$c_l = SBox(r_l) \oplus k_l, ~l \in \{0, 1, ..., 15\},$

где $c_{l}$ и $k_{l}$ — -ый байт шифротекста и -ый байт последнего раундового ключа, соответственно, а $r_{l}$ — некоторое промежуточное значение. Злоумышленник может предположить, что использовался ключ $k^{guess}$ . В таком случае, зная $c_{l}$ , можно найти величину промежуточного байта $r_{l}$ :

$r_l = InvSBox(c_l \oplus k^{guess}_l),~l \in \{0, 1, ..., 15\},$

где InvSBox — таблица обратной замены, известная из стандарта и обладающая свойством , а $k^{guess}_l$ — -ый байт предполагаемого ключа $k^{guess}$ . Мы предположили, что злоумышленник может шифровать любой текст. В частности, он может заготовить текст, состоящий всего из двух типов блоков. При шифровании такого текста значения -го байта $r_{l}$ , полученные каждым из потоков, будут принимать всего два различных значения: $r_{l}^1$ и $r_{l}^2$ . Будучи использованными в качестве индексов для обращения к таблице SBoxLUT, они либо приведут к кэш-коллизии, либо нет. Зная $r_{l}^1$ и $r_{l}^2$ , отличить эти случаи несложно: коллизия происходит только когда обе величины принадлежат одному диапазону: или .

Следующим шагом злоумышленника будет разделение полученных измерений ЭМ-поля на две группы и согласно вычисленным и : где коллизии были и где их не было. Формально это можно записать так:

$G_1 = \{ \vec{T_i}~|~(r_l^1 \in D_1~\text{и}~r_l^2 \in D_1)~\text{или}~(r_l^1 \in D_2~\text{и}~r_l^2 \in D_2) \},$ $G_2 = \{ \vec{T_i}~|~(r_l^1 \in D_1~\text{и}~r_l^2 \in D_2)~\text{или}~(r_l^1 \in D_2~\text{и}~r_l^2 \in D_1) \},$

где под $\vec{T_i}$ понимается набор точек, соответствующих одному раунду шифрования.

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

$\vec{\Delta} = \left| \frac{1}{n_1}\sum_{\vec{T_i} \in G_1} \vec{T_i} - \frac{1}{n_2}\sum_{\vec{T_i} \in G_2} \vec{T_i} \right|,$

показывающую, насколько сильно отличаются средние значения сигналов, помещенных в множества и . Под операцией суммирования здесь понимается сложение соответствующих отсчетов сигналов, а под переменными и — мощности множеств и , соответственно. Здесь необходимо отметить, что, поскольку разбиение сигналов на группы зависит от $k^{guess}_l$ , то и $\vec{\Delta}$ является функцией от $k^{guess}_l$ : $\vec{\Delta} = \vec{\Delta}(k^{guess}_l)$ .

Восстановление ключа

Если предполагаемый ключ $k^{guess}$ совпал с ключом, использованным для шифрования, то восстановленные значения и совпадут с действительно использованными при шифровании, и злоумышленник верно распределит сигналы по группам. Наоборот, при ошибочном выборе $k_{guess}$ разделение на группы по вычисленным промежуточным значениям и приведет к равномерно перемешанным сигналам. При этом значения компонент $\vec{\Delta}(k^{guess}_l)$ в первом случае будут заметно превосходить соответствующие компоненты во втором. Таким образом, для вычисления -го байта секретного ключа злоумышленнику достаточно будет перебрать 256 возможных значений и выбрать то, при котором $\vec{\Delta}(k^{guess}_l)$ принимает наибольшее значение. Делать это авторы предлагают следующим образом:

$\DeclareMathOperator*{\argmax}{argmax} k_l^{correct} = \argmax_k \left( \max_{k\in\{0~..~255\}} \left( \max_{i} \Delta_i \right) \right),$

где $\Delta_i$ — -я координата вектора $\vec{\Delta}$ . Формула легко интерпретируется: каждому из значений соответствует вектор $\vec{\Delta}(k)$ с наибольшей -ой координатой. Запомнив абсолютное значение этой координаты, из полученных 256 значений нужно снова выбрать наибольшее. Соответствующее ему принимается за искомый байт ключа $k^{correct}_l$ . Повторив описанную процедуру для каждого $l \in \{ 0~..~15 \}$ , злоумышленник сможет восстановить полное значение последнего раундового ключа в расписании. Алгоритм восстановления исходного секретного ключа, используемого при генерации расписания, из последнего раундового ключа для алгоритма AES-128 известен и уже обсуждался здесь или здесь.

В работе авторы показывают, что для успешного восстановления ключа таким методом достаточно собрать данные порядка 1000 шифрований, что требует порядка 100 миллисекунд. Дополнительное использование алгоритма перечисления ключей KEA позволяет сократить число измерений до 600.

Сейчас, изучив атаку в деталях, стоит ещё раз посмотреть на её план — теперь он будет гораздо понятнее.

Вместо заключения

На данный момент известно лишь об одной успешной атаке, проведенной данным способом. Эту атаку провели сами авторы оригинальной статьи. В качестве атакуемой видеокарты была выбрана Nvidia GeForce GT 620 с объемом видеопамяти 454MiB. Библиотека, реализующая шифрование — PolarSSL. Для детектирования электромагнитных следов авторами использовался осциллограф Agilent KeySight DSO9104A с пробником магнитного поля Rohde&Schwarz RF B.

Данная атака позволяет узнать значение последнего раундового ключа. В случае шифрования AES-128 этого достаточно, чтобы восстановить исходное значение секретного ключа, однако версии AES-192 и AES-256 остаются устойчивыми к взлому данным образом. Например, знание последнего раундового ключа AES-256 лишь сужает область возможных значений исходного с 2²⁵⁶ до 2¹²⁸, и дальнейший подбор остается вычислительно неосуществим.

Атака впервые применяет изучение ЭМ-утечек информации к взлому шифрования на GPGPU и во многом превосходит другие известные атаки по стороннему каналу. Так, например, она требует на три порядка меньше измерений, чем атака, описанная в похожей работе.

Несмотря на то, что проведение атаки в реальной жизни на данный момент затруднительно, она остается интересной с научной точки зрения и может дать толчок дальнейшему развитию идей в исследуемом направлении.

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

Источник: https://habr.com/ru/post/533012/

Вернуться к списку

Интересные статьи

Kubernetes на собственной инфраструктуре: «за» и «против» приватных облаков

Уважаемые читатели, доброго дня! В данной статье Игорь Котенко, главный архитектор компании «Неофлекс», делится опытом развертывания платформы контейнеризации на инфраструктуре пре...

Финансирование Гражданской войны (США против КША)

Перевод статьи Michael A. Martorelli про источники финансирования войны США против КША — история печати долларов обеих сторон, подделка купюр, займы и облигации, сбор налогов и многое...

Bitrix. Аудит своими руками

Всем привет. Когда я искал информацию о журналировании (аудите событий) в Bitrix, на Хабре не было ни чего, в остальном рунете кое что было, но кто же там найдёт? Для пополнения базы знаний...

Jira REST API. Интеграция Jira с Битрикс КП

Как-то у нас исторически сложилось, что Менеджеры сидят в Битрикс КП, а Разработчики в Jira. Менеджеры привыкли ставить и решать задачи через КП, Разработчики — через Джиру.

2011v2 vs AM4. Динозавры против млекопитающих

Это не столько самостоятельная публикация, сколько дополнение и, что главное, исправление моей прошлогодней 1155 vs 2011. В бой идут одни старики. Тогда у меня не оказалось на руках платформы AM4...