Cryptography.Ru >> Основные тенденции развития открытой криптографии (обзор по заказу cryptography.ru)

Поиск |
 | на сайте в Научной сети
Cryptography.Ru >> Общие вопросы | Обзорные статьи
Написать комментарий Добавить новое сообщение
Вперед Вверх Назад
Вперед: Криптографические алгоритмы гаммирования Вверх: Алгоритмическая криптография Назад: Алгоритмическая криптография

Блочные криптографические алгоритмы

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

Исторически первым из двух упомянутых был разработанный в 1990 году израильскими математиками Э.Бихамом и А.Шамиром метод дифференциального криптоанализа. Д.Копперсмит утверждает [Cop92], что этот метод был известен команде разработчиков DES алгоритма еще в начале 70-х годов. Но в то время этот метод был засекречен. Справедливости ради, необходимо отметить, что идея, близкая к методу дифференциального анализа, была опубликована до работы Э.Бихама и А.Шамира в 1990 году С.Мерфи [Mur90]. Работы по данному направлению для каждого анализируемого шифра сводятся к построению набора алгоритмических приемов поиска дифференциальных характеристик для части итераций, имеющих повышенную вероятность. Введем несколько математических обозначений, которые помогут нам перечислить появившиеся в печати работы по развитию этого метода. Пусть [image] -- отображение, реализуемое частью итераций блочного шифра, для которого ищется дифференциальная характеристика. Вероятностью дифференциальной характеристики [image] называют вероятность выполнения следующего равенства

(1)

при случайном равновероятном выборе [image], где [image] -- операция покоординатного суммирования двоичных векторов одинаковой размерности.

Метод дифференциального анализа развивался в следующих направлениях.

  1. Вскоре после изобретения метода дифференциального анализа было отмечено, что изучать соотношение (1) можно и для случая, когда операция покоординатного суммирования [image] заменяется на операцию суммирования по модулю [image], [Ber92].

  2. В 1993 году израильские математики И.Бен-Аройа и Э.Бихам [BeBi93] предложили искать дифференциальные характеристики, считая, что ключ принимает не все возможные значения, а лишь значения из некоторого подмножества. Этот метод получил название метода условных дифференциалов.

  3. В 1994 году датский математик Ларс Кнудсен [Kn94] предложил строить по аналогии с обычным дифференциальным методом криптоанализа метод усеченных дифференциалов. Фактически Кнудсен предлагает "следить" в равенстве (1) лишь за частью (специально выбираемой) бит векторов [image] и [image].

  4. В 1994 году швейцарский криптограф Х.Лаи [Lai94] (см. также [Kn94]) показал, что для построения метода криптографического анализа вместо пар [image] можно использовать более общие конструкции. А именно, он предложил рассматривать пары (дифференциальные характеристики высших порядков) $ (L,d)$, где $ L$ -- некоторое (собственное) подпространство [image], а [image]. При этом вероятностью дифференциальной характеристики такого вида называют вероятность выполнения следующего равенства

  5. В 1998 году Э.Бихам, А.Бирюков и А.Шамир (их результаты опубликованы на год позже в [BiBi99]) заметили, что для построения метода криптографического анализа можно использовать с равным успехом дифференциалы имеющие не повышенную, а пониженную вероятность, а еще лучше -- нулевую вероятность появления (невозможные дифференциалы). Именно этим методом была обнаружена слабость в криптографическом алгоритме Skipjack -- первом и пока единственным алгоритме, авторство которого официально признано Агентством Национальной Безопасности США (считается, что к разработке DES-алгоритма АНБ США отношения не имеет).

  6. Основная задача при "классическом" варианте дифференциального метода криптографического анализа заключается в поиске дифференциальных характеристик, имеющих "большие" вероятности выполнения равенства (1). Для шифров итерационного типа чаще всего построить дифференциальную характеристику, имеющую гарантировано большую вероятность, не удается. В 1999 году Д.Вагнер [Wag99] предложил следующую идею того, как можно использовать "хорошие" дифференциальные характеристики, полученные только для малой части итераций шифра. Пусть отображение [image] является композицией двух отображений [image]; [image]. Пусть, также для отображений [image], [image] известны "хорошие" дифференциальные характеристики [image] и [image] соответственно, т.е. пусть вероятность выполнения равенств [image] и [image] равны [image] и [image] соответственно. Тогда, если выполнено неравенство [image], то для криптографического анализа становится эффективнее использовать характеристики, состоящие из 4 пар вариантов открытого и шифрованного текстов [image], [image], [image], [image], таких, что [image], [image], [image], [image]. Этот метод автор назвал методом бумеранга.

Идея метода линеаризации была предложена японскими специалистами М.Матцуи и А.Ямагиши [MY92] в 1992 году. Как известно, суть метода сводится к итеративной процедуре поиска линейного статистического аналога, реализуемого блочным шифром, имеющего достаточно большое преобладание. Более точно, пусть блочный шифр (или часть его итераций без первого и/или последнего раунда) реализует отображение [image]. Метод линеаризации, по сути, предлагает способ нахождения векторов [image], [image], для которых вероятность выполнения соотношения

равна [image] при случайном выборе [image] (здесь, запись [image] обозначает скалярное произведение над полем из двух элементов двоичных векторов одинаковой длины). Далее, по величине [image] оценивается объем материала, на котором удастся отбраковать ложные варианты ключей.

В 1994 году американцы Бертон Калиски и Матью Робшау [KR94] предложили вместо одного набора векторов [image], [image] использовать несколько таких наборов [image], [image], [image] на одном и том же множестве сообщений. Такой вариант метода линеаризации называется методом кратного приближения.

Метод линеаризации был обобщен в 1997 году криптографами из Цюриха Карло Харпесом и Джеймсом Месси, [HaMa97]. Суть метода в прежних обозначениях сводится к поиску разбиения пространства [image] и подмножества [image], для которых строится некоторая эмпирическая метрика, позволяющая отличить распределение образов $ F(x)$ по блокам разбиения [image] при случайном выборе аргумента $ x$ из подмножества $ H$. Имеются библиографические ссылки на варианты этого метода, датируемые 1994 годом [MPWW94,Ha94], однако, эти работы нам недоступны. Этот метод называют методом разбиений.

В 1994 году [LaMa94] криптографы из Стэнфордского университета Сьюзан Лэнгфорд и Мартин Хеллман используя идеи как дифференциального анализа, так и линейного предложили новый метод линейно-дифференциального криптоанализа. Суть метода сводится поиску такого вектора [image], что для булевой функции [image] удается построить хорошую дифференциальную характеристику (и, соответственно, авторы строят эту дифференциальную характеристику).

Еще одно обобщение метода линеаризации было предложено Л.Кнудсеном и М.Робшау в 1996 году [KnRo96]. Авторы метода нелинейного приближения заметили, что для отбраковки опробуемых ключей первой и/или последней итераций можно использовать не только линейные соотношения на входных и выходных битах промежуточных шифртекстов.

В 1997 году в работе [JK97] Т.Джекобсен и Л.Кнудсен предложили с помощью интерполяционной формулы Лагранжа сводить задачу определения ключа алгоритма блочного шифрования к нахождению корня нелинейного уравнения от одной переменной в конечном поле (интерполяционная атака). Сложность такого метода определяется степенью многочлена и числом ненулевых мономов в нем. Развивая эту идею, Т.Джекобсен в 1999 году [Ja99] предлагает рассматривать многочлены "приближающие" шифрпреобразование лишь с некоторой вероятностью, но при этом имеющими низкую степень нелинейности. Метод нахождения ключей при таком подходе опирается на алгоритмы декодирования кодов Рида -- Соломона за границей корректирующей способности кода. Вопросы минимизации степени интерполирующего многочлена за счет выбора подходящего примитивного многочлена для задания поля и за счет применения невырожденного линейного преобразования на входе и выходе изучены А.Иоссефом и Г.Гонгом в работе [YG00].

Отдельный класс криптоаналитических методов основан на использовании особенностей построения "ключевых разверток" для шифров итерационного типа (обзор ранних работ по этому направлению см. в [KSW96]). В открытой криптографии метод согласования (meet-in-the middle) для случая, когда множество бит ключа, от которых зависят первые и последние итерации шифра, не пересекаются, фактически является фольклорным (достаточно сложно установить его первоисточник). Постоянно появляются работы, посвященные поиску новых классов "слабых" и "полу-слабых" ключей для различных алгоритмов шифрования. Дифференциальный метод криптографического анализа "породил" метод "связанных ключей" (related key cryptanalysis) [Bih93]. Этот метод рассматривает задачу определения ключа шифрования при условии, что аналитик имеет возможность наблюдать серии пар открытый-шифрованный текст, полученные не на одном ключе, а на нескольких различных ключах, причем известно как эти различные ключи связаны между собой.

В 1999 году эмигрантом из России Алексом Бирюковым и известным американским криптографом Дэвидом Вагнером был предложен новый вид атаки на блочные шифры, эффективность которой не зависит от числа итераций [BiWa99,BiWa00]. Рассмотренный метод криптоанализа получил название "скользящей атаки" (Slide Attacks). Предложенный ими метод основан на том, что некоторые шифры являются композицией нескольких одинаковых (не однотипных, а в точности одинаковых! -- за счет особенностей ключевой развертки) преобразований.

Основные тенденции в синтезе алгоритмов блочного шифрования нашли свое отражение в проведенном конкурсе на новый алгоритм шифрования США. Анализ представленных схем показывает, что все они построены по каноническим принципам К.Шеннона как SP-сети (чередование нелинейных замен в подвекторах шифруемого блока с последующей перестановкой бит между подвекторами), но с увеличенной до 128 бит длиной шифруемого блока. В некоторых алгоритмах авторы отказываются от простой перестановки бит между подвекторами и рассматривают линейные преобразования более общего вида. Остается популярным и подход к построению блочных шифров по схеме Фейстеля, т.е. в виде регистра сдвига на малом числе ячеек с нелинейной обратной связью. Основные достижения в этом направлении связаны с интересными алгоритмическими приемами, позволяющими добиться эффективной реализации схем на вычислительных платформах различного типа.

Вперед Вверх Назад
Вперед: Криптографические алгоритмы гаммирования Вверх: Алгоритмическая криптография Назад: Алгоритмическая криптография

М.И.Анохин/МГУ, Москва
Написать комментарий
См. также:

Популярные статьи В. М. Сидельников. О современной криптографии: О современной криптографии

Курсы лекций Криптография в банковском деле. М. И. Анохин, Н. П. Варновский, В. М. Сидельников, В. В. Ященко: SECTION05000000000000000000

© 2001-2004 Институт проблем информационной безопасности МГУ
© 2001-2004 Московский Центр Непрерывного Математического Образования
Проект осуществляется при поддержке "Научной Сети"
         [AD-SIZE]
[AD]