Теория и практика защиты программ

Сведение защиты программ к забывающему моделированию на RAM-машине


Наконец сейчас будет показано, как свести задачу защиты программ к задаче моделирования RAM-машины на забывающей RAM-машине. Эта задача заключается в сокрытии модели доступа, полностью игнорируя тот факт, что содержимое памяти и коммуникаций между ЦП

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

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

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

RAM-машины остается только скрыть содержимое «области значений» в сообщениях, обмениваемых между ЦП и МП. Это делается посредством шифрования, которое использует случайный оракул.

Теорема5.1. Пусть {RAMk}kÎN - вероятностная RAM-машина, которая выполняет забывающее моделирование универсальной RAM-машины. Кроме того, предположим, что t шагов оригинальной RAM-машины моделируются за менее чем g(t)t шагов забывающей RAM-машины. Тогда существует компилятор, который защищает программы от невмешивающихся противников с затратами не боле O(g(t)).

Доказательство.

Информация, доступная невмешивающемуся противнику состоит из сообщений, обмениваемых между ЦП и МП. Напомним, что сообщения от CPUk к MEMk имеют форму (i,a,v), где iÎ{выборка, сохранить, стоп}, aÎ{1,2,...,2k} и vÎ{0,1}O(k), в то время как сообщения от MEMk к CPUk имеют форму vÎ{0,1}O(k). При забывающем моделировании, по определению, «область адресов» (т.е., a) не вскрывает никакой информации относительно входа y=(Пf,x).
Просто необходимо устранить возможность, когда «область команд» (т.е., i) «давала бы» какой-либо полезную информацию для противника. Следовательно,  осталось только завуалировать содержимое области значений (т.е., v) так, чтобы ЦП мог восстанавливать оригинальные значения. Идея состоит в том, чтобы выполнить завуалировать v, используя оракул, доступный ЦП.



www.kiev-security.org.ua

BEST rus DOC FOR FULL SECURITY

Для завуалирования машина CPUk

содержит специальный счетчик, обозначаемый счт, инициализированный нулевым значением. Мы модифицируем RAMk добавлением случайного оракула, обозначаемого f. Понятно, что новый случайный оракул может быть объединен со случайным оракулом, используемым при забывающем моделировании. Всякий раз, когда CPUk должен сохранять значение в памяти MEMk, счетчик счт увеличивается и значение v шифруется посредством пары (vÅf(счт),счт), где Å обозначает поразрядную операцию «исключающую или». При восстановлении пары (u,j), завуалированное значение восстанавливается посредством вычисления uÅf(j). Подчеркнем, что и завуалирование, и восстановление может быть легко выполнены, когда имеется доступ к оракулу f.

Компилятор C, защищающий программное обеспечение, функционирует следующим образом. На входе параметр k и программы П, состоящей из последовательности команд p1,..,pn, компилятор однородно выбирает функцию f

и множества Пf=(p1Åf(2k+1),2k+1),...,(pnÅf(2k+n),2k+n).

Так как общее время выполнения машины RAMk

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



Напомним, что на практике можно заменять случайный оракул на псевдослучайный. Следовательно, результат теоремы будет верен только для противников, ограниченных по времени некоторым полиномом. В этом случае, компилятор на входном параметре k и программе П равномерно выбирает псевдослучайную функцию f. Функция f может быть аппаратно реализовано в CPUk. Таким образом, ЦП способен вычислять f на входах длины k и poly(k)-временной противник не может различать поведение этого ЦП

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

Теорема 5.2. Пусть {RAMk}kÎN - вероятностная RAM-машина, которая выполняет забывающее моделирование с метками времени универсальной RAM-машины. Кроме того, предположим, что t шагов оригинальной

RAM-машины моделируются меньше, чем за g(t)t шагов забывающей

RAM-машины. Тогда существует компилятор, который защищает программное обеспечение от вмешивающихся противников, с затратами не более O(g(t)).

Доказательство.

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

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

Центральный процессор CPUk, рассмотренный в предыдущей теореме, далее модифицируется следующим образом. Модифицированная машина CPUk

имеет доступ к еще одной случайной функции, обозначаемой f.


Эта функция может быть объединена с другими. В случае если CPUk желает сохранить завуалированное значение v

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

в ответ на запрос («выборка»,a,·), модифицированная машина CPUk определяет текущее значение номера версия(a) и сравнивает t с f(a, версия(a),v). В случае, если эти два значения равны CPUk

работает как и прежде. В противном случае, CPUk

немедленно останавливается, предотвращая, таким образом, защиту от вмешательства. Таким образом, попытки изменить сообщения от МП к ЦП

будут обнаружены с очень высокой вероятностью.   <


Содержание раздела