Методы теории помехоустойчивого кодирования в некоторых задачах защиты информации

Чмора, Андрей Львович

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

кандидата технических наук: Чмора, Андрей Львович
город: Москва
год: 2012
специальность ВАК РФ: 05.13.17

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

Автореферат диссертации по теме "Методы теории помехоустойчивого кодирования в некоторых задачах защиты информации"

На. правах рукописи

Чмора Андрей Львович

Методы теории помехоустойчивого кодирования в некоторых задачах защиты информации

05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 2012

005020038

Работа выполнена в Федеральном государственном бюджетном учреждении науки «Институте проблем передачи информации им. А. А. Харкевича Российской академии наук» (ИППИ РАН).

Научный руководитель : (консультант)

Официальные оппоненты:

Ведущая организация:

доктор техническх наук, профессор, Зяблое Виктор Васильевич

Крук Евгений Абрамович, доктор технических наук, профессор, ГУАП (Санкт-Петербург), заведующий кафедрой «Комплексная загцита информации»

Кабатянский Григорий Анатольевич, доктор физико-математических наук, ИППИ РАН, главный научный сотрудник лаборатории К- 4

Московский физико-т,ехнический институт (государственный универси-

тет)

часов на заседании

Защита состоится «Л 3 >■> с'л' .< 2012 г. в ^

диссертационного совета Д 002.077.01 при ИППИ РАН, расположенном по адресу: 127994, г. Москва, ГСП-4, Большой Каретный переулок, д. 19, стр. 1.

С диссертацией можно ознакомиться в библиотеке ИППИ РАН.

Автореферат разослан * ¿/еЯ /У } 2012 г.

Ученый секретарь

диссертационного совета Д 002.077.01, доктор физико-математических наук

Цитович И. И.

Общая характеристика работы

Актуальность работы. В ближайшие десятилетия следует ожидать появления действующего прототипа квантового компьютера. В 1997 году П. В. Шор1 (P.W. Shor) продемонстрировал существование эффективных квантовых методов решения сложных вычислительных задач, определяющих криптостойкость известных алгоритмов цифровой подписи и асимметричного шифрования. В первую очередь к ним относятся широко применяемые на практике алгоритмы RSA, DSA, KCDSA, EC-DSA, ЕС-KCDSA, EC-GDSA (ISO/IEC 14888-3, ISO/IEC 14888-2 и IEEE Р1363), а также ГОСТ Р 34.10-2001. Другой известный результат2 К.-П. Шнорра (С.-P. Schnorr) и М. Якобссона (М. Jakobsson) указывает на то, что криптостойкость перечисленных алгоритмов определяется вычислительной трудоемкостью решения задач целочисленной факторизации и дискретного логарифмирования.

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

Аппарат теории кодирования широко применяется для построения протоколов идентификации и цифровой подписи. Следует отметить протокол Ж.Штерна4 (J.Stern), а также схему цифровой подписи на случайных кодах5 Г. А. Кабагянского, Е. А. Крука и Б.Дж.М. Смитса (В. J.M. Smeets).

Широко известны криптосистемы Р. МакЭлиса (R. МсЕНесе) и Г. Нидер-райтера (Н. Niederreiter) на основе кодов Гоппы6 и обобщенных кодов Рида-Соломона7. В работе В. М. Сидельникова и С. О. Шестакова предложена эффективная атака на криптосистему на основе обобщенных кодов Рида—Соломона8. В. М. Сидельников разработал вариант криптосистемы на кодах

1 Shor P. W. Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // SIAM J. of Сотр. 1997. no. 26. Pp. 1484-1509.

2 Schnorr C. -P., Jakobsson M. Security of Discrete Log Cryptosystems in the Random Oracle and Generic Model //In The Mathematics of Public-Key Cryptography. The Fields Institute. 1999.

3 Barg A. Complexity Issues in Coding Theory // Handbook of coding theory. Ed. by V. S. Pless, W. C. Huffman, R. Brualdi. Amsterdam, Holland: Elsevier Science, 1998.

4 Stern J. A New Identification Scheme Based on Syndrome Decoding // Advances in Cryptology-CRYPTO'93. Lect. Notes in Сотр. Sci. Springer-Verlag. 1993. Vol. 773. Pp. 13-21.

5 KabatianskiiG., KroukE., Smeets B.J.M. A Digital Signature Scheme Based on Random Error-Correcting Codes // Lect. Notes in Сотр. Sci. Springer-Verlag. 1997. Vol. 1355. Pp. 161-167.

6 McElieceR. A Public-key Cryptosystem Based on Algebraic Coding Theory // Deep Space Network Progress Report / DSN PR 42-44. 1978. - Apr 15. Pp. 114-116.

7 Niederreiter H. Knapsack-type Cryptosystems and Algebraic Coding Theory // Prob. of Control and Inform. Theory. 1986. Vol. 15, no. 5. Pp. 159-166.

8 Sidelnikov V. M., Shestakov S. 0. On Insecurity of Cryptosystems Based on Generalized Reed-Solomon Codes // Disc. Math, and App. 1992. Vol. 2, no. 4. Pp. 439-444.

Рида—Маллера9. Подробное исследование этой криптосистемы завершилось доказательством ее уязвимости10. В 1991 году Э.М. Габидулин, A.B. Парамонов, О. В. Третьяков предложили криптосистему, основанную на кодах, исправляющих ошибки в ранговой метрике11.

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

Для решения задачи применялись методы теории помехоустойчивого кодирования.

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

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

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

Отметим, что известные решения не всегда адекватно согласуются с требованиями практики и часто не обеспечивают достаточного количества эн-

9 Sidelnikov V. М. A Public-key Cryptosystem based on Binary Reed-Muller Codes // Disc. Math, and App. 1994. Vol. 4, no. 3. Pp. 439-444.

10 Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov Cryptosystem // Advances in Cryptology-EUROCRYPT'07 / Ed. by M. Naor. Vol. 4515 of Lect. Notes in Comp. Sei. Springer-Verlag, 2007. Pp. 347-360.

11 Gabidulin E. M., Parainonov A. V., Tretjakov О. V. Ideals Over a Non-Commutative Ring and Their Application in Cryptology // Advances in Cryptology-EUROCRYPT'91 / Ed. by D. W. Davies. Vol. 547 of Lect. Notes in Comp. Sei. Springer-Verlag, 1991. Pp. 482-489.

тропийпых разрядов.

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

DoS12-aTaKH отличаются от других известных атак. Задача DoS-атаки — создание искусственной ситуации, в которой добросовестному потребителю будет отказано в предоставлении соответствующих услуг.

За последние полтора десятка лет разработаны различные меры противодействия DoS-атаке, в том числе и метод шарад13. Обзор существующих решений представлен во второй главе диссертации.

Основная идея метода шарад заключается в создании искусственной вычислительной нагрузки на стороне отправителя — инициатора запроса. Это означает, что для успеха DoS-атаки необходимо инвестировать. Инвестиционные решения могут варьироваться в широком диапазоне: от организации распределенных вычислений до использования высокопроизводительных вычислительных платформ. Понятно, что атакующий способен прибегнуть к той или иной выигрышной стратегии, но неизбежное инвестирование безусловно является сдерживающим фактором. Вычислительный ресурс, задействованный в распределенной DoS-атаке (DDoS14), может также использоваться для отыскания решения, например с помощью распараллеливания вычислений, что очевидно снижает эффективность метода шарад. Кроме этого, шарады некоторых типов, например на основе таких трудноразрешимых задач как факторизация и дискретное логарифмирование, уязвимы с точки зрения атаки с применением квантового компьютера. Таким образом, при DDoS-атаке, а также атаке с применением квантового компьютера, адекватное противодействие с использованием известных решений затруднено или даже невозможно.

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

Цель диссертационной работы. Разработка метода «биометрической вуали», а также эффективных конструкций в рамках метода шарад с привле-

12 Denial of Service.

13 Brainard J., Juels A. Client Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks // Proc. of the ISOC Network and Distr. Sys. Sec. Sym. 1999. Pp. 151-165.

Distributed Denial of Service.

чением аппарата теории помехоустойчивого кодирования.

Задачи исследования. Для достижения поставленной цели необходимо было решить следующие задачи.

1. Построить абстрактную модель маскировки ключа с помощью биометрии на основе фундаментального свойства однородности образов/эталонов, полученных в результате измерений и обработки проекций биометрического объекта, и выполнить ее анализ.

2. Разработать метод маскировки криптографического ключа с помощью биометрии и обосновать его криптостойкость.

3. Разработать конструкции шарад на основе кодов, исправляющих ошибки.

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

Научная новизна. Научная новизна диссертационной работы заключается в том, что в ней впервые:

• построена абстрактная модель маскировки ключа с помощью биометрии на основе фундаментального свойства однородности образов/эталонов, полученных в результате измерений и обработки проекций биометрического объекта;

• предложена практическая реализация модели маскировки ключа с помощью биометрии с привлечением аппарата теории помехоустойчивого кодирования, — так называемый метод «биометрической вуали», и приведен пример кодовой конструкции;

• выполнен анализ криптостойкости метода «биометрической вуали»;

• выполнен анализ метода шарад и обозначены недостатки известных конструкций;

• введен класс шарад на основе кодов, исправляющих ошибки (кодовые шарады);

• сконструирована итеративная кодовая шарада и выполнен анализ ее устойчивости;

• предложена компактная и устойчивая итеративная кодовая шарада, обладающая широким диапазоном трудоемкости и допускающая плавную настройку.

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

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

Научные положения, выносимые на защиту. На защиту выносятся следующие основные результаты и положения:

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

• метод «биометрической вуали», гарантирующий адекватный уровень практической криптостойкости: при параноидальном подходе трудоемкость раскрытия эталона методом силовой атаки не менее 289 двоичных операций;

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

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

• итеративная кодовая шарада, которая не поддается распараллеливанию;

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

Апробация работы. На представленные в первой главе результаты получен патент Российской Федерации, а также патенты Республики Корея и США [1-3]. Кроме этого, материалы диссертационной работы были использованы при подготовке курса лекций по теме «Криптографические методы защиты информации в компьютерных системах и сетях» по направлению 011674 факультета РТК Московского физико-технического института

кафедры «Проблемы передачи и обработки информации», прочитанных в период с 2008 по 2011 гг. Следует также отметить, что результаты, представленные ранее в патентах [1-3] и позднее в публикации [4], были впоследствии воспроизведены группой специалистов Компьютерной лаборатории (Computer Laboratory) Кембриджского университета под руководством известного эксперта в области защиты информации, профессора Р. Андерсона (R. Anderson), и опубликованы в техническом отчете UCAM-CL-TR-640 в июле 2005 г., а затем и в статье15 2006 г. Однако, приоритет принадлежит российским авторами, как авторам первой патентной заявки по данной тематике, зарегистрированной в мае 2004 г. Таким образом, можно заключить, что результаты, изложенные в первой главе настоящей диссертации, с успехом прошли международную апробацию.

Публикации. В ходе подготовки диссертации соискателем опубликованы 14 печатных работ [1-14), включая патенты Российской Федерации, США и Республики Корея. Конкретно по теме диссертации опубликованы 5 печатных работ [1-4, 7], из них 2 опубликованы в реферируемых изданиях, включенных в Перечень ВАК [4, 7].

Личный вклад автора. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы. Подготовка заявок по патентам [1-3] проводилась совместно с соавтором, причем вклад диссертанта не менее 50%. Все представленные в диссертации результаты получены лично автором.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, библиографии и приложения. Общий объем работы составляет 115 страниц. Диссертация содержит 2 рисунка и одну таблицу по объему не превышающих одну страницу. Список литературы состоит из 101 наименования на 13 страницах.

Содержание работы

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

В первой главе описан метод маскировки ключа с помощью биометрии. Результаты опубликованы в работе [4], а также в патентах [1-3].

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

15 Нао F., Anderson R., Daugman J.G. Combining Crypto with Biometrics Effectively // IEEE Trans, on Comp. 2006. Vol. 55, no. 9. Pp. 1081-1088.

страции и сохраняется в долговременной памяти. Биометрический образ5 — характеристика, полученная в результате текущего, как правило однократного, измерения биометрического объекта. Образ предъявляется для распознавания с помощью эталона.

Определение. Образ и эталон считаются однородными, если получены от одного объекта и удовлетворяют критерию однородности, который задастся как ограничение расстояния между образом и эталоном.

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

Для указания на однородность образа и эталона воспользуемся обозначением и — для неоднородности.

Пусть задан криптографический ключ К и произвольные 5, Т. Введем следующую пару преобразований: М = /(Т, К) и К. = д(М:3). Положим 7 = 1о§2 М и Л = 1о§2 К.

Рассмотрим ряд условий и предположений, составляющих основу модели.

1. /(■, •) и д(-, •), Л4 —общедоступны.

2. Если 5 ^ Т, то 1С = К. Если 5 Т, то /С ф К.

3. При известных Т и К, значение А4 вычисляется со сложностью 0(Аа), а > 1.

4. Для заданного Б, 5 ^ Т, ключ К вычисляется со сложностью 0(Х/3),

5. Для заданного 5, 5 ф; Т, ключ К вычисляется со сложностью 0(ехр (7)).

С. При известном Т, ключ К вычисляется со сложностью 0(1).

7. При неизвестном Т, ключ К вычисляется со сложностью 0(ехр (7)).

Согласно 6, ключ К и эталон Т должны сохраняться в секрете. Из 4 следует, что образ 5 также должен сохраняться в секрете.

Предположим, что секретность определяется наличием зоны относительной неуязвимости, которая ограничена периметром безопасности. Следовательно, формирование Тиб1, генерацию ключа К и получение К из М. при заданном 5, необходимо выполнять в пределах обозначенной зоны.

В дальнейшем будем исходить из следующих предположений.

• Доверенная сторона отвечает за регистрацию, генерацию ключа К, формирование эталона Т, а также Л4. Операционная активность доверенной стороны ограничена пределами зоны относительной неуязвимости.

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

• В ходе формирования образа S может быть предъявлен не тот биометрический объект, который использовался при формировании эталонаТ. Также может быть предъявлен артефакт.

• Операционная активность на этапе распознавания образа S с помощью эталона Т и принятия решения по результатам распознавания осуществляется в пределах зоны относительной неуязвимости.

Пусть криптографический ключ К трактуется как информационные символы линейного /с-мерного кода С с минимальным расстоянием d. Код С задан к х п порождающей матрицей G. Тогда существует кодовое слово с = KG, с G кег(Я), где Н — (п — к)хп проверочная матрица кода С. Биометрический эталон Т рассматривается как вектор ошибки е для кодового слова с. Сумма М = с + е = KG ф Т сохраняется в долговременной памяти. Если Т ^ S, то wt(T © S) < [(с? — 1)/2] и код способен исправить Т ф S ошибок. Если Т ^ S, то wt(T® S) > |"(ci — 1)/2] и код не сможет исправить ошибки. Свойства радужной оболочки глаза человека таковы16, что при Т S получение ключа К не сопряжено с высокими вычислительными трудозатратами, но при Т ф S ключ недоступен. Доказано, что декодирование по максимуму правдоподобия случайного кода, эквивалентное в нашем случае декодированию в ближайшее кодовое слово, относится к классу NP-трудных проблем17.

Кроме этого показано, что декодирование по максимуму правдоподобия даже для специфических семейств случайных кодов, например кодов Рида-Соломона, также относится к классу NP-трудных проблем18.

Отметим, что алгоритм декодирования Гурусвами—Судана19 позволяет исправлять ошибки веса t > |~(<i — 1)/2]. Однако несложно выбрать код так, что декодирование с исправлением ошибок станет невозможным.

16 Daugman J. G. Probing the Uniqueness and Randomness of IrisCodcs: Results From 200 Billion Iris Pair Comparisons // Proc. of the IEEE. 2006. Vol. 94, no. 11. Pp. 1927-1935.

17 Berlekamp E. R., McEliece R. J., van Tilborg H. C. A. On the Inherent Intractability of Certain Coding Problems // IEEE Trans. Inform. Theory. 1978. Vol. IT-24, no. 3. Pp. 384-386.

18 Guruswami V., Vardy A. Maximum-Likelihood Decoding of Reed-Solomon Codes is NP-hard // IEEE Trans. Inform. Theory. 2005. Vol. 51, no. 7. Pp. 2249-2256.

19 Guruswami V., Sudan M. Improved Decoding of Reed-Solomon Codes and Algebraic Geometry Codes // IEEE Thms. Inform. Theory. 1999. Vol. 45, no. 6. Pp. 1757-1767.

-Ж

Д»«ОД»Р блочного

(п. Л-ЯМИ

T

Отиаот выделения

2. Ьпфлимостя скотарл**"

Рис. 1. Представление ключа

Рис. 2. Получение ключа

Дадим описание метода «биометрической вуали», который в существенной степени использует свойства радужной оболочки глаза.

Для представления криптографического ключа выполняются следующие действия (рис. 1).

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

2. С помощью генератора псевдослучайных чисел генерируют ключ К.

3. Формируют тестовый образец для проверки ключа. Например, К = h(K), где h(-) — криптографическая хэш-функция.

4. Вычисляют Y = h{T).

5. Ключ К зашифровывают с помощью Y, X = Еу{К), где Еу(•) — функция зашифрования.

G. Выполняют кодирование X блочным (п, к, eQ-кодом с целью получения кодового слова С.

7. Вычисляют поразрядную сумму СфТи сохраняют результат в долговременной памяти.

Для получения криптографического ключа выполняется следующая последовательность действий (рис. 2).

1. Получают данные от, по меньшей мере, одного биометрического объекта.

2. Формируют образ S.

3. Извлекают из долговременной памяти сумму С @Т.

4. Вычисляют поразрядную сумму Сош = С &Т © S. Отметим, что после суммирования кодовое слово Сош все еще может содержать ошибки.

5. Выполняют конструктивное декодирование Сош. Возможны следующие три события.

I. Вес вектора ошибки не превышаешь. Это означает, чтоТ ^ 5. Ошибки будут исправлены в декодере блочного кода, информационные символы X восстановлены корректно.

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

III. Вес вектора ошибки значительно превышаешь. Это означает, что Т ф 3. Декодер блочного кода исправляет ошибки меньшего веса в другом, отличном от Сош, кодовом слове и вместо X восстанавливает случайную последовательность информационных символов. Событие опосредованно обнаруживается на шаге 10.

6. Предположим, что вес вектора ошибки не превышает Ь. В результате декодирования получают исправленное кодовое слово Сош.

7. Извлекают С®Т из долговременной памяти и вычисляют поразрядную сумму Т = Сош Ф (С ф Т).

8. Вычисляют У =

9. Выделяют ключ К = Юу(Х), где £>г(-) — функция расшифрования.

10. Для верификации ключа извлекают тестовый образец из долговременной памяти и проверяют справедливость равенства К = 1г(К). Если равенство не подтверждено, то на специальном выходе формируется признак отказа от получения ключа.

Выполним анализ криптостойкости метода «биометрической вуали». При известном X = Еу(К) несложно вычислить С и Г. Отметим, что X присутствует в памяти устройства в течение короткого промежутка времени, тогда как ключ К используется для зашифрования/расшифрования значительных объемов информации и в большей степени подвержен компрометации. Также возможно использование тестового образца для проверки ключа А" = к (К). Действительно, если автономный носитель доступен на чтение, то злоумышленник может скопировать С ф Т и К без ведома владельца.

Для того, чтобы определить Т при известном К необходимо вычислить X, но для этого необходимо знать Т. Следовательно, при известном К и неизвестном Т невозможно вычислить X.

Предположим, декодер исправляет ошибки веса£ < ("(й - 1)/2]. Обозначим образ-претендент как §, отличное от С кодовое слово обозначим через С,

К = Dy(X), где Y = h(T). Испытание каждого претендента сопровождается проверкой следующих гипотез.

I. C®T®S = C.

II. C®T®S = C.

III. C®T®S = C + e, t< \{d-l)/2\.

IV. C®T®S = C + e,t< \{d — l)/2].

Подтверждение гипотез II и IV указывает на факт получения эталона Т. Причем гипотеза II соответствует случаю S = Т и декодированию без исправления ошибок, а гипотеза IV — декодированию с исправлением ошибок, когда wt(Тф5) < \{d-l)/2}. Поскольку вектор ошибки е = T®S определяется в результате декодирования, то легко вычислить Т — S фе. Однако по результатам декодирования невозможно отделить гипотезу II от I, а также гипотезу IV от III. Тогда равенство К = К свидетельствует о подтверждении гипотезы II или IV, & К Ф К —о подтверждении гипотезы I или III.

Отдельное испытание в ходе силовой атаки состоит из следующих шагов.

1. Синтез претендента S.

2. Декодирование С ф Т ф S. Получение С, X, е.

3. Вычисление Т = S ф е.

4. Вычисление Y = h(T).

5. Расшифрование К = Dy(X).

? ~ ? ~

6. Сравнение К = К или К = h(K).

Образ состоит из 211 двоичных разрядов. Энтропия образа, так же как эталона, не превышает 249 двоичных разрядов20. Предположим, что известны все 249 позиций, на которых располагаются случайные и независимые символы. Предположим также, что этот набор позиций зафиксирован для всевозможных образов. Значения символов на остальных позициях образа могут быть вычислены с приемлемой трудоемкостью. Сделаем упрощающее предположение о расположении на этих позициях символов с нулевыми значениями. Следовательно, если заданы два различных образа 5i и ¿2, то wt(Si ®5t)< 249.

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

20 Daugman J. G. How Iris Recognition Works // IEEE Trans. Circ. Sys. Video Tech. 2004. Vol. 14, no. 1. Pp. 21-30.

неосуществима, так как в среднем для поиска решения необходимо испытать 2218

претендентов.

Предположим, что код исправляет все двоичные ошибки Becai и меньше. Пусть задано кодовое слово с ошибками Сот = СфГ. Очевидно, что значение, которое принимает символ на каждой из 249 позиций слова Сош, есть результат суммирования случайного и кодового символов. Если код исправляет не более t ошибок, то можно изменить значения символов на произвольных t из известных 249 позиций и затем провести испытание (шаги 2, 3, 4, 5 и 6). Пусть задан список из 249 позиций. Чтобы изменить значения символов достаточно сформировать шаблон S веса t такой, что его разрядность равна 2й и на позициях из списка расположены t единиц, а нули расположены на всех остальных позициях. Затем выполнить суммирование Сош ф S. Тогда совокупное число испытаний не превысит (2;9) попыток. Следует, однако, отметить, что при г = 10 число испытаний не более 256, но при г > 100 число испытаний сравнимо с

2248

и атака методом перебора ошибок веса t не имеет

никаких преимуществ.

Из свойств радужной оболочки следует, что можно ввести ограничение на t сверху, положив t = 83. Но уже при t = 16 число испытаний приближается к 280. Согласно действующим прогнозам21, криптостойкость гарантируется при разрядности ключа от 75 до 80. Это означает, что в диапазоне 10 < t ^ 83 исчерпывающий перебор невозможен. Следовательно, с помощью перебора ошибок веса t можно проверить не более 9% от общего числа претендентов.

Оценим трудоемкость перебора как совокупное число двоичных операций при t = 10. Трудоемкость отдельного испытания определяется вычислительной сложностью шагов 2, 4 и 5. Известно, что вычислительная сложность алгоритма синдромного декодирования алгебраического кода полиномиальна по п и, как правило, не превышает 0(пг). Для приведенного ранее примера кодовой конструкции сложность декодирования порядка 233 двоичных операций. Сложность расшифрования по алгоритму AES порядка 210 двоичных операций на 128-разрядный блок22. Для вычисления значения хэш-функции по алгоритму SHA-256 потребуется не более 216 двоичных операций на 512-разрядный блок. Предположим, трудоемкость испытания не превышает 233 двоичных операций. Тогда трудоемкость перебора ошибок веса t = 10 составит порядка 289 двоичных операций. Если производительность испытательного устройства 100 Гбит/с, то для поиска решения методом исчерпывающего перебора при £ = 10 понадобится не менее 108 лет.

21 Yearly Report on Algorithms and Key Sizes (2010) // D.SPA.13 Rev. 1.0. ICT-2007-216676 ECRYPT II. 03/2010.

22 Bertoni G., Breveglieri L., Fragneto P., Macchetti M., Marchesin S. Efficient Software Implementation of AES on 32-bit Platforms // Lect. Notes in Comp. Sei. 2003. Vol. 2523. Pp. 129-142.

Во второй главе приводятся сведения о методе шарад как эффективном способе противодействия DDoS-атаке.

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

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

Назовем экзаменатором того, кто создает шараду и знает её решение, а экзаменуемым того, кто выполняет поиск решения по заданию экзаменатора.

Сформулируем набор требований к шарадам в контексте DDoS-атаки.

A. Собственно шарады не должны быть инструментом атаки. Вычислительная трудоемкость построения шарады и проверки ее решения не должна быть чрезмерной.

B. Трудоемкость решения шарады должна быть регулируемой. Адекватная реакция на изменение сетевой нагрузки достигается настройкой трудоемкости.

C. Решение шарады возможно при наличии определенного вычислительного потенциала. Алгоритм решения должен быть задан явно. Трудоемкость отыскания решения должна быть ограничена сверху.

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

23 В англоязычной литературе используется термин «puzzle».

24 Brainard J., Juels A. Client Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks // Proc. of the ISOC Network and Distr. Sys, Sec. Symp. 1999. Pp. 151-165.

Шарады с последовательным алгоритмом решения25 не допускают распараллеливания, но эффективно решаются при известном ф{п) = (q — 1 ){р— 1), п = pq. Можно получить q и р в результате факторизации п. Алгоритм факторизации с полиномиальной трудоемкостью для квантового компьютера предложен П. В. Шором26.

Другие шарады27 не только эффективно решаются с помощью квантового вычислителя, но также допускают распараллеливание.

В третьей главе описаны конструкции шарад на основе кодов, исправляющих ошибки. Результаты опубликованы в работе [7].

Пусть имеется к-мерный линейный код С с минимальным расстоянием d. Код задан к х п порождающей матрицей G. Тогда существует кодовое слово с = рG, с ç ker(H), где И — (п — к) X п проверочная матрица кода С и р — информационная последовательность. Если Ci,C2 € С, то Сз = ci + Сг = (Pi + P2)G и С3 S С.

Назовем кодовыми шарады, построенные на основе кода С. Код известен как экзаменатору, так и экзаменуемому.

Шарада устойчива, если не существует иного, менее трудоемкого способа её решения, кроме заданного по построению. Устойчивость кодовых шарад теоретически обоснована, т.к. альтернативный способ отыскания решения — декодирование по максимуму правдоподобия, а это —NP-трудная проблема.

Чем меньше минимальное кодовое расстояние cf, тем шире диапазон трудоемкости. Очевидно, что d обратно-пропорционально размерности кода и для конструирования шарад предпочтительнее высокоскоростные коды, для которых отношение R = k/n стремится к 1.

Пусть задан [n,n — d+1, d]q код Рида—Соломона (код PC) над¥9, q = рт, где р — простое число, m — положительное целое, который имеет максимально возможную размерность при заданных п и d. Тогда d = п — /с + 1 и код может исправлять t ^ [(п — к)/2] ошибок. Известно28, что существуют коды PC с блоковой длиной п = q — 1, расширенные с п = q и дважды расширенные с п = q + 1. Это означает, что всегда можно выбрать код с четным п. Шараду на основе кода PC будем называть RSq(n, (¿)-шарадой.

RSq(n, 1)-шарада обладает максимально широким диапазоном трудоемкости, поскольку вес ошибки варьируется в интервале n/2 > t ^ 1. Шарада безусловно устойчива, т.к. к > п/2.

25 Rivest R.L., Shamir A., Wagner D. Time-lock puzzles and timed-release crypto // Tech. Rep. MIT/LCS/TR-684. 1996.

26 Shor P.W. Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // SIAM J. of Comp. 1997. no. 26. Pp. 1484-1509.

27 Waters В., Juels A-, Halderman A-, Feiten E. New Client Puzzle Outsourcing Techniques for DoS Resistance // ACM CCS. 2004. Pp. 246-256.

28 МакВильямс Ф.Д., Слоэн Н.Дж. Теория кодов, исправляющих ошибки. Москва: Связь, 1979.

744 с.

Очевидно, что при к ^ п/2 наблюдается объективное сужение диапазона трудоемкости, т.к. вес ошибки необходимо выбирать из интервала [(с? — 1)/2") + е ^ ( < к. Если указанное ограничение на интервал не выполняется и к < Ь ^ п/2. то шарада неустойчива, т.к. справедливо неравенство < 5Г;=[(<г-1)/21+е(9 — !)'(?) 11 трудоемкость отыскания решения будет ниже запланированной. Здесь е — величина, которая обеспечивает маскировку кода с алгоритмом декодирования полиномиальной трудоемкости под код, для которого возможно только корреляционное декодирование. Для ЯБ^п, 1)-шарады е = 0.

Следовательно, для построения устойчивых Д59(п. с?)-шарад с широким диапазоном трудоемкости следует использовать коды со скоростями в интервале 0.5 < Д < 1. 1)-шарады представляются наиболее перспективными с практической точки зрения.

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

Назовем итеративным хэшированием преобразование вида 1р1-1 = кШ... Н(1г(з))...)), где I — число итераций. Финальное значение

V '

I раз

получается из стартового е. Совокупность значений ^-ъ 4Ч-2> ■ ■ •, ^о будем называть хэш-цепочкой.

Вначале зададим вес ошибки ^ для каждой из í подшарад. Затем для й 6д Ъ методом итеративного хэширования вычислим цепочку "Фе~1, Фе-2-. ■ ■ ■ ■ 4>1, Фо- Отобразим каждый т/>г на линейное пространство размерности п над ¥д. Предположим п = рт, ь = Гыз^]'1 ^ ь ^

п и каждый грг состоит из Ъ д-ичных символов. В результате отображения получим Ф* = где О™-6 — последовательность из п — 6 нулевых символов поля

¥д И Ф< € о «С г ^ £ - 1.

Заданы наборы {Ф^_ь..., Фь Фо} и {¿1,...,^}. Для построения 1)*-шарады экзаменатор выполняет следующие действия.

1. Выбирает информационную последовательность р Ед

2. Сохраняет ¡р = /г(р) для проверки решения.

3. Устанавливает з := 1 и р := р.

4. Выбирает ошибку е 6д такую, что 1 ^ wt(e) ^ tj.

5. Вычисляет с = (р + + е.

6. Устанавливает ,?':=,? +1 и р := с.

?

7. Проверяет ^ = £ + 1. При равенстве к 8, иначе к 4.

8. Передает {с, £, 5, (¿1,..., экзаменуемому.

Экзаменуемый выполняет следующие действия.

1. Устанавливает у := £, р := с и К := /¿(в).

2. Выбирает ошибку е б¥™ такую, что 1 ^ мЛ(е) ^

3. Вычисляет сумму с = р + е.

4. В результате декодирования с получает р.

5. Отображает = %~Ь\\П.

0. Проверяет (р + = с + "$'(-¿0. При равенстве к 7, иначе к 2.

7. Устанавливает ] := ] — 1, р := р + Ф^- и Й:= Л(Й).

?

8. Проверяет ] = 0. При равенстве к 9, иначе к 2.

9. Предъявляет (/г' = /г(р) в качестве решения.

Предположим, что для представления числа 5 в памяти достаточно А двоичных разрядов. Тогда для хранения 1)*-шарады потребуется за-

резервировать не более 0(пт\о$2р + + А) двоичных разрядов.

Трудоемкость отыскания решения не превышает

е Ь .

г=1 4 '

испытаний.

Проанализируем /¿^(тг, 1)*-шараду на устойчивость. Соответствующее итеративное преобразование можно представить в виде

с =((((... ((((р + Ф/_1)(? + е1) + Ф/_2)0 + е2) + ... + Ф1)С + е/_1) + Фо)С+е/)1

где р, ^ £ц и Ф, ф ф; для I ф ], 0 ^ г, ] < £.

Каждое кодовое слово [п,п, 1]9-кода располагается в центре сферы нулевого радиуса и все такие сферы не пересекаются. Число сфер равно числу кодовых слов, которое для [п. п, 1]9-кода совпадает с мощностью Тогда произвольная ошибка веса 0 С ^ ^ тг переводит кодовое слово [п, п, 1]9-кода в другое кодовое слово того же кода с единичной вероятностью и каждая подшарада ИБ^п, 1)*-шарады имеет единственное решение.

При заданном в несложно вычислить Ф^-. Если с = (р + Ф^-^С?, то в результате декодирования будет получена информационная последовательность I = р + и уравнение вида (I + = с + Ф^С следует из линейности кода. По построению кодовое слово с маскируется ошибкой е, 1 ^ ^)ИС = е + е. Решение _?'-ой подшарады заключается в нахождении ошибки е. Пусть заданы с, Ф^- и некоторая ошибка б ^ е. Для с = с + ё в результате декодирования будет получена информационная последовательность I т^ I. Решение ё будет отвергнуто, т.к. (I + Ф^)*? ф с + Ф^С.

Поскольку применяется безызбыточный код, то для ^'-ой подшарады существует ц11 кодовых слов. При 1 ^ ^ п/2 справедливо неравенство <?" > ~ 11 Для отыскания решения исчерпывающий перебор по

е выгоднее, чем исчерпывающий перебор по р.

В ряде случаев экспоненциальное изменение трудоемкости не адекватно воздействию и поэтому не оправдано. Из (1) следует, что трудоемкость отыскания решения для Лй'^тг, 1)*-шарады задается функцией, которая допускает гибкую настройку шага изменения трудоемкости. Очевидно, что = С')йгЬ 1 ^ г ^ п- Тогда при увеличении/уменьшении на единицу веса £ ошибки е трудоемкость отыскания решения возрастает/у бывает в раз. Поскольку (") = п, то для 1)*-шарады минимальный шаг изменения

трудоемкости равен п.

В Заключении обобщены полученные в диссертационной работе результаты и сделаны выводы.

Основные результаты

Сформулируем основные результаты диссертационного исследования.

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

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

3. Выполнен анализ криптостойкости метода «биометрической вуали». Показано, что метод гарантирует адекватный уровень практической криптостойкости.

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

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

6. Сконструирована итеративная кодовая шарада, которая не поддается распараллеливанию.

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

Список публикаций

1. Чмора A. JL, Уривский А. В. Биометрическая система аутентификации / ФГУ ФИПС. Патент на изобретение, 2004.-Май 12. № 2316120.

2. Climora A., Ourivski A. Method and Apparatus for Generating Cryptographic Key Using Biométrie Data / Republic of Korea Patent Office. Republic of Korea Patent, 2005. - Mar 26. No. 10-2005-0025211.

3. Chmora A., Ourivski A. Method and Apparatus for Generating Cryptographic Key Using Biométrie Data / United States Patent and Trademark Office. United States Patent, 2010.-Sep 21. No. 7,802,105.

4. Чмора A. Jl. Маскировка ключа с помощью биометрии // Проблемы Передачи Информации. 2011. Т. 47, № 2. С. 131-146.

5. Чмора Андрей. Современная прикладная криптография. Москва: Гелиос, 2002. 256 с. ISBN: 5-85438-046-3.

6. Error Control, Cryptology, and Speech Compression // Workshop on Information Protection / Ed. by A. Chmora, S. B. Wicker. Lecture Notes in Computer Science. Moscow, Russia: Springer-Verlag, 1994. — Dec 6-9.

7. Чмора A. Jl. Кодовые шарады // Информационно-управляющие системы. 2010. № 6. С. 47-53.

8. Chmora A., Ourivski A. Method and System for Distributed Certificate Management in Ad-hoc Networks / United States Patent and Trademark Office. United States Patent, 2008. - Jun 3. No. 7,382,762.

9. Chmora A., Urivskiy A. Method of Managing a Key of User for Broadcast Encryption / United States Patent and Trademark Office. United States Patent, 2010. - Aug 10. No. 7,774,598.

10. Urivskiy A., Chmora A., Bogachov A. et al. Method for Making Seed Value Used in Pseudo Random Number Generator and Device Thereof / United States Patent and Trademark Office. United States Patent, 2010.— Aug 10. No. 7,773,748.

11. Chmora A., Ourivski A. Light-weight Key Distribution Scheme in Wireless Network / United States Patent and Trademark Office. United States Patent, 2010.-Jun 15. No. 7,738,003.

12. Чмора A. Jl., Уривский А. В., Ким В. Схема предварительного распределения ключей для кластерных сетей и способ ее функционирования / ФГУ ФИПС. Патент на изобретение, 2008. - Июль 27. № 2330382.

13. Чмора A. JL, Уривский А. В., Захаров С. В. и др. Способ и устройство формирования стартового значения для генератора псевдослучайных чисел / ФГУ ФИПС. Патент на изобретение, 2007. - Январь 20. № 2292074.

14. Уривский А. В., Чмора А. Л. Система распределения ключей и способ ее функционирования / ФГУ ФИПС. Патент на изобретение, 2008. — Июль 20. № 2329605.

Подписанно в печать 20.03.2012

Усл.пл. -1.0 Заказ №08080 Тираж: ШОэкз.

Копицентр «ЧЕРТЕЖ.ру» ИНН 7701723201 107023, Москва, ул.Б.Семеновская 11, стр.12 (495) 542-7389 www.chertez.ru

Текст работы Чмора, Андрей Львович, диссертация по теме Теоретические основы информатики

Федеральное государственное бюджетное учреждение науки «Институт проблем передачи информации им. А. А. Харкевича Российской

академии наук»

61 12-5/2339

На правах рукописи

Чмора Андрей Львович

Методы теории помехоустойчивого кодирования в некоторых задачах защиты

информации

05.13.17 - Теоретические основы информатики

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата технических наук

Научный руководитель д.т.н., проф. Зяблов В. В.

Москва - 2012

Содержание

Введение ...........................................4

Глава I. Маскировка ключа с помощью биометрии.......13

1.1. Биометрия и криптографические ключи.............15

1.2. Модель маскировки ключа с помощью биометрии........16

1.3. Статистические свойства радужной оболочки..........21

1.4. Кодовая конструкция........................24

1.5. Постановка задачи..........................25

1.6. Метод «биометрической вуали»..................25

1.7. Сценарий практического применения ...................34

1.8. Выводы................................40

Глава II. Метод шарад..........................42

II. 1. Сетевая DoS-атака..........................42

11.2. Технология САРТСНА.......................43

11.3. Вычислительные шарады......................44

11.4. Шарады и DoS-атака........................56

11.5. Недостатки метода шарад .....................57

Глава III. Кодовые шарады......................60

III. 1. Кодовая конструкция ........................61

111.2. Выбор кода..............................63

111.3. Итеративный метод.........................65

111.4. Выводы................................73

Заключение..................................74

Литература..................................76

Приложение А. Основные понятия теории кодирования .... 89

А.1. Геометрическая интерпретация кода................90

А. 2. Проверочная, порождающая матрицы и их свойства......91

А.З. Коды Рида—Соломона .......................93

А.4. Коды Боуза—Чоудхури—Хоквингема...............94

А.5. Число проверочных матриц кода РС...............94

А.6. Обобщенные коды РС . .......................95

А.7. Обобщенные коды БЧХ.......................95

А.8. Декодирование линейного кода....................96

Приложение Б. Некоторые разделы криптографии.......98

Б.1. Криптографические хэш-функции.................98

Б.2. Блочные шифры...........................105

Приложение В. Парадокс дней рождения.............113

Введение

Актуальность работы. В ближайшие десятилетия следует ожидать появления действующего прототипа квантового компьютера. В 1997 году П. В. Шор1 (P. W. Shor) продемонстрировал существование эффективных квантовых методов решения сложных вычислительных задач, определяющих криптостойкость известных алгоритмов цифровой подписи и асимметричного шифрования. В первую очередь к ним относятся широко применяемые на практике алгоритмы RSA, DSA, KCDSA, EC-DSA, ЕС-KCDSA, EC-GDSA (ISO/IEC 14888-3, ISO/IEC 14888-2 и IEEE Р1363), а также ГОСТ Р 34.10-2001. Другой известный результат3 К.-П. Шнорра (С.-P. Schnorr) и М. Якобссона (М. Jakobsson) указывает на то, что криптостойкость перечисленных алгоритмов определяется вычислительной трудоемкостью решения задач целочисленной факторизации и дискретного логарифмирования.

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

Аппарат теории кодирования широко применяется для построения протоколов идентификации и цифровой подписи. Следует отметить протокол Ж.Штерна4 (J.Stern), а также схему цифровой подписи на случайных ко-

1 Shor P. W. Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum

Computer // SIAM J. of Сотр. 1997- no. 26. Pp. 1484-1509.

2 Schnorr C. -P., Jakobsson M. Security of Discrete Log Cryptosystems in the Random Oracle and Generic

Model //In The Mathematics of Public-Key Cryptography. The Fields Institute. 1999.

3 Barg A. Complexity Issues in Coding Theory // Handbook of coding theory. Ed. by V. S. Pless, W. C. Huffman, R. Brualdi. Amsterdam, Holland: Elsevier Science, 1998.

4 Stern J. A New Identification Scheme Based on Syndrome Decoding // Advances in

дах5 Г. А. Кабатянского, Е. А. Крука и Б. Дж. М. Смитса (В. J. М. Smeets).

Широко известны криптосистемы Р. МакЭлиса (R. МсЕНесе) и Г. Нидер-райтера (Н. Niederreiter) на основе кодов Гоппы6 и обобщенных кодов Рида-Соломона7. В работе В. М. Сидельникова и С. О. Шестакова предложена эффективная атака на криптосистему на основе обобщенных кодов Рида—Соломона8. В. М. Сидельников разработал вариант криптосистемы на кодах Рида—Маллера9. Подробное исследование этой криптосистемы завершилось доказательством ее уязвимости10. В 1991 году Э. М. Габидулин, А. В. Парамонов, О. В. Третьяков предложили криптосистему, основанную на кодах, исправляющих ошибки в ранговой метрике11.

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

Cryptology-CRYPTO'93. Lect. Notes in Сотр. Sci. Springer-Verlag. 1993. Vol. 773. Pp. 13-21.

5 KabatianskiiG., KroukE., Smeets B.J.M. A Digital Signature Scheme Based on Random Error-

Correcting Codes // Lect. Notes in Сотр. Sci. Springer-Verlag. 1997. Vol. 1355. Pp. 161-167.

6 McEliece R. A Public-key Cryptosystem Based on Algebraic Coding Theory // Deep Space Network

Progress Report / DSN PR 42-44. 1978. - Apr 15. Pp. 114-116.

7 Niederreiter H. Knapsack-type Cryptosystems and Algebraic Coding Theory // Prob. of Control and

Inform. Theory. 1986. Vol. 15, no. 5. Pp. 159-166.

8 Sidelnikov V. M., Shestakov S. 0. On Insecurity of Cryptosystems Based on Generalized Reed-Solomon

Codes // Disc. Math, and App. 1992. Vol. 2, no. 4. Pp. 439-444.

9 Sidelnikov V. M. A Public-key Cryptosystem based on Binary Reed-Muller Codes // Disc. Math, and

App. 1994. Vol. 4, no. 3. Pp. 439-444.

10 Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov Cryptosystem // Advances in Cryptology-EUROCRYPT'07 / Ed. by M. Naor. Vol. 4515 of Lect. Notes in Сотр. Sci. Springer-Verlag, 2007. Pp. 347-360.

11 Gabidulin E.M., Paramonov A.V., Tretjakov О. V. Ideals Over a Non-Commutative Ring and Their Application in Cryptology // Advances in Cryptology-EUROCRYPT'91 / Ed. by D.W. Davies. Vol. 547 of Lect. Notes in Сотр. Sci. Springer-Verlag, 1991. Pp. 482-489.

Для решения задачи применялись методы теории помехоустойчивого кодирования.

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

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

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

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

Разработка метода маскировки криптографического ключа с помощью биометрии, удовлетворяющего практическим требованиям и гарантирую-

щего адекватный уровень криптостойкости, представляется перспективной и актуальной.

DoS12-aTaKH отличаются от других известных атак. Задача DoS-атаки — создание искусственной ситуации, в которой добросовестному потребителю будет отказано в предоставлении соответствующих услуг.

За последние полтора десятка лет разработаны различные меры противодействия DoS-атаке, в том числе и метод шарад13. Обзор существующих решений представлен во второй главе диссертации.

Основная идея метода шарад заключается в создании искусственной вычислительной нагрузки на стороне отправителя — инициатора запроса. Это означает, что для успеха DoS-атаки необходимо инвестировать. Инвестиционные решения могут варьироваться в широком диапазоне: от организации распределенных вычислений до использования высокопроизводительных вычислительных платформ. Понятно, что атакующий способен прибегнуть к той или иной выигрышной стратегии, но неизбежное инвестирование безусловно является сдерживающим фактором. Вычислительный ресурс, задействованный в распределенной DoS-атаке (DDoS14), может также использоваться для отыскания решения, например с помощью распараллеливания вычислений, что очевидно снижает эффективность метода шарад. Кроме этого, шарады некоторых типов, например на основе таких трудноразрешимых задач как факторизация и дискретное логарифмирование, уязвимы с точки зрения атаки с применением квантового компьютера. Таким образом, при DDoS-атаке, а также атаке с применением квантового компьютера, адекватное противодействие с использованием известных решений затруднено или даже невозможно.

12 Denial of Service.

13 Brainard J., Juels A. Client Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks // Proc. of the ISOC Network and Distr. Sys. Sec. Sym. 1999. Pp. 151-165.

14 Distributed Denial of Service.

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

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