Цифровые водяные знаки, устойчивые к атаке сговором

За основу языка программирования AspectTalk взят диалект Little Smalltalk [3] языка Smalltalk. В него введён специальный тип данных — метакласс, элементы которого являются классами классов и позволяют программисту давать виртуальной машине дополнительные указания о функционировании объектной системы. Эти указания определяются в виде обработчиков операции посылки сообщения от объекта к объекту и наследуются метаклассами в иерархии наследования метаклассов. Граф иерархии наследования метаклассов является подграфом графа иерархии наследования классов. Данный подход позволяет избавиться от недостатков АОП, описанных в [4], а также упростить семантическую модель языка. Подробнее об AspectTalk можно прочитать в [5].

Виртуальная машина имеет стековую архитектуру с разделением стека данных и стека вызова процедур. Набор команд виртуальной машины включает операции управления стеком данных, а также операции над примитивными типами данных. Язык программ для виртуальной машины представляет собой польскую инверсную запись последовательности команд. Для реализации транслятора с AspectTalk в язык виртуальной машины построена грамматика класса LL(2).

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

ЛИТЕРАТУРА

1. Elrad T., Aksit M.M., Kiczales G., et al. Discussing aspects of AOP // Communications of

ACM. 2001. October. V. 44. No. 10. P. 33-38.

2. Kiczales G. The Art of Meta-Object Protocol. The MIT Press, 1991. 345 p.

3. Budd T. A Little Smalltalk. Addison-Wesley, 1987. 280 pp.

4. Bouraqadi N., Seriai A., Leblanc G. Towards unified aspect-oriented programming // ESUG 2005 Research Conference. 2005. 22 p.

5. Стефанцов Д. А. Реализация политик безопасности в компьютерных системах с помощью аспектно-ориентированного программирования // Прикладная дискретная математика. 2008. №1(1). С. 94-100.

УДК 681.511:3

ЦИФРОВЫЕ ВОДЯНЫЕ ЗНАКИ, УСТОЙЧИВЫЕ К АТАКЕ СГОВОРОМ

Р. С. Стружков, Т. М. Соловьёв, Р. И. Черняк

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

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

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

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

Предлагается следующий подход к противодействию этой атаке.

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

Отходя от деталей внедрения, под водяными знаками будем понимать булевы векторы некоторой размерности п и их множество обозначать Шп или Ш, если размерность векторов в нём несущественна. Для того чтобы противостоять атаке сговором, предлагается в качестве последнего использовать такое подмножество W С {0,1}п, называемое допустимым, которое удовлетворяет условию: каждому подмножеству Р С Ш минимальный интервал I(Р) в {0,1}п, его покрывающий, сопоставляется взаимно-однозначно, т. е. если Р\,Р2 С Ш и Р1 = Р2, то I(Р1) = I(Р2), и, кроме того, если |Р | > 1, то I (Р) = Р .В этом случае злоумышленник, проводящий атаку сговором, имеет копии некоторого медиа-данного с водяными знаками в некотором Р С W с |Р | ^ 2 и получает копию этого медиа-данного с ложным водяным знаком w1 выбирая его произвольно из множества I(Р) \ Р. Для такого верно ^ Ш, ибо иначе

I(Р) = I(Р и {и>}), что противоречит допустимости Ш.

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

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

Обозначим к(!) размерность (количество переменных компонент векторов) интервала I в {0,1}п.

Утверждение 1. k(I(P)) ^ |P| для любого P Ç W мощности |P| > 2 и допустимого W.

Утверждение 2. Для любых допустимых множеств W и W' в {0,1}n если W Ç W', то |W'| ^ |W| + n — k(I(W)).

Утверждение 3. Мощность любого допустимого множества Wn не больше n.

Отсюда следует, что количество всех допустимых множеств векторов в {0, 1}n не превосходит числа £™=1 С\п.

Пусть Oi(a) обозначает окружность радиуса 1 вокруг булева вектора a в пространстве {0,1}n, т. е. O1(a) = {x G {0,1}n : d(x,a) = 1}, где d(x,y) —расстояние Хэмминга между булевыми векторами x и у.

Утверждение 4.

1) Oi(a) — допустимое множество;

2) всякое допустимое множество мощности n имеет вид O1 (a).

Ввиду утверждения 3 это значит, что все допустимые множества векторов в {0,1}n наибольшей мощности суть O1 (a) для a G {0,1}n, и их количество равно 2n.

Два интервала будем называть эквивалентными, если их множества внутренних (переменных) компонент совпадают. Все интервалы размерности 0 являются эквивалентными по определению. Пусть также E(W) = {I(P) : P Ç W, |Р| > 1}.

Утверждение 5. Для любого допустимого множества W все элементы в E(W) попарно не эквивалентны.

Подмножества W и W' в {0,1}n будем называть эквивалентными, если |W| = |W;| и для каждого интервала любого одного из множеств E (W) и E (W;) найдётся эквивалентный ему интервал в другом. Если W и W' допустимые, то по утверждению 5 последнее соответствие устанавливается единственным образом. Заметим также, что любое множество, эквивалентное допустимому, также допустимо. Непосредственно проверяется, что для любого n все допустимые множества O1(a) С {0,1}n образуют класс эквивалентности.

Утверждение 6. Мощность любого класса эквивалентности допустимых множеств векторов в {0,1}n не меньше 2n.

В доказательстве этого утверждения показывается, как по любому допустимому множеству можно построить ещё, как минимум, 2n — 1 эквивалентных ему других допустимых множеств с линейной сложностью построения одного множества.

При обнаружении ложного водяного знака w в копии некоторого медиа-данного возникает задача идентификации создавших его участников атаки сговором, состоящая в вычислении подмножества водяных знаков, из которого атакой сговором получен этот знак, т. е. такого P Ç W (или непустой его части), что w G I(P) \ P. Ввиду возможности пересечения минимальных интервалов, покрывающих различные подмножества булевых векторов, эта задача может иметь несколько решений — «подозреваемых» подмножеств в W. В этом случае среди последних выбираются все минимальные по включению (их множество обозначается M(W, w)), и из них, рассматриваемых в порядке неубывания мощности, находится настоящий «нарушитель» путём «следственных мероприятий».

Качество допустимого множества W можно оценить по его характеристическому вектору H(W) = Hi(W)H2(W)... Hm(W), где m = |W| и для любого i = 1,... , m

Hj(W)= max ( max |M(W,w)|) .

PCW,\P\=i \we(I(P)\P) J

В случае, если Hi(W) = 1 для i = 1,...,t и некоторого t ^ m и атака сговором проводится группой из t или менее пользователей, т. е. ложный водяной знак w построен по некоторому множеству P С W мощности |P | ^ t, то непустая часть этого P вычисляется по w однозначно и, следовательно, некоторые участники этого сговора идентифицируются знаком w безошибочно.

Допустимое множество водяных знаков W называется разделимым, если для любых различных подмножеств P1, P2,. . . , Pk С W верно

k k

pi Pi=0 ^ p| i(Pi)=0.

i=1 i=1

В случае разделимого множества W решением задачи идентификации участников сговора по ложному водяному знаку w является множество P = Р|pP, где Q = = {P С W: |P| > 1, w e I(P) \ P}.

Утверждение 7. Длина векторов в разделимом множестве W не меньше, чем

2|W\-1 — 1 — количества разбиений множества Wна два блока.

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

УДК 004.732

ИССЛЕДОВАНИЕ БЕЗОПАСНОСТИ БЕСПРОВОДНЫХ СЕТЕЙ г. ТОМСКА

М. И. Цой

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

Наиболее известными стандартами, описывающими механизмы обеспечения безопасности в сетях WiFi, являются:

— IEEE 802.11, предполагающий использование алгоритма RC4 для шифрования данных и алгоритма CRC32 для контроля их целостности в протоколе WEP. В настоящее время известно множество уязвимостей как в алгоритме RC4, так и в его реализациях в WEP, поэтому последний не обеспечивает приемлемой степени защиты;