автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.19, диссертация на тему:Статистические методы и средства оценки защищённости информации при использовании итеративных блочных шифров

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

Пестунов Андрей Игоревич

СТАТИСТИЧЕСКИЕ МЕТОДЫ И СРЕДСТВА ОЦЕНКИ ЗАЩИЩЁННОСТИ ИНФОРМАЦИИ ПРИ ИСПОЛЬЗОВАНИИ ИТЕРАТИВНЫХ БЛОЧНЫХ ШИФРОВ

05.13.19 — Методы и системы защиты информации, информационная безопасность

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

2 7::он т

Новосибирск 2013

005531005

Работа выполнена в федеральном государственном бюджетном учреждении науки Институте вычислительных технологий Сибирского отделения Российской академии наук (ИВТ СО РАН)

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

Осипов Александр Леонидович, кандидат технических наук, старший научный сотрудник, заведующий кафедрой прикладных информационных технологий Новосибирского государственного университета экономики и управления "НИНХ"

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

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

Токарева Наталья Николаевна, кандидат физико-математических наук, старший научный сотрудник лаборатории дискретного анализа Института математики им. С. Л. Соболева СО РАН

Ведущая организация: Федеральное государственное автономное

образовательное учреждение высшего профессионального образования "Сибирский федеральный университет" (СФУ), г. Красноярск

Защита состоится "21" июня 2013 г. в 10.35 на заседании диссертационного совета Д 212.267.22 на базе федерального государственного бюджетного образовательного учреждения высшего профессионального образования "Национальный исследовательский Томский государственный университет" по адресу: 634050, г.Томск, пр. Ленина, 36 (учебный корпус №2, ауд.212б).

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

Автореферат разослан "20" мая 2013 г.

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

диссертационного совета х/Ш* Тренькаев В. Н.

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

доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

Таким образом, теоретическое обоснование и применение статистических методов анализа блочных шифров, а также разработка и исследование эффективности статистических тестов имеет важное значение для оценки защи-

щённости информации, обеспечиваемой итеративными блочными шифрами. Несмотря на существующие российские и зарубежные стандарты на шифры, актуальность создания новых и совершенствования существующих блочных шифров по-прежнему высока. Это приводит к тому, что в последние годы активно проводятся международные проекты, направленные на их комплексный анализ и стандартизацию (AES, NESSIE, CRYPTREC).

Целью работы является разработка, теоретическое и экспериментальной обоснование и исследование эффективности статистических методов и средств оценки защищённости информации при использовании итеративных блочных шифров.

Для достижения этой цели были поставлены следующие задачи.

• Оценка защищённости информации, обеспечиваемой итеративными блочными шифрами, методом разностного анализа.

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

• Теоретическое и экспериментальное исследование эффективности статистических тестов и критериев.

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

Объектом исследований являются статистические модели и методы оценки защищённости информации итеративными блочными шифрами; статистические тесты и критерии.

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

Методы исследований. Аппарат математического анализа, теории вероятностей и математической статистики; методы статистического моделирования и регрессионного анализа; технологии программирования на языках С, С++ и Java.

Научная новизна

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

(а) Формализованы основные понятия данного метода и систематизированы связи между ними.

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

2. Методом разностного анализа проведена оценка защищённости информации кандидатами конкурса AES шифрами MARS и CAST-256.

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

(б) Получены оценки сложности разностной атаки в общем случае при различных параметрах итеративных блочных шифров.

3. Теоретически и экспериментально обоснована эффективность статистического теста "стопка книг".

(а) Теоретически доказано, что для одного класса альтернативных гипотез тест "стопка книг" позволяет достичь заданных значений ошибок первого и второго рода при размере выборки O(VS), где S — размер алфавита, которому принадлежат элементы выборки.

(б) Экспериментально показано, что для класса линейных конгруэнтных генераторов "стопка книг" эффективнее спектрального теста.

4. Проведено статистическое исследование защищённости информации итеративными блочными шифрами, заявленными на конкурс AES.

(а) Определены зависимости от числа раундов длин последовательностей псевдослучайных чисел (генерируемых этими шифрами), при которых тест "стопка книг" отличает их от равномерно распределённых случайных чисел.

(б) Найдено число раундов, при котором псевдослучайные числа, генерируемые рассматриваемыми шифрами, не отличаются от равномерно распредёленных случайных чисел.

Соответствие диссертации паспорту специальности. Диссертация соответствует п. 9 "Модели и методы оценки защищенности информации и информационной безопасности объекта" паспорта специальности 05.13.19.

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

Положения, выносимые на защиту.

1. Формализация основных понятий разностного метода и систематизация связей между ними.

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

3. Разностные характеристики шифров MARS и CAST-256; атаки на эти шифры, основанные на предложенных характеристиках; оценки сложности разностной атаки в зависимости от параметров блочных шифров.

4. Теоретическое и экспериментальное обоснование эффективности статистического теста "стопка книг".

5. Зависимости от числа раундов длин псевдослучайных последовательностей, генерируемых шифрами-кандидатами AES, при которых тест "стопка книг" отличает их от равномерно распределённых случайных чисел. Минимальное число раундов, при котором эти последовательности обладают удовлетворительными статистическими свойствами.

Практическая ценность. Разработан программный комплекс для статистического оценивания защищённости информации при использовании итеративных блочных шифров "СКАБШ-2012". Найдены зависимости статистических свойств блочных шифров от числа раундов, что может служить рекомендацией к применению шифров для генерации псевдослучайных чисел.

Основные результаты работы использовались при выполнении базовых проектов ИВТ СО РАН по приоритетным направлениям фундаментальных исследований РАН (Ж№ гос. регистрации 01.2007.07871 и 01.2010.61308) и внедрены в учебный процесс Новосибирского государственного университета экономики и управления (НГУЭУ) при подготовке студентов по специальности "Организация и технология защиты информации" и направлению "Информационная безопасность".

Исследования по теме диссертации поддержаны грантом Лаврен-тьевского конкурса молодежных проектов СО РАН (2010-2011 гг.), грантом № 11-07-09299 Российского фонда фундаментальных исследований по программе "Мобильность молодых ученых" (2011 г.), грантом Фонда содействия отечественной науке в номинации "Лучшие аспиранты РАН" (2006-2007 гг.), стипендией администрации Новосибирской области в сфере научной деятельности (2006 г.) и частично грантами Ж№ НШ-931.2008.9 и НШ-6068.2010.9 Президентской программы "Ведущие научные школы РФ" (рук. академик Ю.И. Шокин).

Апробация работы. Результаты диссертации докладывались и обсуждались на следующих конференциях и семинарах: VII Intern. Conf. on Intelligent Information Hiding and Multimedia Signal Processing, Dalian, China, 2011; XII Всеросс. научно-практ. конф. "Проблемы информационной безопасности государства, общества и личности", Томск- Барнаул-Белокуриха, 2010; IX Сибирская науч. школа-семинар с междунар. участием "Компьютерная безопасность и криптография" (Sibecrypt-IX), Тюмень, 2010; IEEE Region 8 Intern. Conf. on Computational Technologies in Electrical and Electronic Engineering (Sibircon-2008), Novosibirsk, 2008; Российско-Казахстанское совещание рабочей группы, Новосибирск, 2007; XI Intern. Symp. on Problems of Redundancy in Information and Control Systems, Saint Petersburg,

2007; Междунар. конф. "Вычислительные и информационные технологии в науке, технике и образовании", Павлодар, 2006; VII Всеросс. конф. молодых ученых по матем. моделированию и информационным технологиям, Красноярск, 2006 Междунар. школа-конф. по приоритет, направл. развития науки и техники с участием молодых ученых, аспирантов и студентов, Москва, 2006; конф. "Информационная безопасность" в рамках науч. сессии НГУЭУ в 2010-2013 гг.; семинары ИВТ СО РАН: "Информационные технологии" (рук.: академик Ю.И. Шокин, чл.-корр. A.M. Федотов, д.ф.-м.н. С.К. Голушко), "Информационно-вычислительные технологии" (рук.: академик Ю.И. Шокин, д.ф.-м.н. В.М. Ковеня), "Информационно-вычислительные технологии в задачах поддержки принятия решений" (рук.: академик Ю.И. Шокин, д.ф.-м.н. JI.B. Чубаров, д.ф.-м.н. М.П. Федорук); семинар каф. защиты информации и криптографии ТГУ (рук. д.т.н. Г.П. Агибалов), семинар "Криптография и криптоанализ" (рук. к.ф.-м.н. H.H. Токарева, ИМ СО РАН).

Публикации. По теме диссертации опубликовано 14 работ, в том числе 7 статей в журналах, рекомендованных ВАК, 4 работы в трудах международных конференций и 3 работы в тезисах конференций.

Личный вклад автора. Все результаты, выносимые на защиту, получены автором лично. В совместной работе [7] автор программно реализовал тест "стопка книг" и провел эксперименты по предложенной соавтором схеме.

Структура и объём работы. Диссертация включает введение, три главы, заключение и список литературы из 156 наименований. Основной текст работы, содержащий 32 таблицы и 11 рисунков, изложен на 124 страницах. Общий объём диссертации составляет 161 страницу.

Благодарность. Автор выражает глубокую благодарность директору Института вычислительных технологий СО РАН академику Ю.И. Шокину за постоянное внимание к работе и поддержку.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Глава 2 посвящена оценке защищённости информации, обеспечиваемой блочными шифрами, с использованием разностного метода анализа.

В §2.1 описаны проблемы в существующей терминологии разностного анализа итеративных блочных шифров и предложен набор определений, образующих строгую единообразную терминологию, согласованную с существу-

ющими понятиями. В качестве основных проблем отмечены отсутствие строгих общепринятых терминов и отсутствие точных соответствий между понятиями характеристики, дифференциала, усечённой характеристики и усечённого дифференциала. Такая ситуация не позволяет проводить какие-либо рассуждения, применимые сразу для всех этих объектов, но требует рассмотрения частных случаев. Предложенный набор определений решает обозначенные проблемы и формирует терминологию, в рамках которой дифференциал, усечённый дифференциал и характеристика при определённых условиях являются усечёнными характеристиками. Показано, как вычисляется вероятность объединения усечённых характеристик для марковских шифров с использованием уравнения Колмогорова-Чепмена по аналогии с тем, как это сделано в статье К. Лэй и Дж. Мэсси для характеристик.

В §2.2 теоретически исследована зависимость между весом Хэмминга разности и вероятностью её сохранения после арифметических операций по модулю 2". Результаты сформулированы в виде теорем и следствий. Пусть ЕВ, В и Ш — соответственно сложение, вычитание и умножение по модулю 28, © — операция Х(Ж, Ы{О, I}8 — равномерное распределение на множестве двоичных векторов длины 5, Я(-) — функция вычисления веса Хэмминга, Д1-Ч -(й — 1)-ый (старший) бит величины Д.

Теорема 2.1. Пусть X, 2 ~ Ы{О, I}8 и У = X Ш А, где Я(Д) = Л, 0</г<й-1и Д^11 = 0, тогда

р((х ш2)е(ушг) = д)= 2~н.

Утверждение 2.1. Пусть X, Я ~ Ы{ О,1}8иГ = 1шД, где Я( Д) = Л,'

1 < Н < в и Д[8_11 = 1, тогда

Р((Х Ш2)®(УШг)=Д)= 2~{-к-1).

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

(а) Пусть X, 2 ~ Ы{ 0,1}! и У = X ® Д, где Я(Д) = Л, 0<Л<а-1и

А[в-ц = 0) тогда Рцх вг)ф(увг) = д)= 2~к.

(б) Пусть Х,2 ~ и{ О, I}8 и У = X © Д, где Я(Д) = К, КНви д[.-1] = тогда р((х В2)®(УВг) = Д)= 2-^1

Утверждение 2.3. Пусть X, 2 ~ Ы{0,1}а и У = I ® 2™, тогда

(а) Р((Х Ш2)®(УШг)= 2т)= 1/2, если ш < я - 1,

(б) Р((Х В 2) © (У В 2) = 2т)= 1/2, если т < в - 1,

(в) Р((Х Ш 2) © (У Ш 2) = 2т)= 1, если ш = в - 1,

(г) Р((Х В 2) Ф (У В = 2т)= 1, если т = а- 1.

Теорема 2.2 Пусть I, У, 2 6 {О, I}8 и X ф У = 28"1, причём младший бит ^ равен 1, тогда

{X И 2) © (У 11 2) = 28"1.

Все теоретические результаты подтверждены экспериментально, далее они используются при анализе защищённости информации шифрами MARS и CAST-256 разностным методом.

В §2.3 анализируется 32-раундовый шифр MARS, который имеет 256-битовый секретный ключ и состоит из "пред-отбеливания", "пост-отбеливания", 16 core раундов и 16 mixing раундов. Развёрнутый ключ шифра состоит из 40 ключей раундов и имеет длину 1248 бит. В диссертации предложена разностная характеристика для 8 backward core раундов, которая выглядит следующим образом:

(ОДО)218) "пред-о^ел." + 3 раунда ^q^q) ¿Р^ (29,?,?,231) ^

(?, ?, ?, 222) =(0,0,0,222) ^^ (222t о, о, 0). (1)

Вероятность этой характеристики составляет 2-98.

На основе предложенной характеристики разработана атака, направленная на нахождение ключей раундов у шифра MARS, состоящего из "пред-" и "пост-отбеливаний", 8 backward core раундов и 8 backward mixing раундов. Обозначим такой вариант шифра через MARS16 и заметим, что его развёрнутый ключ имеет длину 752 бита, в то время как наиболее эффективная из существующих атак направлена на вариант шифра MARS с развёрнутым ключом длиной 682 бита (см. табл. 1). Значит, предложенная атака является более эффективной, чем существующие. В данном случае эффективность атаки определяется не числом раундов шифра, а количеством вычисленных битов ключа, поскольку раунды шифра MARS не являются равноправными в том смысле, что mixing раунды не зависят от ключа.

Разработанная атака состоит из двух этапов: вычисление ключей "постотбеливания" и вычисление оставшихся ключей (для соге-раундов и "пред-отбеливания"). Рассмотрим четыре 32-битовых ключа "пост-отбеливания" как один 128-битовый, тогда атака, направленная на его нахождение будет иметь следующий вид.

Шаг 1. Сформировать 6 групп, состоящих из 2101 различных пар блоков с разностью (0,0,0,218); обозначим эти пары блоков через (Af, Bf), гДе 9 = 1)6, t = 1,2й»1.

Таблица 1: Лучшие атаки на шифр MARS

Биты Раунды "Отбеливания" Сложность

клю- Всего Core Mixing Пред- Пост- Блоки Память Шифро- Источ-

чей (в бантах) вания ник

566 21 5 16 + + 23 2236 2232 Д. Келси и др.

566 21 5 16 + + 250 2197 2247 -1-

628 12 6 6 + + 269 2 73 2197 -1-

682 11 11 0 - - 265 269 2229 -1-

752 16 8 8 + + 2104,6 2108,6 2231,6 §2.3

Шаг 2. Для каждой пары (Af, Bf) запросить пару шифрованных блоков X9t = MARS16(A®) и У/ = MARS16(Bf); полученные 6 • 2101 пар шифрованных блоков сохранить в памяти.

Шаг 3. Перебрать все возможные значения вычисляемого ключа (обозначим его через к), к = О, 2128 — 1, и для каждого из возможных значений выполнить следующие действия:

(а) g := 1;

(б) сохранённые пары шифрованных блоков из группы g расшифровать на "пост-отбеливание" с ключом А; и на 8 backward mixing раундов; обозначим полученные пары через Р[' и Q'[]

(в) если Pt9 ® Q\ ф (0,0,0,222) для всех t = 1,2101, то к — ложный ключ-кандидат; отбросить его и перейти на шаг (3), где выбрать следующий ключ-кандидат;

если Ff ® Qf = (0,0,0,222) выполняется хотя бы для одной из пар, то перейти на шаг (г);

(г) если g < 6, то g := g + 1 и перейти на шаг (б); иначе к — это истинный ключ.

Для реализации разработанной атаки требуется 2104,6 выбранных открытых текстов, 2108'6 байт памяти и 2231,6 операций шифрования, что является быстрее полного опробования 256-битовых ключей. Вероятность успеха атаки (вероятность вычислить истинный ключ) составляет приблизительно 99%.

В §2.4 исследована защищённость информации при использовании шифра CAST-256. Предложена следующая разностная характеристика для 18 раундов этого шифра:

/ о п гл 2 РаУВДа /п n а \ 1 РаУД, t n n гЛ 15 РаУпДов. /-о п о „ \

(р, а, 0,0)-> (0,0, Р, а)-> {а, 0,0,0)-> (?, ?, ?, а),

где а = 29jf<n, /3 = 60Л40Х, индекс х означает запись числа в шестнадцате-ричном виде, п выбрано случайно из множества {0,1,... ,31}, a t/<<n — циклический сдвиг влево величины у на n бит. Согласно полученной оценке вероятность этой характеристики составляет 2~17.

На основе предложенной характеристики разработана атака на CAST-256, состоящий из 24-х раундов. Схема атаки аналогична схеме атаки на MARS. Вычислительная сложность атаки на CAST-256 составляет приблизительно 225'2 выбранных открытых текстов, 229'2 байт памяти и 2245,2 операций шифрования. Это меньше сложности полного опробования 256-битовых ключей. Вероятность успеха атаки приблизительно равна 99%.

На шифр CAST-256 опубликованы две атаки (см. табл. 2): первая вычисляет ключ шифра, состоящего из 16 раундов, а вторая — для шифра, имеющего до 36 раундов, но только для одного класса слабых ключей. В частности, к 24-раундовому CAST-256 атака применима только для 2~30 части всех

Таблица 2: Лучшие атаки на шифр CAST-256

Кол-во Сложность атаки Число Источ-

атакованных Кол-во Память Кол-во ключей ник

раундов блоков (в байтах) шифрований

16 249,3 не указано не указано Все Д. Вагпер

24 по указано пе указано не указано 2-25 часть X. Секи и др.

36 2123 не указано 2юо 2-35 часть X. Секи и др.

24 225,2 229,2 2245,2 Все §2.4

ключей. Разработанная в диссертации атака применима ко всем ключам, следовательно, она более эффективна для 24 раундов шифра CAST-256.

Проведена экспериментальная проверка предложенных характеристик и разработанных атак на MARS и CAST-256 посредством их моделирования на ЭВМ. В §2.6 атака описана в общем виде, и рассчитана её сложность в зависимости от параметров шифра для достижения вероятности успеха 99%.

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

Пусть некоторый источник порождает буквы из алфавита^ = {ai,..., as}, и дана выборка X = (xi,..., ггдг) из этого алфавита. Тест "стопка книг" является критерием согласия с гипотезой Но о том, что элементы выборки имеют равномерное распределение, т. е.

Р{хп = <ц) = 1/5, п = 1, АГ, ¿ = 1,5.

При использовании теста "стопка книг" в алфавите А фиксируется некоторый произвольный порядок, который меняется после анализа каждого выборочного элемента хп следующим образом: буква а; = хп получает первый номер, номера тех букв, которые были меньше её номера, инкрементируются, а у остальных букв номера сохраняются. Формально эта процедура выглядит так: пусть сип(а) — номер буквы а после анализа элементов Х\, х2, ..., хп, и начальный порядок сУ'(-) на буквах А задан произвольно, тогда после анализа элемента хп+\ буквы получат следующие номера:

U1'

1, если а = xn+i;

шп(а) + 1, если шп(а) < wn(xn+1); (2)

uin(a), если шп(а) > и>"(хп+1).

Перед тестированием множество номеров {1,..., 5} разбивается на I > 1 частей

А1 = { 1, 2, ..., Ki}, А2={Кi + l, KI+2, ..., Х2}, Ai = {Kt_i + 1, 1 + 2, ..., Кг = S}.

Для этих подмножеств по выборке Х2,... ,£лг) подсчитываются числа г^-, ] = 1,1, каждое из которых означает, сколько номеровшп(хп+1) принадлежит

подмножеству А^. Далее вычисляется статистика

= £ Где ^ = (3)

3=1 3

и тест записывается в следующем виде:

если X1 < Х1-1;а,

К = < „

иначе.

(4)

В §3.2 эффективность статистического теста "стопка книг" обоснована теоретически при I = 2, т.е. множество номеров букв разбивается на две части размеров К и Б — К соответственно.

Для упрощения выкладок сформируем начальный порядок номеров не произвольно, а специальным образом на основе подготовительной выборки. Такая модификация позволит упростить выкладки, не меняя их сути. Вначале зафиксируем произвольный порядок, а затем обработаем подготовительную выборку, состоящую из К элементов, переупорядочивая номера букв согласно правилам (2). Выборку, по которой производится подсчёт величины и, назовём контрольной. _

Рассмотрим некоторую перестановку индексов а{€), £ — 1,5 и соответствующую ей простую гипотезу Я^ с параметрами 7 е (0,1/2] и (5 € (0,1); она заключается в том, что

Рг = Р(х„ = =

1/5(1+5), если г = 1, ...,75; 1/5(1 — 6), если г = 75 + 1, ..., 275; 1/5, если г = 275 + 1, ..., 5.

Подобные варианты альтернативной гипотезы приведены в ряде источников (Б. Я. Рябко и др., М. Кендалл и А. Стьюарт). Параметр7 определяет долю букв, вероятность которых отлична от 1/5, а параметр <5 — величину отклонения этой вероятности. Гипотеза говорит о том, что вероятности появления некоторых букв равны 1/5, а остальные либо больше этого значения, либо меньше, причём на одинаковую величину и таких значений поровну.

Теперь определим сложную гипотезу %7,<5 как множество со все-

возможными перестановками (всего их 5!). Эта гипотеза говорит о том, что параметры 5 и 7 известны, но неизвестно, каким буквам какие вероятности соответствуют. Вместо сложной гипотезы возьмём её сужение 7Р'6 и критерий (4) преобразуем к виду

если х2 < XI; 1-<»;

тг =

иначе.

Основным теоретическим результатом является следующая

Теорема. Для любых а и /3 из интервала (0,1) существует константа С = С{а, /3;7, > 0 такая, что при К = \fS и при размере контрольной выборки N = С ■ К ошибки первого и второго рода критерия тт асимптотически при S —» сю не превосходят а* и ¡3 соответственно, где а* « а с точностью, удовлетворительной для практических целей.

Таким образом, тест "стопка книг" в некотором смысле предлагает группировку для критерия хи-квадрат, которая позволяет (согласно доказанной теореме) в случае рассмотренной альтернативной гипотезы использовать для тестирования выборку размера 0(y/S).

В §3.3 эффективность теста "стопка книг" обоснована экспериментально для класса мультипликативных линейных конгруэнтных генераторов (МЛКГ), которые успешно прошли спектральный тест (работа P. L'Ecuyer), являющийся одним из наиболее эффективных критериев и, как отмечает Д. Кнут, хорошо подходит для тестирования генераторов именно этого типа. МЛКГ генерирует псевдослучайные числа согласно следующей формуле:

Xi+i = а • Xi mod т.,

где xq, а и т — целочисленные константы, являющиеся параметрами МЛКГ. МЛКГ предназначен для получения целых чисел, равномерно распределённых на множестве {0,..., т—1}. В ряде источников отмечается, что младшие знаки таких чисел могут иметь неудовлетворительные статистические свойства, поэтому существует рекомендация использовать только старшие знаки. Согласно этой рекомендации выделяется старший бит или старший байт; в дальнейшем эти режимы обозначены и R$ соответственно.

При проведении экспериментов последовательность полученных таким образом псевдослучайных бит разбивалась на блоки длины s и при тестировании рассматривалась как выборка из алфавита размера 2s. Множество номеров в "стопке книг" разбивалось на две или на три части. Каждый генератор тестировался в режиме Ri при разных размерах выборок; если удавалось найти размер выборки, при котором тест "стопка книг" отличал генерируемые числа от равномерно распределённых, то все вычисления повторялись при этой длине по другим 100 ранее не задействованным выборкам. При этом вычислялись величины Ua, равные количеству тех выборок, на которых критерий (4) отвергал гипотезу Но при уровне значимости а. Если отклонения определить не удавалось, то вычисления повторялись в режиме R&.

В табл. 3 отражены результаты экспериментов, где № — это номер генератора, R — режим тестирования, а и т — параметры генератора, s — длина блока, N — размер выборки в словах, N ■ s — размер выборки в битах, К и L — соответственно размеры частей Ai и А2.

Непосредственным вычислением установлено, что, если 6одг, > 12 или Uo,5 > 73, то с вероятностью 99,9% распределение элементов тестируемых

Таблица 3: Результаты тестирования линейных конгруэнтных генераторов

№ я тп а я N дг-в К Ь 5 ^0,05

1 1 28 — 5 33 8 70 560 23 25 72 0

2 1 29 — 3 35 8 70 560 23 25 100 0

3 1 210 - 3 65 8 100 800 23 25 95 4

4 1 211 - 9 995 8 500 4000 25 27 73 18

5 1 212 - 3 209 8 200 1600 25 27 71 21

6 1 213_ 1 884 8 1000 8000 25 27 71 13

7 1 2и_ 3 572 16 1500 12000 2ю 2й 85 3

8 1 215 _ 19 219 16 2000 32000 213 213 80 26

9 1 21б_ 15 17364 16 2000 32000 29 214 71 9

10 1 217 - 1 43165 16 4000 60000 212 214 72 21

11 1 218 — 5 92717 16 4000 64000 211 213 70 9

12 1 219_ 1 283741 24 25000 600000 213 - 80 18

13 1 220 _ 3 380985 24 30000 720000 213 - 71 23

14 1 221 - 9 360889 24 200000 4800000 217 - 80 24

15 1 222 _ 3 914334 24 100000 2400000 213 - 79 14

16 1 223 - 15 653276 24 150000 3600000 213 - 67 24

17 8 224 - 3 6423135 24 25000 600000 214 - 90 30

18 8 225 — 39 25907312 24 35000 840000 214 - 72 14

19 8 226 - 5 26590841 24 45000 1080000 214 - 66 13

20 8 227 — 39 45576512 24 80000 1520000 215 - 66 16

21 8 228 - 57 246049789 24 200000 4800000 217 - 84 29

22 8 22Э_ 3 520332806 24 300000 7200000 217 - 66 13

выборок не является равномерным. Табл. 3 показывает, что для всех генераторов найдены параметры, при которых одно из этих условий выполняется, следовательно, тест "стопка книг" определяет отклонения от равномерного распределения для рассмотренных генераторов, а спектральный тест — нет.

Корректность реализации теста "стопка книг" проведена посредством тестирования генераторов, классифицированных Д. Кнутом как "удовлетворительные", "находящиеся на грани" и "неудовлетворительные". Результаты их анализа тестом "стопка книг" согласуются с данной классификацией: "удовлетворительные" генераторы прошли тестирование успешно, а "находящиеся на грани" и "неудовлетворительные" — нет, причём у "неудовлетворительных" генераторов отклонения фиксировались на выборках меньшей длины, чем у "находящихся на грани".

В §3.4 при помощи теста "стопка книг" проведён статистический анализ защищённости информации при использовании блочных шифров, заявленных на конкурс ЛЕЯ.

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

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

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

Опишем метод генерации псевдослучайных бит с помощью блочного шифра и схему экспериментов. Представим 128-битовый блок в виде четырех 32-битовых подблоков, занумерованных 0, 1, 2, 3 от старшего к младшему. Рассмотрим последовательность блоков X", и £ {0,1,2,3}, у которых подблок с номером и равен г, а остальные — нулевые, г пробегает значения 0,1,..., N - 1. Например, = (7,0,0, 0), а Xf = (0,0,0,5). Обозначим через у"'" 32-битовый подблок зашифрованного блока Xf с номером v. Например, зашифровав X®, получаем блок у®'1, у®'2, У?'3)- Любую часть такого

блока можно взять в качестве псевдослучайного числа.

Экспериментальный анализ состоит из двух этапов: подбор подходящих параметров и тестирование. Цель первого этапа — определить параметры и, V, s, К и N, при которых тест "стопка книг" отличает генерируемую последовательность от последовательности равномерно распределенных случайных чисел. Здесь s — размер слова, К — размер верхней части "стопки книг", N — длина последовательности. На втором этапе с помощью 100 случайных ключей генерируются 100 последовательностей с выбранными на первом этапе параметрами. Для каждой из последовательностей вычисляются значения х2 согласно формуле (3), и подсчитываете« величина Un,m, означающая, сколько раз из 100 значения х2 превысили квантиль распределения хи-квадрат уровня 0,01. Если распределение шифртекста для всех 100 ключей является равномерным, то £/o,oi в среднем равно единице, и непосредственным вычислением показано, что, если ÏTo.oi > 4, то с вероятностью более 99,9% распределение шифртекста — не равномерное.

Рассмотрим 32-раундовый шифр MARS, состоящий из 8 раундов четырёх типов: forward core, backward core, forward mixing и backward mixing раунды. При его анализе рассматриваются следующие варианты: раунды одного типа или одинаковое число раундов каждого типа. В табл. 4 показаны результаты экспериментов, откуда видно, что C/o,oi значительно больше 4, поэтому на основании приведённых выкладок можно сделать вывод о том, что распределение шифртекста не является равномерным с вероятностью более 99,9%.

Статистический анализ защищённости информации шифрами FROG и LOKI97 проведён по той же схеме. При использовании шифра FROG наибольшие отклонения от равномерного распределения достигаются при и = 2 и V = 2 (см. табл.5), а при использовании шифра LOKI97 параметры и и V равны соответственно 1 и 2 для всех раундов кроме восьмого, а для него -« = 0и1) = 3 (см. табл.6). Для этих двух шифров величина C/q.oi также

Таблица 4: Результаты статистического анализа шифра MARS

г N Uo,m К s г N С/о,01 К s

Forward mixing и = 3, v = 2 Backward mixing и = 3, v = 1

2 26 100 26 8 4 26 100 2® 8 6 214 67 214 24 8 218 43 218 32 2 26 100 26 8 4 26 100 26 8 6 2 8 9 9 26 8 8 214 25 218 24

Forward core и = 3, v = 3 Backward core и = 3, v = 0

1 2e 100 2s 8 3 26 100 2e 8 5 220 17 218 32 1 26 100 26 8 3 2е 100 26 8 5 26 100 2е 8

Всех раупдов поровну и = 3,v = 0

1+1+1+1 2® 100 26 8 || 2+2+2+2 218 29 218 32

значительно превосходила 4. Результаты анализа защищённости при использовании остальных 12 участников конкурса AES приведены в табл. 7.

Таблица 5: Результаты статистического анализа шифра FROG

г N Uo,oi Я" s г N Uo,01 Я" S

1 29 100 28 16 3 222 20 218 32

2 213 22 210 16 4 232 17 220 32

Таблица 6: Результаты статистического анализа шифра LOKI97

г лг к s г JV СЛ),01 К s

1 23 100 23 6 5 218 52 216 32

2 25 100 23 6 6 219 66 2i6 32

3 28 100 2е 8 7 22Т 31 218 32

4 212 100 2ю 16 8 231 22 220 32

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

Даны точки (г\,Г2,.. ■, гд>) и соответствующие им значения (/i, /2, • • •, /л*)-Требуется построить полиномиальную функцию вида

/(г) = Ьо + bir + b2r2 + ... + bmrm,

Таблица 7: Результаты статистического анализа шифров-кандидатов AES

Шифр г R N C^o.oi К s и u

Е2 3 12 320 100 218 32 1 0

Dfc 3 8 220 100 218 32 0 1

CAST-256 2 12 218 68 218 32 0 1

Rijndael 2 10,12,14 218 40 218 32 2 2

Crypton 3 12 25 100 25 8 0 1

Serpent 3 32 231 31 220 32 0 3

safer+ 2 8,12,16 2 30 77 220 32 1 2

Deal 2 6,8,8 2e 100 25 8 2 2

Magenta 2 6,6,8 26 100 2s 8 0 1

Hpc 1 8 210 100 210 16 2 2

Rc6 4 20 227 47 220 32 0 2

Twofish 3 16 220 52 218 32 2 0

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

f{r) = Ъ0 + Ь\Г + b2r2.

При вычислении неизвестных коэффициентов bo, Ь\ и Ь2 методом наименьших квадратов решается система так называемых нормальных уравнений:

' R* Л* Л*

= b0(R* + 1) + h + b2 £rf,

¿=0 i=0 ¿=0

R* Я* R' Л*

г=0 ¿=0 г=0 г=0

Ii* R* R* R*

. i=0 i=0 ¿=0 i=0

Система линейна относительно искомых коэффициентов, поэтому может быть решена методом Гаусса.

Для шифров LOKI97 и FROG зависимость величины 1од2М от числа раундов, приведённая в табл. 6, почти линейная, поэтому её разумно приблизить квадратичной функцией

log2N(r) = b2r2 + b\r + b0

и с помощью метода наименьших квадратов найти коэффициенты bo, 61 и 62-Для шифра FROG указанная зависимость имеет вид

log2N(r) = 0,5 г2 + 5,7 г + 0,8, 17

а для шифра ШК197 - 1од2Й{г) = 0,2г2 + 2,5г - 0,3.

В табл. 8 и 9 показаны численные значения полученных функций.

Таблица 8: Прогноз для шифра FROG

Эксперименты Прогноз

п Ni 0 12 3 4 20 29 213 222 232 5 6 7 8 2<i2 253 265 278

Таблица 9: Прогноз для шифра LOKI97

Эксперименты Прогноз

П Ni 012345678 2° 23 25 28 212 218 219 227 231 10 12 14 16 243 266 270 286

В §3.5 описан программный комплекс для статистического оценивания защищённости информации при использовании итеративных блочных шифров "СКАБШ-2012", включающий программу, моделирующую атаки на MARS и CAST-256; тест "стопка книг" и его применение к анализу защищённости информации блочными шифрами; метод наименьших квадратов; расчёт сложности разностной атаки в зависимости от параметров шифра. Исходный код программного комплекса приведён в приложении. В заключении сформулированы результаты диссертационной работы.

1. Формализованы основные понятия разностного метода анализа итеративных блочных шифров, и систематизированы связи между ними.

2. Теоретически определено влияние (найдена зависимость) веса Хэммин-га разности двух величин на вероятность её сохранения после арифметических операций по модулю 2S.

3. Методом разностного анализа проведена оценка защищённости информации при использовании блочных шифров MARS и CAST-256. Предложены разностные характеристики, позволившие разработать атаки на эти шифры, являющиеся эффективнее существующих.

4. Теоретически и экспериментально обоснована эффективность статистического теста "стопка книг" для одного класса альтернативных гипотез и одного класса генераторов псевдослучайных чисел.

5. Статистически исследована защищённость информации, обеспечивае-

мая итеративными блочными шифрами кандидатами конкурса AES.

Определены зависимости их статистических свойств от числа раундов.

Для каждого шифра найдено минимальное число раундов, при котором

он обладает удовлетворительными статистическими свойствами.

6. Разработан программный комплекс "СКАБШ-2012", предназначенный для статистического оценивания защищённости информации при использовании итеративных блочных шифров, включающий в себя следующие основные части: моделирование атак на шифры MARS и CAST-256, расчёт характеристик S-блоков шифра MARS, реализацию статистического теста "стопка книг" и его применение к статистическому анализу итеративных блочных шифров.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

В журналах, рекомендованных ВАК:

[1] Пестунов А. И. О вероятности протяжки однобитовой разности через сложение и вычитание по модулю // Прикладная дискретная математика. - 2012. - № 4. - С. 53-60.

[2] Пестунов А. И. Дифференциальный криптоанализ блочного шифра CAST-256 // Безопасность информационных технологий. — 2009. — № 4. - С. 57-62.

[3] Пестунов А. И. Дифференциальный криптоанализ блочного шифра MARS // Прикладная дискретная математика. — 2009. - № 4 (6). -С. 56-63.

[4] Пестунов А. И. Статистический анализ современных блочных шифров // Вычислительные технологии. — 2007. - Т. 12, № 2. - С. 122-129.

[5] Пестунов А. И. Блочные шифры и их криптоанализ // Вычислительные технологии. — 2007. — Т. 12, спец. вып. № 4. — С. 42-49.

[6] Пестунов А. И. Теоретические исследования статистического теста "Стопка книг" // Вычислительные технологии. — 2006. — Т. 11, № 6. — С. 96-103.

[7] Рябко Б. Я., Пестунов А. И. "Стопка книг" как новый статистический тест для случайных чисел // Проблемы передачи информации. — 2004. — Т. 40, № 1. - С. 73-78.

В трудах международных конференций:

[8] Pestunov А. Differential cryptanalysis of 24-round CAST-256 // Proc. IEEE Region 8 International Conf. on Computational Technologies in Electrical and Electronic Engineering (Sibircon-2008). — Novosibirsk. — 2008. — P. 46-49.

[9] Pestunov A. Differential Cryptanalysis of Reduced-Round MARS // Proc. XI International Symposium on Problems of Redundancy in Information and Control Systems. — Saint Petersburg. — 2007. — P. 197-201.

[10] Пестунов А. И. Асимптотические свойства статистического теста "Стопка книг" // Тр. междунар. конф. "Вычислительные и информационные технологии в науке, технике и образовании". — Павлодар. — 2006. — Т. 2. - С. 110-117.

[11] Пестунов А. И. Статистический анализ блочного шифра MARS // Тр. междунар. конф. "Вычисл. и информационные технологии в науке, технике и образовании". — Павлодар. — 2006. — Т. 2. — С. 118-123.

В тезисах конференций:

[12] Пестунов А. И. Оценки сложности дифференциальной атаки при различных параметрах блочного шифра // Тез. докл. IX сибирской науч. школы-семинара с междунар. участием "Компьютерная безопасность и криптография" (Sibecrypt-Ю). - Тюмень: ТюмГУ. - 2010. - С. 25-27.

[13] Пестунов А. И. Новые статистические атаки на блочные и потоковые шифры // Тез. докл. междунар. школы-конф. по приоритетным направлениям развития науки и техники с участием молодых ученых, аспирантов и студентов. — Москва: РГУИТП. — 2006. — С. 58-60.

[14] Пестунов А. И. Градиентная статистическая атака на блочный шифр FEAL // Тез. докл. VII всеросс. конф. молодых ученых по матем. моделированию и информ. технологиям. — Красноярск: ИВМ СО РАН. — 2006. - С. 91-92.

СВИДЕТЕЛЬСТВО О РЕГИСТРАЦИИ ПРОГРАММЫ ДЛЯ ЭВМ

[15] Пестунов А. И. Программный комплекс для статистического оценивания защищённости информации при использовании итеративных блочных шифров "СКАБШ-2012" // Свид. о гос. регистрации программы для ЭВМ. — Федеральная служба по интеллектуальной собственности, патентам и товарным знакам. — 12.02.2013.

Подписано в печать 17.05.2013 г. Формат 60x84 1/16. Гарнитура Times. Тираж 100 экз. Усл. печ. л. 1,25.

Новосибирский государственный университет экономики и управления "НИНХ" 630099, г. Новосибирск, ул. Каменская, 56

Федеральное государственное бюджетное учреждение науки Институт вычислительных технологий Сибирского отделения Российской академии наук (ИВТ СО РАН)

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

04201360702

Пестунов Андрей Игоревич

СТАТИСТИЧЕСКИЕ МЕТОДЫ И СРЕДСТВА ОЦЕНКИ ЗАЩИЩЁННОСТИ ИНФОРМАЦИИ ПРИ ИСПОЛЬЗОВАНИИ ИТЕРАТИВНЫХ БЛОЧНЫХ ШИФРОВ

Диссертация на соискание учёной степени кандидата физико-математических наук по специальности 05.13.19 — Методы и системы защиты информации, информационная безопасность

Научный руководитель: кандидат технических наук, старший научный сотрудник Осипов Александр Леонидович

Новосибирск — 2013

а

Оглавление

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

Глава 1. Итеративные блочные шифры и методы оценки защищённости информации при их использовании .........12

1.1. Итеративные блочные шифры и их структура..........12

1.2. Подходы к оценке защищённости информации при использовании блочных шифров........................17

1.3. Актуальные проблемы и постановка

задач диссертации..........................26

Глава 2. Оценка защищённости информации итеративными блочными шифрами разностным методом...............36

2.1. О строгой единообразной терминологии разностного метода . . 36

2.2. Теоретическое исследование влияния веса Хэмминга разности двух величин на вероятность её сохранения после арифметических операций............................44

2.3. Разработка атаки на блочный шифр MARS ...........55

2.4. Разработка атаки на блочный шифр CAST-256 ..................67

2.5. Анализ разработанных атак и их сравнение с существующими . 73

2.6. Оценка сложности разностной атаки в зависимости от параметров итеративного блочного шифра ..............81

Глава 3. Статистическое оценивание защищённости информации блочными шифрами при помощи теста "стопка книг" . . 85

3.1. Базовые определения и описание теста..............85

3.2. Теоретическое обоснование эффективности теста "стопка книг" 89

3.3. Экспериментальное обоснование эффективности теста.....101

3.4. Статистический анализ защищённости информации при использовании итеративных блочных шифров..............106

3.5. Описание программного комплекса для статистического оценивания защищённости информации при использовании итеративных блочных шифров "СКАБШ-2012"...........117

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

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

Приложение А. Исходный код программного комплекса

"СКАБШ-2012".............................142

А.1. Расчёт характеристик S-блока шифра MARS...........142

А.2. Программа для проверки разностных характеристик шифров

MARS и CAST-256 ......................... 146

А.З. Моделирование атаки на блочный шифр CAST-256 ....... 147

А.4. Реализация статистического теста "стопка книг".........149

А.5. Программа для статистического анализа защищённости информации блочными шифрами с помощью теста "стопка книг" . . .153

А.6. Построение прогноза методом наименьших квадратов .....156

А.7. Оценка сложности разностной атаки в зависимости от параметров блочного шифра.......................159

Введение

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

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

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

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

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

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

Таким образом, теоретическое обоснование и применение статистических методов анализа блочных шифров, а также разработка и исследование эффективности статистических тестов имеет важное значение для оценки защищённости информации, обеспечиваемой итеративными блочными шифрами. Несмотря на существующие российские и зарубежные стандарты на шифры, актуальность создания новых и совершенствования существующих блочных шифров по-прежнему высока. Это приводит к тому, что в последние годы активно проводятся международные проекты, направленные на их комплексный анализ и стандартизацию (АЕБ, КЕЗБШ, СЮТТЯЕС).

Целью работы является разработка, теоретическое и экспериментальной обоснование и исследование эффективности статистических методов и средств оценки защищённости информации при использовании итеративных блочных шифров.

Для достижения этой цели были поставлены следующие задачи.

• Оценка защищённости информации, обеспечиваемой итеративными блочными шифрами, методом разностного анализа.

• Теоретическое обоснование метода разностного анализа и разработка его строгой единообразной терминологии.

• Теоретическое и экспериментальное исследование эффективности статистических тестов и критериев.

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

Объектом исследований являются статистические модели и методы оценки защищённости информации итеративными блочными шифрами; статистические тесты и критерии.

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

Методы исследований. Аппарат математического анализа, теории вероятностей и математической статистики; методы статистического моделирования и регрессионного анализа; технологии программирования на языках С, С++ и Java.

Научная новизна

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

(а) Предложен набор определений, позволивший формализовать связи и соотношения между основными понятиями этого метода.

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

2. Методом разностного анализа проведена оценка защищённости информации кандидатами конкурса AES шифрами MARS и CAST-256.

(а) Предложены разностные характеристики этих шифров и получены оценки их вероятностей, на основании чего разработаны атаки на

данные шифры, являющиеся эффективнее существующих.

(б) Получены оценки сложности разностной атаки в общем случае при различных параметрах итеративных блочных шифров.

3. Теоретически и экспериментально обоснована эффективность статистического теста "стопка книг".

(а) Теоретически доказано, что для одного класса альтернативных гипотез тест "стопка книг" позволяет достичь заданных значений ошибок первого и второго рода при размере выборки О (у/Б), где 5 — размер алфавита, которому принадлежат элементы выборки.

(б) Экспериментально показано, что для класса линейных конгруэнтных генераторов "стопка книг" эффективнее спектрального теста.

4. Проведено статистическое исследование защищённости информации итеративными блочными шифрами, заявленными на конкурс АЕБ.

(а) Определены зависимости от числа раундов длин последовательностей псевдослучайных чисел, генерируемых рассматриваемыми шифрами, при которых тест "стопка книг" отличает их от равномерно распределённых случайных чисел.

(б) Найдено число раундов, при котором псевдослучайные числа, генерируемых рассматриваемыми шифрами, не отличаются от равномерно распредёленных случайных чисел.

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

Положения, выносимые на защиту.

1. Набор определений, образующих строгую единообразную терминологию разностного метода, согласованную с существующими понятиями.

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

3. Разностные характеристики шифров MARS и CAST-256; атаки на эти шифры, основанные на предложенных характеристиках; оценки сложности разностной атаки в зависимости от параметров блочных шифров.

4. Теоретическое и экспериментальное обоснование эффективности статистического теста "стопка книг".

5. Зависимости от числа раундов длин псевдослучайных последовательностей, генерируемых шифрами-кандидатами AES, когда тест "стопка книг" отличает их от равномерно распределённых случайных чисел. Минимальное число раундов, при котором эти последовательности обладают удовлетворительными статистическими свойствами.

Практическая ценность. Разработан программный комплекс для статистического оценивания защищённости информации при использовании итеративных блочных шифров "СКАБШ-2012". Найдены зависимости статистических свойств блочных шифров от числа раундов, что может служить рекомендацией к применению шифров для генерации псевдослучайных чисел.

Основные результаты работы использовались при выполнении базовых проектов МВТ СО РАН по приоритетным направлениям фундаментальных исследований РАН гос. регистрации 01.2007.07871 и 01.2010.61308) и внедрены в учебный процесс НГУЭУ при подготовке студентов по специальности "Организация и технология защиты информации" и направлению "Информационная безопасность".

Исследования по теме диссертации поддержаны грантом Лаврен-тьевского конкурса молодежных проектов СО РАН (2010-2011 гг.), грантом № 11-07-09299 Российского фонда фундаментальных исследований "Мобильность молодых ученых" (2011 г.), грантом Фонда содействия отечественной

науке в номинации "Лучшие аспиранты РАН" (2006-2007 гг.), стипендией администрации Новосибирской области в сфере научной деятельности (2006 г.) и частично грантами Ж№ НШ-931.2008.9 и НШ-6068.2010.9 Президентской программы "Ведущие научные школы РФ" (рук. академик Ю.И. Шокин).

Апробация работы. Результаты диссертации докладывались на следующих конференциях и семинарах: VII Intern. Conf. on Intelligent Information Hiding and Multimedia Signal Processing, Dalian, China, 2011; XII Всеросс. научно-практ. конф. "Проблемы информационной безопасности государства, общества и личности", Томск- Барнаул-Белокуриха, 2010; IX Сибирская науч. школа-семинар с междунар. участием "Компьютерная безопасность и криптография" (Sibecrypt-IX), Тюмень, 2010; IEEE Region 8 Intern. Conf. on Computational Technologies in Electrical and Electronic Engineering (Sibircon-2008), Novosibirsk, 2008; Российско-Казахстанское совещание рабочей группы, Новосибирск, 2007; XI Intern. Symp. on Problems of Redundancy in Information and Control Systems, Saint Petersburg, 2007; Междунар. конф. "Вычислительные и информационные технологии в науке, технике и образовании", Павлодар, 2006; VII Всеросс. конф. молодых ученых по матем. моделированию и информационным технологиям, Красноярск, 2006 Междунар. школа-конф. по приоритет, направл. развития науки и техники с участием молодых ученых, аспирантов и студентов, Москва, 2006; конф. "Информационная безопасность" в рамках науч. сессии НГУЭУ в 2010-2013 гг.; семинары ИВТ СО РАН: "Информационные технологии" (рук.: академик Ю.И. Шокин, чл.-корр. А.М. Федотов, д.ф.-м.н. С.К. Голушко), "Информационно-вычислительные технологии" (рук.: академик Ю.И. Шокин, д.ф.-м.н. В.М. Ковеня), "Информационно-вычислительные технологии в задачах поддержки принятия решений" (рук.: академик Ю.И. Шокин, д.ф.-м.н. Л.Б. Чубаров, д.ф.-м.н. М.П. Федорук); семинар каф. защиты информации и криптографии ТГУ (рук. д.т.н. Г.П. Агибалов), семинар "Криптография и криптоанализ" (рук. к.ф.-м.н. H.H. Токарева, ИМ СО РАН).

Публикации. По теме диссертации опубликовано 14 работ, в том числе 7 статей в журналах, рекомендованных ВАК, 4 работы в трудах международных конференций и 3 работы в тезисах конференций.

Личный вклад автора. Все результаты, выносимые на защиту, получены автором лично. В совместной работе [31] автор программно реализовал тест "стопка книг" и провел эксперименты по предложенной соавтором схеме.

Структура и объём работы. Диссертация включает введение, три главы, заключение и список литературы из 156 наименований. Основной текст работы, содержащий 32 таблицы и 13 рисунков, изложен на 124 страницах. Общий объём диссертации составляет 161 страницы.

Благодарность. Автор выражает глубокую благодарность директору Института вычислительных технологий СО РАН академику Ю.И. Шокину за постоянное внимание к работе и поддержку. Автор особенно благодарен д.т.н. Г.П. Агибалову, заведующему кафедрой защиты информации и криптографии ТГУ, за большую помощь в организации экспертизы диссертации и на этапе её подготовки к защите.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

метических операций от веса Хэмминга этой разности.

Теоретически обоснована зависимость между вероятностью сохранения разности через сложение и умножение по модулю 2S и весом Хэмминга этой разности. Полученные результаты использованы для построения разностных характеристик шифров MARS и CAST-256, на основе которых разработаны атаки на данные шифры, являющиеся эффективнее существующих.

В главе 3 теоретически и экспериментально обоснована эффективность статистического теста "стопка книг". Теоретически доказано, что для одного класса альтернативных гипотез заданные значения ошибок первого и второго рода достигаются при размере выборки равном 0{^/~S), где S — это длина алфавита, которому принадлежат элементы выборки. В то же время критерий хи-квадрат требует выборки размера 0(5). Экспериментально показано, что для класса линейных конгруэнтных генераторов тест "стопка книг" эффективнее, чем спектральный тест.

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

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

В заключении сформулированы основные результаты диссертации.

В