Защита программ и забывающее моделирование на RAMмашинах

Основные положения

В этом разделе рассматриваются теоретические аспекты защиты программ от копирования. Эта задача защиты сводится к задаче эффективного моделирования RAMмашины (машины с произвольным доступом к памяти [2]) посредством забывающей RAMмашины. Следует заметить, что основные результаты по данной тематике (их можно получить на соответствующем личном интернетовском сайте) принадлежат О. Голдрайху и Р. Островски и эти исследования активно продолжаются в настоящее время.

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

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

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

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

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

Сокрытие оригинальной модели доступа к памяти это абсолютно новая проблема и традиционные криптографические методы здесь не применимы. Цель в таком случае состоит в том, чтобы сделать невозможным для противника получить о программе чтолибо полезное из модели доступа. В этом случае ЦП не будет выполнять программу обычным способом, однако он заменяет каждый оригинальный цикл "выборки/запоминания" многими циклами "выборки/запоминания". Это будет "путать" противника и предупреждать его от "изучения" оригинальной последовательности операций доступа к памяти (в отличие от фактической последовательности). Следовательно, противник не может улучшить свои способности по восстановлению оригинальной программы.

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

Предположим, что односторонние функции существуют и пусть k параметр безопасности функции. Тогда существует эффективный способ преобразования программ в пары, состоящие из физически защищенного ЦП с k битами внутренней защищенной памяти и соответствующей зашифрованной программы такой, что ЦП имитирует взаимодействие с зашифрованной программой, реализуемое за время, ограниченное poly(k). Кроме того, t команд оригинальной программы выполняются с использованием менее чем за tk0(1) команд зашифрованной программы, а увеличение размера внешней памяти ограничиваются коэффициентом k.

Вышеупомянутый результат доказывается посредством сведения задачи создания ЦП, который нарушает эксперименты по вмешательству, к задаче сокрытия модели доступа. Посуществу, последняя задача формулируется как задача моделирования на независимой забывающей RAMмашине.


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок