Содержание к диссертации
Введение
1. Исследование возможности применения метода дифференциального к анализу современных алгоритмов блочного шифрования с помощью распределенных многопроцессорных вычислений 15
1.1 Метод полного перебора 16
1.2 Парадокс Дней Рождений 18
1.3 Метод дифференциального криптоанализа 21
1.4 Параллелизм в задачах криптоанализа І 26
1.4.1 Теоретические основы оценки эффективности параллельных алгоритмов 28
1.4.2 Разработка универсального алгоритма проведения ДК алгоритмов блочного шифрования с помощью РМВ 33
1.4 Выводы 38
2. Разработка последовательных алгоритмов проведения дифференциального криптоанализа криптосистем, построенных по схеме Фейстеля 40
2.1 Разработка алгоритмов проведения дифференциального криптоанализа алгоритма шифрования DES 40
2.1.1 Исходные сведения о дифференциальном криптоанализе алгоритма шифрования DES 41
2.1.2 Разработка алгоритма построения таблиц анализа для S-блоков замены 50
2.1.3 Выявление основных свойств таблиц анализа для S-блоков замены 52
2.1.4 Способ сокращения числа анализируемых текстов за счет использования невозможных дифференциалов 56
2.1.4 Разработка алгоритмов проведения ДК алгоритма шифрования DES... 58
2.1.5 Анализ 6 раундов алгоритма DES с использованием наиболее вероятных дифференциалов 65
2.2 Разработка алгоритмов для проведения ДК алгоритма шифрования ГОСТ 28147-89 в режиме простой замены 67
2.2.1 Анализ циклического сдвига 68
2.2.2 Анализ операции сложения двух чисел по модулю 2" 69
2.2.3 Анализ преобразования с помощью S-блоков замены 73
2.2.4 Разработка алгоритма анализа алгоритма ГОСТ 28147-89 75
2.3 Выводы 83
3. Разработка параллельных алгоритмов дифференциального криптоанализа алгоритмов блочного шифрования, построенных по схеме Фейстеля 85
3.1 Разработка алгоритмов проведения ДК алгоритма шифрования DES с использованием РМВ 85
3.2 Расчет эффективности разработанных алгоритмов для алгоритма шифрования DES 101
3.2.1 Экспериментальные данные для алгоритма шифрования DES 103
3.3 Разработка алгоритмов проведения ДК алгоритма шифрования ГОСТ 28147-89 с использованием РМВ 107
3.3.1 Трудоемкость перебора 115
3.3.2 Организация межпроцессорных обменов 118
3.4 Экспериментальная оценка эффективности разработанных алгоритмов для ГОСТ 28147-89 120
3.5 Выводы 128
4. Дифференциальный криптоанализ стандарта шифрования данных AES . 131
4.1 Стандарт шифрования данных AES 131
4.1.1 Раундовое преобразование 133
4.1.2 Алгоритм выработки ключей 140
3.1.1 Функция зашифрования 142
4.1.1 Функция обратного дешифрования 144
4.1.2 Функция прямого дешифрования 146
4.2 Анализ основных преобразований, входящих в состав стандарта AES 148
4.2.1. Анализ преобразования SubBytes() 148
4.2.2 Анализ преобразования MixColumns() 150
4.3 Построение многораундовых характеристики для стандарта AES и эффективность их применения 154
4.6 Разработка алгоритмов для проведения дифференциального криптоанализа стандарта AES с использованием РМВ 159
4.7 Выводы 163
Заключение 165
Список использованных источников
- Метод дифференциального криптоанализа
- Выявление основных свойств таблиц анализа для S-блоков замены
- Расчет эффективности разработанных алгоритмов для алгоритма шифрования DES
- Анализ основных преобразований, входящих в состав стандарта AES
Введение к работе
Актуальность. Ключевой задачей криптографии является создание стойких алгоритмов шифрования. Любой конструируемый алгоритм подвергается тщательному анализу с целью выявления его слабых мест и возможности взлома. Алгоритм является относительно стойким до тех пор, пока не будут обнаружены методы и пути его анализа, позволяющие получить секретный ключ шифрования значительно быстрее, чем это можно сделать с использованием метода «грубого перебора» [1].
В начале 90-х годов прошлого века в криптоанализе был сделан большой скачок развития, благодаря работам Э. Бихама (Е. Biham) и А. Шамира (A. Shamir) [2,3]. Это связано в первую очередь с тем, что появилась необходимость создания криптографических алгоритмов, отвечающих ряду критериев, таких как стойкость, стоимость, гибкость, программная и аппаратная реализуемость. Первые работы были посвящены дифференциальному криптоанализу (ДК) наиболее стойких и используемых на тот момент алгоритмов шифрования, таких как DES (Data Encryption Standard) и IDEA (International Data Encryption Algorithm). Однако, в связи с тем, что DES в то время являлся действующим стандартом шифрования, в печати появлялись лишь тезисы, содержащие сведения о том, что учеными разработан новый метод анализа алгоритмов блочного шифрования (АБШ), краткие сведения о нем, и результат работы данного метода, позволяющий сократить сложность анализа алгоритма шифрования DES с 256, что соответствует методу полного перебора до 2 [4]. После этого стали появляться публикации, посвященные анализу других АБШ. При их рассмотрении стало ясно, что не существует единого алгоритма. Есть общий принцип, заключающийся в прослеживании несхожести двух текстов при их прохождении через раунды шифрования. Но то, как это должно быть сделано, зависит от структуры анализируемого алгоритма, составляющих его криптографических примитивов и используемого числа раундов.
Изучение источников информации и публикаций, посвященных анализу алгоритмов блочного шифрования (АБШ) показало, что в настоящий момент существует два основных, можно даже сказать эталонных, метода анализа АБШ. Это методы дифференциального и линейного криптоанализа. Если алгоритм выдерживает атаку с использованием этих двух методов, то он считается стойким и без опаски может быть использован при передаче конфиденциальных данных.
Однако, несмотря на огромную значимость вышеуказанных методов, они все еще сравнительно мало изучены. Их применение к анализу алгоритмов разнится и зависит от структуры АБШ, а именно: от используемых криптографических примитивов и числа раундов. Поэтому актуальным является вопрос исследования и систематизации основных аспектов применения методов криптоанализа АБШ.
Кроме того, как уже отмечалось выше, эффективность использования того или иного метода анализа напрямую зависит от скорости определения секретного ключа. Поэтому не менее актуальным является вопрос разработки высокопроизводительных алгоритмов анализа на основе используемого метода. Одним из методов повышения производительности при анализе АБШ является использование распределенных многопроцессорных вычислений (РМВ). Из-за специфики алгоритмов нельзя разработать универсальный скоростной алгоритм анализа, поэтому целесообразно начинать исследование с тех АБШ, которые в настоящий момент широко используются. К ним в первую очередь относятся государственные стандарты шифрования - это два стандарта шифрования США AES и отечественный стандарт ГОСТ 28147-89. Кроме того, сюда можно отнести бывший стандарт шифрования данных США - DES. Несмотря на то, что алгоритм шифрования DES не используется как государственный стандарт, а рекомендован только для коммерческих целей, с его помощью можно конструировать комбинированные алгоритмы. Поэтому рассматриваемые методы анализа для него актуальны.
Таким образом, исследования, ставящие целью изучение метода дифференциального криптоанализа на примере алгоритмов шифрования DES, ГОСТ 28147-89 и AES (под алгоритмом шифрования AES понимается АБШ Rijndael, лежащий в основе стандарта AES) и разработка на их основе алгоритмов анализа, в том числе с использованием РМВ, являются актуальными и представляют научный и практический интерес.
Цель работы заключается в разработке последовательных и параллельных алгоритмов анализа стойкости блочных шифров методом дифференциального криптоанализа (ДК) и выявление особенностей реализации его основных этапов.
Для достижения поставленной цели решаются следующие основные задачи;
выявление особенностей применения метода дифференциального
криптоанализа к анализу блочных шифров на примере алгоритмов
DES,AES и ГОСТ 28147-89;
разработка последовательных и параллельных алгоритмов проведения
дифференциального криптоанализа АБШ DES, AES и ГОСТ 28147-89;
разработка последовательных и параллельных алгоритмов поиска
дифференциалов, обладающих максимальной вероятностью, для
проведения ДК алгоритма ГОСТ 28147-89;
исследование зависимости быстродействия разработанных алгоритмов
от используемого числа процессоров и исходных данных анализа для
алгоритмов DES и ГОСТ 28147-89;
Объект исследования. Объектом исследования являются:
особенности использования дифференциального криптоанализа при
оценке стойкости АБШ; - зависимость времени анализа блочных шифров от числа процессоров
при использовании РМВ.
Методы исследования основаны на использовании теории вероятностей, теории конечных полей, теории множеств, теории кодирования информации, а также на современных методологиях построения
программных комплексов и систем. При разработке алгоритмов анализа в качестве инструментальных средств учитывались особенности применения стандарта передачи данных MPI (Message Passing Interface).
Научная новизна полученных в диссертации основных результатов заключается в следующем.
Исследованы дифференциальные свойства основных криптографических примитивов, входящих в состав современных алгоритмов блочного шифрования, получены численные результаты анализа таблиц замены и правила определения вероятности дифференциала для операции целочисленного сложения по модулю 2", которые являются неотъемлемой частью проведения ДК АБШ.
Разработаны алгоритмы поиска правильных пар текстов по заданному дифференциалу для алгоритмов шифрования DES, AES и ГОСТ 28147-89.
На основе метода дифференциального криптоанализа, предложенного Э. Бихамом и А. Шамиром, разработаны последовательные и параллельные алгоритмы для проведения анализа n-раундового (п<16) алгоритма DES.
Разработан рекурсивный алгоритм поиска дифференциалов, обладающих максимальной вероятностью, для алгоритма шифрования ГОСТ 28147-89, учитывающего различные варианты заполнения для блоков замены, для отбора правильных пар текстов при дальнейшем анализе.
Разработан параллельный алгоритм поиска наиболее вероятных дифференциалов для алгоритма ГОСТ 28147-89 (по пункту 4) с учетом статического и динамического распределения данных и межпроцессорных взаимодействий при выявлении дифференциала с максимальной вероятностью.
Разработан параллельный алгоритм проведения ДК алгоритма AES с учетом межпроцессорного распределения данных и взаимодействия процессов при нахождении ключа шифрования.
7. Результаты экспериментов, подтверждающие пункты 1 - 5. В частности:
Проведен анализ 6 раундов алгоритма DES с использованием наиболее вероятных значений дифференциалов. Показано, что на 2-процессорной системе с частотой процессоров 1,41 ГГц время анализа в среднем составляет 7,5 минут, на 16-процессорной - 56 секунд.
Проведен полный анализ диапазона входных разностей для алгоритма DES, состоящего из 8, 10, 12, 14 и 16 раундов на т-процессорном кластере (т<16) с использованием разработанной методики. Показано, что при увеличении числа процессоров наблюдается практически линейный рост ускорения времени анализа. Кроме того, показано, что процент текстов, полностью соответствующих схеме преобразования заданного дифференциала, от общего числа найденных правильных пар текстов, лежит в диапазоне от 80% до 100%, что гарантирует успех анализа.
Проведен анализ 16-раундового алгоритма DES с использованием 16-процессорного кластера (частота 1,41 ГГц). Показано, что время работы программы составило 24 часа 13 минут.
7.5. Проведены тестовые испытания анализа алгоритма шифрования ГОСТ 28147-89 для различных сочетаний следующих параметров: числа раундов шифрования, начального значения пороговой вероятности, количества процессоров, способа распределения данных. Показано, что при задании ненулевого значения пороговой вероятности, скорость вычислений в среднем возрастает в 1,285 раз. Показано, что при использовании 16 процессоров для анализа со статическим распределением данных время вычислений сокращается в 2,88 раза, а с динамическим - в 4,4 раза по сравнению с такими же расчетами на двухпроцессорной системе. Показано, что для алгоритма с динамическим распределением данных до 8 процессоров наблюдается линейный рост ускорения.
Практическая значимость.
Проведен предварительный анализ алгоритмов DES, AES и ГОСТ 28147-89, результаты которого систематизированы в виде таблиц и основных положений. Это позволяет использовать полученные результаты в дальнейшем для непосредственного анализа зашифрованных данных без проведения подготовительных работ.
Разработаны и реализованы алгоритмы, предназначенные для анализа данных, зашифрованных с помощью алгоритмов DES, AES и ГОСТ 28147-89. Разработанные алгоритмы позволяют при определенных условиях выявлять секретный ключ шифрования, что необходимо для оценки их стойкости.
Ценность разработки подтверждает использование комплекса лабораторных работ, разработанных на основе предложенных алгоритмов, в учебном процессе кафедры Безопасности Информационных Технологий Таганрогского Технологического Института Южного Федерального Университета (ТТИ ЮФУ), как базовое средство обучения по курсу «Криптографические методы и средства обеспечения информационной безопасности».
Основные положения, выносимые на защиту. На защиту выносятся:
Выявленные дифференциальные свойства основных криптографических примитивов, входящих в состав современных алгоритмов блочного шифрования, необходимы для проведения анализа n-раундовых алгоритмов шифрования (п определяется числом раундов рассматриваемого алгоритма).
Разработанный алгоритм поиска правильных пар текстов по заданному дифференциалу для алгоритма шифрования DES дает результат с вероятностью от 0,8 до 1, что гарантирует успех дальнейшего анализа.
Разработанный параллельный алгоритм для проведения анализа п-раундового (п<16) алгоритма DES при увеличении числа процессоров обеспечивает линейный рост ускорения.
Разработанный алгоритм анализа АБШ ГОСТ 28147-89 позволяет
проводить его с различными значениями S-блоков замены.
Разработанный параллельный алгоритм поиска наиболее вероятных дифференциалов для алгоритма ГОСТ 28147-89 в среднем имеет быстродействие 1,285 при задании ненулевого значения пороговой вероятности.
Разработанный параллельный алгоритм поиска наиболее вероятных дифференциалов для алгоритма ГОСТ 28147-89 с использованием динамического распределения данных обеспечивает линейный рост ускорения при увеличении числа процессоров до 8. Использование результатов работы. Результаты, полученные в ходе
работы над диссертацией, используются:
В гранте РФФИ 06-07-89010-а «Разработка методов и моделей биометрических криптосистем на основе голосового пароля»
В гранте РФФИ 04-07-90137-в «Исследование и разработка моделей, методов и средств обнаружения атак»
В учебном процессе в Технологическом Институте Южного Федерального Университета в г. Таганроге (ТТИ ЮФУ) на кафедре Безопасности Информационных Технологий в дисциплине «Криптографические методы и средства обеспечения информационной безопасности».
Использование результатов диссертационной работы подтверждено актами об использовании.
Достоверность полученных результатов подтверждается строгостью математических выкладок, корректностью используемого математического аппарата, разработкой действующих программ и результатами экспериментов.
Апробация работы. Основные результаты, полученные в ходе работы
над диссертацией, докладывались и обсуждались:
1. На международной научно-практической конференции
«Информационная безопасность» (ТРТУ (ТТИ ЮФУ), г. Таганрог,
2003-2007).
На международной научно-практической конференции и Российской научной школе молодых ученых и специалистов "Системные проблемы качества, математического моделирования, информационных и электронных технологий", 1-12 октября 2003 г., г. Сочи
На всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (ТРТУ, г.Таганрог, 2005,2006).
На всероссийской научной конференции «Проблемы информационной безопасности в системе высшей школы» (МИФИ, г. Москва, 2003-2004).
На 3-ей Международной конференции «Информационные системы и технологии» (IST'2006), Минск.
Публикации. Результаты, полученные в работе, нашли отражение в 20 печатных работах, среди них 8 тезисов, 7 статей, 3 лабораторных практикума, 1 методическое пособие и 1 учебное пособие, рекомендованное УМО вузов РФ. Кроме того, имеется 2 свидетельства об официальной регистрации программ для ЭВМ (№2003611519 и №2003611520).
Объем и структура диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 71 наименование, двух приложений. Основной текст диссертации изложен на 173 страницах, включая 43 рисунка и 30 таблиц.
Диссертация состоит из четырех глав. Первая глава является постановочной. Здесь дается краткий обзор современных методов криптоанализа, проводится теоретический анализ предметной области, формулируются цели и задачи работы над диссертацией, а также основные пути их решения. Кроме того, в первой главе рассмотрены общие принципы применения метода дифференциального криптоанализа к АБШ, показана возможность применения многопроцессорных вычислений, сформулированы общие алгоритмы проведения анализа как с помощью последовательной, так и с помощью параллельной реализации. Вторая глава посвящена
дифференциальному анализу алгоритмов шифрования, построенных по схеме Фейстеля, а именно: алгоритмов DES и ГОСТ 28147-89. В ней проведено исследование особенностей применения метода ДК, разработаны последовательные алгоритмы проведения атак с помощью метода ДК, предложен метод понижения сложности атаки на алгоритм шифрования DES с помощью использования невозможных дифференциалов. В третьей главе приводятся разработанные алгоритмы проведения анализа алгоритмов DES и ГОСТ с использованием РМВ, проведена теоретическая оценка разработанных алгоритмов, а также анализ и сравнение экспериментальных данных. В четвертой главе описываются основные криптографические примитивы, входящие в состав алгоритма шифрования AES, приводится исследование их влияния на проведение ДК и разрабатывается алгоритм нахождения правильных пар текстов для проведения ДК на основе РМВ, приводятся теоретические расчеты эффективности разработанного алгоритма.
Метод дифференциального криптоанализа
Подключ последнего цикла шифрования можно найти, используя следующий алгоритм. АЛГОРИТМ 1; 1. Выбираем дифференциал (а, 3), для которого вероятность Р(АХ(1) = а, AY(r-l) = p) большая. 2. Случайно выбираем Х(1) и подбираем Х (1) так, чтобы АХ(1) = а. Пусть известны Y(r) и Y (r). 3. Делаем предположение, что AY(r-l) = Р и, зная Y(r) и Y (r), находим К(г). 4. Повторяем 2 и 3 пока один подключ не начнет появляться чаще других.
Данный алгоритм сформулирован в [12], однако он не отражает в полной мере всю сложность проводимого анализа. В [13] нами было показано, что, несмотря на то, что, по сути, анализ заключается в выполнение четырех вышеуказанных пунктов, гораздо более важную роль играет предварительный анализ позволяющий выявить правильные дифференциалы, то есть дифференциалы, имеющие наибольшую вероятность. Для этого проводится анализ всех нелинейных криптографических элементов, входящих в состав исследуемого алгоритма; строятся таблицы анализа, содержащие значения вероятностей, с которыми появляются значения разностей на выходе криптографического примитива при каждом из возможных значений входных разностей. На основании построенных таблиц, формируются дифференциалы.
Правильность проведения предварительного анализа играет решающую роль в дальнейшей схеме определения секретного ключа. При этом проводится анализ криптографических примитивов, составляющих функцию F (рисунок 1.2), которые представляют собой различные математические преобразования, схемы подстановок и перестановок. Так как нет никаких ограничений "на использование таких примитивов, за исключением того, что они должны оперировать блоками данных, возникает проблема выработки единой стратегии анализа. Поэтому важно выявить характерные черты анализа используемых криптографических функций алгоритма, принципы объединения результатов анализа отдельных примитивов с целью построения правильных дифференциалов.
Кроме того, более тщательное рассмотрение частных случаев анализа АБШ показывает, что целесообразней модифицировать вышеприведенный алгоритм следующим образом. Алгоритм 2: 1. Анализируем все составные криптографические примитивы алгоритма шифрования, в результате анализа получаем таблицы с вероятностями зависимостей выходной разности AY от входной разности АХ. 2. На основании таблиц, построенных в пункте 1, строим ранудовые дифференциалы и определяем их вероятность. 3. Получаем все возможные дифференциалы вида (ДХ(1) = аь AY(r) = pj), где і = l,2n, j = 1,2", n - размерность шифруемого блока данных и определяем их вероятности Р. 4. Из множества дифференциалов, определенном в пункте 3, выбираем дифференциал (a, J3), для которого вероятность Р(АХ(1) = а, AY(r) = Р) большая. 5. Случайно выбираем Х(1) и подбираем Х (1) так, чтобы АХ(1) = а. 6. Считаем, что значения Y(r) и Y (r) известны. 7. Если AY(r) Ф AY (r) = Р, то проводим анализа последнего раунда шифрования. При этом зная Y(r) и Y (r), находим возможное значение секретного ключа К(г). 8. Повторяем пункты 5-7 пока один подключ не начнет появляться чаще других.
Второй представленный алгоритм не просто более подробно раскрывает процесс предварительного анализа, но и имеет некоторые существенные отличия. Так, в первом алгоритме анализу подвергаются все рассматриваемые пары текстов, хотя не всегда значение AY(r-l) будет совпадать со значением J3. Тот факт, что рассматриваемый дифференциал имеет большую вероятность, дает уверенность в том, что из всех рассмотренных случаев именно он будет встречаться чаще всего. Это значит, что секретный ключ, который будет встречаться при анализе чаще всего, вероятнее всего будет соответствовать искомому секретному ключу шифрования. Такой подход правомерен, но требует больших вычислительных затрат и объемов памяти. Это связано с тем, что необходимо проводить анализ последнего раунда шифрования для всех рассматриваемых пар текстов, и, кроме того, необходимо иметь 2т счетчиков для накопления статистики о наиболее часто встречающихся значениях ключа, где m - длина ключа последнего раунда шифрования.
Второй алгоритм модифицирован таким образом, что анализу подвергается лишь та пара, которая точно соответствует определенному дифференциалу. В этом случае смысл заключается не столько в накоплении статистики, сколько в поиске правильной пары текстов, которая бы соответствовала выбранному дифференциалу. Опираясь на Парадокс дней Рождений можно определить минимальное количество текстов kol, при которых с вероятностью 0,5 такая пара будет найдена.
Выявление основных свойств таблиц анализа для S-блоков замены
Другая разность без обоснования выбора из представленных в п.п. 2.3.1 показана на рисунке 2.5. Эта разность после прохождения таблицы перестановки с расширением обеспечит поступление нулевых разностей во все блоки замены кроме первого. На вход первого блока замены 1 поступит разность ДА = 001100. С вероятностью р = 14/64 ей будет соответствовать разность АС = ОНО (это видно из таблицы А1, приведенной в приложении, -на пересечении 001100 строки и 0110 столбца стоит значение 14. Это говорит о том, что при входной разности АА = 001100 выходная разность АС = 0110 появляется в 14 из 64 случаев). С учетом того, что на выходе остальных блоков замены будут находиться разности, равные 0, а также учитывая таблицу перестановки Р, выходная разность раунда будет равна 00 80 82 00х (рис. 2.5).
Как видно, Э. Бихамом и А. Шамиром было предложено использовать пару, не имеющую максимально возможную вероятность. Это связано с тем, что при рассмотрении правильных пар необходимо также учитывать, сколько S-блоков будут участвовать в анализе. Если бы мы взяли к рассмотрению правильную пару для блока замены S1 (110100, 0010), то вынуждены были бы рассматривать еще и последний блок замены, так как, согласно таблице перестановки с расширением, 32-ой бит исходного сообщения является первым и пятым входным битом соответственно первого и восьмого блоков замены. При этом вероятность р определялась бы как произведение вероятностей для пары первого блока замены и вероятности для пары восьмого блока замены, в результате чего итоговое значение вероятности оказалось гораздо меньше, чем для пары, рассмотренной Э. Бихамом и А. Шамиром.
Естественным образом возникает вопрос, почему для анализа полного алгоритма шифрования DES в качестве входной разности было выбрано значение Авх = 19 60 00 ООх. Для того, чтобы на него ответить, первым делом надо определить критерии выбора входных разностей, наиболее пригодных для анализа. Во-первых, это должна быть такая разность, которая при прохождении через F-функцию может давать на выходе как нулевое значение разности (с достаточно большой вероятностью), так и ненулевое. Нулевые разности на выходе F-блока (при ненулевой входной разности) требуются для прохождения полного алгоритма шифрования DES (рисунок 2.7). Во-вторых, эта разность должна затрагивать не больше трех блоков замены. Дело в том, что в случае, когда анализу подвергается больше трех блоков замены (например, четыре), во входной разности ненулевыми могут быть 16 бит и больше. И на выходе при прохождении через блоки замены также будет находиться 16 бит и больше выходной разности. В этом случае необходимо будет проанализировать 216 216 = 232 вариантов входной разности, каждая из которых может быть получена 232 способами. В этом случае анализ становится гораздо сложнее, чем метод грубого перебора и будет требовать больших временных и аппаратных затрат.
Внимательно изучив таблицы дифференциального анализа алгоритма шифрования DES (табл. Al - А8), можно увидеть, что не существует возможности проводить анализ только одного блока замены. Объясняется это просто. На вход блоков замены поступает входная разность, преобразованная с помощью перестановки с расширением Е, которая расширяет 32 бита входа до 48 путем повторения крайних битов для каждого из блоков замены. Получается, что для того, чтобы подвергнуть анализу всего один блок замены необходимо, чтобы его входная разность содержала два первых и два последних нуля, то есть существует всего четыре варианта такой разности: 000000 000100 001000 001100 Самую первую нулевую разность мы не рассматриваем, так как она на выходе всегда дает ноль, а оставшиеся три входные разности при прохождении через блок замены должны иметь вероятность появления как нулевой, так и ненулевой разности. Изучив таблицы, приходим к выводу, что ни для одного из блоков замены вышеперечисленные разности не могут давать на выходе нулевую разность.
Для облегчения анализа была разработана вспомогательная программа, которая позволяет путем простого перебора проанализировать все возможные значения входных разностей (всего их 2 2) и выбрать те из них, которые могут дать на выходе нулевое значение разности с вероятностью не ниже заданной. В пункте 2.3 было определено, что для входной разности Двх = 19 60 00 ООх вероятность появления на выходе нулевой разности равна:
Поэтому в качестве порога в разработанной программе для анализа было указано значение вероятности 0,004. В результате анализа было обнаружено всего два возможных значения входной разности, имеющих одинаковые вероятности получения нулевых разностей на выходе. Первая вероятность - это значение Авх = 19 60 00 ООх и второе Двх = 1В 60 00 00х. Оба эти значения фигурируют в работе [2]. Таким образом, для проведения анализа по вышеизложенному алгоритму можно использовать два равновероятных значения входных разностей.
В п.п. 2.1.1 представлено краткое описание проведения ДК алгоритма шифрования DES, представленное в работе [2]. При этом опущены или не обоснованы многие важные детали и нюансы.
Задача заключается в том, чтобы определить два алгоритма, которые необходимо выполнять один за другим для достижения успешного результата анализа: алгоритма поиска правильных пар текстов и алгоритма поиска секретного ключа на основе найденных правильных пар текстов.
На рисунке 2.7 обозначено входное значение разности в алгоритм шифрования. При этом правая часть разности определена однозначно и равна 19 60 00 00х, а вторая часть не определена и может принимать одно из нескольких допустимых значений.
Расчет эффективности разработанных алгоритмов для алгоритма шифрования DES
Для наглядности и удобства работы последний описанный алгоритм распределения данных между процессорами для проведения дифференциального криптоанализа алгоритма шифрования DES представлен в виде блок-схемы на рисунке 3.2. При таком распределении данных будет наблюдаться линейный рост ускорения вплоть до использования 2 процессоров.
Таким образом, в общей сложности было разработано три алгоритма распределения данных между процессорами. Применение каждого из них зависит от числа процессоров п, принимающих участие в вычислениях и может быть сформулировано следующим образом: 1. Если п 2 , то целесообразно распределять данные путем распределения значений входных разностей. 2. Если 212 п 224, то необходимо распределять данные путем распределения возможных открытых текстов. 3. Если 224 п 236, то производится распределение и входных разностей и открытых текстов.
Естественно, что для большого числа процессоров, п 224 первый и второй алгоритмы распределения данных будут неприменимы. А вот для малого числа процессоров (п 212) можно применить второй и третий алгоритмы, однако этого делать не стоит, так как дополнительные вычисления проводимые во втором и третьем алгоритме будут замедлять анализ (хоть и незначительно), и если есть возможность, то лучше этого избежать.
Для определения возможных значений секретного подключа, воспользуемся алгоритмом, приведенном в предыдущем разделе. Так как анализу подвергаются ранее определенные правильные пары текстов, то нам известны входные сообщения X = (XL XR) и XI = (XL1 XR1) и соответствующие им шифрованные сообщения Y = (YL YR) и Yl = (YL1 YR1).
На рисунке 3.3 приведена блок-схема алгоритма нахождения возможных значений подключа. Здесь Авых - разность сообщений на выходе функции F последнего раунда шифрования, Р"1 обозначает операцию, обратную перестановке Р в функции F.
Значения E(YR) и E(YR1) - результат преобразования входов функции F последнего 16-го раунда шифрования с помощью таблицы перестановки с расширением Е.
Переменные і и j - счетчики; і - для перебора всех блоков замены (S-блоков), j - для перебора всех возможных значений той части подключа, которая соответствует анализируемому блоку замены. Значение AS определяет значение разности на выходе блоков замены последнего (анализируемого) раунда шифрования.
В результате работы данного алгоритма будет заполнен двумерный массив, каждый столбец которого будет соответствовать определенному блоку замены, а каждая строка - возможному значению битов подключа для данного блока замены. Выбрав из каждого столбца максимальное значение, получим искомый ключ.
Вычислительная сложность метода ДК может быть сведена к количеству компьютерных операций, которые необходимо выполнить для нахождения правильной пары текстов, так как сам анализ найденной пары не представляет особой сложности и выполняется очень быстро в сравнении со временем поиска правильной пары текстов.
В общей сложности к анализу предлагается Q = 236 вариантов пар открытых текстов, которые необходимо зашифровать и проверить шифртексты, полученные в результате шифрования на соответствие правильной паре. Пусть w(DES) число компьютерных операций, затрачиваемых на шифрование одного текста с помощью алгоритма шифрования DES, q - количество текстов шифруемых в рамках одного преобразования (q=2 - так как все тексты рассматриваются парами), и Wi(dY) - число компьютерных операций, затрачиваемых на сравнение полученных шифртекстов. Тогда, для реализации метода ДК алгоритма шифрования DES необходимо выполнить: W=Q W,, (3.1) где Wj - количество компьютерных операций, затрачиваемых на проверку одной пары текстов. То есть: W, =q w(DES) + w,(dY) = 2 w(DES) + w,(dY) (3.2) Подставив (3.2) в (3.1), получим: W = Q W, = 236 (2 w(DES) + w,(dY)) = 236 W,. (3.3)
Из выражения (3.3) следует, что 236 операций опробования каждой пары текстов на соответствие правильной пары могут выполняться параллельно, то есть Wnp = W. Из скалярных операций, которые нельзя подвергнуть распараллеливанию, есть только операции выделения секретного ключа из найденной правильной пары текстов. Так как в главе 2 было показано, что из опробуемого числа пар текстов (2 ) может быть найдена всего одна правильная пара текстов, то есть операция выделения секретного подключа может быть произведена в 1 из 2 случаев, то значением WCK можно пренебречь, то есть принять WCK = 0. Тогда: W W
Для применения сетевого закона Амдала, необходимо определить какие в разработанной программе выполняются передачи данных и сколько они занимают времени. Итак, в начале работы программы главный процесс рассылает всем процессам (в том числе и себе самому) значение диапазона расчета. В конце анализа все процессы пересылают главному результаты своей работы, после чего главный процесс осуществляет вьщеление секретного ключа. Передача данных в начале и в конце работы программы занимает разное количество времени и поэтому можно через ti обозначить время передачи данных в начале работы программы и через t2 - время передачи данных в конце
Анализ основных преобразований, входящих в состав стандарта AES
В рассматриваемой задаче ключом будет являться значение вероятности. Если при вызове рекурсивной процедуры будет получено значение вероятности, не превышающее пороговое значение, то процедура будет возвращать указатель на следующий уровень дерева, в противном случае должен происходить возврат и поиск по другой ветке. Если поиск для вершины х не дал желаемого результата ни по одному ветвлению, тогда надо осуществить переход на предыдущий уровень. Поиск продолжается до тех пор, пока не будут проверены все ветви корня дерева.
Для детализации алгоритма необходимо ввести несколько структур данных, которые позволят легко и просто координировать движение по дереву и не терять полученные результаты. Исходными данными для анализа являются S блоки замены алгоритма. На основании их необходимо построить таблицы анализа подобно тому, как это сделано было сделано для алгоритма шифрования DES (п.п. 2.1.1). В результате анализа будут сформированы таблицы, имеющие 16 строк (возможные значения входных разностей) и 16 столбцов (возможные значения выходных разностей). Пример таких таблиц можно посмотреть в приложении (табл. А18 - А24). На рисунке 3.6 таблицы показаны в левом столбце. На основании полученных таблиц формируем структуру данных ind S, которая представляет собой трехмерный массив. Первый элемент массива имеет 8 возможных значений и обозначает номер блока замены. Для каждого из блоков замены есть 16 возможных значений входной разности - это второй индекс массива. Для каждой входной разности есть возможные выходные разности. Минимум это одно значение (как, например, для входной разности, равной нулю), максимум - восемь (так как каждое значение выходной разности должно дублироваться, а всего возможных выходов - 16). Поэтому для каждого значения входной разности определяем запись из 9 элементов. Первый элемент определяет количество ненулевых выходных разностей, соответствующих данной входной. Остальные элементы - сами значения выходных разностей.
Структура ind_S по своей сути дублирует таблицы анализа. Однако содержит в себе только значимые элементы. Так как целью ставится полный поиск, то использование структуры подобного типа избавит от многочисленных сравнений в таблицах анализа при поиске очередного возможного значения выходной разности, что как следствие приведет к значительному сокращению времени анализа.
Следующая определяемая структура - это структура mas_ind (на рис. 3.6 правый столбец), показывающая текущее состояние указателей каждого уровня дерева. Первый индекс этой структуры меняется от 1 до 32 (по количеству раундов алгоритма шифрования) и указывает на двумерный массив. Этот массив состоит из 8 строк (по количеству блоков замены) и двух столбцов. Первый столбец показывает текущее значение входной разности, а второй - номер выходной разности в массиве ind_S. По своей сути, массив indmas определяет многообразие вершин Б-дерева.
Введем еще несколько обозначений. Пусть массив mas_razn представляет собой массив разностей для каждого уровня. Так как оперируем 32-битными половинками, то общее количество элементов этого массива будет равно числу раундов, умноженному на 2. Аналогично массиву разностей, определим массив вероятностей, в который будут заноситься вероятности текущего раунда. Таким образом, получается, что данный массив будет содержать только элементов, сколько раундов будет подвергнуто анализу (то есть максимум 32). Кроме того, пусть P_porog - пороговое значение вероятности; Р_А11 - общее значение вероятности (т.е. для совокупности раундов); kolround - общее количество раундов tekjound - текущий раунд. Тогда алгоритм поиска можно сформулировать следующим образом: 1. Берется очередное значение входной разности dXL, dXR (вершина Б-дерева). 2. Пороговое значение вероятности полагается равным 0: P_porog=0. 3. Tek_round=l. 4. Заполняется двумерный массив структуры mas_ind для раунда tekround. Значение входной разности определяется по входной разности dXR. Значение очередной выходной разности - по структуре ind_S. 5. Вычисляется значение раундовой вероятности Р. 6. Если tek_round=0, то Р_А11=Р, иначе P_AH=mas_P[tek_round-l] P. 7. Заносим текущие значения разностей: mas_razn[tek_round 2]=dXL; mas_razn[tek_round 2+1 ]=dXR. 8. Если P_AH P_porog, то переходим к пункту 9, иначе к пункту 12. 9. Процедура определения выходного значения разности dXL, dXR с заполнением соответствующих структур. 10.tek_round=tek_round+1. И.Если tek_round=kol_round, то переопределение порогового значения разности (P_porog=P_All), вывод найденной пары разностей и переход к пункту 13. 12.Переход к пункту 4. 13.tek_round=tek_round-l. 14.Если tek_round l, то переход к пункту 17. 15.Если есть еще не проанализированные выходы для данной входной разности, то переход к следующему значению, иначе переход к пункту 13. Іб.Возвратк пункту 5.
Если все варианты входных разностей проанализированы, то конец работы алгоритма, иначе - переход к пункту 1. В приложении Б приведен псевдокод данного алгоритма. Разработанный алгоритм представляет собой рекурсивный алгоритм поиска наиболее вероятных пар разностей для проведения ДК алгоритма шифрования ГОСТ 28147-89 [71]. Распределение данных для многопроцессорных вычислений будет проводиться по алгоритму 1.14
