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

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

Методы теории помехоустойчивого

кодирования в некоторых задачах защиты

информации

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

АВТОРЕФЕРАТ

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

кандидата технических наук

Москва – 2012

Федеральном государственном бюджетном

Работа выполнена в учреждении науки «Институте проблем передачи информации им.

А. А. Харкевича Российской академии наук» (ИППИ РАН).

доктор техническх наук, профессор,

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

(консультант) Зяблов Виктор Васильевич доктор

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

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

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

ститут (государственный универси­ тет)

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

адресу:

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

Автореферат разослан « » 2012 г.

Ученый секретарь диссертационного совета Д 002.077.01, доктор физико-математических наук Цитович И. И.

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

В ближайшие десятилетия следует ожидать Актуальность работы.

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

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

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

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

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 Comp. Sci. Springer-Verlag. 1993. Vol. 773. Pp. 13–21.

5 Kabatianskii G., Krouk E., Smeets B. J. M. A Digital Signature Scheme Based on Random Error­ Correcting Codes // Lect. Notes in Comp. Sci. Springer-Verlag. 1997. Vol. 1355. Pp. 161–167.

6 McEliece R. A Public-key Cryptosystem Based оn 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. O. 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 году Э. М. Габидулин, А. В. Пара­ монов, О. В. Третьяков предложили криптосистему, основанную на кодах, исправляющих ошибки в ранговой метрике11.

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

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

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

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

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

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

Отметим, что известные решения не всегда адекватно согласуются с тре­ бованиями практики и часто не обеспечивают достаточного количества эн­ 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 Comp. Sci. Springer-Verlag, 2007.

Pp. 347–360.

11 Gabidulin Е. М., Paramonov А. 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. Sci. Springer-Verlag, 1991. Pp. 482–489.

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

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

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

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

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

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

Цель диссертационной работы.

вуали», а также эффективных конструкций в рамках метода шарад с привле­ 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. Разработать конструкции шарад на основе кодов, исправляющих ошиб­ Методы исследования.

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

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

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

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

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

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

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

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

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

Практическая значимость работы.

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

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

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

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

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

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

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

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

Апробация работы.

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

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

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

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

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

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

Результаты опубликованы в работе [4], а также в патентах [1–3].

Биометрический эталон — обобщенная характеристика, полученная в результате измерений и обработки множества проекций одного и того же био­ метрического объекта. Биометрический эталон формируется на этапе реги­ 15Hao F., Anderson R., Daugman J. G. Combining Crypto with Biometrics Effectively // IEEE Trans.

on Comp. 2006. Vol. 55, no. 9. Pp. 1081–1088.

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

Определение.

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

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

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

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

1. (·, ·) и (·, ·), — общедоступны.

3. При известных и, значение вычисляется со сложностью ( ), 4. Для заданного,, ключ вычисляется со сложностью ( ), 5. Для заданного,, ключ вычисляется со сложностью (exp ()).

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

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

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

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

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

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

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

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

Также может быть предъявлен артефакт.

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

Пусть криптографический ключ трактуется как информационные симво­ лы линейного -мерного кода с минимальным расстоянием. Код задан порождающей матрицей. Тогда существует кодовое слово c =, c ker(), где — () проверочная матрица кода. Биометрический эталон рассматривается как вектор ошибки e для кодового слова c. Сумма = c + e = сохраняется в долговременной памяти. Если, то wt( ) < ( 1)/2 и код способен исправить ошибок. Если, то wt( ) > ( 1)/2 и код не сможет исправить ошибки. Свой­ ства радужной оболочки глаза человека таковы16, что при получение ключа не сопряжено с высокими вычислительными трудозатратами, но при ключ недоступен. Доказано, что декодирование по максимуму правдоподобия случайного кода, эквивалентное в нашем случае декодирова­ нию в ближайшее кодовое слово, относится к классу NP-трудных проблем17.

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

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

16 Daugman J. G. Probing the Uniqueness and Randomness of IrisCodes: 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 Trans. Inform. Theory. 1999. Vol. 45, no. 6. Pp. 1757–1767.

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

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

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

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

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

4. Вычисляют = ( ).

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

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

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

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

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

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

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

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

Вес вектора ошибки не превышает. Это означает, что будут исправлены в декодере блочного кода, информационные символы восстановлены корректно.

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

Вес вектора ошибки значительно превышает. Это означает, что III.

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

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

7. Извлекают из долговременной памяти и вычисляют поразрядную 8. Вычисляют = ( ).

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

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

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

Действительно, если автономный носитель доступен на чтение, то злоумыш­ ленник может скопировать и без ведома владельца.

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

Предположим, декодер исправляет ошибки веса < ( 1)/2. Обозна­ чим образ-претендент как, отличное от кодовое слово обозначим через, = (), где = ( ). Испытание каждого претендента сопровождается проверкой следующих гипотез.

Подтверждение гипотез II и IV указывает на факт получения эталона. Причем гипотеза II соответствует случаю = и декодированию без ис­ правления ошибок, а гипотеза IV — декодированию с исправлением ошибок, когда wt( ) < ( 1)/2. Поскольку вектор ошибки e = определя­ ется в результате декодирования, то легко вычислить = e. Однако по результатам декодирования невозможно отделить гипотезу II от I, а также гипотезу IV от III. Тогда равенство = свидетельствует о подтверждении гипотезы II или IV, а = — о подтверждении гипотезы I или III.

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

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

2. Декодирование. Получение,, e.

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

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

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

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

Пусть имеется шаблон из 211 разрядов. Синтез образа заключается в генерации 249 случайных двоичных символов и размещении значений на из­ вестных позициях шаблона. При таком подходе силовая атака практически 20Daugman J. G. How Iris Recognition Works // IEEE Trans. Circ. Sys. Video Tech. 2004. Vol. 14, no. 1.

Pp. 21–30.

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

Предположим, что код исправляет все двоичные ошибки веса и меньше.

Пусть задано кодовое слово с ошибками ош =. Очевидно, что значение, которое принимает символ на каждой из 249 позиций слова ош, есть резуль­ тат суммирования случайного и кодового символов. Если код исправляет не более ошибок, то можно изменить значения символов на произвольных из известных 249 позиций и затем провести испытание (шаги 2, 3, 4, 5 и 6).

Пусть задан список из 249 позиций. Чтобы изменить значения символов до­ статочно сформировать шаблон веса такой, что его разрядность равна 211 и на позициях из списка расположены единиц, а нули расположены на всех остальных позициях. Затем выполнить суммирование ош. Тогда со­ вокупное число испытаний не превысит =0 попыток. Следует, однако, отметить, что при = 10 число испытаний не более 256, но при > 100 число испытаний сравнимо с 2248 и атака методом перебора ошибок веса не имеет никаких преимуществ.

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

Оценим трудоемкость перебора как совокупное число двоичных опера­ ций при = 10. Трудоемкость отдельного испытания определяется вычисли­ тельной сложностью шагов 2, 4 и 5. Известно, что вычислительная сложность алгоритма синдромного декодирования алгебраического кода полиномиаль­ на по и, как правило, не превышает (3 ). Для приведенного ранее при­ мера кодовой конструкции сложность декодирования порядка 233 двоичных операций. Сложность расшифрования по алгоритму AES порядка 210 двоич­ ных операций на 128-разрядный блок22. Для вычисления значения хэш-функ­ ции по алгоритму SHA-256 потребуется не более 216 двоичных операций на 512-разрядный блок. Предположим, трудоемкость испытания не превышает 233 двоичных операций. Тогда трудоемкость перебора ошибок веса = составит порядка 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. Sci. 2003. Vol. 2523. Pp. 129–142.

ном способе противодействия DDoS-атаке.

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

Сервер предлагает решить шараду в ответ на запрос. Доступ к ресурсу предоставляется по факту решения шарады. При 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 не допускают распа­ раллеливания, но эффективно решаются при известном () = ( 1)( 1), =. Можно получить и в результате факторизации. Алгоритм факторизации с полиномиальной трудоемкостью для квантового компьюте­ ра предложен П. В. Шором26.

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

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

Пусть имеется -мерный линейный код с минимальным расстоянием.

Код задан порождающей матрицей. Тогда существует кодовое слово c = p, c ker(H), где H — ( ) проверочная матрица кода и p — информационная последовательность. Если c1, c2, то c3 = c1 + c2 = как экзаменатору, так и экзаменуемому.

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

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

Пусть задан [, +1, ] код Рида—Соломона (код РС) над F, =, где — простое число, — положительное целое, который имеет максималь­ но возможную размерность при заданных и. Тогда = + 1 и код может исправлять ( )/2 ошибок. Известно28, что существуют коды РС с блоковой длиной = 1, расширенные с = и дважды расширен­ ные с = + 1. Это означает, что всегда можно выбрать код с четным.

Шараду на основе кода РС будем называть (, )-шарадой.

(, 1)-шарада обладает максимально широким диапазоном трудоем­ кости, поскольку вес ошибки варьируется в интервале /2 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 B., Juels A., Halderman A., Felten E. New Client Puzzle Outsourcing Techniques for DoS Resistance // ACM CCS. 2004. Pp. 246–256.

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

744 c.

Очевидно, что при /2 наблюдается объективное сужение диапазо­ на трудоемкости, т.к. вес ошибки необходимо выбирать из интервала ( <. Если указанное ограничение на интервал не выпол­ 1)/2 + няется и /2, то шарада неустойчива, т.к. справедливо неравен­ ство < дет ниже запланированной. Здесь — величина, которая обеспечивает мас­ кировку кода с алгоритмом декодирования полиномиальной трудоемкости под код, для которого возможно только корреляционное декодирование. Для (, 1)-шарады = 0.

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

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

1 = ((... (())...)), где — число итераций. Финальное значение получается из стартового. Совокупность значений 1, 2,..., 0 будем называть Вначале зададим вес ошибки для каждой из подшарад. За­ тем для Z методом итеративного хэширования вычислим цепочку 1, 2,..., 1, 0. Отобразим каждый на линейное пространство раз­ дый состоит из -ичных символов. В результате отображения получим = 0, где 0 — последовательность из нулевых символов поля (, 1)* -шарады экзаменатор выполняет следующие действия.

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

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

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

6. Устанавливает := + 1 и p :=.

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

8. Передает {,,, (1,..., )} экзаменуемому.

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

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

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

6. Проверяет ( + ) = +. При равенстве к 7, иначе к 2.

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

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

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

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

Проанализируем (, 1)* -шараду на устойчивость. Соответствующее итеративное преобразование можно представить в виде = ((((... ((((p+1 )+e1 )+2 )+e2 )+...+1 )+e1 )+0 )+e ), Каждое кодовое слово [,, 1] -кода располагается в центре сферы нуле­ вого радиуса и все такие сферы не пересекаются. Число сфер равно числу кодовых слов, которое для [,, 1] -кода совпадает с мощностью F. Тогда произвольная ошибка веса 0 < переводит кодовое слово [,, 1] -кода в другое кодовое слово того же кода с единичной вероятностью и каждая подшарада (, 1)* -шарады имеет единственное решение.

При заданном несложно вычислить. Если c = (p + ), то в результате декодирования будет получена информационная последователь­ ность I = p + и уравнение вида (I + ) = c + следует из линейности кода. По построению кодовое слово c маскируется ошибкой e, 1 wt(e) и ^ = c + e. Решение -ой подшарады заключается в нахожде­ нии ошибки e. Пусть заданы ^, и некоторая ошибка = e. Для = ^ + в результате декодирования будет получена информационная последователь­ ность = I. Решение будет отвергнуто, т.к. ( + ) = +.

Поскольку применяется безызбыточный код, то для -ой подшарады существует кодовых слов. При 1 /2 справедливо неравенство > =1 ( 1) и для отыскания решения исчерпывающий перебор по e выгоднее, чем исчерпывающий перебор по p.

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

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

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

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

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

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

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

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

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

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

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

2. Chmora A., Ourivski A. Method and Apparatus for Generating Cryptographic Key Using Biometric 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 Biometric Data / United States Patent and Trademark Office.

United States Patent, 2010. — Sep 21. No. 7,802,105.

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

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

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

7. Чмора А. Л. Кодовые шарады // Информационно-управляющие системы.

2010. № 6. С. 47–53.

8. Chmora A., Ourivski A. Method and System for Distributed Certificate Man­ agement 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,663.

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

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

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