Композиции шифров

нижнюю границу энтропии пространства ключей.

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-блока была однородной. Это

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

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

такого проектирования можно назвать алгоритм LOKI. Однако такой подход

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

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

Кванджо Ким (Kwangjo Kim) выдвинул пять критериев проектирования S-блоков,

напоминающих критерии проектирования S-блоков DES.

Выбор хороших S-блоков - нелегкая задача. Известно множество

конкурирующих подходов ее решения; среди hих можно выделить четыре

основных.

V Случайный выбор. Ясно, что небольшие случайные S-блоки ненадежны, но

крупные случайные S-блоки могут оказаться достаточно хорошими.

Случайные S-блоки с восемью и более входами достаточно стойки, еще

лучше 12-битовые S-блоки. Стойкость S-блоков возрастает, если они

одновременно и случайны, и зависят от ключа.

V Выбор с последующим тестированием. В некоторых шифрах сначала

генерируются случайные S-блоки, а затеи их свойства тестируются на

соответствие требованиям.

V Разработка вручную. При этом математический аппарат используется

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

приемов. Барт Пренел (Bart Preneel) заявил, что «... теоретически

интересные критерии недостаточны (для выбора булевых функций S-

блоков)...», и «... необходимы специальные критерии проектирования».

V Математическая разработка. S-блоки создаются в соответствии с законами

математики, поэтому обладают гарантированной устойчивостью к

дифференциальному и линейному криптоанализу и хорошими рассеивающими

свойствами.

Раздавались призывы объединить «математический» и «ручной» подходы, но

реально, по-видимому, конкурируют случайно выбранные S-блоки и S-блоки с

определенными свойствами. К преимуществам последнего подхода можно отнести

оптимизацию против известных методов вскрытия — дифференциального и

линейного криптоанализа. Однако в этом случае неясна степень защиты от

неизвестных методов вскрытия. Разработчики DES знали о дифференциальном

криптоанализе, поэтому S-блоки DES оптимизированы надлежащим образом. Но,

вероятнее всего, о линейном криптоанализе они не знали, и S-блоки DES очень

слабы по отношению к такой атаке. Случайно выбранные S-блоки в DES были бы

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

криптоанализу.

С другой стороны, случайные S-блоки могут быть и неоптимальны к данным

атакам, но они могут быть достаточно большими и, следовательно, достаточно

стойкими. Кроме того, они, скорее всего, окажутся достаточно устойчивыми к

неизвестным методам вскрытия. Споры все еще кипят, но лично мне кажется,

что S-блоки должны быть такими большими, насколько это возможно, случайными

и зависящими от ключа.

2.7. Проектирование блочного шифра

Спроектировать блочный шифр нетрудно. Если рассматривать 64-битовый

блочный шифр как перестановку 64-битовых чисел, ясно, что почти все эти

перестановки безопасны. Трудно спроектировать такой блочный шифр, который

не только стоек, но также может быть легко описан и реализован.

Нетрудно спроектировать блочный шифр, если объем памяти достаточен для

размещения 48*32-битовых S-блоков. Трудно спроектировать нестойкий вариант

алгоритма DES, если нужно использовать в нем 128 раундов. При длине ключа

512 битов нет нужды беспокоиться о какой-либо зависящей от ключа

комплементарности.

Настоящий фокус - и причина, почему на самом деле очень трудно

спроектировать блочный шифр - это разработать алгоритм с возможно

наименьшим ключом, требованиям к памяти и максимальной скоростью работы.

3. Блочные шифры

3.1. Алгоритм Lucifer

В конце шестидесятых годов корпорация IBM запустила исследовательскую

программу по компьютерной криптографии, названную Lucifer (Люцифер) и

руководимую сначала Хорстом Файстелем (Horst Feistel), а затем Уолтом

Тачменом (Walt Tuchman). Такое же имя - Lucifer - получил блочный алгоритм,

появившийся в результате этой программы в начале семидесятых годов. В

действительности существует, по меньшей мере, два различных алгоритма с

таким именем. Один из них содержит ряд пробелов в спецификации алгоритма.

Все это привело к заметной путанице.

Алгоритм Lucifer представляет собой сеть перестановок и подстановок,

его основные блоки напоминают блоки алгоритма DES. В DES результат функции

f складывается операцией XOR с входом предыдущего раунда, образуя вход

следующего раунда. У S-блоков алгоритма Lucifer 4-битовые входы и выходы,

вход S-блоков представляет собой перетасованный выход S-блоков предыдущего

раунда, входом S-блоков первого раунда служит открытый текст. Для выбора

используемого S-блока из двух возможных используется бит ключа. (Lucifer

реализует все это в едином Т-блоке с 9 битами на входе и 8 битами на

выходе). В отличие от алгоритма DES, половины блока между раундами не

переставляются, да и само понятие половины блока в алгоритме Lucifer не

используется. У этого алгоритма 16 раундов, 128-битовые блоки и более

простая, чем в DES, схема развертки ключа.

Применив дифференциальный криптоанализ к первой реализации алгоритма

Lucifer, Бихам и Шамир показали, что Lucifer с 32-битовыми блоками и 8

раундами можно взломать с помощью 40 подобранных открытых текстов за 229

операций. Этот же метод позволяет вскрыть Lucifer с 128-битовыми блоками и

8 раундами с помощью 60 подобранных открытых текстов за 253 шагов. Другая

дифференциальная атака вскрывает 18-раундовый, 128-битовый Lucifer с

помощью 24 подобранных открытых текстов за 221 операций. Во всех этих

вскрытиях использовались стойкие S-блоки алгоритма DES. Применив

дифференциальный криптоанализ ко второй реализации Lucifer, Бихам и Шамир

обнаружили, что его S-блоки намного слабее, чем в алгоритме DES. Дальнейший

анализ показал нестойкость более половины возможных ключей. Криптоанализ на

основе связанных ключей позволяет взломать 128-битовый Lucifer с любым

числом раундов с помощью 233 подобранных открытых текстов для подобранных

ключей или 265 известных открытых текстов для подобранных ключей. Вторая

реализация Lucifer еще слабее.

Некоторые полагают, что Lucifer надежнее DES из-за большей длины ключа

и малочисленности опубликованных сведений. Но очевидно, что это не так. На

алгоритм Lucifer выданы нескольких патентов США. Сроки действия всех этих

патентов уже истекли.

3.2. Алгоритм Madryga

В. Е. Мадрига (W. E. Madryga) предложил этот блочный алгоритм в 1984

году. Его можно эффективно реализовать программным путем: в алгоритме нет

раздражающих перестановок, и все операции выполняются над байтами.

Стоит перечислить задачи, которые решал автор при проектировании

алгоритма:

V Без помощи ключа открытый текст невозможно получить из шифртекста.

(Это означает только то, что алгоритм стоек).

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

шифртекста и открытого текста, должно быть статистически равно

произведению числа операций при шифровании на число возможных ключей.

(Это означает, что никакое вскрытие с открытым текстом не может быть

эффективнее лобового вскрытия).

V Опубликование алгоритма не влияет на стойкость шифра. (Безопасность

полностью определяется ключом).

V Изменение одного бита ключа должно радикально изменять шифртекст

одного и того же открытого текста, а изменение одного бита открытого

текста должно радикально изменять шифртекст для того же ключа

(лавинный эффект).

V Алгоритм должен содержать некоммутативную комбинацию подстановок и

перестановок.

V Подстановки и перестановки, используемые в алгоритме, должны

определяться как входными данными, так и ключом.

V Избыточные группы битов открытого текста должны быть полностью

замаскированы в шифртексте.

V Длина шифртекста должна совпадать с длиной открытого текста.

V Между любыми возможными ключами и особенностями шифртекста недопустимы

простые взаимосвязи.

V Все возможные ключи должны обеспечивать стойкость шифра. (Не должно

быть слабых ключей).

V Длина ключа и текст должны иметь возможность варьирования для

реализации различных требований к безопасности.

V Алгоритм должен допускать эффективную программную реализацию на

мэйнфреймах, мини- и микрокомпыотерах и с помощью дискретной логики.

(По существу, число функций, используемых в алгоритме, ограничено

операциями XOR и битовым сдвигом).

Алгоритм DES удовлетворял первым девяти требованиям, но последние три

появились впервые. Если допустить, что лучший способ взлома алгоритма -

лобовое вскрытие, переменная длина ключа, конечно же, заставит замолчать

тех, кто считает, что 56 битов - слишком малая величина. Такие люди могут

реализовать этот алгоритм с любой длиной ключа. А любой, кто когда-нибудь

пытался реализовать DES программными средствами, обрадуется алгоритму,

который учитывает особенности программных реализаций.

3.3.1. Описание алгоритма Madryga

Алгоритм Madryga состоит из двух вложенных циклов. Внешний цикл

повторяется восемь раз (для гарантии надежности число циклов можно

увеличить) и заключается в применении внутреннего цикла к открытому тексту.

Внутренний цикл превращает открытый текст в шифртекст и выполняется

однократно над каждым 8-битовым блоком (байтом) открытого текста. Таким

образом, весь открытый текст последовательно восемь раз обрабатывается

алгоритмом.

Итерация внутреннего цикла оперирует с 3-байтовым окном данных,

называемым рабочим кадром (Рис. 1.). Это окно сдвигается на 1 байт за

итерацию. (При работе с последними 2 байтами данные полагаются циклически

замкнутыми). Первые два байта рабочего кадра циклически сдвигаются на

переменное число позиций, а для последнего байта исполняется операция XOR с

несколькими битами ключа. По мере перемещения рабочего кадра все байты

последовательно циклически сдвигаются и подвергаются операции XOR с частями

ключа. Последовательные циклические сдвиги перемешивают результаты

предыдущих операций XOR и циклического сдвига, причем на циклический сдвиг

влияют результаты XOR. Благодаря этому процесс в целом обратим.

|Движущийся |WF(1) |WF(2) | |WF(3) | | | |

|рабочий кадр | | | | | | | |

| |8 битов|8 битов| |8 битов | | | |

| |ROT | | | | | |

|Перемещение |Объект сдвига | | |Счетчик сдвига | | |

| |16 бит | |3 бита | | |

| | | | |XOR | | | |

|Хэш ключа |1|2|3|… |KL | | |

| | | | | | | | |

Рис. 1. Одна итерация алгоритма Madryga

Поскольку каждый байт данных влияет на два байта слева и на один байт

Страницы: 1, 2, 3, 4, 5