Научный журнал

Современные наукоемкие технологии

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

Рис. 1. Структура шифра MYSTY1

Рис. 2. Схема выработки подключей

Выборка подключей

Метод дифференциального криптоанализа впервые был предложен в начале 1990-х гг. Э. Бихамом и А. Шамиром для анализа алгоритма шифрования DES. Хотя в книге Б. Шнайера упоминается о том, что разработчики алгоритма DES знали о возможности такого анализа еще во время разработки алгоритма в 1970-х гг., широкая общественность узнала о дифференциальном криптоанализе именно из работ [4, 5]. С помощью метода дифференциального криптоанализа сложность анализа алгоритма DES сократилась до 237. Дальнейшее развитие этого метода показало возможность его применения к целому классу различных видов шифров, позволило выявить слабые места многих используемых и разрабатываемых алгоритмов шифрования. Сегодня этот метод, а также некоторые его производные, такие как метод линейно-дифференциальный, метод невозможных дифференциалов, метод бумеранга, широко используются для оценки стойкости вновь создаваемых шифров [6].

Анализ S-блоков. Число раундов MISTY1 должно быть всегда кратным 4, рекомендуемым же является MISTY1 с 8 раундами. В целях наилучшего понимания механизмов шифра и его подверженности дифференциальным атакам на старте были приняты следующие решения. Рассматривать упрощенную модель MISTY1. Для этого убрать из алгоритма шифра все FL-функции. Сократить рекомендуемые 8 раундов до четырех (тем самым мы не будем нарушать целостности шифра, которая также обеспечивается кратностью, но проанализируем более короткую версию шифра).

Начальными элементами, от которых следует отталкиваться при дифференциальном анализе, являются нелинейные блоки. В шифре MYSTY1 есть два блока замены: S7 и S9. Первый этап дифференциального анализа заключался в построении таблиц вероятностей для этих блоков замен. Таблица вероятности представляет собой по горизонтали входящую разность текстов, по вертикали – выходящую разность текстов, а на пересечении вероятность соответствия выходной разности заданной входной разности. Алгоритм анализа дифференциальных свойств нелинейных блоков приведен в работе [7]. В результате анализа было показано, что любая входная разность текстов приводит к любой выходной разности либо с вероятностью 0, либо с вероятностью 2 к 128 или 512 соответственно для блоков S7 и S9. Также важно отметить, что входная разность, равная нулю, с вероятностью 100 % даст на выходе S-блока также нулевую разность.

Анализ функции FI. При анализе функции FI было сделано предположение, что есть такая разность ΔA, которая может отразиться сама в себя. То есть S9(ΔA) = S7(ΔA) = ΔA. Для подтверждения этого факта был разработан алгоритм и проанализированы таблицы с вероятностями для входных-выходных разностей блоков S7 и S9. После анализа S-блоков было обнаружено 33 варианта ΔA, которая отражалась бы сама в себя. На рис. 3 показаны три варианта прохождения входной разности через функцию FI, в случае, когда значение разности после S-преобразования остается неизменным. В первом варианте (рис. 3, а) левая половина разности равна значению ΔA1, правая часть разности равна нулю (Δ0). Во втором варианте (рис. 3, б) левая половина разности равна нулю (Δ0), а правая часть разности равна значению ΔA1. В третьем варианте (рис. 3, в) обе части разности равны значению ΔA1. Для дальнейшего анализа мы будем использовать второй вариант схемы, приведенный на рис. 3, б.

Анализ функции FO. Для построения разностных схем функции FO можно использовать тот же принцип, что и для функции FI. Будем рассматривать случаи, когда преобразование FI оставляет входную разность неизменной. Нами было рассмотрено несколько вариантов построения подобных схем, три из которых представлены на рис. 4. При выборе схемы для дальнейшего анализа мы руководствовались тем, какую ключевую информацию нам позволит извлечь рассматриваемая схема. Так, схема, приведенная на рис. 4, в, позволит нам определить только ключ KOi,2. Вариант, представленный на рис. 4, а, даст нам возможность найти ключи KOi,1 и KOi,3, но строго последовательно, т.е. мы сможем найти KOi,3 и KIi,3 только после того, как найдем KOi,1 и KIi,1. Вариант, представленный на рис. 4, б позволяет найти ключи KIi,2, KOi,2 и KIi,1, KOi,1 независимо друго от друга. Поэтому дальнейший анализ основывается на схеме, представленной, на рис. 4, а.

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

Исходя из вариантов, представленных на рис. 5, можно определить, какую часть секретного ключа можно будет определить с использованием данных разностных схем. Так, с помощью схемы, представленной на рис. 5, а, можно проанализировать блоки FO1 и FO4 параллельно. Блок FO2 не может быть подвергнут анализу из-за нулевой разности, а блок FO3 из-за того, что он зависит от блока FO2. С помощью схемы, представленной на рис. 4, б, можно независимо проанализировать блоки FO1, FO4. После этого можно будет извлечь информацию из блока FO2. Блок FO3 придется пропустить из-за нулевой разности. Схема, представленная на рис. 5 в, является самой малоинформативной, так как имеет в своем составе сразу два блока с нулевой разностью. Выбирая между схемами, представленными на рис. 4, а и б, стоит учесть, что для схемы 4, а, подбор подключей будет проводиться по первому и последнему раунду, а для схемы 4, б, – по первому и второму (последовательно). При этом вероятность нахождения правильных пар текстов для обеих схем составит .

В связи с тем, что для поиска правильных пар текстов, удовлетворяющих заданным вероятностям, необходимо проанализировать большое количество пар текстов, в данном случае целесообразно использовать технологии распределенных многопроцессорных вычислений, такие как MPI и NVIDIA CUDA [8, 9]. Согласно Парадоксу Дней Рождений [10], проанализировав 242 пар текстов, можно найти правильную пару текстов с вероятностью р = 0,5. Экспериментальные данные при поиске дифференциалов для шифра MYSTI1 на основе технологии MPI были получены с использованием семи двухъядерных вычислительных узлов Intel Core i5 – 3320М CPU, 2.60 GHz, 4 Gb RAM. Среднее время обработки 242 пар текстов с использованием 14 процессоров составило в среднем 900 часов (15 дней). При использовании технологии NVIDIA CUDA вычисления производились на ПК Intel i5 2400 NVIDIA GTS 459 8 Gb RAM. Было показано, что при количестве процессоров, равном 1024, среднее время вычислений составляет 640 минут (около 11 часов).

В заключительном этапе анализа был реализован алгоритм поиска битов секретного ключа. Так, для схемы 5, б, был предложен алгоритм, состоящий из трех этапов. На первом этапе, анализируя значения разностей, аналитик может восстановить раундовые подключи К1, К3, К4, К8 и К'1, K'4, K'6, K'7. На втором этапе, используя уже найденные значения подключей, аналитик может восстановить связанные с ними раундовые подключи: К2, К5, К7 и К'3, K'8. К сожалению, в данном случае нельзя получить информацию о раундовых подключах К6 и К'2, K'5 – их можно определить только перебором.

Работа выполнена при поддержке гранта РФФИ № 17-07-00654-а.