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

Содержание к диссертации

Введение

Глава 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

Литература

• Подходы к оценке защищённости информации при использовании блочных шифров
• Теоретическое исследование влияния веса Хэмминга разности двух величин на вероятность её сохранения после арифметических операций
• Оценка сложности разностной атаки в зависимости от параметров итеративного блочного шифра
• Статистический анализ защищённости информации при использовании итеративных блочных шифров

Введение к работе

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

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

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

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

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

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

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

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

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

ция связей и соотношений между его понятиями.

тип ических тестов и критериев.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. 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 г.) и частично грантами ..V⁰A'⁰ НШ-931.2008.9 и НШ-6068.2010.9 Президентской программы "Ведущие научные школы РФ" (рук. академик Ю.И. Шокин).

   Апробация работы. Результаты диссертации докладывались и обсуждались на следующих конференциях и семинарах: VII Intern. Conf. on Intelligent Information Hiding and Multimedia Signal Processing, Dalian, China, 2011; XII Bcepocc. научно-практ. конф. "Проблемы информационной безопасности государства, общества и личности", Томск- Барнаул-Белокуриха, 2010; IX Сибирская науч. школа-семинар с междунар. участием "Компьютерная безопасность и криптография" (Sibecrypt-ІХ), Тюмень, 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. Федотов, д.ф.-м.н. С.К. Голушко), "Информационно-вычислительные технологии" (рук.: академик Ю.И. Шокин, д.ф.-м.н. В.М. Ковеня), "Информационно-вычислительные технологии в задачах поддержки принятия решений" (рук.: академик Ю.И. Шокин, д.ф.- м.н. Л.Б. Чубаров, д.ф.-м.н. М.П. Федорук); семинар каф. защиты информации и криптографии ТГУ (рук. д.т.н. Г.П. Агибалов), семинар "Криптография и криптоанализ" (рук. к.ф.-м.н. И.И. Токарева, ИМ СО РАН).

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

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

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

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

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

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

   Единый стандарт шифрования данных в России определяется ГОСТом 28147-89 [2], где описан 64-битовый блочный шифр с 256-битовым ключом. Данный шифр используется для выработки кода аутентичности сообщения, и на его базе построен старый российский стандарт на хеш-функцию, определяемый ГОСТом Р34.11-94 [44]. Сейчас используется ГОСТ Р34.11-2012.

   Блочные шифры AES [47] и DES [81] являются соответственно новым и старым стандартами США. Финалистами конкурса AES стали RlJNDAEL [80], TWOFISH [42], MARS [73], RC6 [35] и SERPENT [42], показавшие эффективную работу на различных платформах и высокую стойкость.

   В рамках проектов NESSIE [130] и CRYTPREC [78] исследовались блочные шифры и другие методы защиты информации.

   Crypto++ — это библиотека с открытым исходным кодом на C++ [77], предоставляющая широкий набор методов и средств защиты информации, среди которых асимметричные шифрсистемы, поточные и блочные шифры, коды аутентичности сообщений, хеш-функции, шифрсистемы на эллиптических кривых. В набор блочных шифров включены кандидаты конкурса AES RIJNDAEL, RC6, TWOFISH, MARS, SERPENT и CAST-256, а также IDEA, 3DES, CAMELLIA, RC5, BLOWFISH, TEA, XTEA, SKIPJACK. Некоторые блочные шифры, реализованные с этой библиотеке, классифицированы, как "нестойкие или устаревающие", в том числе, DESX, RC2, SAFER, SHARK.

   Платформа .NET и язык С предоставляет программистам средства защиты информации через библиотеку System. Security. Cryptography [39], которая наряду с другими средствами защиты информации включает блочные шифры DES, 3DES, AES и RC2. Классы, предназначенные для обеспечения информационной безопасности в языке Java, расположены в пакете Java.security [96], содержащем блочные шифры AES, 3DES и RC2. Для доступа к методам защиты информации на языке РНР следует воспользоваться библиотекой MCrypt [122], предоставляющей следующие блочные шифры: BLOWFISH, DES, 3DES, TWOFISH, TEA, RC2.

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

   В рамках правила Керкгоффса существует несколько типов (сценариев) атак [82]: атака по известному шифртексту (ciphertext-only attack), атака по известному открытому тексту (known-plaintext attack), атака по выбранному открытому тексту (chosen-plaintext attack), атака по выбранному шифр-тексту (chosen-ciphertext attack), атака по адаптивно выбранному открытому тексту/шифртексту (adaptive chosen-ciphertext/plaintext attack), атака на связанные ключи (related-key attack), атака на связанные шифры (related-cipher attack) [152].

   Необходимым требованием к блочному шифру является его стойкость к универсальным атакам, что обеспечивается выбором его параметров. Считается, что стойкость против метода полного опробования ключей гарантируется при длине ключа не менее 80 бит [82], а в самых ответственных приложениях — 256 бит [42]. Для обеспечения стойкости шифра к атаке со словарём и к атаке, основанной на парадоксе дней рождений, следует выбирать достаточный размер блока, равный обычно 128 битам.

   Разностный метод [60] наряду со своими модификациями [51, 99, 149] является распространённым методом оценки защищённости информации при использовании блочных шифров. Основной целью данного метода является поиск таких разностей блоков открытого текста, которые могли бы привести к определённой разности блоков шифрованного текста с относительно большой вероятностью. Основными понятиями этого метода являются разность, характеристика, дифференциал, а также вероятность характеристики и дифференциала. Определение [60]. Пусть X Є {0,1}S и Y Є {0,1}S, где s 0, — некоторые двоичные вектора. Разностью этих векторов называется результат опе рации XOR, произведённой над ними: X ф У. Определение [60]. R-раундовая разностная характеристика— это упорядоченное множество Д = (5, ..., SR), где 6Г Є {0,1}S, г = 1, Я. Для обозначения характеристики используется общепринятое обозначение Определение [60]. Пусть — Д-раундовый блочный шифр, Д — і?-раун-довая характеристика и р Є [0,1]. Будем говорить, что шифр Е допускает характеристику Д с вероятностью р, если при случайно и независимо выбранных ключах раундов и блоках открытого текста С0 и D0 выполняется P(Cl D1 = д\ ..., CR DR = 6R\C D0 = 6) = р.

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

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

   Гипотеза стохастической эквивалентности [111]. Если (5m,5out,R) — произвольный дифференциал, то "почти для всех ключей" К P{CRDR = 6R\CD = 5,K = К ) « P(CRDR = 6R\C@D = 6).

   Из этой гипотезы следует, что, если (Sm, 5outі тгпі mout, R) — произвольный усечённый дифференциал, то "почти для всех ключей" К P({CR ф DR)kmout = 60Utkmout (С0 DQ)kmin = 6inkmin, К = К ) « P((CR Ф DR)kmout = 5outkmout (С0 ф DQ)kmin = 5inkmin). Если шифр допускает некоторый дифференциал с вероятностьюр такой, р P(XR YR = A0Ut): то можно разработать алгоритм вычисления секретного ключа данного шифра, трудоёмкость которого ниже, чем у метода полного опробования ключей. Количество выбранных открытых текстов для вычисления ключа составляет 0(1/р). Существует метод преобразования разностной атаки по выбранному открытому тексту в атаку по известному открытому тексту. Если исходная разностная атака требует iV выбранных открытых текстов, то для соответствующей ей атаки по известному открытому тексту необходимо 2s 2y/2N текстов (s — это размер блока). В [63] предложены методы уменьшения сложности описанного метода и преобразования атаку в атаку по шифртексту, если источник, порождающий блоки открытого текста, избыточен, и шифр используется в режиме ЕСВ. 2.2. Теоретическое исследование влияния веса Хэмминга разности двух величин на вероятность её сохранения после арифметических операций

   В главе 1 замечено, что задача протяжки разности через операции циклического сдвига и XOR решается тривиально. Поясним, как это делается. Пусть даны два блока (подблока) X и Y с определённой разностью А, другими словами, X 0 Y = А. Поскольку операция XOR коммутативна, то (X 0 Z) {Y 0 Z) = X 0 Y. Это означает, что операция XOR не изменяет разность, и вероятность протяжки разности через неё равна 1. Для наглядности изобразим этот факт следующим образом: А А. P=I Подобным свойством обладает и операция циклического сдвига: (X z) 0 (Y z) = {Х Y) z. Здесь разность не сохраняется, но преобразуется в другую с вероятностью 1, поэтому можно записать д «z) д « . р=1 Что же касается операций сложения и вычитания по модулю, то в общем случае при произвольно взятой разности А не существует разности А , чтобы выполнялось А А или А А . p=i р=1 Теорема 2.1. Пусть X, Z ZY{0,1}S и Y = X Є А, где Я(Л) = h, О h s - 1 и А -Ч = 0, тогда Р((Х Шг)0(УШ2) = А)= 2"\ Доказательство. Доказательство проведем индукцией по h. База индукции. Пусть h = О, следовательно, Д = 0 и X = Y. Отсюда получаем, что XffiZ = YH1Z, поэтому (X ЕВ Z) ф (У ЕВ Z) =Ас вероятностью 1. Поскольку в данном случае 2 h = 2 = 1, то база индукции доказана. Предположение индукции. Предположим, что утверждение теоремы справедливо при h — t, т. е. при Н(А) = t выполняется Р((Х ЕВ Z) ф (Y ЕВ Z) = Д) = Т1. Шаг индукции. Используя предположение индукции, докажем, что утверждение теоремы справедливо при h = t+1, т. е. при Н(А) = t+І выполняется Р((Х ЕВ Z) Ф (У ЕВ Z) = Д)= 2 (t+1). 1. Введем обозначения, используемые далее. Обозначим через m номер старшего ненулевого бита в Д, т.е. Х ф F ml = 1 и Х ф У = 0 при к т. Для определённости положим, что Х = 0, а У = 1. Представим интересующие нас величины следующим образом: Х = (х+\\0\\х-), у = (0+111112,-), Z = (z+\\zW\\z-), А = (6+\\1\\ё-), ГДЄ Х = Xfm_1 - ], у = ytm-l.-.Ol z- = [m-l,...,0]) J- = J[m-1,...,0]; ж+ = j5-[s-l,...,m+l] + _ y[s-l,...,m+l] Ч- _ [s-l,...,m+l] J+ _ д[8-1,...,го+1]_ Введем величины Х- и У-, получаемые соответственно из х и г/- посредством их дополнения нулями до s-битовых векторов: Х- = (О- НОНяГ), У" = (О- НОПзГ). (2.1) Обозначим также P = XEBZnQ = yEBZ. Таким образом, для доказательства теоремы требуется показать, что Р(Р Ф Q — А) = 2 (t+l . 2. Представим событие Р Ф Q = А в виде пересечения трёх событий: (Р Ф Q)lTO_1 -.o] _ j- (обозначим его через Л ),

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

   В данном параграфе разностная характеристика (2.20) используется для разработки атаки на шифр MARS, состоящего из пред- и пост- отбеливаний, восьми backward core раундов и восьми backward mixing раундов; сохраняя исходную нумерацию раундов, можно сказать, что атака направлена на шифр, состоящий из отбеливаний и 16 раундов — с 17-го по 32-ой; такой вариант шифра MARS использует 752 бита ключей отбеливания и ключей раундов.

   Обозначим через Y = MARSi6(X) зашифрование блока X в блок Y таким шифром MARS. Разработанная атака выполняется в два этапа: сначала вычисляются ключи пост-отбеливания, а затем — ключи раундов ядра и ключей пред-отбеливания.

   Вычисление ключей пост-отбеливания. Для удобства рассмотрим четыре 32-битовых ключа пост-отбеливания как один 128-битовый; первым и наиболее трудоёмким этапом атаки является вычисление этого ключа. Атака реализуется в несколько шагов.

   Шаг 1. Сформировать 6 групп, каждая из которых состоит из 2101 различных пар блоков с разностью (0, 0, 0, 218); эта разность является входной для характеристики (2.20); обозначим пары блоков через (Л, Bf), где 0 = 1, ...,б, = 1, ...,2101.

   Шаг 2. Для каждой пары (Af, Bf) запросить пару шифрованных блоков XI = MARSi6(Af) и Yf = MARSi6(Bf); полученные б 2101 пар шифрованных блоков сохранить в памяти.

   Шаг 3. Перебрать все возможные значения вычисляемого 128-битового ключа пост-отбеливания (обозначим его через к), который может быть равен любому числу из множества {0, ..., 2128 — 1}; для каждого из перебираемых значений выполнить следующие действия: (а) д := 1; (б) сохранённые в памяти пары шифрованных блоков из группы д расшифровать на пост-отбеливания на ключе к и восемь обрат ных раундов перемешивания; обозначим полученные пары через Р! и Q?; (в) если Р? Є Q\ ф (0,0,0,222) для всех t = 1, ..., 2101, то к - это ложный ключ-кандидат; отбросить его и перейти на шаг (3), где выбрать следующий ключ-кандидат; если Р/ Q9t = (0,0,0, 222) выполняется хотя бы для одной из пар, то перейти на шаг (г); (г) если д 6, то д := д + 1 и перейти на шаг (б); иначе к — это истинный ключ. Вычисление ключей раундов ядра и пред-отбеливания. После того, как 128-битовый ключ пост-отбеливания вычислен, все хранящиеся в памяти шифрованные блоки необходимо расшифровать на пост-отбеливание и на восемь не снабжённых ключами backward mixing раундов. Блоки окажутся зашифрованными с помощью шифра MARS, состоящего из пред-отбеливания и восьми backward core раундов. На основании приведённых ниже дифференциалов нужно реализовать аналогичную атаку, перебирая 64-битовые ключи (с 62 неизвестными битами) backward core раундов один за другим. Для определения ключа последнего раунда необходимо использовать дифференциал (О, 0, 0, 218) "РеД-о елизание + 7 раунде р=2 98 для определения ключа предпоследнего раунда необходимо использовать дифференциал (О, 0, 0, 218) Добеливание + 6 раунде р=2 98 затем — СП О П 918ї пРеД-тбеливание + 5 раундов /? 22\ Р=1/2 СО 0 0 218) пРед отбеливание + 4 РаУнда, /п9 7 о31) р=1/2 (0,0,0, 218) пред-тбеливание + 3 раунда) (218,0, 0,0), р=1/2 (0,0,0,218) пред тбеливание + 2раунда) (0,218,0,0), р=1/2 (0,0,0,218) пред-тбеливание + Х раунд) (0,0,218,0), Р=1/2 (0, 0,0, 218) пред отбеливание) (0,0,0,218). р=1/2 После вычисления всех раундовых ключей необходимо расшифровать блоки шифрованного текста всеми раундами и вычислить ключи пред-отбеливания вычитанием подблоков открытого текста из блоков шифрованного текста. 2.4. Разработка атаки на блочный шифр CAST-256

   Шифр CAST-256 [46] представляет собой обобщённую схему Фейстеля, состоящую из 48 раундов двух типов: Л я В, использующих три типа ра-ундовой функции: F1, F2 и F3. Если раунд использует функцию F1, то он обозначается Лг или Вг, а если тип функции F не важен, то индех г опускается. Вначале блок открытого текста преобразуется 24 раундами типа Л, а затем — 24 раундами типа В, точная последовательность раундов следующая: А1 А2 А3 Л1 А1 А2 А3 А1 24 раунда в1, в3, в2, в\ в\ в3, в2, в1,... (2.21) раунда Три типа функции F (рис. 2.2) имеют одинаковую схему и отличаются только порядком операций в них (табл. 2.4). Таблица 2.4. Операции в функции F г е\ щ Щ е\ 1 ш в ш 2 е в ш 3 в ш е в Рассмотрим в качестве примера функцию F2. Эта функция имеет три аргумента: 32-битовое слово IN, 5-битовый ключ циклического сдвига Кг и 32-битовый ключ маски Кт. Возвращает данная функция одно 32-битовое слово OUT. Ниже представлены преобразования, осуществляемые функцией F2:

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

   Генераторы, исследуемые в данном параграфе, относятся к классу линейных конгруэнтных генераторов. Напомним, что линейный конгруэнтный генератор работает по следующей формуле: ХІ+І = (ахі + с) mod m, (3.21) где XQ, а, с и т — целочисленные константы. Линейные конгруэнтные генераторы псевдослучайных чисел предназначены для получения целых чисел, равномерно распределенных на множестве {0,... ,т — 1}. Младшие знаки таких чисел (получаемых по формуле (3.21)) могут иметь плохие статистические свойства, поэтому существует рекомендация использовать только старшие знаки [10]. Согласно этой рекомендации можно выделять старший бит или старший байт; в дальнейшем эти режимы обозначены R\ и Rg соответственно. В режиме Ri для четного т старший бит уп вычисляется по формуле

   В [10] отмечается, что спектральный критерий является важным методом проверки качества псевдослучайных чисел, получаемых с помощью линейного конгруэнтного генератора. Многие генераторы, признанные неудовлетворительными, не прошли именно этот критерий, поэтому спектральный критерий является одним из наиболее эффективных на сегодняшний день. Преобразуем последовательность {хп}, полученную согласно (3.21) в последовательность {ип} по следующей формуле: ип = хп/т. Элементы последовательности {ип} принадлежат интервалу [0,1). Для каждого целого t 0 определим Tt = {йп = (м„,..., Un+t-i) п 0, х0 Zm)}.

   Далее рассматриваются все семейства (t-l)-MepHbix гиперплоскостей в кубе [0,1] , покрывающие все точки из Ті, и выбирается то семейство, где расстояние между гиперплоскостями максимальное, это расстояние обозначим через dt. Чем больше dt, тем более случайны числа. Алгоритмы нахождения этого значения достаточно громоздки и могут быть найдены в [10].

   Последовательность уп Є {0,1} разбивалась на блоки длины s, и при тестировании она рассматривалась как выборка из алфавита размера S = 2s, состоящего из всех двоичных слов длины s. Множество позиций в "стопке книг" разбивалось на два подмножества

   При проведении экспериментов каждый генератор тестировался в режиме R\ при разных размерах выборок; если удавалось найти размер выборки, при котором тест "стопка книг" отличал генерируемые последовательности от равномерно распределенных, то все вычисления повторялись при этой длине по другим 100 выборкам, ранее не использовавшимся для тестирования. При этом вычислялись величины Uа, равные количеству тех выборок, на которых значение х1 (вычисленное согласно (3.2)) больше, чем квантиль распределения хи-квадрат уровня а с соответствующим числом степеней свободы. Если не удавалось найти отклонений от случайности, то все вычисления повторялись в режиме Rs В табл. 3.1 отражены результаты экспериментов, где № — это номер генератора, R — режим тестирования, а и т — параметры генератора, s — длина слова (25 — это размер алфавита), N — размер выборки в словах, N s — размер выборки в битах, К и L — параметры теста.

   Если распределение выборок является равномерным, то вероятность того, что х2 Хо,05, равна 0,05, а вероятность того, что х2 Хо,5 равна 0,5; следовательно, в среднем С/о,о5 будет равна 5, a UQ$ — 50, И статистики статистики окажутся больше квантили хі;0,ооі приблизительно равна 10,83; статистика (3.22) принимает это значение при /о,о5 приблизительно равном 12, а статистика (3.23) — при Щ приблизительно равном 73. Следовательно, если С/0,05 12 или /7о,5 73, то с вероятностью 99,9% распределение элементов тестируемых выборок не является равномерным. Из результатов, приведенных в табл. 3.1, видно, что для всех генераторов были найдены параметры, при которых одно из этих условий выполняется. Таким образом, тест "стопка книг" определяет отклонения от равномерного распределения для рассмотренных генераторов.

   Правильность реализации теста и достоверность результатов проверялась следующим образом. В [10] приведены результаты тестирования генераторов, обозначенных В, С, D, Е и F. Генераторы В-Е являются линейными конгруэнтными генераторами, a F — это датчик Фибоначчи, работающий по формуле Xi = {xi-i + Жг-г) mod т. В результате тестирования был сделан вывод, что генераторы D, Е и F прошли испытания неудовлетворительно, В прошел испытания удовлетворительно, а С "находится на грани". Результаты проверки данных генераторов тестом "стопка книг" хорошо согласуются с этой классификацией; действительно, генератор F ведет себя неудовлетворительно уже при длине выборки 240 бит, генераторы С и D требуют выборок большего размера, а генератор В прошел проверку успешно.

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

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

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

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

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

   

   Модели и методы комплексной оценки аппаратно-программных средств обеспечения конфиденциальности и целостности информацииСавельева, Александра Александровна

   

   Разработка и исследование алгоритмов анализа стойкости блочных шифров методом дифференциального криптоанализаИщукова Евгения Александровна

   

   Методы и средства контроля и управления доступом в АСУ ТП на основе биометрических характеристик пользователяАфрин Алексей Григорьевич

   

   Разработка математической модели информационного обмена в локальной вычислительной сети для реализации средств и метода сетевой защиты информацииПелешенко Виктор Сергеевич

   

   Методы и средства автоматизированного обнаружения уязвимостей в программах на языке C на основе статического анализа их исходных текстовПучков Федор Михайлович

   

   Развитие методов и средств обеспечения целостности и конфиденциальности регистрируемой информации системы информационной безопасности организации воздушного движенияЛёвин, Валерий Юрьевич

   

   Разработка методов и средств проектирования инфраструктуры обеспечения информационной безопасности автоматизированных системНестеров Сергей Александрович

   

   Метод разработки средств автоматизации и проектирования сетей приманокХусни

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

   

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