WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

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

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

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

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. В. М. Сидельников разработал вариант криптосистемы на кодах 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.

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.

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.

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.

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.

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.

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

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

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

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

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

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

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.

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 использованием известных решений затруднено или даже невоз­ можно.

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

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

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-6в июле 2005 г., а затем и в статье15 2006 г. Однако, приоритет принадлежит российским авторами, как авторам первой патентной заявки по данной те­ матике, зарегистрированной в мае 2004 г. Таким образом, можно заключить, что результаты, изложенные в первой главе настоящей диссертации, с успе­ хом прошли международную апробацию.

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

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

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

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

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

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

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

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

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

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

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

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

Пусть задан криптографический ключ K и произвольные S, T. Введем следующую пару преобразований: M = f(T, K) и K = g(M, S). Положим = log2 M и = log2 K.

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

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

2. Если S T, то K = K. Если S T, то K = K.

3. При известных T и K, значение M вычисляется со сложностью O(), > 1.

4. Для заданного S, S T, ключ K вычисляется со сложностью O(), .

5. Для заданного S, S T, ключ K вычисляется со сложностью O(exp ()).

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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.

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.

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. В результате обработки множества проекций биометрического объекта получают набор данных, на основании которого формируют эталон T.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8. Вычисляют Y = h(T ).

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

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

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

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

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

Предположим, декодер исправляет ошибки веса t < (d - 1)/2. Обозна­ чим образ-претендент как S, отличное от C кодовое слово обозначим через , ).

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

I. C T S = .

II. C T S = C.

III. C T S = + e, t < (d - 1)/2.

IV. C T S = C + e, t < (d - 1)/2.

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

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

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

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

3. Вычисление T = S e.

).

4. Вычисление = h(T 5. Расшифрование K = D (X).

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

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

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

Pp. 21–30.

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

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

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

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

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

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

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

Bertoni G., Breveglieri L., Fragneto P., Macchetti M., Marchesin S. E cient 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 допускают возможность отыскания решения неза­ висимыми вычислителями, причем каждый из таких вычислителей выполня­ ет поиск в пределах некоторого подмножества претендентов, мощность кото­ рого меньше мощности исходного множества. Назовем такой подход к поис­ ку решения распараллеливанием. Атакующий может воспользоваться мето­ дом распределенных вычислений. Для организации таких вычислений необ­ ходимо выполнить предварительную подготовку заданий с последующим их распределением с помощью специализированного протокола. Как только ре­ шение найдено одним из вычислителей, все остальные должны по команде прекратить обработку заданий.

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

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

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

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

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

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

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

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

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

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

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

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

Rivest R. L., Shamir A., Wagner D. Time-lock puzzles and timed-release crypto // Tech. Rep.

MIT/LCS/TR-684. 1996.

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.

Waters B., Juels A., Halderman A., Felten E. New Client Puzzle Outsourcing Techniques for DoS Resistance // ACM CCS. 2004. Pp. 246–256.

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

744 c.

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

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

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

Назовем итеративным хэшированием преобразование вида l-1 = h(h(... h(h(s))...)), где l — число итераций. Финальное значение l- l раз получается из стартового s. Совокупность значений l-1, l-2,..., 0 будем называть хэш-цепочкой.

Вначале зададим вес ошибки tj для каждой из подшарад. За­ тем для s R Z методом итеративного хэширования вычислим цепочку -1, -2,..., 1, 0. Отобразим каждый i на линейное пространство раз­ мерности n над Fq. Предположим n = pm, b = m log2 p, 1 b n и каж­ дый i состоит из b q-ичных символов. В результате отображения получим i = 0n-bi, где 0n-b — последовательность из n - b нулевых символов поля q q Fq и i Fn, 0 i - 1.

q Заданы наборы {-1,..., 1, 0} и {t1,..., t}. Для построения RS(n, 1)*-шарады экзаменатор выполняет следующие действия.

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

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

: :

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

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

q 5. Вычисляет = ( + -j)G + e.

p : :

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

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

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

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

: : :

1. Устанавливает j = , p = и = h(s).

2. Выбирает ошибку e Fn такую, что 1 wt(e) tj.

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

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

5. Отображает -j = 0n-b.

q ? 6. Проверяет ( + -j)G = + -jG. При равенстве к 7, иначе к 2.

p : : :

7. Устанавливает j = j - 1, p = p + -j и = h( ).

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

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

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

Трудоемкость отыскания решения не превышает tj n (q - 1)i (1) i j=1 i=испытаний.

Проанализируем RS(n, 1)*-шараду на устойчивость. Соответствующее q итеративное преобразование можно представить в виде = ((((... ((((p+-1)G+e1)+-2)G+e2)+...+1)G+e-1)+0)G+e), где p, ej R Fn и j = i для i = j, 0 i, j .

q Каждое кодовое слово [n, n, 1]q-кода располагается в центре сферы нуле­ вого радиуса и все такие сферы не пересекаются. Число сфер равно числу кодовых слов, которое для [n, n, 1]q-кода совпадает с мощностью Fn. Тогда q произвольная ошибка веса 0 < t n переводит кодовое слово [n, n, 1]q-кода в другое кодовое слово того же кода с единичной вероятностью и каждая подшарада RS(n, 1)*-шарады имеет единственное решение.

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

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

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

t+n Поскольку = n, то для RS(n, 1)*-шарады минимальный шаг изменения q трудоемкости равен n.

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

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

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 O ce. 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 O ce.

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 O ce.

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 O ce. 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 O ce. 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 O ce. United States Patent, 2010. — Jun 15. No. 7,738,663.

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

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

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




© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.