White-Box Cryptography: Расшифровываем эту белую коробку

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

В общем криптографическую систему в таком случае можно представить как какой-то black box, который на вход принимает какие-то данные и ключ и на выходе отдает эти данные в преобразованном виде (шифрованные или расшифрованные в зависимости от контекста).

Главная наша цель при атаке на криптографическую систему – это узнать секретный ключ, который в ней используется. Поэтому, когда мы можем взаимодействовать с данной системой, только подавая на вход какой-то определенный input и оценивая выход работы программы, такой контекст атаки называется black-box context.

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

Соответственно при обычной реализации какого-то криптографического алгоритма, если злоумышленник имеет доступ к самому исполняемому файлу, он может легко вычленить оттуда секретный ключ. Поэтому нам как безопасникам важно исключить такую возможность. Именно с этой целью и была придумана технология White-Box Cryptography (WBC).

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

Мы в рамках нашей статьи будем рассматривать только WBC для алгоритмов симметричного шифрования (т.е. AES, DES).

Технология WBC

Впервые термин White-Box Cryptography вместе с первой его имплементацией для алгоритмов DES и AES был упомянут в 2002 году в работах Chow et al [1,2]. Как уже было сказано, цель WBC – это не дать злоумышленнику вытащить ключ из имплементации какого-либо криптографического алгоритма, поэтому алгоритмы WBC «прячут» ключ в самой имплементации алгоритма. Схематично, например, white-box DES будет выглядеть примерно так.

В работе Chow показано несколько подходов к реализации WBC. Для основного «замыливания» ключа предлагается использовать так называемые look-up tables. Look-up tables – это таблицы, которые уже содержат заранее посчитанные операции алгоритма с учетом ключа и работают в данном случае как S-box. Схематично это можно представить следующим образом.

Однако, как видим, при дебаге программы все равно можно узнать информацию о состоянии шифрованных данных на каждом раунде алгоритма, поэтому вместе с таблицами также используются внутреннее и внешнее кодирование (internal and external encoding).

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

Внешнее же кодирование применяется к выходным данным алгоритма шифрования, чтобы препятствовать атакам различного рода. При использовании внешнего кодирования при процессе шифрования, когда закодированный шифр-текст попадает на вход дешифратора, он дополнительно декодируется и далее дешифруется. Таким образом, при использовании внутреннего кодирования из старой таблицы T получается новая таблица T’:

где g, f – случайные функции кодирования, f^-1 – функция декодирования.

Если R – следующая таблица, идущая после T, то она преобразится следующим образом:

то есть две подряд идущие таблицы будут давать следующий результат:

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

Однако, данные имплементации WB-AES и WB-DES были взломаны в 2004 в статье Billet et al. [3]. Были и попытки улучшения алгоритма Chow. Например, в [4], где вместо look-up tables использовались функции над полем F_2ⁿ для определенного значения n вместе с кодированием и добавочным шумом в виде случайных вычислений. Однако, класс подобных схем, основанных на работе Chow, был взломан в работе [5].

Новый подход к конструированию алгоритмов WBC использует методы «неразличимой обфускации» (indistinguishability obfuscation, iO) [6]. Однако, существующие конструкции iO не являются практичными, и требуются дополнительные исследования в области конструирования WBC на iO.

Поскольку на данный момент не существует открытых безопасных алгоритмов WBC, компании используют проприетарные алгоритмы WBC по принципу «security by obscurity», то есть безопасность данных алгоритмов WBC строится на их неизвестности. Чтобы взломать проприетарные WBC-алгоритмы, на данный момент существует несколько типов атак, которые мы рассмотрим далее.

Атаки на WBC

1. Differential Fault Analysis

Differential Fault Analysis (DFA) – специальная атака для алгоритмов DES и AES, впервые представленная в [7]. Для реализаций WB-AES и WB-DES данная атака была представлена в работах [8] и [9]. Суть атаки заключается в следующем:

1. Атакующий встраивает ошибки в данные по ходу выполнения работы программы. Чаще всего меняются данные, подаваемые на вход на последнем раунде алгоритма. Если WBC представлено как хардварное решение (то есть нет доступа к самому бинарю), то ошибки могут вноситься при помощи изменения окружающей среды устройства (например, скачки напряжения и т.п.).

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

Покажем данную атаку на примере шифра AES-128. Будем вставлять ошибку перед алгоритмом MixColumns на 9 раунде.

Проведем все операции 9 и 10 раунда на наших данных с ошибкой. Сначала идет MixColumns. Поскольку нам не интересны значения в ячейках таблицы, которые не поменяются из-за ошибки, не будем их расписывать. Так как MixColumns влияет на весь столбец с ошибкой, получаем следующий вид.

Далее идет операция AddRoundKey 9 раунда, и начинается последний 10 раунд, который не включает в себя MixColumns. После преобразований итоговые значения будут выглядеть так. К_i,j – это значения i-го байта ключа на j-1 раунде.

Мы получили измененные значения после внесения ошибки и имеем корректные значения без ошибок. Получаем следующие пары уравнений для каждой ошибки. Например, для крайней левой ячейки получим два следующих уравнения:

Далее заксорим два выше указанных уравнения и получим следующее:

для которого можем найти набор потенциальных решений для первого байта ключа. Такие же уравнения строим для каждой внесенной ошибки и получаем возможные варианты ключей. Для уменьшения количества возможных вариантов встраиваем другие ошибки и в конце концов получим значение ключа. Для AES-128 нам хватит всего одного раундового ключа, чтобы восстановить весь ключ, для AES-192 и AES-256 потребуется уже 2 раундовых ключа.

Для применения данной атаки к имплементации AES предварительно нужно определить, на какой инструкции начинается новый раунд. Это можно сделать с помощью статического или динамического анализа приложения.

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

2. Differential Computational Analysis

Differential Computational Analysis (DCA) на данный момент является одной из самых эффективных атак на WBC, так как она не требует полной информации о white-box конструкции алгоритма, поэтому на реверс самого приложения не тратится большое количество времени. Сама атака была впервые представлена в работе Bos et al. [10]. DCA по факту является атакой DPA (Differential Power Analysis), только с учетом специфики применения к WBC.

Сама атака состоит из нескольких шагов.

Шаг 1: Определение алгоритма. Сначала собираем трассу работы приложения, а именно – данные и адреса, которые использовала программа. И, визуализируя трассу, анализируем, какой алгоритм перед нами находится. Вот так, например, по трассе ниже можно определить, что перед нами алгоритм DES, так как видна цикличность в 16 раундов. (Черной линией представлены адреса инструкций, а зеленой – адреса памяти, из которых читали и куда записывали информацию; по оси абсцисс находятся виртуальные адреса приложения, по оси ординат – время).

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

Шаг 3: Преобразование трассу к виду, необходимому для использования DPA-атаки. Далее нам осталось определить ключ, проанализировав нашу трассу, используя утилиты для DPA. Для этого нашу трассу, состоящую из полученных адресов и данных, нужно преобразовать в вектора нулей и единиц. Когда мы используем DPA, то зачастую в качестве источника информации, с которого собирается трасса, является 8-битная шина памяти, где все 8 линий будут переключаться между низким и высоким напряжением в зависимости от передаваемых данных. В таком случае аналоговым значением является общая мощность передаваемого сигнала, то есть сумма единиц в байте, и модель атаки тогда использует расстояние Хемминга между предполагаемыми и замеренными значениями при реализации атаки DPA. Однако в данном случае мы можем атаковать не один байт, а один бит, условно представив, что данные передаются по шине из одного бита. На рисунке ниже видна разница между замером трассы на железке с реализованным алгоритмом AES (а) и программной трассы, преобразованной к такому виду (b).

Шаг 4: Применение DPA к нашей преобразованной трассе. Приведя трассу к удобному виду, запускаем на нее атаку DPA, которая с помощью статистических методов определит вероятное значение ключей. Подробно про атаку DPA можно прочитать здесь [11].

DCA является универсальной атакой на алгоритмы WBC, однако на данный момент существуют определенные способы защиты против нее, а именно – маскировка (англ. masking). Суть маскировки заключается в «замыливании» входных данных и использовании случайности в вычислениях. Например, в работе [12] данные, подаваемые на вход, делятся определенным образом на n частей

где x ∈ F₂  и части независимо друг от друга преобразуются, а потом собираются вместе определенным образом.

Поскольку главными преимуществами атаки DCA являлись ее универсальность и возможность не тратить время на дополнительный реверс приложения, то такой подход значительно осложняет использование данной атаки. Для атаки на маскированные white-box имплементации используются специальные алгебраические атаки (algebraic attacks), с которыми можно ознакомиться в работах [13, 14].

Методы защиты на уровне приложения

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

• Обфускация приложения. Обфускация затруднит процесс реверса приложения, сюда относятся обфускация потока выполнения программы, а также обфускация данных.

• Анти-отладочные и анти-тамперинг механизмы. Данные методы будут определять использование дебаггера или эмулятора и прерывать процесс работы программы, а также будут определять хуки и модификации программы. Данные методы сильно осложнят злоумышленнику использование различных атак, например DFA.

• Привязка к железу/приложению. WBC может быть реализован как модуль на каком-то железе или в рамках большого приложения. Поэтому злоумышленник может просто изъять данный модуль и использовать только его, а не само приложение, что может позволить ему, не зная ключа, расшифровать/зашифровать все данные, которые ему потребуются. Поэтому такие механизмы необходимы для защиты от подобных атак.

В данной части мы подробно описали WBC и рассмотрели атаки на него. В следующей части мы покажем практическую реализацию атак на различные имплементации WB с примерами кода и используемых инструментов.