Дифференциальный криптоанализ. 
Криптографическая защита информации: симметричное шифрование

Метод дифференциального криптоанализа впервые был предложен в начале 90-х гг. прошлого века Э. Бихамом и А. Шамиром для анализа алгоритма шифрования DES. Хотя в книге Б. Шнайсра [2] упоминается о том, что разработчики алгоритма DES знали о возможности такого анализа еще во время разработки алгоритма в 70-х гг. XX в., широкая общественность узнала о дифференциальном криптоанализе именно из работ [19, 20]. Метод ДК оказался первым методом, позволяющим взломать DES при оценке сложности задач менее 2⁵⁵. Согласно [19], с помощью данного метода можно провести криптоанализ DES при усилиях порядка 2³⁷, но при наличии 2⁴⁷ вариантов избранного открытого текста. Хотя 2⁴⁷, очевидно, значительно меньше, чем 2⁵⁵, необходимость при этом иметь 2⁴⁷ вариантов избранного открытого текста превращает данный вариант схемы криптоанализа в чисто теоретическое упражнение [6]. Это связано с тем, что метод ДК был известен в момент разработки DES, но засекречен по очевидным соображениям, что подтверждается публичными заявлениями самих разработчиков [2]. В работе [20] показано, что если поменять порядок следования блоков замены в алгоритме шифрования DES или использовать другие наборы таблиц подстановок и перестановок, то алгоритм становится сразу намного слабее и может быть взломан менее чем за половину времени, требуемого для анализа алгоритма DES с помощью полного перебора. Это показывает значимость знания возможных путей анализа разрабатываемого алгоритма.

С помощью метода дифференциального криптоанализа (differential cryptanalysis), предложенного Э. Бихамом и А. Шамиром [19, 20], сложность анализа сократилась до 2³⁷. Однако при этом для проведения анализа необходимо было иметь 2³⁷ особым образом подобранных текстов, зашифрованных на одном и том же секретном ключе. Несмотря на накладываемые ограничения в использовании новых предложенных методов анализа — это был прорыв! Дальнейшее развитие этого метода показало возможность его применения к целому классу различных видов шифров, позволило выявить слабые места многих используемых и разрабатываемых алгоритмов шифрования. Сегодня этот метод, а также некоторые его производные, такие как метод линейно-дифференциальный, метод невозможных дифференциалов, метод бумеранга, широко используются для оценки стойкости вновь создаваемых шифров. Именно поэтому специалисту по защите информации необходимо иметь представление о механизмах анализа шифров с использованием современных методов криптоанализа.

Само название дифференциальный криптоанализ происходит от английского слова difference, т. е. разность. Именно поэтому в отечественной литературе этот вид анализа еще иногда называют разностным методом. Исходя из названия, можно понять, что при рассмотрении возможности анализа некоторого блочного алгоритма шифрования ученым пришло в голову использовать нс отдельные тексты, а пары текстов. Понятно, что два текста будут иметь различия в некоторых позициях. Для того чтобы определить это различие, достаточно пару текстов сложить между собой по модулю 2. Результат такого сложения даст на выходе значение 0 в тех позициях, в которых исходные тексты были равны между собой, и соответственно значение 1 в тех позициях, в которых исходные тексты отличались. Например, рассмотрим два 4-битовых сообщения: X = ООП и X' = 1010. В результате сложения текстов X и X' была получена разность АХ = 1001, полученное значение АХ принято называть дифференциалом, или разностью. В дифференциальном криптоанализе значение разности (дифференциала) принято обозначать символом Д. Разность, полученная в результате сложения текстов X и X', показывает, что во второй и третьей позициях исходные сообщения X и X' были равны, а в первой и четвертой отличались друг от друга.

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

Разность (дифференциал) — результат поразрядного сложения по модулю 2 (операция XOR) двух отдельно шифруемых на одном и том же секретном ключе текстов, находящихся в одной и гой же позиции рассматриваемого алгоритма шифрования.

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

Выходная разность (выходной дифференциал) — разность, образованная на выходе рассматриваемого преобразования.

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

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

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

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

Рис. 102. Основные значения дифференциального критоанализа.

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

• 1. Нахождение для алгоритма шифрования характеристик, обладающих максимальными характеристиками. Поиск характеристик ведется на основе дифференциальных свойств нелинейных криптографических примитивов, входящих в состав алгоритма шифрования.
• 2. Поиск правильных пар текстов с использованием найденных характеристик.
• 3. Анализ правильных пар текстов и накопление статистики о возможных значениях секретного ключа шифрования.

Первый пункт, заключающийся в поиске лучших характеристик, для большинства алгоритмов выполняется единожды и является теоретической задачей. Значения характеристик полностью зависят от структуры алгоритма шифрования и используемых криптографических примитивов. Иначе дело обстоит лишь с теми алгоритмами, которые обладают нефиксированными элементами. К таким алгоритмам можно, например, отнести алгоритм шифрования ГОСТ 28 147–89, у которого S-блоки замены могут выбираться произвольным образом. Для таких алгоритмов поиск характеристик необходимо каждый раз начинать сначала, основываясь на дифференциальных свойствах выбранных S-блоков. Для автоматизации процесса анализа можно разработать алгоритм поиска лучших характеристик, основываясь на алгоритмах поиска по дереву. Для таких алгоритмов можно использовать параллельные модели для ускорения поиска характеристик.

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

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

Более подробно о дифференциальном криптоанализе различных блочных алгоритмов шифрования, а также о различных производных данного метода можно прочитать в работах [7, 9, 19, 20].