Кодовые шарады

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 519. 688
КОДОВЫЕ ШАРАДЫ
А. Л. Чмора,
ведущий специалист
ОАО «Инфотекс»
Рассматривается метод противодействия DoS-атаке с использованием шарад, построенных на основе кодов, исправляющих ошибки. Обосновывается практическая состоятельность итеративного метода конструирования шарад. Итеративные кодовые шарады позволяют исключить применение квантового компьютера и массированного распараллеливания в целях снижения трудоемкости отыскания решения.
Ключевые слова — DoS-атака, вычислительные шарады, коды, исправляющие ошибки, линейные коды.
Введение
DoS-атаки (Denial of Service) широко распространены в сети Интернет [1, 2]. Задача атакующего — создать искусственную ситуацию, в которой добросовестному потребителю будет отказано в предоставлении соответствующих услуг. Для объяснения воспользуемся следующей бытовой аналогией. Предположим, что в ресторане имеется некоторое количество столиков и каждый можно зарезервировать, позвонив по телефону. Звонки принимаются до часа дня включительно. Злоумышленник, воспользовавшись простейшей стратегией, способен причинить ресторану ощутимый финансовый и репутационный ущерб. Для этого достаточно зарезервировать все доступные столики до установленного часа. Очевидно, что если все столики уже зарезервированы, то большинство потенциальных посетителей откажется от запланированного посещения и предпочтет другой ресторан. Конечно же, в какой-то момент руководство ресторана обнаружит факт злоупотребления и аннулирует резервирование, но с непренебрежи-мой вероятностью некоторое количество столиков в течение вечера не будет востребовано.
Сетевая DoS-атака
Поглощающая ресурсы стратегия относится к наиболее распространенному типу DoS-атаки. Так, злоумышленник способен инициировать аномальное количество сетевых соединений, но предусмотренные протоколом правила взаимодействия при этом умышленно игнорируются. Рассмотрим подробнее, как это происходит на примере TCP-соединения [3].
Обычно ТСР-соединение устанавливается при помощи полуторараундного протокола1. Клиент инициирует соединение, передав серверу специальный SYN-пакет. В ответ сервер передает пакет SYN АСК и тем самым подтверждает соединение. По факту подтверждения соединения сервер выделяет некоторую область памяти. Подчеркнем, что объем выделенной под соединения памяти конечен. В завершение клиент выполняет квитирование и передает серверу АСК-пакет. Атакующий инициирует множество соединений, в которых пакеты SYN и SYN АСК передаются в соответствии с протоколом, но умышленно опускает квитирование, т. е. АСК-пакет никогда не передается. В итоге соединение не устанавливается, но при этом сервер не освобождает выделенную область памяти. Если количество таких незавершенных соединений достаточно велико, то происходит переполнение памяти и сервер перестает реагировать на какие-либо запросы. Понятно, что на прикладном уровне описанная сетевая атака приводит к отказу в обслуживании.
Вычислительные шарады
Воспользуемся вычислительной задачей, для которой трудоемкость отыскания решения варьируется в широком диапазоне значений и задается параметрически. Для этой цели подходят такие задачи, про которые известно, что для них не существует иных, более эффективных, методов
1 Раунд состоит из запроса и ответного подтверждения. Полуторараундный протокол включает дополнительное сообщение-квитанцию в ответ на подтверждение.
решения. Например, никакие выполненные заранее предвычисления не способствуют снижению трудоемкости. Решение может быть найдено исключительно при помощи силовой атаки, т. е. методом проб и ошибок с исчерпывающим перебором вариантов. Для обозначения таких задач воспользуемся термином шарада (puzzle). Идеологическая подоплека метода шарад, а также исследование их свойств восходят к пионерской работе Р. Меркля [4].
Назовем экзаменатором того, кто создает шараду и по построению располагает ее решением, а экзаменуемым того, кто выполняет отыскание решения по заданию экзаменатора.
В работе [5] предложен практический метод противодействия сетевой атаке. Сервер предлагает решить шараду каждый раз, когда устанавливается соединение. Память под соединение выделяется только при условии предоставления правильного решения. Атакующий продуцирует запросы на установление соединения. Поскольку число таких запросов аномально велико, и в этом суть атаки, то и число шарад также велико. Искусственно созданная сетевая нагрузка возвращается к атакующему в виде вычислительной нагрузки, и для достижения поставленной цели он вынужден инвестировать. Тогда DoS-атака перестает быть беззатратной и атакующий вынужден платить за ее осуществление. Добросовестный пользователь, в отличие от атакующего, продуцирует умеренное число запросов, и для него вычислительная нагрузка не обременительна. Следует подчеркнуть, что эффективность механизма противодействия обусловлена исключительно разницей в количестве запросов на установление соединения. В работах [6−8] метод шарад применяется для противодействия DoS-атаке в ряде других приложений.
Сформулируем набор требований к шарадам в контексте DoS-атаки.
1. Собственно шарады не должны быть инструментом атаки. Вычислительная трудоемкость построения шарады и проверки ее решения не должна быть чрезмерной.
2. Трудоемкость решения шарады должна быть регулируемой. Необходимо, чтобы сервер имел возможность гибко настраивать трудоемкость, оперативно реагируя на увеличение или снижение сетевой нагрузки.
3. Решение шарады возможно при наличии определенного вычислительного потенциала. Алгоритм решения должен быть задан строго. Трудоемкость решения должна быть ограничена сверху. Решение может быть получено за конечное время. Не должно существовать известных методов повышения эффективности решения.
Недостатки метода шарад
Известные шарады [5, 9] допускают возможность отыскания решения независимыми вычислителями, причем каждый из таких вычислителей выполняет поиск в пределах некоторого подмножества претендентов, мощность которого меньше мощности исходного множества. Назовем такой подход к поиску решения распараллеливанием. На практике это означает, что атакующий может воспользоваться методом распределенных вычислений. Тогда применение N независимых вычислителей или вычислителя сядерной архитектурой позволяет получить результат в N раз быстрее. Очевидно, что для организации таких вычислений атакующему необходимо выполнить предварительную подготовку заданий с последующим их распределением при помощи специализированного протокола. Как только решение найдено одним из вычислителей, все остальные должны по команде прекратить обработку заданий.
Напротив, шарады с последовательным алгоритмом решения [10] не допускают распараллеливания, и в этом их бесспорное преимущество. Однако эти шарады уязвимы с точки зрения атаки при помощи квантового компьютера. Известно, что трудоемкость отыскания решения шарады [10] может быть эффективно снижена в результате факторизации. Метод с полиномиальной трудоемкостью, известный как алгоритм факторизации Шора [11, 12], в существенной мере использует принцип квантовых вычислений. Объявлено о создании прототипа программируемого квантового компьютера с ограниченными вычислительными возможностями [13]. Известен также пример факторизации при помощи алгоритма Шора на реальном квантовом вычислителе [14]. Для эффективной факторизации числа из & amp- двоичных разрядов понадобится квантовый вычислитель с регистром на К*2& amp- квантовых состояний (кубит) [15]. Логично ожидать появления полноценного квантового компьютера в ближайшие десятилетия. Шарады [9] не только эффективно решаются при помощи квантового вычислителя [11], но также допускают распараллеливание.
Выделим следующие типы шарад с регулируемой трудоемкостью решения.
1. Шарады, допускающие распараллеливание с применением квантовых/неквантовых вычислителей, для которых неизвестен эффективный квантовый алгоритм решения [5].
2. Шарады, допускающие распараллеливание с применением квантовых/неквантовых вычислителей, для которых известен эффективный квантовый алгоритм решения [9].
3. Шарады, не допускающие распараллеливания с применением квантовых/неквантовых вычислителей, для которых известен эффективный квантовый алгоритм решения [10].
Таким образом, к недостаткам шарад перечисленных типов следует отнести возможность распараллеливания и существование эффективного квантового алгоритма решения.
Следует также упомянуть отсутствие строгого доказательства того факта, что фундаментальные задачи, лежащие в основе известных шарад, относятся к классуР-трудных. По мнению ряда специалистов, наличие подобного доказательства предоставляет достаточные гарантии относительной неуязвимости в долгосрочной перспективе.
Постановка задачи
Задача заключается в конструировании шарады с регулируемой трудоемкостью отыскания решения, максимально широким диапазоном трудоемкости с возможностью плавной регулировки, минимальными объемом памяти и накладными расходами при передаче, которая не поддается эффективному распараллеливанию и для которой не известен эффективный квантовый алгоритм. Для решения задачи воспользуемся методами теории помехоустойчивого кодирования и линейной алгебры.
Кодовые шарады
Мотивация подхода в том, что вопрос об эффективном решении на квантовом компьютере фундаментальных задач теории помехоустойчивого кодирования в настоящее время остается открытым. Более того, в работе [16] показано, что эти задачи относятся к классу NP-трудных. Известно также [17], что трудоемкость зашифрования для кодовой асимметричной криптосистемы ниже, чем трудоемкость зашифрования для криптосистемы RSA. Логично предположить, что шарады на основе кодов не превосходят по трудоемкости построения шарады из работы [10] и сравнимы с шарадами из работы [9].
Пусть имеется & amp--мерный линейный код С с минимальным расстоянием d [18]. Код задан ккп порождающей матрицей G. Тогда существует кодовое слово с = pG, с е кег (Н), где Н — (п-к)хп проверочная матрица кода С и р — информационная последовательность. Множество = {х = (хь … ,
хп) | Xj е } рассматривается как линейное пространство размерности п над
Через Щ-) обозначим криптографическую хэш-функцию /^: {0, 1}*-& gt-{0, 1}1 для некоторого 1. Свойства ^-) подробно описаны [19]. Отметим, что ^-)
доступна как экзаменатору, так и экзаменуемому.
Назовем кодовыми шарады, построенные на основе кода С. Отметим, что код С известен как экзаменатору, так и экзаменуемому.
Для заданного [п, & amp-, d]q-кода экзаменатор выполняет следующие действия.
1. Выбирает информационную последовательность р еR.
2. Сохраняет ф = h (p) для проверки решения.
3. Выбирает ошибку е еR ®п Хэмминга юЦе) = t и [(d-1)/21& lt-t<-[n/21.
4. Вычисляет значение хэш-функции Ц = й-(р || е).
5. Вычисляет сумму с = pG + е.
6. Передает {с, у, t} экзаменуемому.
Для поиска решения экзаменуемый выполняет следующие действия.
1. Выбирает ошибку е е такую, что wt (e) & lt- t.
2. Вычисляет сумму с = с + е.
3. Выполняет декодирование с и получает р.
4. Проверяетр || е) = у.
5. Еслир || е) = у, то переходит к 6, иначе к 1.
6. Предъявляет ф'- = ^р) в качестве решения.
Заметим, что в кодовой шараде секретный
ключ состоит из двух компонент — информационной последовательности р и ошибки е. Если известно р, то легко вычислить е, так как е = с + pG, и наоборот.
Вес t всегда должен превышать половину кодового расстояния на величину е, которая обеспечивает маскировку кода с алгоритмом декодирования полиномиальной трудоемкости под код, для которого возможно только корреляционное декодирование. Размерность кода следует выбирать так, чтобы трудоемкость поиска решения перебором по р превышала трудоемкость поиска решения перебором по е. Действительно, если
& lt- Е («-1
-=[^-1)/2]+е
(1)
то экзаменуемый найдет решение шарады {с, у, ^ в среднем за дк-1 испытаний, воспользовавшись следующим методом.
1. Выбирает информационную последовательность р е & lt-.
2. Вычисляет кодовое слово с = р^.
3. Вычисляет сумму? е = С+с.
4. Проверяетр || е) = у.
5. Еслир || е) = у, то переходит к 6, иначе к 1.
6. Предъявляет ф'- = ^р) в качестве решения.
Использование критерия у =р || е) не позволяет экзаменуемому получить искомое решение за меньшее число испытаний. Предположим, у = ^р) и необходимо найти р. Пусть выбрано е
такое, что юЩ + е) & lt- - 1)/2]. Если вес ошибки
не превышает половины кодового расстояния, то в результате декодирования последовательность р будет восстановлена правильно и решение будет получено при е ^ е. Очевидно, чтор || е) = у только при е = е.
Кодовая шарада должна допускать регулировку трудоемкости отыскания решения. Вес Хэмминга t ошибки е — один из параметров, определяющий объем перебора при поиске решения. Обозначим через Ж множество всевозможных претендентов. Известно, что |Ж| достигает своего максимума при t = [п/2]. Например, для д = 2 су-
ществует Е ?-
[^-1)/2]+е
& lt---------^ 2 претен-
(п/2-^
дентов на е. Для поиска решения при t = п/2 — 1 экзаменуемому потребуется выполнить в среднем не более п2п — 4 испытаний. С другой стороны, следует выбирать параметры кода так, чтобы трудоемкость отыскания решения варьировалась в широком диапазоне. Из указанных ограничений следует, что — 1)/2] + е & lt- t & lt- [п/2] и
(й-1) / 2] + е & lt-[п / 2]-1. (2)
Например, если предположить равенство в (2), то при фиксированном п существует единственная шарада с максимальной трудоемкостью.
Назовем шараду устойчивой, если не существует иного, менее трудоемкого способа ее решения, кроме заданного по построению. Необходимо определить допустимый диапазон скоростей кода такой, чтобы гарантировать устойчивость кодовой шарады и обеспечить максимально широкий диапазон трудоемкости.
Чем меньше минимальное кодовое расстояние d, тем шире диапазон трудоемкости. Очевидно, что d обратно пропорционально размерности кода. Это означает, что для конструирования шарад предпочтительнее высокоскоростные коды, для которых отношение R = & amp-/п стремится к 1.
Пусть задан [п, п — d + 1, d]q-код Рида-Соломона RSq (n, d) над ??, д = рт, где р — простое число- т — положительное целое, который имеет максимально возможную размерность при заданных п и d [18]. Тогда d = п — & amp- + 1 и код исправляет t & lt- [(п — & amp-)/2] ошибок. Существуют RSq (n, d)-коды с блоковой длиной п = д — 1, расширенные с п = д и дважды расширенные с п = д + 1. Это означает, что всегда можно выбрать код с четным п. Шараду на основе RSq (n, d)-кода будем называть RSq (n, d)-шарадой.
Не существует обоснованных возражений против использования безызбыточных кодов. Тогда RSq (n, 1)-шарада обладает максимально широким диапазоном трудоемкости, поскольку е = 0 и
вес ошибки варьируется в интервале п/2 & gt- t & gt- 1. Шарада безусловно устойчива, так как & amp- & gt- п/2. Следовательно, верхняя граница скорости кода совпадает с конструктивным ограничением.
Нижняя граница может быть получена при помощи следующих простых рассуждений. Очевидно, что при & amp- & lt- п/2 наблюдается объективное сужение диапазона трудоемкости, поскольку вес ошибки [^ - 1)/2] + е & lt- ^& amp-. Если & lt- п/2, то ша-
рада неустойчива. Это объясняется тем, что справедливо неравенство (1) и трудоемкость отыскания решения будет ниже запланированной. Таким образом, для построения устойчивых RSq (n, d)-шарад с широким диапазоном трудоемкости следует использовать коды со скоростями в интервале 0,5 & lt- R & lt- 1. RSq (n, 1)-шарады представляются наиболее перспективными с практической точки зрения.
Отметим, что для RSq (n, 1)-шарад ограничение на блоковую длину не является критичным, поскольку трудоемкость поиска решения в существенной степени определяется весом t.
RSq (n, d)-шарады допускают распараллеливание. Попытаемся устранить этот недостаток. Воспользуемся следующим наблюдением. Как было отмечено, для организации параллельных вычислений необходимо выполнить распределение заданий. Если такое распределение выполняется однократно, то возникающими накладными расходами можно пренебречь. Предположим, что шарада состоит из нескольких подшарад. Процесс распределения заданий усложнится, если скомбинировать подшарады таким образом, что решение каждой последующей будет зависеть от решения предыдущей. Иначе говоря, атакующий будет вынужден распределять задания для каждой подшарады. При этом важно, чтобы подша-рады не были известны заранее и раскрывались последовательно по мере получения промежуточных решений.
Сконструируем RS? (п, 1)-шараду, состоящую из? вложенных подшарад. Для этого зададим вес ошибки tj для каждой из? подшарад. В результате получим набор {^, …, tt}. Напомним, что для RSq (n, 1)-шарады t е [1, п/2].
Для построения RS? (п, 1)-шарады экзаменатор выполняет следующие действия.
1. Выбирает информационную последовательность Р е R ??.
2. Сохраняет ф = h (p) для проверки решения.
3. Устанавливает у: = 1 и р := р.
4. Выбирает ошибку е е R? такую, что 1 & lt- ю^е) & lt- tj.
5. Вычисляет значение хэш-функции У j = h (p || е).
6. Вычисляет с = рО + е.
7. Устанавливает у: = у + 1 и р: = с-.
8. Проверяет у =? + 1.
9. Если у =? + 1, то переходит к 10, иначе к 4.
10. Передает {с, ?, {у^ у},{tl, …, tp}} экзаменуемому.
Для поиска решения экзаменуемый выполняет следующие действия.
1. Устанавливает у: =? и р: = с.
е Є К'-
такую, что
2. Выбирает ошибку 1 & lt- ю^е) & lt- tj.
3. Вычисляет сумму с.
4. В результате декодирования с получает р.
5. Проверяет h (р || е) =уу.
6. Еслир || е) = уj, то переходит к 7, иначе к 2.
7. Устанавливает у. = у — 1 и р := р.
8. Проверяет у =0.
9. Если у = 0, то переходит к 10, иначе к 2.
10. Предъявляет ф'- = ^р) в качестве решения.
Конструкция RS? (п, 1)-шарады такова, что объем памяти для хранения результирующей шарады равен объему памяти для хранения отдельной подшарады. Однако потребуется дополнительная память для хранения? пар {уу, t¦}. Заметим, что все у- имеют одинаковую разрядность
1 и tj& lt- п/2. Тогда для хранения RSfq (п, 1)-шарады при п = рт необходимо зарезервировать
О
пт 1о2 Р + ?
пт 1о2 Р
-X
двоичных разря-
дов.
Из представленной конструкции следует, что применение безызбыточного кода вполне оправдано — объем памяти для хранения подшарад не зависит от ?. Однако для уу и tj объем памяти растет линейно по ?. С точки зрения резервирования памяти вклад уу и tj неравнозначен. Как правило, веса ошибок подчиняются монотонной зависимости. Следовательно, можно хранить не веса ошибок, а описание функции, при помощи которой несложно вычислить произвольное t¦. Объем памяти для хранения такого описания не зависит от ?. Будем считать, что накладными расходами, связанными с хранением tj, можно пренебречь. Для хранения уу, в противоположность tj, может потребоваться относительно большой объем памяти. Например, если воспользоваться хэш-функцией SHA-256, то при? = 100 и п = 28 объем памяти для хранения всех Уу на порядок превысит объем памяти для хранения с и tj, 1 & lt- у & lt- ?.
Рассмотрим такую конструкцию шарады, у которой объем памяти для хранения у не зависит от ?.
Назовем итеративным хэшированием преобразование вида у-1 = ЩЩ… ЩЩв))…)), где? -
^___________/
? раз
число итераций. Финальное значение у _ і получается из стартового в.
Понадобится также следующее свойство кода С. Пусть С^, С2 є С. Тогда Сз = Сі + С2 = (Рі + Р2) С и Сз є С.
Подойдем к конструированию шарады следующим образом. Вначале зададим вес ошибки tj для каждой из? подшарад. Затем для в є методом итеративного хэширования вычислим у _ і, у _2, •& quot-, Уі, Уо. Отобразим каждый у на линейное пространство размерности п над ??. Предпо-
ложим, п = рт, Ь =
X
т 1оЄ2 Р
, 1 & lt- Ь & lt- п и каждый у¦
состоит из Ь-ичных символов. В результате ото-
бражения получим Wj = 0^~и || уj, где 0п- - последовательность из п — Ь нулевых символов поля и '-?j е ??, 0 & lt- у & lt-? — 1.
Заданы наборы {^ - 1, …, Ч^, Т0} и {tl, …, tl}. Для построения Rs? (п, 1)*-шарады экзаменатор выполняет следующие действия.
1. Выбирает информационную последовательность р е R ??.
2. Сохраняет ф = h (p) для проверки решения.
3. Устанавливает у = 1 и р := р.
4. Выбирает ошибку е е R ?^ такую, что 1 & lt- ю^е) & lt- tу.
5. Вычисляет с = (р + ^ -j)О + е.
6. Устанавливает у = у + 1 и р := с.
7. Проверяет у =? + 1.
8. Если у =? + 1, то переходит к 9, иначе к 4.
9. Передает {с, ?, в, {^, …, }} экзаменуемому.
Экзаменуемый выполняет следующие действия.
1. Устанавливает у = ?, р: = с и Й: = Щв).
2. Выбирает ошибку е е такую, что 1 & lt- ю^е) & lt-
3. Вычисляет сумму с = р + е.
4. В результате декодирования с получает р.
5. Отображает- = Оп- || Й.
6. Проверяет (р) + ^ --) О = с + ^ _! О.
7. Если (р + ^-j)О = с +-jО, то переходит к 8, иначе к 2.
8. Устанавливает у = у — 1, р := р + '-?i-j и Й: = h (Й).
9. Проверяет у =0.
10. Если у = 0, то переходит к 11, иначе к 2.
11. Предъявляет ф'- = ^р) в качестве решения. Предположим, что для представления числа в в
памяти достаточно 1 двоичных разрядов. Тогда для хранения RSfg (п, 1)*-шарады потребуется зарезер-
вировать не более О
пт 1о2 Р ¦
?пт 1о2 Р
+ X
двоичных разрядов.
Трудоемкость отыскания решения не превышает
і
EE (q-l)i j=1 i=1
(З)
испытаний.
Проанализируем Rs? (п, 1)*-шараду на устойчивость. Соответствующее итеративное преобразование можно представить в виде с = ((((… ((((р + ^-1)О + е1) + ^-2)О + е2) +
+… + Ч"1)О + е, -1) + ^0)О + е,),
где р, е j е R и для I + у, 0 & lt- I, у & lt- ?.
Необходимо ответить на следующий вопрос: способен ли экзаменуемый, располагая набором {с, ?, в,{^, …, tf}}, а также последовательностью Ч — 1, •••, Ч1, Т0, уменьшить запланированную трудоемкость поиска решения?
Конструкция Rs? (п, 1)*-шарады напоминает луковицу. Доступ к некоторому внутреннему слою возможен только после удаления всех объемлющих слоев. Каждый слой ассоциирован с отдельной подшарадой. Слой с номером у считается удаленным, если найдено решение для у-й подшарады. Поиск решения начинается с первого внешнего слоя, который всегда доступен. Собственно решение шарады располагается в сердцевине луковицы — в последнем внутреннем слое.
Если воспользоваться геометрической интерпретацией, то каждое кодовое слово RSq (n, 1)-кода располагается в центре сферы нулевого радиуса и все такие сферы не пересекаются. Число сфер равно числу кодовых слов, которое для RSq (n, 1)-кода совпадает с мощностью ??. Тогда произвольная ошибка веса 0 & lt- t & lt- п переводит кодовое слово RSq (n, 1)-кода в другое кодовое слово того же кода с единичной вероятностью. Это означает, что каждая подшарада Rs? (п, 1)*-шарады имеет единственное решение.
При заданном в несложно вычислить Ч — у, которое используется в качестве критерия. Если с = (р + Ч —, то в результате декодирования будет получена информационная последовательность I = р + Ч Из линейности кода следует,
что (I + Ч — ^ = с + Ч. По построению кодовое слово с маскируется ошибкой е, 1 & lt- ю^е) & lt- t ¦, и с* = с + е. Решение у-й подшарады заключается в нахождении ошибки е. Пусть заданы С, Ч — у и некоторая ошибка ё + е. Для с = С + е в результате декодирования будет получена информационная
Литература
1. Naraine R. Massive DDOS Attack Hit DNS Root Servers. Oct. 23, 2002. http: //siliconvalley. internet. com/
последовательность I ^ I. Решение с будет отвергнуто, так как (1 + Т,_)в) +)е_)
Поскольку применяется безызбыточный код, то для у-й подшарады существует дп кодовых слов. При 1 & lt- у& lt- п/2 справедливо неравенство
qn & gt-Е t=l (q-1)i
и для отыскания решения
исчерпывающий перебор ошибок ограниченного веса выгоднее, чем исчерпывающий перебор информационных последовательностей.
Помимо ширины диапазона значение также имеет функция, при помощи которой задается трудоемкость. Для шарад [5] трудоемкость отыскания решения определяется мощностью множества возможных претендентов и равна 2 Г для некоторого параметра г. В ряде случаев экспоненциальное изменение трудоемкости не адекватно воздействию и поэтому не оправдано. Необходима плавная регулировка. Rs? (п, 1)*-шарады допускают такую регулировку за счет полиномиальной по п функции изменения трудоемкости для каждой подшарады и общей линейной зависимости. Как было показано (3), трудоемкость отыскания решения для Rs? (п, 1)*-шарады задается аддитивной функцией и допускает гибкую настройку шага изменения трудоемкости. Оче-
видно, что
n n n — i
i + 1 i i + 1,
1 & lt- i & lt- n. Тогда при уве-
личении/уменьшении на единицу веса t ошибки е трудоемкость отыскания решения возрастает/
убывает в (n — t)/(t + 1) раз. Поскольку
= n, то
для RSq (п, 1)*-шарады минимальный шаг изменения трудоемкости равен п. Например, можно сконструировать шараду со средней трудоемкостью отыскания решения.
Заключение
В статье рассматривается метод шарад как способ противодействия DoS-атаке. Предложены конкретные конструкции шарад на основе кодов, исправляющих ошибки, в том числе и итеративная конструкция, которая гарантирует устойчивость, обладает широким диапазоном трудоемкости и допускает гибкую настройку.
news/article. php/1 486 981 (дата обращения:
1О. О6. 2О1О).
2. Wagner J. SCO Hit By Another DDoS Attack. Dec.
1О, 2ООЗ. http: //www. internetnews. com/dev-news/ article. php/3 287 781 (дата обращения: 1О. О6. 2О1О).
3. Schuba C. L. et al. Analysis of a denial of service attack on TCP // Proc. IEEE Symp. on Security and Privacy. IEEE Computer Society Press, May 1997. Р. 208−223.
4. Merkle R. C. Secure Communications Over Insecure Channels // Communications of the ACM. Apr. 1978. Vol. 21. N 4. Р. 294−299.
5. Brainard J., Juels A. Client Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks // Proc. of the 1999 ISOC Network and Distributed System Security Symp. 1999. P. 151−165.
6. Aura T., Nikander P., Leiwo J. DoS-resistant authentication with client puzzles // 8th Intern. Workshop on Security Protocols. Springer-Verlag, 2000. P. 170 181.
7. Dean D., Stubblefield A. Using client puzzles to protect TLS//SSYM'01 Proc. of the 10th Conf. on USENIX Security Symp./ USENIX Association Berkeley. CA, USA, 2001. P. 1−8.
8. Adkins D., Lakshminarayanan K., Perrig A., Stoica I. Taming IP packet flooding attacks // Computer Communication Review. 2004. Vol. 34. N 1. P. 45−50.
9. Waters B., Juels A., Halderman A., Felten E. New Client Puzzle Outsourcing Techniques for DoS Resistance // ACM CCS. 2004. P. 246−256.
10. Rivest R. L., Shamir A., Wagner D. Time-lock puzzles and timed-release crypto // Technical Report MIT/LCS/TR-684. MIT, 1996. http: //people. csail. mit. edu/rivest/RivestShamirWagner-timelock. pdf (дата обращения: 22. 10. 2010).
11. Shor P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum com-
puter // SIAM J. of Computing. 1997. N 26. P. 14 841 509.
12. Ekert A., Jozsa R. Quantum computation and Shor’s factoring algorithm // Rev. Mod. Phys. 1996. Vol. 68. N 3. P. 733−753.
13. Hanneke D. et al. Realization of a programmable two-qubit quantum processor // Nature Physics. 2009. N 6. P. 13−16.
14. Vandersypen L. M. K. et al. Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance // Nature. 2001. N 414. P. 883 887. http: //www. nature. com/nature/journal/v414/ n6866/abs/41 4883a. html (дата обращения:
22. 10. 2010).
15. Beauregard S. Circuit for Shor’s algorithm using 2n + 3 qubits // Quantum Information and Computation. 2003. N 3. P. 175−185.
16. Barg A. Complexity Issues in Coding Theory // Electronic Colloquium on Computational Complexity (ECCC). 1997. Vol. 4. N 46. http: //www. eccc. uni-trier. de/report/1997/046/ (дата обращения: 22. 10. 2010).
17. Riek J. R. Observations on the Application of Error-Correcting Codes to Public Key Encryption // Proc. of the IEEE 1990 Intern. Carnahan Conf. on Security Technology, Crime Countermeasures. 1990. P. 15−18.
18. МакВильямс Ф. Д., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. — М.: Связь, 1979. — 744 c.
19. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. 5th print. — CRC-Press, 2001. — 780 р. http: //www. cacr. math. uwaterloo. ca/ hac/about/chap9. pdf (дата обращения: 22. 10. 2010).

ПоказатьСвернуть
Заполнить форму текущей работой