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

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

Ищукова Евгения Александровна

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

КРИПТОАНАЛИЗА

Специальность 05 13 19 — Методы и системы защиты информации, информационная безопасность

АВТОРЕФЕРАТ

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

Таганрог 2007

003061606

Работа выполнена в Технологическом институте Южного федерального университета в г Таганроге на кафедре «Безопасность информационных технологий»

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

дохтор технических наук, профессор Бабенко Людмила Климентьевна

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

доктор технических наук, профессор Молдовян А А (г Санкт - Петербург), кандидат технических наук, доцент Котенко В В (г Таганрог)

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

ФГУП «Концерн «Системпром» (г Москва)

Защита диссертации состоится «28» августа 2007 г в 14 20 часов на заседании диссертационного совета ДМ 212 208 25 при Южном федеральном университете по адресу 347928, Ростовская область, г Таганрог, ул Чехова, 2, ауд И-425

Отзывы на автореферат просьба направлять по адресу 347928, Ростовская область, г Таганрог, пер Некрасовский, 44, Технологический институт Южного федерального университета в г Таганроге, Ученому секретарю диссертационного совета ДМ 212 208 25, Галуеву Г А

С диссертацией можно ознакомиться в Зональной научной библиотеке ЮФУ по адресу

344007, Ростовская область, г Ростов-на-Дону, ул Пушкинская, 148 Автореферат разослан июля 2007 г

Ученый секретарь диссертационного совета, доктор технических наук,

профессор

Галуев Г А

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность. Ключевой задачей криптографии является создание стойких алгоритмов шифрования Любой конструируемый алгоритм подвергается тадаетьному анализ} с целью выявления его слабых мест и возможное™ взлома Проведенный анализ источников информации и публикаций, посвященных анализу алгоритмов блочного шифрования (АЕШ) показал, что в настоящий момент существует два основных,' можно даже сказать эталонных, метода анализа АБШ Это методы дифференциального и линейного криптоанализа Если алгоритм выдерживает атаку с использованием этих двух методов, то он считается стойким и без опаски может быть использован при передаче конфиденциальных данных

Однако, несмотря на огромную значимость вышеуказанных методов, они все еще сравнительно мало изучены Их применение к анализу алгоритмов разнится и зависит от структуры АБШ, а именно от используемых криптографических примитивов и числа раундов Поэтому актуальным является вопрос исследования и систематизации основных аспектов применения методов криптоанализа АБШ

Кроме того, как уже отмечалось выше, эффективность использования того или иного метода анализа напрямую зависит от скорости определения секретного ключа Поэтому не менее актуальным является вопрос разработки высокопроизводительных алгоритмов анализа на основе используемого метода Одним из методов повышения производительности при анализе АБШ является использование распределенных многопроцессорных вычислений (РМВ) Из-за специфики алгоритмов нельзя разработать универсальный скоростной алгоритм анализа, поэтому целесообразно начинать исследование с тех АБШ, которые в настоящий момент широко используются К ним в первую очередь относятся государственные стандарты шифрования - это два стандарта шифрования стандарт США AES и отечественный стандарт ГОСТ 28147-89 (далее по тексту ГОСТ) Кроме того, сюда можно отнести бывший стандарт шифрования данных США - DES Не смотря на то, что алгоритм шифрования DES не используется как государственный стандарт, а рекомендован только для коммерческих целей, с его помощью можно конструировать комбинированные алгоритмы, поэтому рассматриваемые методы анализа для него актуальны

Таким образом, разработки, ставящие целью исследование применимости на пракгике метода дифференциального криптоанализа на примере алгоритмов шифрования DES, ГОСТ и AES (под алгоритмом шифрования AES понимается АБШ Ryndael, лежащий в основе стандарта AES) и создание на их основе алгоритмов анализа, в том числе с использованием распределенных многопроцессорных вычислений, являются актуальными и представляют научный и практический интерес

Цель работы заключается в разработке последовательных и параллельных алгоритмов анализа стойкости блочных шифров методом дифференциального криптоанализа (ДК) и выявление особенностей реализации его основных этапов

Для достижения поставленной цели решаются следующие основные задачи:

выявление особенностей применения метода дифференциального криптоанализа к анализу блочных шифров на примере алгоритмов DES, AES и ГОСТ 28147-89,

- разработка последовательных и параллельных алгоритмов проведения дифференциального криптоанализа АБШ DES, AES и ГОСТ 28147-89,

разработка последовательных и параллельных алгоритмов поиска дифференциалов, обладающих максимальной вероятностью, для проведения ДК алгоритма ГОСТ 28147-89,

- исследование зависимости быстродействия разработанных алгоритмов от используемого числа процессоров и исходных данных анализа для алгоритмов DES и ГОСТ 28147-89,

Объект исследования Объектом исследования являются

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

теории множеств, теории кодирования информации, а также на современных методологиях построения программных комплексов и систем При разработке алгоритмов анализа в качестве инструментальных средств учитывались особенности применения стандарта передачи данных MPI (Message Passing Interface)

, Научная новизна полученных в диссертации основных результатов заключается в следующем

1 Исследованы дифференциальные свойства основных криптографических примитивов, входящих в состав современных алгоритмов блочного шифрования, получены численные результаты анализа таблиц замены и правила определения вероятности дифференциала для операции целочисленного сложения по модулю 2", которые являются неотъемлемой частью проведения ДК АБШ

2 Разработаны алгоритмы поиска правильных пар текстов по заданному дифференциалу для алгоритмов шифрования DES, AES и ГОСТ 28147-89

3 На основе метода дифференциального криптоанализа, предложенного Э Бихамом и А Шамиром,

3

4

5

6

7

1

2

3

1

2

3

4

5

4

разработаны последовательные и параллельные алгоритмы для проведения анализа п-рауидового (п<16) алгоритма DES

Разработан рекурсивный алгоритм поиска дифференциалов, обладающих максимальной вероятностью, для алгоритма шифрования ГОСТ 28147-89, учитывающего различные варианты заполнения для блоков замены, для отбора правильных пар текстов при дальнейшем анализе Разработай параллельный алгоритм поиска наиболее вероятных дифференциалов дня алгоритма ГОСТ 28147-89 (по пункту 4) с учетом статического и динамического распределения данных и межпроцессорных взаимодействий при выявлении дифференциала с максимальной вероятностью Разработан параллельный алгоритм проведения ДК алгоритма AES с учетом межпроцессорного распределения данных и взаимодействия процессов при нахождении ключа шифрования Результаты экспериментов, подтверждающие пункты 1 - 5 В частности

7 1 Проведен анализ б раундов алгоритма DES с использованиемнаиболее вероятных значений дифференциалов Показано, что на 2-процессорной системе с частотой процессоров 1,41 ГГц время анализа в среднем составляет 7,5 минут, на 16-процессорной - 56 секунд 7 2 Проведен полный анализ диапазона входных разностей для алгоритма DES, состоящего из 8, 10, 12,14 и 16 раундов на га-процессорном кластере (т<16) с использованием разработанной методики Показано, что при увеличении числа процессоров наблюдается практически линейный рост ускорения времени анализа Кроме того, показано, что процент текстов, полностью соответствующих схеме преобразования заданного дифференциала, от общего числа найденных правильных пар текстов, лежит в диапазоне от 80 до 100 %, что гарантирует успех анализа 7 3 Проведен анализ 16-раундового алгоритма DES с использованием 16-процессорного кластера

(частота 1,41 ГТц) Показано, что время работы программы составило 24 часа 13 минут 7 4 Проведены тестовые испытания анализа алгоритма шифрования ГОСТ 28147-89 для различных сочетаний следующих параметров числа раундов шифрования, начального значения пороговой вероятности, количества процессоров, способа распределения данных Показано, что при задании ненулевого значения пороговой вероятности, скорость вычислений в среднем возрастает в 1,285 раз 'Показано, что при использовании 16 процессоров для анализа со статическим рас- пределением данных время вычислений сокращается в 2,88 раза, а с динамическим - в 4,4 раза по сравнению с такими же расчетами на двухпроцессорной системе Показано, что для алгоритма с динамическим распределением данных до 8 процессоров наблюдается линейный рост ускорения Практическая значимость

Проведен предварительный анализ алгоритмов DES, AES и ГОСТ 28147-89, результаты которого систематизированы в виде таблиц и основных положений Это позволяет использовать полученные результаты в дальнейшем для непосредственного анализа зашифрованных данных без проведения подготовительных работ

Разработаны и реализованы алгоритмы, предназначенные для анализа данных, зашифрованных с помощью алгоритмов DES, AES и ГОСТ 28147-89, которые позволяют при определенных условиях выявлять секретный ключ шифрования, что необходимо для оценки их стойкости Ценность разработки подтверждает использование комплекса лабораторных работ, разработанных на основе предложенных алгоритмов, в учебном процессе кафедры Безопасности Информационных Технологий Таганрогского Технологического Института Южного Федерального Университета (ТТИ ЮФУ), как базовое средство обучения по курсу «Криптографические методы и средства обеспечения информационной безопасности», ' Основные положения, выносимые на защиту На защиту выносятся

Выявленные дифференциальные свойства основных криптографических примитивов, входящих в состав современных алгоритмов блочного шифрования, необходимы для проведения анализа п-раукдовых алгоритмов шифрования (п определяется числом раундов рассматриваемого алгоритма) Разработанный алгоритм поиска правильных пар текстов по заданному дифференциалу для алгоритма шифрования DES дает результат с вероятностью от 0,8 до 1, что гарантирует успех дальнейшего анализа

Разработанный параллельный алгоритм для проведения анализа n-раундового (п<16) алгоритма DES при увеличении числа процессоров обеспечивает линейный рост ускорения

Разработанный алгоритм анализа АБШ ГОСТ 28147-89 позволяет проводить его с различными значениями S-блоков замены

Разработанный параллельный алгоритм поиска наиболее вероятных дифференциалов для алгоритма ГОСТ 28147-89. с нулевым значением пороговой вероятности обеспечивает сокращение времени

\

анализа в 1,285 по сравнению с ненулевым 6 Разработанный параллельный алгоритм поиска наиболее вероятных дифференциалов дня алгоритма ГОСТ 28147-89 с использованием динамического распределения данных обеспечивает линейный рост ускорения при увеличении числа процессоров до 8

Использование результатов работы Результаты, полученные в ходе работы над диссертацией, используются

1 В гранте РФФИ 06-07-89010-а «Разработка методов и моделей биометрических криптосистем на основе голосового пароля»

2 В гранте РФФИ 04-07-90137-в «Исследование я разработка моделей, методов и средств обнаружения атак»

3 В учебном процессе в Технологическом Институте Южного Федерального Университета в г Таганроге (ТТИ ЮФУ) на кафедре Безопасности Информационных Технологий в дисциплине «Криптографические методы и средства обеспечения информационной безопасности»

Использование результатов диссертационной работы подтверждено актами об использовании

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

Апробация работы Основные результаты, полученные в ходе работы над диссертацией, докладывались и обсуждались

1 На международной научно-практической конференции «Информационная безопасность» (ТРТУ (ТТИ ЮФУ), г Таганрог, 2003-2007)

2 На международной научно-практической конференции и Российской научной школе молодых ученых и специалистов "Системные проблемы качества, математического моделирования, информационных и электронных технологий", 1-12 октября 2003 г, г Сочи

3 На всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (ТРТУ, г Таганрог, 2005,2006)

4 На всероссийской научной конференции «Проблемы информационной безопасности в системе высшей школы» (МИФИ, г Москва, 2003-2004)

5 На 3-ей Международной конференции «Информационные системы и технологии» (IST'2006), Минск

Публикации. Результаты, полученные в работе, нашли отражение в 20 печатных работах, среди них 8 тезисов, 7 статей, 3 лабораторных практикума, 1 методическое пособие и 1 учебное пособие, рекомендованное УМО вузов РФ Кроме того, имеется 2 свидетельства об официальной регистрации программ для ЭВМ (№2003611519 и Afü2003611520)

Объем и структура диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 71 наименование, двух приложений Основной текст диссертации изложен на 173 страницах, включая 43 рисунка и 30 таблиц

СОДЕРЖАНИЕРАБОТЫ Во введении кратко рассматривается актуальность работы, цели и основные задачи, научная новизна и практическая ценность работы, приведено краткое описание основных разделов диссертации

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

Приведен краткий обзор некоторых методов и средств анализа АБШ, таких как метод полного перебора, парадокс Дней Рождений, метода дифференциального криптоанализа (ДК) Показана значимость ДК в процессе создания новых алгоритмов шифрования Кроме того, показано, что применение метода ДК не имеет единого алгоритма работы и напрямую зависит от структуры объекта анализа. Сделан вывод о необходимости обработки и систематизации уже имеющихся и полученных в ходе работы'над диссертацией знаний, с целью выявления характерных черт применения метода анализа в зависимости от используемых криптографических функций алгоритма. При этом показано, что полученная система знаний значительно упрощает работу, связанную с предварительным анализом алгоритма шифрования и подготовкой исходных данных к анализу

Для дальнейшего изложения необходимо ввести несколько определений, которыми оперирует ДК Разность АХ- несходство двух текстов X и X', определяемое путем сложения по модулю два Раундовая характеристика (дифференциал) - пара входная разность раунда (Двх) - выходная разность раунда (Двых)

Вероятность раундовой характеристики (дифференциала) - это вероятность появления выходной разности (Двых) при прохождении входной разности (Двх) через раунд шифрования

Правильная пара текстов - пара текстов (открытый - закрытый текст), которая удовлетворяет заданной характеристике (дифференциалу)

Ядро метода ДК составляет атака на основе выборочно! о открытого текста Анализ заключается в изучении процесса изменения несходства для пары открытых текстов, имеющих определенные исходные различия, в процессе прохождения через циклы шифрования с одним и тем же ключом При этом не существует каких-либо ограничений на выбор открытых текстов Достаточно различия в некоторых позициях Исходя из различий в получившихся шифртекстах, ключам присваиваются различные вероятности Истинный ключ определяется в процессе дальнейшего анализа пар шифртекстов как наиболее вероятный ключ среди множества претендентов

В ходе работы было выделено четыре основных дапа проведения ДК современных АБШ

1 Анализ криптографических примитивов, обладающих свойством нелинейности

2 Поиск дифференциала, обладающего максимальной вероятностью

3 Поиск правильных пар текстов по заданному дифференциалу

4 Определение секретного ключа путем анализа правильных пар текстов

На основании вышеприведенных этапов сформулирован общий алгоритм ДК АБШ Сделано и обосновано предложение использования многопроцессорных распределенных вычислений с целью сокращения времени анализа алгоритмов Проведен обзор современных средств, поддерживающих программное распараллеливание Обоснован выбор пакета прикладных программ для кластерных систем МРГСН 1 2 5, разработанного на основе стандарта MPI, как наиболее удобного в пчане переносимости с одной вычислительной машины на другую, а также простого и понятного интерфейса

Определены основные принципы построения параллельных алгоритмов с использованием пакета программ на основе MPI работой всей программы управляет главный процесс, программа, построенная на основе разработанного алгоритма должна позволять использовать в вычислениях любое число процессоров, при этом с помощью разработанного алгоритма данные для анализа должны распределяться равномерно

Разработан общий алгоритм ДК анализа АБШ с помощью распределенных многопроцессорных вычислений Проведен выбор метода для оценки эффективности параллельных алгоритмов Разработан алгоритм распределения данных при параллельных вычислениях

Во второй главе разрабатываются последовательные алгоритмы проведения ДК стандартов шифрования, построенных по схеме Фейстеля бывшего стандарта шифрования США DES и действующего отечественного стандарта ГОСТ 28147-89

Для алгоритма шифрования DES обозначены основные имеющиеся сведения и пути анализа на основе работ Э Бихама и А Шачира. Представлены одно- двух- и многораувдовые характеристики

Для проведения атаки на полный 16-раундовый алгоритм шифрования Э Бихамом и А. Шамиром было предложено использовать в одном раунде такую разность, которая бы при прохождении F-функции давала на выходе нулевую разность Один из возможных вариантов такой входной разности - значение ,19 60 00 00х в правой половине входной разности (нижний индекс х указывает на то, что число представлено в шестнадцатеричном виде) В этом случае после прохождения таблицы перестановки с расширением на вход первых трех блоков замены поступают значения разностей, которые при прохождении блоков замены могут дать на выходе нулевые разности На вход всех остальных блоков замены поступают нули, которые так и остаются нулями при прохождении блоков замены (рис 1) Авторами показано, что вероятность того, что при поступлении на вход раунда разности 19 60 00 00х на выходе появится нулевая разность, равнарл 1

В ходе работы над диссертацией для проведения первичного анализа разработан алгоритм построения таблиц анализа дня любых S-блоков замены, входящих в состав современных АБШ

1 Берется очередной блок замены, на вход которого поступает п бит

2 В таблице анализа для данного блока замены все исходные значения полагаются равными 0

3 Определяется первое возможное значение входной разности ДА=0

4 Определяется значение первого входа Х=0 в анализируемый S-блок

5 Вычисляется второе значение входа X' = X Ф ДА

6 Для входов X и X' в соответствии с принципом работы S-блока определяются соответственно выходы Y(X) и Y'(X')

7 Вычисляется значение выходной разности АС = Y © Y'

8 В таблице анализа увеличивается на 1 значение, стоящее на пересечении строки с номером ДА и столбца с номером ДС

9 Значение X увеличивается на 1

10 Если Х<2°, то происходит переход к пункту 5 î 1 Значение ДА увеличивается на 1

12 Если ДА < 2", то происходит переход к пункту 4

13 Если не все блоки замены проанализированы, то происходит переход к пункту 1, иначе алгоритм завершает свою работу

С помощью данного алгоритма построены таблицы анализа 8 блоков замены, входящих в состав алгоритма шифрования DES, проведен их анализ, выявлены основные закономерности построения подобных таблиц и характерные особенности таблиц анализа для алгоритма шифрования DES Показано, что

1 Сумма всех значений одной горизонтальной линии, то есть количество различных значений выходных разностей ДС, соответствующих одному и тому же значению входной разности ДА всегда равна 2", где п - размерность вектора, входящего в S-блок, то есть для DES - 26

2 Для алгоритма DES не встречается ни одной пары разностей (ДА, ДС), вероятность которой превышала бы 'Л

3 Количество соответствий данного значения выходной разности ДС данному значению входной разности ДА всегда четное Это связано с тем, что ДА = X © X' = X' © X, то есть одно и то же значение входной разности ДА получается дважды одной и той же парой входов, меняется только порядок поступления значений иа вход

4 Для алгоритма шифрования DES существует несколько наиболее вероятностных пар разностей (ДА, ДС) Все они имеют вероятность У*

В диссертации предложена методика сокращения анализируемых текстов за счет использования невозможных дифференциалов с целью нахождения правильных пар Э Бихамом и А Шамиром для анализа полного алгоритма DES перебирались все 2'2 возможных комбинаций левой части входной разности Показано, что есть выходные разности, которые никогда не могут появиться на выходе блоков замены при рассматриваемом значении входной разности Комбинируя их, получаем, что на выходе блоков замены никогда не смогут появиться следующие значения (х означает любое значение бита) ЮПхххххчхх, UJlxxxxxxxx, ххххППхххх и ххххххххОЮО Важно отметить, что после прохождения через блоки замены, разность рассеивается при помощи перестановки Р, поэтому учет битов необходимо веста в соответствии с ней

Так как в каждой из вышеприведенных комбинаций присутствует S неопределенных битов, то всего получается 4*28 = 4*256 = 1024 невозможных значений выходной разности Таким образом, количество рассматриваемых возможных выходных разностей при входной разности 19 60 00 00«, сокращается с 4096 до 3072, что приводит к сокращению общего времени анализа на 25%

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

1 Выбрать правые части открытых текстов XR и XR1 так, что XR Ф XR1 = PR = 19 60 00 00„

2 Выбрать возможное значение левой части входной разности Pl При этом значение Pl может иметь ненупевые биты в позициях 2,6,9, 13,16,17,18, 23, 24, 28, 30, 31 (обусловлено перестановкой Р) Кроме того, не должны встречаться следующие комбинации

- 9,23 и 31 биты одновременно равны единице,

- 2, 13,18,28 биты одновременно равны единице,

- 6,24 и 30 биты равны нулю, а 16 бит - единице Выбрать левые части открыть« текстов XL и XL1 так, что

XL®XL1=Pl,

Выбранные пары текстов зашифровать с помощью алгоритма шифрования DES В результате получаются два шифртекста (YL YR) и (YLl YR1)

Рис 1 - ДК алгоритма шифрования DES

5 Определить значение правой части выходной разности Ся = УК. © УЮ (см рис 1) Если значение Ся принимает одно из возможных значений Рь то выполнить следующий пункт алгоритма, иначе анализируемая пара является неправильной и надо осуществить переход к пункту 7

6 Определить значение левой части выходной разности О, - УЬ © У1Л Если разность на выходе функции Р последнего раунда шифрования Н1 = О. © 19 60 00 ОСЬ, принимает одно из возможных значений Рь, то анализируемая пара является правильной

7 Пункты 3-6 повторяются для всех возможных комбинаций ХЬ и ХЫ, образующих выбранную входную разность Рь

8 Пункты 2- 7 повторяются для всех возможных значений Рь

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

2. Алгоритм определения секретного ключа:

1 Определить значение разности Н' на выходе функции И последнего раунда шифрования путем сложения по модулю два значений разностей О. и Ря Н' = Сь © Рь

2 Применив перестановку к разности Н', обратную перестановке Р, определить значение разности на выходе блоков замены Р '{Н') Пусть на выходе каждого из блоков замены находится значе ние где

3 Применив перестановку с расширением Е ко входу УЯ (правой части одного шифртекста), поступающему на вход функции V, получить значение Е(УЛ), поступающее на вход блоков замены (без учета сложения с ключом) Пусть на вход каждого из блоков замены поступает значение Е(УИ),, сложенное с частью секретного ключа, где j = p

4 Применив перестановку с расширением Е ко входу УК1 (правой части второго шифртекста), поступающему на вход функции Р, получить значение Е(УИ I), поступающее на вход блоков замены (без учета сложения с ключом) Пусть на вход каждого из блоков замены поступает значение Е(УШ)^ сложенное с частью <;екретиого ключа, где у = 1,8

5 Для каждого из всех 8 блоков замены осуществить перебор возможных значений подключа Так как на вход каждого блока замены поступает 6 битов сообщения, то для каждого из блоков необходи-

. мо перебрать 26~64 вариантов значений подключа Для этого а Определить значение К очередного секретного подключа Ь Определить значение БСУ), на выходе ,)-го блока замены при входном значении Е(УЯ)3 Ф К с Определить значение 8(УЦ на выходе л-го блока замены при входном значении Е(УК1® К й Если З(У), © 8(У1); = Р'!(Н')|, то значение К секретного подключа

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

Для алгоритма шифрования ГОСТ 28147-89 проведен анализ основных элементов, входящих в его состав, и оказывающих влияние на значение вероятности раундового дифференциала операции целочисленного сложения по модулю 2п и блоков замены

Методом индукции выведены правила определения значения вероятности, с которой разность останется неизменной при прохождении через операцию сложения по модулю 2°,

1 Любое значение входной разности Двх может отобразиться само в себя, то есть остаться неизменным Вероятность такого отображения определяется следующим образом

если входная разность Двх < 2°"', то вероятность „ = _1_ ,

2*

е-

II

с,

^ФУН'

Рис 2 - Анализ последнего раунда

Уй ф =Сц

Рис 3 - Функция И последнего рй-унда шифрования

если входная разность Двх >2"то вероятность г. — ,

у 2и

где к - число ненулевых позиций входной разности,

2 Для входной разности Двх - 0 на выходе преобразования будет находиться значение выходной разности Двых = 0 с вероятностью р = 1

3 Для входной разности Двх = 2"-! на выходе преобразования будет значение выходной разности Двых = 2"-1 с вероятностью р=1

Так как алгоритм ГОСТ может оперировать различными блоками замены, то к рассмотрению было взято 2 набора таких блоков фиксированный (который можно найти в литературе например у Б Шнайе-ра) и сформированный случайным образом Оба набора блоков были проанализированы с помощью вышеприведенного алгоритма, и были выявлены следующие свойства

1 Сумма всех значений одной горизонтальной линии, т е количество различных значений выходных разностей ДС, соответствующих одному и тому же значению входной разности ДА, всегда равна 2*

2 Ненулевое значение входной разности ДА ни в одном из блоков не может быть заменено на значение АС = 0

3 Для фиксированных таблиц наиболее уязвимыми являются 87 и 88 блоки

4 Для случайных таблиц, участвовавших в эксперименте, наиболее уязвимыми являются 83, 84 и Яб блоки

На основании анализа таблиц было выявлено (пункт 2), что способ построения многраундовых дифференциалов, предложенный Э Бихамом и А Шамиром для анализа алгоритма ОЕБ, для алгоритма ГОСТ использоваться не может Мною был предложен следующий способ, позволяющий определять дифференциалы, имеющие наибольшее значение вероятности правая часть входной разности должна подбираться таким образом, чтобы затрагивать всего один блок замены при прохождении через функцию Р первого раунда шифрования, а правая часть разности должна быть равна наиболее вероятному значению выхода функции К первого раунда шифрования В этом случае на вход второго раунда шифрования поступит значение разности, равное нулю, которое с вероятностью р = 1 даст на выходе нулевое значение разности, а значит второй раунд можно будет исключить из учета общей вероятности

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

На основании проделанной работы был разработан алгоритм поиска правильных пар текстов и нахождения битов секретного ключа по заданным парам разностей для алгоритма ГОСТ 28147-89

1 Выбрать пары текстов (ХЬ, ХИ) и (XIЛ, ХЯ1) такие, что их разность равна заданной входной разности

2 Выбранные пары текстов зашифровать с помощью алгоритма шифрования ГОСТ 28147-89 В результате будут получены два шифргекста (¥1- У11) и (УЫ УЯ1)

3 Определить значение правой части выходной разности Ся - УК ® УЯ1 Если значение Сц совпадает с заданным значением выходной разности, то выполнить следующий пункт алгоритма, иначе анализируемая пара является неправильной и необходимо осуществил, переход к пункту 8

4 Определить значение левой част выходной разности О. = УЬ © У1Л Если сумма по модулю два значений О. и правой части разноси предыдущего пункта принимает одно из возможных значений, то анализируемая пара является правильной и надо выполнить следующий пункт алгоритма. Иначе осуществить переход к пункту 8

5 Применив операцию циклического сдвига вправо на 11 позиций к разности ДО., определить значение разности на выходе блоков замены О."1 Пусть на выходе каждого из блоков замены находится значение С,.'„ где }

6 Пусть на вход каждого из блоков замены поступает значение первого текста УК,, сложенное с частью секретного ключа, где у = 1,8 И также пусть на вход каждого из блоков замены поступает значение второго текста УК^, сложенное с частью секретного ключа, где у =1$

7 Для каждого из всех восьми блоков замены осуществить перебор возможных значений подключа. Так как на вход каждого блока замены поступает 4 бита сообщения, то для каждого из блоков необходимо перебрать 24 = 16 вариантов'значений подключа Для этого

8 Определить значение К очередного секретного подключа

9 Определить значение 3(УЯ), на выходе .¡-го блока замены при входном значении УЯ, ® К

10 Определить значение S(YRl), на выходе j-ro блока замены при входном значении YR1, © К

11 _ Если S(YR)j © S(YRl), = Cl"1* то значение К секретного подключа является допустимым и необхо-

димо его счетчик увеличить на 1

12 Подключи, имеющие максимальные значения счетчиков и будут являться искомыми

13 Пункты 1-7 повторять для всех возможных комбинаций пар текстов (XL, XR) и (XL1, XR1) до тех пор, пока одно из значений секретною подключа (для каждого из блоков замены) не качнет встречаться чаще остальных

В третьей главе на основании разработанных последовательных алгоритмов анализа, разрабатывается алгоритм применения метода ДК с использованием РМВ для анализа алгоритма DES

"Для организации РМВ, необходимо равномерно распределить данные для анализа между всеми вычислительными процессами Эту задачу решает главный процесс, имеющий нулевой ранг После распределения и передачи данных от главного процесса всем остальным (рис 4), каждым процессом осуществляется перебор пар текстов из отведенного ему диапазона В случае, если анализируемая пара текстов оказывается правильной, она подвергается дополнительному анализу с целью определения возможных значений подключа последнего раунда шифрования Результаты анализа (массив возможных значений подключа последнего раунда шифрования) от каждого из процессов передаются главному процессу После этого все процессы, кроме главного, завершают свою работу, а главный процесс объединяет результате анализа всех процессов и выделяет истинный подключ

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

Если 0 < гаек < Р„ (процессы, на которые распространяется распределение остатка)

Оь = rank*Pc+ tank, Dc = Db+Pc,

Если rank > P0 (процессы, на которые не распространяется распределение остатка)

Оъ = гапк*Рс+Р„, Dc = Db+(Pc-1)

где Db - начало диапазона анализа, De - конец диапазона анализа,

rank - номер процесса, для которого вычисляется диапазон анализа,

Рс - целая часть от деления общего числа текстов для анализа на число процессов, участвующих в вычислениях,

п - число процессов, участвующих в вычислениях,

Р0- остаток от деления общего числа текстов для анализа на число процессов, участвующих в вычислениях

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

Если n < 212, то лучше распределять данные путем распределения значений входных разностей Если 212 < n < 2й, то надо распределять данные путем распределения возможных открытых текстов Если 234 < n < 236, то производится распределение и входных разностей и открытых текстов

( — )

Рис 4 - Алгоритм проведения ДК с помощью РМВ для АБШ DES

Экспериментально были получены данные дли анализа алгоритма СЕЧ, состоящего из 8, 10, 12, 14 и ' 6 раундов Результаты "экспериментов приведены в табл. I. Из табл. 5 видно, что при увеличении числа процессоров, принимающих участие а вычислениях на&водастс* практически .тнейный рост ускорения бремени анализа. Это же можно видеть и из ¡рафика, приведенного на рисунке 5. Таблице. 1 - Экспериментальны датшые анализа различных конфигураций алгоритма шифровали РЕЗ ___

1 а. о 5 JS Л f. И п É 1 ц „ 9 р

ш s Г'1 ж я у z 5 X 6 ЕЙ I I £ ; 2 if ъ *

в 2 125 ч. 17 мин.

Э 103 ч 11 мнн. 2« ью

4 78 ч 47 ИМИ.

5 60 ч. 3 5 ИЛП

Ю 2 131 ч 28 мин.

3 105 ч. 58 мнн. 113 41

4 ч. 35 мин

i 63 ч. «ни.

12 2 137 н 1S мин

3 108 ч. 10 мнн. 37 34

84 ч. 53 мин

5 65 ч. 48 шт.

14 2 142 ч 37 ни»

1 111ч. 57 ш«н 5 4

4 88 ч. 27 мн*

S 6"> ч 13 мин

16 2 14Й, ч. 23 мин.

3 ÍIS ч 21 мнн ! 1

i 4 90 ч 15 мнн

5 7! ч 12 мин.

Íífíuffivq»

Рис 5 - Зависимость нрсмсия анализа от числа процессоров г,

Для 16-процессорного кластера с частотой процессоров 1.41 ГГц время работы программы для 16 раундов алгоритма DCS составило 24 ч. 13 мин.

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

дифференциалам (Лих = (u, PPj; Авых = (С^ Сц)}. Соотношение действительных пар текстов к общему числу полученных пар текстов лежит в диапазона от Я0% до 100%.

Если для алгоритма DHS дифференциал с максимальной вероятностью может быть однозначно определен и в дальнейшем использоваться для ЯК различных данных., то дня алгоритма шифрования ГОСТ блоки замены не известны, поэтому в случай, если блоки замены станут известны аналитику, первым делом необходимо провести их анализ дли выявлении наиболее вероятного значения дифференциала.

Ветвление возможных выходки* значений разнос™ от раувдз к раунду сходно с построением Б-деревьев. введем несколько структур данных, которые отвадят легко и просто координировать движение );о дереву и не терять полученные результаты. Исходными данными для анализа являются S блоки замены алгоритма. На основании их необходимо построить таблицы анализа в соответствии с алгоритмом, разработанным но второй главе В результате анализа будут сформированы таблицы, имеющие 15 строк (возможные значения входных разностей) н Í6 столбцов (возможные значения выходных разностей!. На основании полученных таблиц формируем структуру данных indS, которая представляет собой трехмерный массив. Первый элемент массива имеет 8 позможньгх значений и обозначает номер блока замены. Для каждого из блоков замены есть 16 возможных значений входной разности - это второй индекс массива. Для каждой входной разности гсть возможные выходные разности. Минимум это одно значение (пак, например, для входной разноеги, равной нулю), максимум - восемь (тая как каждое значение выходной разности должно дублироваться, а всего возможных выходов - 16). Поэтому для каждого значения входной разности определяем запись ш 9 элежню». Первый элемент определяет количество ненулевых выходных разностей, соответствующих данной входной Остальные элементы - сами значении выходных разностей.

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

Следующая стру ктура masjnd, показывает текущее состояние указателей каждого уровня дерева Первый индекс этой структуры меняется от 1 до 32 (по количеству раундов алгоритма шифровании) и

указывает на двумерный массив, котороый состоит из 8 строк (по количеству блоков замены) и двух столбцов Первый столбец показывает текущее значение входной разности, а второй - номер выходной разности в массиве ш<1_8 По своей сути, массив т£1_тав определяет многообразие вершин дерева

Пусть массив та^гагп представляет собой массив разностей для каждого уровня Так как оперируем 32-битными половинами, то общее количество элементов этого массива будет равно числу раундов, умноженному на 2 Аналогично массиву разностей, определим массив вероятностей, в который будут заноситься вероятности текущего раунда Таким образом, получается, что данный массив будет содержат?, столько элементов, сколько раундов будет подвергнуто анализу (то есть максимум 32) Кроме того, пусть Р_Р°Т08 - пороговое значение вероятности, Р_А11 - общее значение вероятности, ко!_гоивй - общее количество раундов, 1ек_гоипс1 - текущий раувд

Тогда алгоритм поиска можно сформулировать следующим образом

1 Берется очередное значение входной разности Рь Рк (вершина Б-дерева)

2 Пороговое значение вероятности полагается равным 0 Р_рок^=0

3 Тек_гошк1=1

4 Заполняется двумерный массив структуры яш_им1 для раунда 1ек_гоишЗ Значение входной разности определяется по правой части входной разности Ра Значение очередной выходной разности - по структуре т<1_8

5 ~ Вычисляется значение раундовой вероятности Р

6 Если 1ек_гокпс1=0, то Р_А!!=Р, иначе Р_А1!=та8_Р[1ек_гошк1-13*Р

7 Заносим текущие значения разностей

та8_га2п[1ек_гоипй*2]= Ри таз_га/п [гек_гоипй *2+1 ]= Рн

8 Если Р_А11>Р__ро1^, то переход к пункту 9, иначе к пункту 12

9 Процедура определения выходного значения разности Рь, Рц с заполнением соответствующих структур

10 1ек_гоип<3=*ек_гош1(1+1

11 Если 1ек_гоип<1=ко1_гс>шк1, то переопределение порогового значения разности (Р_рого£=Р__А15), вывод найденной пары разностей и переход к пункту 13

12 Переход х пункту 4

13 1ек_гошкМек_гошк1-1

14 Если 1ек_гоип<1<1, то переход к пункту 17

15 Если есть еще не проанализированные выходы для данной входной разности, то переход к следующему значению, иначе переход к пункту 13

16 Возврат к пункту 5

17 Если все варианты входных разностей проанализированы, то конец работы алгоритма, иначе - переход к пункту 1

Разработанный алгоритм представляет собой рекурсивный алгоритм поиска наиболее вероятных пар для проведения ДК алгоритма шифрования ГОСТ ¿8147-89

Поиск пар разностей проводится в соответствии с пороговым значением вероятности Было выделено два пути задания порогового значения вероятности Первый - это задание напрямую В этом случае в результате поиска будут найдены все пары разностей, вероятности которых не ниже заданного порогового значения Второй путь - это динамическое изменение значения пороговой вероятности В этом случае будут найдены все пары разностей, имеющие максимальные значения вероятностей из всего диапазона поиска

В соответствии с предложенным способом определения раундовых дифференциалов, анализу следует подвергать только те входы, которые при прохождении через первый раувд шифрования будут затрагивать всего один блок замены Тах как в алгоритме ГОСТ предусмотрено 8 блоков замены, на вход каждого из которых поступает 4-битовое значение (те имеется 15 ненулевых возможных входов), то всего возможно 8*15=120 вариантов входных разностей, которые могут дать наибольшую вероятность прохождения через раунды шифрования

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

пор, пока не будут розданы и проанализированы все данные диапазона анализа.

Как при статическом, так и при динамическом распределения данных каждому из процессов будет посылаться целое число из диапазона от 1 до 120 Для получения очередной входной разности, котирую необходимо подвергнуть анализу, необходимо: 1 Определить целую часть Ре от деления н остаток отделения Ро очередного числаз из определенного интервала на 15 (по количеству ненулевых входов ь блок замены) 2, Если остаток от деления равен нулю Ро, то получен™« значение целой части Рс уменьшить на 1 3 Определить значение входа 5ух в блок замены по формуле: 8у* =]-Ре*! 5,

А Для получения «полной разности при анализе (1Х_Й сдвинуть значения входа в блок замены на количество позиций, кратное 4 ¿Х^Н-^Вух «( Рс *4)):

Понятно, что простого распределения данньи для расчета между процессами будет недостаточно, В данном случае требуется коллективный обмен данными для таге, чтобы постоянно растущее значение пороговой вероятности бмло известно всем процессам, а не только тому, который се определил. При этом необходимо учесть, что в момент обмена пороговыми вероятностями тот процесс, которому значение вероятности было передано, может находиться на большой глубине и поднятия на один уровень вверх дажст оказаться недостаточно для тар», чтобы удовлетворить новому получен^му 1>£>рогй№»!у значению 1 веройтноети Й связи с этим, был предусмотрен механизм возврата До того уровня, на котором вероятность ниже порогового значения. I Так как не известно, в какое время и сколько раз будет осуществляться межпроцессорный обмен, то

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

В ходе работы было реализовано пае программы иа основе разработанного ларитлельного алгоритма: одна с использованием статического распределения данных, другая - с использованием динамического. Работа обеих программ была протестирована с помощью 1 б ^процессорного кластера. В ходе тестовых экспериментов проводились замеры времени вычислений для разных мачалбных условий: числа прсцес-| соров, участвующих а вычислениях, количества раундов шифрования и начального значения пороговой вероятности При угон для каждого п-раундопого алгоритма (где п не больше 8) проводились замеры яремени для двух разных начальных значений пороговой вероятности равной 0 и отличной от 0. Из дан-1 ных для нулевого к ненулевого значений пороговой вероятности следует, что при задании ненулевого значения пороговой вероятности а средне« скорость вычислений возрастает в 1,285 раз.

Для программы с динамическим распределением данных скорость работы для п-раундового алгоритма шифрования, где п<1 сказалась лучше, чем дня статического распределения. При этом все процессоры получили одинаковую нагрузку, и соответственно примерно одинаково« время работы, в огличке от ! алгоритма статистического распределения, где некоторые процессы считали быстрее остальных. Однако, I при семи раундах время работы значительно превышает время работы программы со статическим распре-( делением. Это объясняется так: при статистическом распределении процессы для анализа получают значения из разных диапазонов, при этом одно из этих значений позволяет практически сразу определить пару входная - пыхолизя разность, имеющую вероятность, сильно приближенную к максимально возможной. Вследствие межпроцессорного обмена, это значение вероятности становится пороговым для всех , процессов. Поэтому дальнейший внализ проходит с большим отсечением заведомо плохих пар, то есть пар, имеющих вероятность ниже текущего порогового значения. 11рн динамическом раелреде/киия данных такое хорошее значение вероятности сразу не определяется, поэтому процессам приходится осущесг-I влять перебор практически по полному дереву, что существенно тормозит процесс анализа.

Исходя из этого, можно сделать вывод, что эффективность применении разработанных алгоритмов зависит не только от числа используемых процессоров и количества раундов шифрования, но и от спосо-) Ба раслредедсш данных анализа. Чем быстрее будет найдена вероятное 1Ъ, максимально приближенная к Наилучшей, тем быстрее будет проведен анализ. При этом также необходимо помнить, что различные

Рис. 6 - Гхуафик зависимое времени вычислений от числа не пользуем их процессорам

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

На рис 6 представлены графики зависимости продолжительности расчетов от числа используемых процессоров, полученные для 6 раундов алгоритма шифрования с пороговым значением вероятности, равным 0 Из графика' видно, что при использовании 16 процессоров для анализа общее время вычислений существенно сокращается (при статическом распределении - в 2,88 раза, а при динамическом - в 4,4 раза) по сравнению с такими же расчетами на двухпроцессорной системе При этом для динамического распределения данных до 8 процессоров показан практически линейный рост ускорения

В 'четвертой главе разрабатывается алгоритм анализа шифра AES В ДК самое большое влияние на изменение схожести оказывают те блоки алгоритма, в которых происходит нелинейное преобразование В алгоритме AES подобного рода нелинейную замену данных выполняет преобразование SubBytes, обеспечивающее побайтную замену данных Анализ преобразования SubBytes на предмет стойкости к дифференциальному криптоанализу был проведен по сформулированному ранее алгоритму анализа блоков замены и позволил выявить следующие особенности

- максимальное значение в таблице равно 4, за исключением первой ячейке, соответствующей разностям ДА = 0 и ДС = 0, значение а которой равно 256,

для каждой входной разности только одна выходная разность встречается с вероятностью р = 4/256, все остальные выходные разности имеют вероятность появления р = 2/256,

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

значение входной разности ДА = 197 остается неизменным на выходе с вероятностью р = 4/256, остальные входные разности либо не могут оставаться неизменными либо имеют вероятность в два раза меньшую

Другим, оказывающим серьезное влияние на изменение диффереациалов в процессе прохождения данных через алгоритм шифрования, является преобразование перемешивания столбцов (MixCoiumns) При этом преобразование MixCoiumns является линейным и не оказывает влияние на вероятности дифференциалов Рассматривая его, необходимо помнить, что разность рассматриваемся как сумма по модулю 2 между двумя состояниями текста, то есть ДХ = X Ф X' В этом случае 2*ДХ =■ 2*Х © 2*Х' и 3*&Х - 3*Х ® 3*Х' Принимая это во внимание, были выявлены правила изменения разности столбцов в процессе прохождения данных через преобразование MixCoiumns При этом рассматривались следующие варианты входных столбцов разностей ненулевое значение имеет всего один байт, одинаковое ненулевое значение имеют 2 байта, ненулевое значение имеют два байт, и при этом ненулевые байты имеют разные значение, 3 ненулевых байта, имеющих одинаковое значение, все байты равны между собой и отличны от О

На основании выявленных свойств в диссертации на примере 4 раундов шифрования показано, каким образом можно строить дифференциалы С учетом этого разработан алгоритм проведения ДК

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

ТТ - . , О 197 О О

Пусть значение входной разности задается массивом Двх и имеет вид 4~= 0 о 197 о

А значение открытого сообщения X определяется с помощью массива ° °

маски X_mask, который в общем виде можно представить следующим образом

'S« S!tt S<>2 8,. -S,, S« S,, s* Sjt Sj, S„ 9K Ssl Sz, 8„

В массиве X_mask байты обозначены как S, как принято в стандарте AES Полужирным шрифтом выделены те значения, которые могут изменяться При этом сразу следует отметить, что в выбираемой паре открытых текстов X и X' разниться могут лишь три байта на главной диагонали (от левого верхнего угла к правому нижнему углу) Остальные байты должны имел, одинаковые значения, так как их разность равна 0 Поэтому для элементов Soi, S0j, S№, Su, S2i, S30, S» можно ввести массив счетчиков S_co«nt(7J, значение каждого из которых будет определять текущее значение байга Для определения значений трех байтов на главной диагонали воспользуемся 32-битовой переменной S _mam которую будем изменять от О до 2"-1, с тем, чтобы из младших 24 битов извлечь значения Soo, Su, S22 Это необходимо в связи с тем,

X таак =

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

1 Начальное значение переменной S_mam полагается равным О

2 Начальное значение элементов массива счетчика S count полагаются равными нулю

3 Из значения S_main выделяются значения байтов главной диагонали

S,» = (S_mam»16) & 255, S,¡ = ÍS_mam»8) & 255, S22 = S_mam & 255,

4 Определяется первый открытый текст X следующим образом

Si, S_cowt[0¡ S_etKjnt{1] о "} S.CMntpî S,, o s_eounq3j

о г„£мM«) s* о 1 S.ceunttSl о о s_count(eJ

5 Определяется второй открытый текст X' X' = X © Xmask

6 В результате шифрования сообщений X и X' не секретном ключе с помощью стандарта AES получаются соответственно шифрованные сообщения Y и У*

7 Определяется значение выходной разности Л Y ДY = Y Ф Y'

8 Если в ДУ есть 4 нулевых байта (в соответствии с заданным дифференциалом), то выполняется следующий пункт, иначе осуществляется переход к пункту 16

9 Значение 8 бит секретного ключа К принимается равным О

10 Для каждого байта сообщений Y и У' определяется Y © К и У' ® К

11 Получаются значения ISB(Y©K) ISB(Y'©K) (ISB - обратное преобразование замены байтов)

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

13 Берется следующее значение ключа К путем увеличения его на 1 К = К + 1

14 Если К<256, то осуществляется переход к пункту 10

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

16 Если проанализированы не все возможные комбинации счетчиков, то увеличивается значение счетчика S[count] (при достижении максимального значения 255 значение младшего счетчика становится равным 0, а значение старшего увеличивается на 1) и происходит переход к пункту 4

17 Берется очередное значение S_count путем увеличения на 1

18 Если значение S_count равно 224, то по текущему значению счетчиков ключа определяется возможное значение секретного ключа и алгоритм завершает свою работу

Для реализации представленного алгоритма в параллельном виде необходимо определить способ межпроцессорного распределения данных С этой целью была введена переменная S_main Ее значение должно быть не больше 224 Распределять данные можно по этой величине с помощью вышеприведенного универсального алгоритма В этом случае изменятся второй пункт (начальное значение S_main будет полагаться равным не 0, а значению начала диапазона анализа Db для каждого из процессоров) и последний пункт (значение S_mam будет сравниваться не с максимально возможным, а со значением конца диапазона анализа De для каждого из процессоров) представленного алгоритма

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

В заключении перечисляются результаты, рассматриваются пути развития ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ Основные теоретические и практические результаты, полученные к ходе работы над диссертацией, заключаются в следующем

1 Выявлены дифференциальные свойства следующих криптографических примитивов АБШ различных вариаций блоков замены, целочисленного сложения по модулю 2", побайтного преобразования столбцов

2 Разработаны и реализованы алгоритмы поиска правильных пар текстов по заданному дифференциалу для n-раундовых (п определяется числом раундов алгоритма) шифров DES, AES и ГОСТ

3 Разработаны и реализованы алгоритмы поиска секретного ключа на основе найденных правильных

пар текстов для n-раундовых (п по числу раундов алгоритма) шифров DES, AES и ГОСТ

4 Разработаны и реализованы алгоритмы распределения данных для проведения анализа п-раундового (п<16) алгоритма DES с помощью РМВ

5 Предложен способ снижения числа анализируемых текстов алгоритма шифрования DES для повышения скорости анализа

6 Экспериментально показано, что для алгоритма DES с помощью РМВ наблюдается практически линейный рост ускорения анализа.

7 Разработан рекурсивный алгоритм поиска наиболее вероятных дифференциалов для алгоритма шифрования ГОСТ 28 J 47-89, учитывающего различные варианты заполнения блоков замены

8 Разработан и реализован параллельный алгоритм поиска наиболее вероятных дифференциалов для алгоритма шифрования ГОСТ 28147-89, учитывающего различные варианты заполнения блоков замены с учетом статического и динамического распределения данных и межпроцессорных взаимодействий при выявлении дифференциала, обладающего максимальной вероятностью

9 Для алгоритма шифрования ГОСТ 28147-89 показано влияние на скорость вычислений таких параметров, как число процессоров, число раундов шифрования, способ распределения данных, начальное значение пороговой вероятности

10 Разработан параллельный алгоритм проведения ДК алгоритма AES с учетом межпроцессорного распределения данных и взаимодействия процессов при нахождении ключа шифрования

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

1 Бабенко JIК Мишустина (Ищукова) Е А Применение методов криптоанализа для исследования стойкости современных блочных шифров II Тезисы докладов X всероссийской научной конференции "Проблемы информационной безопасности в системе высшей школы", M МИФИ, 2003r# У^

2 Бабенко Л К Мишустина (Ищукова) Е А Методическое пособие по изучению современных методов криптоанализа // Таганрог ТРТУ, 2003, С.

3 Бабенко Л К Мишустина (Ищукова) Е А Применение современных методов криптоанализа при проектировании скоростных блочных шифров //журнал «Телекоммуникации», M «Наука и технологии», 2003, у /ЗГ— ZJ

4 Бабенко Л К Мишустина (Ищукова) Е А Разработка комплекса яабораторно-пракгических работ по изучению современных методов криптоанализа - Известия ТРТУ Тематический выпуск Материалы V Международной научной конференции «Информационная безопасность», Таганрог Изд-во ТРТУ, 2003, №4 (33), с 280-282

5 Бабенко Л К Ищукова Е А Параллельная реализация метода дифференциального криптоанализа // Материалы VI Международной научно-практической конференции «Информационная безопасность», Таганрог ТРТУ, 2004, tf. Si"

6 Бабенко Л К Ищукова Е А Тестирование алгоритмов шифрования с помощью многопроцессорных вычислительных систем // Материалы VII международной научно-практической конференции «Информационная безопасность» -TaraHpoi Изд-во ТРТУ, 2005 -с 229-230

7 Бабенко Л К Ищукова Е А Современны® алгоритмы блочного шифрования и методы их анализа // Москва, «Гели-ос АРВ», 2006 г - 376 с

8 Ищукова Е А Дифференциальный криптоанализ алгоритма шифрования DES с использованием распределенных вычислений // VIII Всероссийская научная конференция студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления», Таганрог Изд-во ТРТУ, 2006 г, с 340 - 341

9 Бабенко Л К Ищукова Е А Статистические метода анализа аяторлтмов блочного шифрования и их основные особенности // Информационные системы и технологии (IST'2006) третья Международная конференция (Минск, 1-3ноября2006г) -С 62-67

10 Бабенко Л К Ищукова Е А Особенности дифференциального криптоанализа алгоритма AES // Известия ТРТУ 7 Тематический выпуск Материалы VIII Международной научно-практической конференции «Информационная безопасность»-Таганрог,3-7июня -С 183-185

11 Ищукова Е А Применение рекурсивного алгоритма поиска в Б-деревьях для дифференциального криптоанализа алгоритма шифрования ГОСТ 28147-89 // Материалы IX Международной научно-практической конференции «Информационная безопасность» Часть 2 - Таганрог, Изд-во ТТИЮФУ2007-С 92-97

Личный вклад автора в работах, написанных в соавторстве, состоит в следующем [1,9]- систематизация знаний по применению метода ДК АБШ, [2, 4] -выявление характерных особенностей анализа алгоритмов блочного шифрования, разработка алгоритмов и реализация программ для проведения лабораторных работ, [3] - разработка алгоритма проведения ДК криптографических примитивов на основе управляемых подстановочных операций, [5] - разработка алгоритма межпроцессорного распределения данных для проведения ДК, [6] - разработка алгоритма проведения ДК АБШ DBS с использованием РМВ, [7] - выявление характерных особенностей применения метода ДК, [10] - анализ основных криптографических составляющих алгоритма шифрования AES

"С"

Формат 60x84 1/16 Бумага офсетная

Печать офсетчая Уел п л - 1

Заказ №Д8Э Тираж 100 экз

Издательство Технологического института ЮФУ ГСП 17А, Таганрог, 28, Некрасовский, 44 Типография Технологического института ЮФУ ГСП 17А, Таганрог, 28, Энгельса, 1

Обозначения и сокращения.

Введение.

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

1.1 Метод полного перебора.

1.2 Парадокс Дней Рождений.

1.3 Метод дифференциального криптоанализа.

1.4 Параллелизм в задачах криптоанализа.

1.4.1 Теоретические основы оценки эффективности параллельных алгоритмов.

1.4.2 Разработка универсального алгоритма проведения ДК алгоритмов блочного шифрования с помощью РМВ.

1.4 Выводы.

2. Разработка последовательных алгоритмов проведения дифференциального криптоанализа криптосистем, построенных по схеме Фейстеля.

2.1 Разработка алгоритмов проведения дифференциального криптоанализа алгоритма шифрования DES.

2.1.1 Исходные сведения о дифференциальном криптоанализе алгоритма шифрования DES.

2.1.2 Разработка алгоритма построения таблиц анализа для S-блоков замены.

2.1.3 Выявление основных свойств таблиц анализа для S-блоков замены.

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

2.1.4 Разработка алгоритмов проведения ДК алгоритма шифрования DES.

2.1.5 Анализ 6 раундов алгоритма DES с использованием наиболее вероятных дифференциалов.

2.2 Разработка алгоритмов для проведения ДК алгоритма шифрования ГОСТ 28147-89 в режиме простой замены.

2.2.1 Анализ циклического сдвига.

2.2.2 Анализ операции сложения двух чисел по модулю 2".

2.2.3 Анализ преобразования с помощью S-блоков замены.

2.2.4 Разработка алгоритма анализа алгоритма ГОСТ 28147-89.

2.3 Выводы.

3. Разработка параллельных алгоритмов дифференциального криптоанализа алгоритмов блочного шифрования, построенных по схеме Фейстеля.

3.1 Разработка алгоритмов проведения ДК алгоритма шифрования DES с использованием РМВ.

3.2 Расчет эффективности разработанных алгоритмов для алгоритма шифрования DES.

3.2.1 Экспериментальные данные для алгоритма шифрования DES.

3.3 Разработка алгоритмов проведения ДК алгоритма шифрования ГОСТ 28147-89 с использованием РМВ.

3.3.1 Трудоемкость перебора.

3.3.2 Организация межпроцессорных обменов.

3.4 Экспериментальная оценка эффективности разработанных алгоритмов для ГОСТ 28147-89.

3.5 Выводы.

4. Дифференциальный криптоанализ стандарта шифрования данных AES.

4.1 Стандарт шифрования данных AES.

4.1.1 Раундовое преобразование.

4.1.2 Алгоритм выработки ключей.

3.1.3 Функция зашифрования.

4.1.4 Функция обратного дешифрования.

4.1.5 Функция прямого дешифрования.

4.2 Анализ основных преобразований, входящих в состав стандарта AES.

4.2.1. Анализ преобразования SubBytes().

4.2.2 Анализ преобразования MixColumns().

4.3 Построение многораундовых характеристики для стандарта AES и эффективность их применения.

4.6 Разработка алгоритмов для проведения дифференциального криптоанализа стандарта AES с использованием РМВ.

4.7 Выводы.

Актуальность. Ключевой задачей криптографии является создание стойких алгоритмов шифрования. Любой конструируемый алгоритм подвергается тщательному анализу с целью выявления его слабых мест и возможности взлома. Алгоритм является относительно стойким до тех пор, пока не будут обнаружены методы и пути его анализа, позволяющие получить секретный ключ шифрования значительно быстрее, чем это можно сделать с использованием метода «грубого перебора» [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; Объект исследования. Объектом исследования являются: особенности использования дифференциального криптоанализа при оценке стойкости АБШ; - зависимость времени анализа блочных шифров от числа процессоров при использовании РМВ.

Методы исследования основаны на использовании теории вероятностей, теории конечных полей, теории множеств, теории кодирования информации, а также на современных методологиях построения 8 программных комплексов и систем. При разработке алгоритмов анализа в качестве инструментальных средств учитывались особенности применения стандарта передачи данных MPI (Message Passing Interface).

Научная новизна полученных в диссертации основных результатов заключается в следующем.

1. Исследованы дифференциальные свойства основных криптографических примитивов, входящих в состав современных алгоритмов блочного шифрования, получены численные результаты анализа таблиц замены и правила определения вероятности дифференциала для операции целочисленного сложения по модулю 2", которые являются неотъемлемой частью проведения ДК АБШ.

2. Разработаны алгоритмы поиска правильных пар текстов по заданному дифференциалу для алгоритмов шифрования DES, AES и ГОСТ 2814789.

3. На основе метода дифференциального криптоанализа, предложенного Э. Бихамом и А. Шамиром, разработаны последовательные и параллельные алгоритмы для проведения анализа n-раундового (п<16) алгоритма DES.

4. Разработан рекурсивный алгоритм поиска дифференциалов, обладающих максимальной вероятностью, для алгоритма шифрования ГОСТ 28147-89, учитывающего различные варианты заполнения для блоков замены, для отбора правильных пар текстов при дальнейшем анализе.

5. Разработан параллельный алгоритм поиска наиболее вероятных дифференциалов для алгоритма ГОСТ 28147-89 (по пункту 4) с учетом статического и динамического распределения данных и межпроцессорных взаимодействий при выявлении дифференциала с максимальной вероятностью.

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

7. Результаты экспериментов, подтверждающие пункты 1 - 5. В частности:

7.1. Проведен анализ 6 раундов алгоритма DES с использованием наиболее вероятных значений дифференциалов. Показано, что на 2-процессорной системе с частотой процессоров 1,41 ГГц время анализа в среднем составляет 7,5 минут, на 16-процессорной - 56 секунд.

7.2. Проведен полный анализ диапазона входных разностей для алгоритма DES, состоящего из 8, 10, 12, 14 и 16 раундов на ш-процессорном кластере (ш<16) с использованием разработанной методики. Показано, что при увеличении числа процессоров наблюдается практически линейный рост ускорения времени анализа. Кроме того, показано, что процент текстов, полностью соответствующих схеме преобразования заданного дифференциала, от общего числа найденных правильных пар текстов, лежит в диапазоне от 80% до 100%, что гарантирует успех анализа.

7.3. Проведен анализ 16-раундового алгоритма DES с использованием 16-процессорного кластера (частота 1,41 ГГц). Показано, что время работы программы составило 24 часа 13 минут.

7.5. Проведены тестовые испытания анализа алгоритма шифрования ГОСТ 28147-89 для различных сочетаний следующих параметров: числа раундов шифрования, начального значения пороговой вероятности, количества процессоров, способа распределения данных. Показано, что при задании ненулевого значения пороговой вероятности, скорость вычислений в среднем возрастает в 1,285 раз. Показано, что при использовании 16 процессоров для анализа со статическим распределением данных время вычислений сокращается в 2,88 раза, а с динамическим - в 4,4 раза по сравнению с такими же расчетами на двухпроцессорной системе. Показано, что для алгоритма с динамическим распределением данных до 8 процессоров наблюдается линейный рост ускорения.

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

1. Проведен предварительный анализ алгоритмов DES, AES и ГОСТ 28147-89, результаты которого систематизированы в виде таблиц и основных положений. Это позволяет использовать полученные результаты в дальнейшем для непосредственного анализа зашифрованных данных без проведения подготовительных работ.

2. Разработаны и реализованы алгоритмы, предназначенные для анализа данных, зашифрованных с помощью алгоритмов DES, AES и ГОСТ 28147-89. Разработанные алгоритмы позволяют при определенных условиях выявлять секретный ключ шифрования, что необходимо для оценки их стойкости.

3. Ценность разработки подтверждает использование комплекса лабораторных работ, разработанных на основе предложенных алгоритмов, в учебном процессе кафедры Безопасности Информационных Технологий Таганрогского Технологического Института Южного Федерального Университета (ТТИ ЮФУ), как базовое средство обучения по курсу «Криптографические методы и средства обеспечения информационной безопасности».

Основные положения, выносимые на защиту. На защиту выносятся:

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

2. Разработанный алгоритм поиска правильных пар текстов по заданному дифференциалу для алгоритма шифрования DES дает результат с вероятностью от 0,8 до 1, что гарантирует успех дальнейшего анализа.

3. Разработанный параллельный алгоритм для проведения анализа п-раундового (п<16) алгоритма DES при увеличении числа процессоров обеспечивает линейный рост ускорения.

4. Разработанный алгоритм анализа АБШ ГОСТ 28147-89 позволяет проводить его с различными значениями Б-блоков замены.

5. Разработанный параллельный алгоритм поиска наиболее вероятных дифференциалов для алгоритма ГОСТ 28147-89 в среднем имеет быстродействие 1,285 при задании ненулевого значения пороговой вероятности.

6. Разработанный параллельный алгоритм поиска наиболее вероятных дифференциалов для алгоритма ГОСТ 28147-89 с использованием динамического распределения данных обеспечивает линейный рост ускорения при увеличении числа процессоров до 8. Использование результатов работы. Результаты, полученные в ходе работы над диссертацией, используются:

1. В гранте РФФИ 06-07-89010-а «Разработка методов и моделей биометрических криптосистем на основе голосового пароля»

2. В гранте РФФИ 04-07-90137-в «Исследование и разработка моделей, методов и средств обнаружения атак»

3. В учебном процессе в Технологическом Институте Южного Федерального Университета в г. Таганроге (ТТИ ЮФУ) на кафедре Безопасности Информационных Технологий в дисциплине «Криптографические методы и средства обеспечения информационной безопасности».

Использование результатов диссертационной работы подтверждено актами об использовании.

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

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

1. На международной научно-практической конференции «Информационная безопасность» (ТРТУ (ТТИ ЮФУ), г. Таганрог, 2003-2007).

2. На международной научно-практической конференции и Российской научной школе молодых ученых и специалистов "Системные проблемы качества, математического моделирования, информационных и электронных технологий", 1-12 октября 2003 г., г. Сочи

3. На всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (ТРТУ, г.Таганрог, 2005,2006).

4. На всероссийской научной конференции «Проблемы информационной безопасности в системе высшей школы» (МИФИ, г. Москва, 20032004).

5. На 3-ей Международной конференции «Информационные системы и технологии» (IST'2006), Минск.

Публикации. Результаты, полученные в работе, нашли отражение в 20 печатных работах, среди них 8 тезисов, 7 статей, 3 лабораторных практикума, 1 методическое пособие и 1 учебное пособие, рекомендованное УМО вузов РФ. Кроме того, имеется 2 свидетельства об официальной регистрации программ для ЭВМ (№2003611519 и №2003611520).

Объем и структура диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 71 наименование, двух приложений. Основной текст диссертации изложен на 173 страницах, включая 43 рисунка и 30 таблиц.

Основные результаты работы опубликованы в виде статей и тезисов докладов [57, 58, 60, 63, 64, 67, 68, 70, 71], а также в виде учебного пособия [13].

Работа выполнялась при поддержке Российского фонда фундаментальных исследований: гранты №06-07-89010-а «Разработка методов и моделей биометрических криптосистем на основе голосового пароля» и №04-07-90137-в «Исследование и разработка моделей, методов и средств обнаружения атак»

Заключение

В работе исследованы криптографические примитивы, входящие в состав большинства алгоритмов блочного шифрования. Представлены разработанные последовательные и параллельные алгоритмы применения метода дифференциального криптоанализа к анализу стандартов шифрования DES, AES и ГОСТ 28147-89.

Часть алгоритмов реализована в виде отдельных программных модулей и может быть использована для различных конфигураций алгоритмов DES и ГОСТ 28147-89 как на однопроцессорных, так и на многопроцессорных вычислительных системах.

Для осуществления распределенных вычислений был использован пакет прикладных программ MPICH 1.2.5, реализованный на основе стандарта «Интерфейса передачи сообщений» (Message Passing Interface).

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

1. Выявлены дифференциальные свойства следующих криптографических примитивов АБШ: различных вариаций блоков замены, целочисленного сложения по модулю 232, побайтного преобразования столбцов

2. Разработаны и реализованы алгоритмы поиска правильных пар текстов по заданному дифференциалу для n-раундовых (п определяется числом раундов алгоритма) шифров DES, AES и ГОСТ 28147-89.

3. Разработаны и реализованы алгоритмы поиска секретного ключа на основе найденных правильных пар текстов для n-раундовых (п определяется числом раундов алгоритма) шифров DES и ГОСТ 28147-89.

4. Разработаны и реализованы алгоритмы распределения данных для проведения анализа n-раундового (п<16) алгоритма DES с помощью РМВ.

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

6. Экспериментально показано, что для алгоритма DES с помощью РМВ наблюдается практически линейный рост ускорения времени анализа при увеличении числа используемых процессоров.

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

8. Разработан рекурсивный алгоритм поиска наиболее вероятных дифференциалов для алгоритма шифрования ГОСТ 28147-89, учитывающего различные варианты заполнения блоков замены.

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

10. Для алгоритма шифрования ГОСТ 28147-89 показано влияние на скорость вычислений таких параметров, как: число процессоров, число раундов шифрования, способ распределения данных, начальное значение пороговой вероятности.

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

1. Бабенко J1.K., Методическое пособие: Ведение в специальность «Организация и технология защиты информации» Таганрог: ТРТУ, 1999, №2800

2. Е. Biham, A. Shamir: "Differential Cryptanalysis of the Full 16-round DES", Crypto'92, Springer-Velgar, 1998, p.487

3. E. Biham, A. Shamir: "Differential Cryptanalysis of DES-like Cryptosystems", Extended Abstract, Crypto'90, Springer-Velgar, 1998, p.2

4. Шнайер Б., Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: Издательство ТРИУМФ, 2002.

5. Бабенко JI.K. Мишустина (Ищукова) Е.А. Программа для проведения лабораторной работы по дифференциальному криптоанализу -Свидетельство об официальной регистрации программ для ЭВМ №2003611519.- М.: Роспатент,- 25.06.03г.

6. Бабенко JI.K. Мишустина (Ищукова) Е.А. Программа для проведения лабораторной работы по линейному криптоанализу -Свидетельство об официальной регистрации программ для ЭВМ №2003611520.- М.: Роспатент,- 25.06.03г.

7. Бабенко JI.K. Мишустина (Ищукова) Е.А. Методическое пособие по изучению современных методов криптоанализа Таганрог: ТРТУ, 2003.

8. Бабенко JI.K. Мишустина (Ищукова) Е.А. Разработка комплекса лабораторно-практических работ по изучению современных методов криптоанализа Известия ТРТУ. Тематический выпуск. Материалы V

9. Международной научной конференции «Информационная безопасность», Таганрог: Изд-во ТРТУ, 2003, №4 (33), с.280-282

10. Бабенко JI.K. Ищукова Е.А. Лабораторный практикум. Изучение методов линейного и дифференциального криптоанализа блочных шифров, построенных по принципу сети SPN Таганрог: ТРТУ, 2004. №3667

11. Столлингс В., Криптография и защита сетей: принципы и практика, 2-е изд.: Пер. с англ. М,: Издательский дом «Вильяме», 2001.

12. Грушо A.A., Тимонина Е.Е., Применко Э.А., Анализ и синтез криптоалгоритмов. Курс лекций. Йошкар-Ола, издательство МФ МОСУ, 2000.

13. Бабенко JI.K. Ищукова Е.А. Современные алгоритмы блочного шифрования и методы их анализа Москва, «Гелиос АРВ», 2006 г.

14. М. Matsui: "Linear Cryptanalysis Method for DES Cipher", Advances in Cryptology EUROCRYPT'93, Springer-Verlag, 1998, p.386.

15. Mitsuru Matsui, "The First Experimental Cryptanalysis of the Data Encryption Standard", Crypto'94, Springer-Velgar, 1998, p.l

16. Чмора А.Л., Современная прикладная криптография. 2-е изд., -M.: Гелиос АРВ, 2002.

17. Шпаковский Г., Серикова Н., Программирование для многопроцессорных систем в стандарте MPI, Минск, БГУ,2002.

18. Немнюгин С., Стесик О., Параллельное программирование для многопроцессорных вычислительных систем, Санкт-Петербург, «БХВ-Петербург», 2002.

19. Howard M.Heys, "A Tutorial on Linear and Differential Cryptanalysis"

20. Burton S. Kaliski Jr., Yiqun Lisa Yin, "On Differential and Linear Cryptanalysis of the RC5 Encryption Algorithm", Crypto'95, Springer-Velgar, 1998, p.171

21. Ishai Ben-Aroya, Eli Biham, "Differential Cryptanalysis of Lucifer", Crypto'93, Springer-Velgar, 1998, p.18738. citeseer.ni.nec.com/bihamO 1 linear.html E.Biham, O.Dunkelman, N.Keller, "Linear Cryptanalysis of Reduced Round Serpent"

22. E. Biham, A. Shamir, "Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer", Extended Abstract, Crypto'91, Springer-Velgar, 1998, p. 156

23. A. Shimizu, S. Miyaguchi, "Fast Encipherment Algorithm FEAL", Eurocrypt '87, Springer-Velgar, 1998, p.267

24. E.Biham, A.Shamir, "Differential Cryptanalysis of Feal and N-Hash", Crypto'87, Springer-Velgar, 1998, p. 151. Birukov A., 'Thesis"52. http://www.secinf.net/uplarticle/4/rc6.pdf. Riverst R., Robshaw, 'The RC6 Block Cipher'

25. Грегори P. Эндрюс, Основы многопоточного, параллельного и распределенного программирования.: Пер. с англ. М.: Издательский дом «Вильяме», 2003. - 512 с.54. http://www.nestor.minsk.bv/sr/2003/02/30208.html. Цилюрик О., QNX: многомашинные вычисления.

26. Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ. М.:МЦНМО, 2001. 960 е., 263 ил.

27. Антонов А.С., Параллельное программирование с использованием технологии MPI: Учебное пособие. М.: Изд-во МГУ, 2004. -71с.m *

28. Бабенко JI.K. Мишустина (Ищукова) Е.А.Лабораторный практикум по изучению современных методов криптоанализа // Таганрог: ТРТУ, 2003.

29. Бабенко Л.К. Мишустина (Ищукова) Е.А. Применение современных методов криптоанализа при проектировании скоростныхблочных шифров // журнал «Телекоммуникации», М.: «Наука и технологии», 2003, №7

30. Бабенко Л.К. Ищукова Е.А. Параллельная реализация метода дифференциального криптоанализа // Материалы VI Международной научно-практической конференции «Информационная безопасность», Таганрог: ТРТУ, 2004.

31. Бабенко Л.К. Ищукова Е.А. Тестирование алгоритмов шифрования с помощью многопроцессорных вычислительных систем // Материалы VII международной научно-практической конференции «Информационная безопасность». Таганрог: Изд-во ТРТУ, 2005. - с. 229 -230

32. Ищукова Е.А. Разработка инструментария для создания и анализа новых алгоритмов блочного шифрования // Материалы VIII Международной научно-практической конференции «Информационная безопасность». Часть 2. Таганрог, 3-7 июня. - С. 65-66.

33. Ищукова Е.А. Разработка и внедрение новых методик для подготовки специалистов по защите информации // Материалы VIII Международной научно-практической конференции «Информационная безопасность». Часть 2. Таганрог, 3-7 июня. - С. 231-233.т

34. Бабенко JI.K. Ищукова Е.А. Статистические методы анализа алгоритмов блочного шифрования и их основные особенности // Информационные системы и технологии (IST'2006): третья Международная конференция (Минск, 1-3 ноября 2006г.). С. 62-67.

35. Бабенко JI.K. Ищукова Е.А. Применение распределенных вычислений к задачам теории чисел // Информационные системы и технологии (IST'2006): третья Международная конференция (Минск, 1-3 ноября 2006г.). С. 57-62.

36. Бабенко JI.K. Ищукова Е.А. Особенности дифференциального криптоанализа алгоритма AES // Известия ТРТУ 7. Тематический выпуск. Материалы VIII Международной научно-практической конференции «Информационная безопасность».- Таганрог, 3-7 июня. С. 183-185

37. Ростовцев А.Г., Маховенко Е.Б., Теоретическая криптография. -СПб.: АНО НПО «Профессионал, 2005. 480 с.

38. Маховенко Е.Б., Теоретико-числовые методы в криптографии: Учебное пособие М.: Гелиос АРВ, 2006. - 320 с.

39. Венбо Мао, Современная криптография: теория и практика (Modern Cryptography: Theory and Practice). — M.: «Вильяме», 2005. — с. 768.

40. Новиков Ф.А., Дискретная математика для программистов. Учебник для вузов. 2-е изд. СПб.Ж Питер, 2007. - 364 с.