Композиции шифров
еще более стоек.
2.1. Сети Файстеля
Большинство блочных алгоритмов относятся к так называемым сетям
Файстеля. Идея этих сетей датируется началом семидесятых годов. Возьмем
блок длиной п и разделим его на две половины длиной n/2: L и R. Разумеется,
число п должно быть четным. Можно определить итеративный блочный шифр, в
котором результат j-го раунда определяется результатом предыдущего раунда:
Li = Ri-1
Ri = Li-1 ( f(Ri-1, Ki)
Ki - подключ j-го раунда, а f - произвольная функция раунда.
Применение этой концепции можно встретить в алгоритмах DES, Lucifer,
FEAL, Khufu, Khafre, LOKI, ГОСТ, CAST, Blowfish и других. Этим
гарантируется обратимость функции. Так как для объединения левой половины с
результатом функции раунда используется операция XOR, всегда истинно
следующее выражение:
Li-1 ( f(Ri-1, Ki ) ( Li-1 ( f(Ri-1, Ki) = Li-1
Шифр, использующий такую конструкцию, гарантированно обратим, если можно
восстановить исходные данные f на каждом раунде. Сама функция f не важна,
она не обязательно обратима. Мы можем спроектировать сколь угодно сложную
функцию f, но нам не понадобится реализовывать два разных алгоритма - один
для зашифрования, а другой для расшифрования. Об этом автоматически
позаботится структура сети Файстеля.
2.2. Простые соотношения
Алгоритм DES характеризуется следующим свойством: если ЕК(Р) = С, то
ЕK' (Р') = С', где Р', С' и K' - побитовые дополнения Р, С и K. Это
свойство вдвое уменьшает сложность лобового вскрытия. Свойства
комплементарности в 256 раз упрощают лобовое вскрытие алгоритма LOKI.
Простое соотношение можно определить так:
Если ЕK(Р) = С, то Ef(K)(g(P,K)) = h(C,K)
где f, g и h - простые функции. Под «простыми функциями» подразумевают
функции, вычисление которых несложно, намного проще итерации блочного
шифра. В алгоритме DES функция f представляет собой побитовое дополнение
K, g - побитовое дополнение Р, a h - побитовое дополнение C. Это -
следствие сложения ключа и текста операцией XOR. Для хорошего блочного
шифра простых соотношений нет.
2.3. Групповая структура
При изучении алгоритма возникает вопрос, не образует ли он группу.
Элементами группы служат блоки шифртекста для каждого возможного ключа, а
групповой операцией служит композиция. Изучение групповой структуры
алгоритма представляет собой попытку понять, насколько возрастает
дополнительное скрытие текста при многократном шифровании.
Важен, однако, вопрос не о том, действительно ли алгоритм - группа, а
о том, насколько он близок к таковому. Если не хватает только одного
элемента, алгоритм не образует группу, но двойное шифрование было бы, с
точки зрения статистики, просто потерей времени. Работа над DES показала,
что этот алгоритм весьма далек от группы. Существует также ряд интересных
вопросов о полугруппе, получаемой при шифровании DES. Содержит ли она
тождество, то есть, не образует ли она группу? Иными словами, не генерирует
ли, в конце концов, некоторая комбинация операций зашифрования (не
расшифрования) тождественную функцию? Если так, какова длина самой короткой
из таких комбинаций?
Цель исследования состоит в оценке пространства ключей для
теоретического лобового вскрытия, а результат представляет собой наибольшую
нижнюю границу энтропии пространства ключей.
2.4. Слабые ключи
В хорошем блочном шифре все ключи одинаково сильны. Как правило, нет
проблем и с алгоритмами, включающими небольшое число слабых ключей,
например, DES. Вероятность случайного выбора одного из них очень мала, и
такой ключ легко проверить и, при необходимости, отбросить. Однако если
блочный шифр используется как однонаправленная хэш-функция, эти слабые
ключи иногда могут быть задействованы.
2.5. Устойчивость алгоритма к дифференциальному и
линейному криптоанализу
Исследования дифференциального и линейного криптоанализа значительно
прояснили теорию проектирования надежных блочных шифров. Авторы алгоритма
IDEA ввели понятие дифференциалов, обобщение основной идеи характеристик.
Они утверждали, что можно создавать блочные шифры, устойчивые к атакам
такого типа. В результате подобного проектирования появился алгоритм IDEA.
Позднее это понятие было формализовано в работах Кайса Ниберг (Kaisa
Nyberg) и Ларе Кнудсен, которые описали метод создания блочных шифров,
доказуемо устойчивых к дифференциальному криптоанализу. Эта теория была
расширена на дифференциалы высших порядков и частные дифференциалы. Как
представляется, дифференциалы высших порядков применимы только к шифрам с
малым числом раундов, но частные дифференциалы прекрасно объединяются с
дифференциалами.
Линейный криптоанализ появился сравнительно недавно, и продолжает
совершенствоваться. Были определены понятия ранжирования ключей и
многократных аппроксимаций. Кем-то была предпринята попытка объединения в
одной атаке дифференциального и линейного методов криптоанализа. Пока
неясно, какая методика проектирования сможет противостоять подобным атакам.
Кнудсен добился известного успеха, рассматривая некоторые необходимые
(но, возможно, недостаточные) критерии того, что он назвал практически
стойкими сетями Файстеля - шифров, устойчивых как к дифференциальному, так
и к линейному криптоанализу. Ниберг ввел для линейного криптоанализа аналог
понятия дифференциалов в дифференциальном криптоанализе.
Достаточно интересна, как представляется, двойственность
дифференциального и линейного методов криптоанализа. Эта двойственность
становится очевидной как при разработке методики создания хороших
дифференциальных характеристик и линейных приближений, так и при разработке
критерия проектирования, обеспечивающего устойчивость алгоритмов к обоим
типам вскрытия. Пока точно неизвестно, куда заведет это направление
исследований. Для начала Дэймен разработала стратегию проектирования
алгоритма, основанную на дифференциальном и линейном криптоанализе.
2.6. Проектирование S-блоков
Мощь большинства сетей Файстеля, а особенно их устойчивость к
дифференциальному и линейному криптоанализу, напрямую связана с их S-
блоками. Поэтому вопрос о том, что же образует хороший S-блок, стал
объектом многочисленных исследований.
S-блок - это просто подстановка: отображение m-битовых входов на n-
битовые выходы. Применяется большая таблица подстановок 64-битовых входов
на 64-битовые выходы. Такая таблица представляет собой S-блок размером
64*64 бит. S-блок с m-битовым входом и n-битовым выходом называется m*n-
битовым S-блоком. Как правило, обработка в S-блоках - единственная
нелинейная операция в алгоритме. Именно S-блоки обеспечивают стойкость
блочного шифра. В общем случае, чем больше S-блоки, тем лучше.
В алгоритме DES используются восемь различных 6*4-битовых S-блоков. В
алгоритмах Khufu и Khafre предусмотрен единственный 8*32-битовый S-блок, в
LOKI – 12*8-битовый S-блок, а в Blowfish и CAST – 8*32-битовые S-блоки. В
IDEA S-блоком, по сути, служит умножение по модулю, это 16+16-битовый S-
блок. Чем больше S-блок, тем труднее обнаружить статистические данные,
нужные для вскрытия методами дифференциального или линейного криптоанализа.
Кроме того, хотя случайные S-блоки обычно не оптимальны с точки зрения
устойчивости к дифференциальному и линейному криптоанализу, стойкие S-блоки
легче найти среди S-блоков большего размера. Большинство случайных S-блоков
нелинейны, невырождены и характеризуются высокой устойчивостью к линейному
криптоанализу, причем с уменьшением числа входных битов устойчивость
снижается достаточно медленно.
Размер т важнее размера п. Увеличение размера п снижает эффективность
дифференциального криптоанализа, но значительно повышает эффективность
линейного криптоанализа. Действительно, если п ? 2m - т, наверняка
существует линейная зависимость между входными и выходными битами S-блока.
А если п ? 2m , линейная зависимость существует даже только между выходными
битами. Заметная доля работ по проектированию S-блоков состоит в
изучении булевых функций. Для обеспечения безопасности, булевы функции S-
блоков должны отвечать определенным требованиям. Они не должны быть ни
линейными, ни аффинными, ни даже близкими к линейным или аффинным функциям.
Число нулей и единиц должно быть сбалансированным, и между различными
комбинациями битов не должно быть никаких корреляций. При изменении
значения любого входного бита на противоположное выходные биты должны вести
себя независимо. Эти критерии проектирования так же связаны с изучением
бент-функций (bent functions): функций, которые, как можно показать,
оптимально нелинейны. Хотя они определены просто и естественно, их изучение
очень трудно.
По-видимому, очень важное свойство S-блоков - лавинный эффект: сколько
выходных битов S-блока изменяется при изменении некоторого подмножества
входных битов. Нетрудно задать для булевых функций условия, выполнение
которых обеспечивает определенный лавинный эффект, но проектирование таких
функций задача сложная. Строгий лавинный критерий (Strict Avalanche
Criteria - SAC) гарантирует изменение ровно половины выходных битов при
изменении единственного входного бита. В одной из работ эти критерии
рассматриваются с точки зрения утечки информации.
Несколько лет назад крипгографы предложили выбирать S-блоки так, чтобы
таблица распределения различий для каждого S-блока
| |  скачать работу |
Композиции шифров |
