Криптографическая обфускация и принцип «белого ящика» в криптографии

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

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

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

Определение обфускатора

Обфускатор O представляет из себя «компилятор», который принимает на вход программу P и на выходе выдает обфусцированную программу O(P). В соответствии с W09 вероятностный алгоритм O является обфускатором, если выполняются следующие три условия:

1. Для любой машины Тьюринга M, O(M) описывает машину Тьюринга, которая вычисляет ту же функцию, что и M;
2. Имея доступ к O(M) злоумышленник не сможет узнать об M больше, чем можно узнать об M, имея к ней доступ как к «черному ящику»;
3. Размер описания и время выполнения O(M) полиномиально зависят от соответствующих величин машины Тьюринга M. То есть должен существовать полином p такой, что для каждой машины Тьюринга M:

где |M| – это размер описания машины Тьюринга M. И если M завершает выполнение через t шагов при некотором входе x, то O(M) при том же входе x завершает выполнение через p(t) шагов.

История изучения

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

Впервые определение криптографической обфускации и обфускаторов программного кода было формально предложено в работе Хады (H00), после чего оно было модифицировано в работе Барака и его коллег (BGIRSVY01). В последующих своих работах Барак и коллеги доказали, что в соответствии со сформулированным ими определением будут существовать программы, которые будет невозможно обфусцировать. Для доказательства данного утверждения они построили семейство функций, которые в соответствии с их определением не могут быть обфусцированы.

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

Первым подходом к криптографической обфускации, который был сформулирован и достаточно широко изучен, является принцип «черного ящика».

Принцип «черного ящика»

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

При этом Алисе мы дадим копию обфусцированной программы O(P), т.е. она сможет запустить ее на своем ПК. Копию исходной программы P мы запустим на компьютере, помещенном в «черный ящик», и дадим доступ к нему Бобу. При этом Боб может взаимодействовать с программой, подавая ей данные на вход и получая выходной результат. В этом случае обфускация будет являться безопасной в случае, если Алиса не узнает о внутренней работе программы больше, чем Боб.

В описании эксперимента при детальном рассмотрении было найдено несколько слабых мест. Например, после окончания эксперимента у Боба не будет доступа к программе P, в то время как у Алисы будет копия обфусцированной программы O(P), которая будет работать. Для их устранения в работе Барака и коллег было предложено использовать программу, которая вычисляет некоторый предикат и в качестве результата возвращает один бит.

Кроме того, Барак с коллегами в BGIRSVY01 показали, что не могут быть обфусцированы некоторые виды криптографических примитивов, в частности – примитивы, которые используют однонаправленные функции. Однако, здесь стоит особо отметить, что речь идет не о конкретном обфускаторе для конкретного примитива, а об общем обфускаторе для всего семейства примитивов. Иными словами, было доказано, что принцип «черного ящика» не подходит для обфускации любой программы в общем случае. Голдвассер и Калай представили схожие результаты в GK05, а Хада с коллегами в H00 показали, что невозможно обфусцировать псевдо-случайную функцию.

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

Рассмотрим пример такой функции (функция 1), которая проверяет переданный ей на вход пароль на соответствие константе, которая хранится в функции.

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

Обфусцированная версия не содержит правильный пароль в открытом виде. В своих работах Ви (W05) и Канетти (C97, CD08) показали, что если правильный пароль для этой функции очень трудно угадать (иными словами он выбирается случайно из очень большого множества паролей) и используемая хэш-функция является стойкой, то функция 2 является криптографически обфусцированным вариантом функции 1.

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

Перспективные работы в области криптографической обфускации

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

Пусть даны две программы C1 и C2, вычисляющие одну и ту же функцию. При этом при одинаковых значениях входных параметров, данные программы имеют одинаковое выходное значение, но внутри реализованы данные программы могут быть совершенно по-разному. Тогда преобразование «неразличимой обфускации» - это такое преобразование обфускации, при котором не существует эффективного алгоритма, который сможет отличить O(C1) от O(C2).

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

Другим перспективным направлением исследований в данной области является преобразование «различающая обфускации». «Различающий обфускатор» гарантирует, что если нарушитель сможет все-таки различить обфусцированные программы O(C1) и O(C2), то он сможет найти такие значения входных параметров, при которых O(C1) от O(C2) дадут различные выходные значения. Принципы построения таких обфускаторов представлены в работе B14.

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

Модели криптосистем и принцип «белого ящика» в криптографии

Классическая модель криптосистемы была впервые представлена в классической работе Клода Шеннона «A mathematical theory of communication». Описанная им модель представлена на рисунке 1.

Современная классическая модель построена на принципе Керкгоффса. Как правило взаимодействуют 2 стороны (Алиса и Боб), которые хотят передать сообщение m конфиденциальным образом по открытому каналу связи. Для этого они вырабатывают общий ключ k и по открытому каналу связи Алиса передает уже не исходное сообщение m, а зашифрованное c.

В свою очередь Боб на общем с Алисой ключе k расшифровывает полученное сообщение c и получает исходное m.

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

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

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

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

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

Кроме того, в своей работе Чоу с коллегами представили модель нарушителя в рамках модели, реализующей принцип «белого ящика». Она состоит из трех пунктов:

1. Вредоносное ПО, обладающее правами администратора, установлено на том же хосте, что и криптографическое ПО;
2. Нарушитель может исследовать криптографическое ПО с помощью методов динамического анализа;
3. Внутренние данные и механизмы работы криптографического алгоритма известны нарушителю и он может их изменять.

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

1. Исходя из того, что все части алгоритма известны злоумышленнику - они должны быть рандомизированы;
2. Используемый криптографический ключ должен быть распределен по всей исполняемой программе, для того, чтобы злоумышленник не смог его извлечь, изучив лишь часть программы.

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

Реализации криптосистем с использованием принципа «белого ящика» в криптографии

В последующих работах рабочая группа под руководством Чоу представили реализации алгоритмов DES и AES, реализованных с помощью принципа «белого ящика». Реализация DES в частности предназначалась для использования в систем защиты интеллектуальной собственности. Однако в обеих реализациях позже были найдены уязвимости, которые делают их неприменимыми на практике. Атака представлена в работе Джейкоба и коллег.

В 2004 году Биллет с коллегами в своей работе представили очень эффективную атаку на «white-box» реализации шифра AES, которая заключалась в использовании специальным образом подобранных таблиц поиска.

В 2005 году Линк и Ньюман представили собственную реализацию DES, которая являлась стойкой ко всем известным на тот момент атакам. Но в 2007 году все существующие реализации DES, использующие принцип «белого ящика» в криптографии, были взломаны независимо группами под управлением Вайзера и Гаубина. При этом подходы, используемые для криптоанализа реализаций DES, у данных групп отличались.

Обзор основных принципов построения реализаций с использованием принципа «белого ящика» и наиболее эффективных атак представлены в работе W09. Успешные атаки на такие криптосистемы с использованием фреймворков бинарной инструментации представлены в работе B15.

Рассмотрим атаки, которые могут быть нивелированы с использованием принципа «белого ящика».

Применение принципа «белого ящика» в криптографии

В наше время принцип «белого ящика» в криптографии находит два основных применения. Это технические средства защиты авторских прав и аггрегирующие поисковые системы, представленные выше. Кроме того, данный принцип широко применяется для создания военных криптосистем. Представляется, что данный принцип найдет широкое применение при написании криптографического программного обеспечения под мобильные платформы.

Мировые лидеры IT-индустрии (Sony, Microsoft) представляют свои реализации программных продуктов, использующие принцип «белого ящика» в криптографии. Сотрудники компании Samsung в этом году в своей работе C15 представили новый подход к реализации криптосистем с использованием принципа «белого ящика», который направлен в основном на коммерческие программные системы, использующие криптографию внутри. Летом 2015 года компания Xiaomi внедрила систему защиты данных пользователей whiteCryption , которая реализует принцип «белого ящика» в криптографии в свои продукты.

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

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

С другой стороны реализация криптографических алгоритмов (шифрования, расшифрования) обладает малой энтропией, потому что представляет собой исполняемый файл, состоящий из определенных инструкций под конкретную платформу. На рисунке 2 представлен дамп памяти реализации криптографического алгоритма с «зашитым» секретным ключом. Нулевой бит представлен на рисунке черным квадратом, единичный бит - белым квадратом.

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

Данная атака была представлена в 1998 году Шамиром и Ван Сомереном. Она применима для любых контейнеров, к которым у нарушителя есть права на чтение - будь то дамп оперативной памяти или исполняемый файл на жестком диске. Идеи, предложенные Шамиром и Ван Сомереном были развиты в работе Халдермана и его коллег.

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