Проектирование S-блоков

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-блоков нелинейны, невырождены и характеризуются высокой устойчивостью к линейному криптоанализу, причем с уменьшением числа входных битов устойчивость снижается достаточно медленно.

Размер т важнее размера п. Увеличение размера п снижает эффективность дифференциального криптоанализа, но значительно повышает эффективность линейного криптоанализа. Действительно, если п ≥ 2^m - т, наверняка существует линейная зависимость между входными и выходными битами S-блока. А если п ≥ 2^m , линейная зависимость существует даже только между выходными битами. Заметная доля работ по проектированию S-блоков состоит в изучении булевых функций. Для обеспечения безопасности, булевы функции S-блоков должны отвечать определенным требованиям. Они не должны быть ни линейными, ни аффинными, ни даже близкими к линейным или аффинным функциям. Число нулей и единиц должно быть сбалансированным, и между различными комбинациями битов не должно быть никаких корреляций. При изменении значения любого входного бита на противоположное выходные биты должны вести себя независимо. Эти критерии проектирования так же связаны с изучением бент-функций (bent functions): функций, которые, как можно показать, оптимально нелинейны. Хотя они определены просто и естественно, их изучение очень трудно.

По-видимому, очень важное свойство S-блоков - лавинный эффект: сколько выходных битов S-блока изменяется при изменении некоторого подмножества входных битов. Нетрудно задать для булевых функций условия, выполнение которых обеспечивает определенный лавинный эффект, но проектирование таких функций задача сложная. Строгий лавинный критерий (Strict Avalanche Criteria - SAC) гарантирует изменение ровно половины выходных битов при изменении единственного входного бита. В одной из работ эти критерии рассматриваются с точки зрения утечки информации.

Несколько лет назад крипгографы предложили выбирать S-блоки так, чтобы таблица распределения различий для каждого S-блока была однородной. Это обеспечило бы устойчивость к дифференциальному криптоанализу за счет сглаживания дифференциалов на любом отдельном раунде. В качестве примера такого проектирования можно назвать алгоритм LOKI. Однако такой подход иногда облегчает дифференциальный криптоанализ. На самом деле, удачнее подход, гарантирующий наименьшее значение максимального дифференциала. Кванджо Ким (Kwangjo Kim) выдвинул пять критериев проектирования S-блоков, напоминающих критерии проектирования S-блоков DES.

Выбор хороших S-блоков - нелегкая задача. Известно множество конкурирующих подходов ее решения; среди hих можно выделить четыре основных.

ü Случайный выбор. Ясно, что небольшие случайные S-блоки ненадежны, но крупные случайные S-блоки могут оказаться достаточно хорошими. Случайные S-блоки с восемью и более входами достаточно стойки, еще лучше 12-битовые S-блоки. Стойкость S-блоков возрастает, если они одновременно и случайны, и зависят от ключа.

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

ü Разработка вручную. При этом математический аппарат используется крайне незначительно: S-блоки создаются с использованием интуитивных приемов. Барт Пренел (Bart Preneel) заявил, что «... теоретически интересные критерии недостаточны (для выбора булевых функций S-блоков)...», и «... необходимы специальные критерии проектирования».

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

Раздавались призывы объединить «математический» и «ручной» подходы, но реально, по-видимому, конкурируют случайно выбранные S-блоки и S-блоки с определенными свойствами. К преимуществам последнего подхода можно отнести оптимизацию против известных методов вскрытия — дифференциального и линейного криптоанализа. Однако в этом случае неясна степень защиты от неизвестных методов вскрытия. Разработчики DES знали о дифференциальном криптоанализе, поэтому S-блоки DES оптимизированы надлежащим образом. Но, вероятнее всего, о линейном криптоанализе они не знали, и S-блоки DES очень слабы по отношению к такой атаке. Случайно выбранные S-блоки в DES были бы слабее к дифференциальному криптоанализу, но устойчивее к линейному криптоанализу.

С другой стороны, случайные S-блоки могут быть и неоптимальны к данным атакам, но они могут быть достаточно большими и, следовательно, достаточно стойкими. Кроме того, они, скорее всего, окажутся достаточно устойчивыми к неизвестным методам вскрытия. Споры все еще кипят, но лично мне кажется, что S-блоки должны быть такими большими, насколько это возможно, случайными и зависящими от ключа.

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

Спроектировать блочный шифр нетрудно. Если рассматривать 64-битовый блочный шифр как перестановку 64-битовых чисел, ясно, что почти все эти перестановки безопасны. Трудно спроектировать такой блочный шифр, который не только стоек, но также может быть легко описан и реализован.

Нетрудно спроектировать блочный шифр, если объем памяти достаточен для размещения 48*32-битовых S-блоков. Трудно спроектировать нестойкий вариант алгоритма DES, если нужно использовать в нем 128 раундов. При длине ключа 512 битов нет нужды беспокоиться о какой-либо зависящей от ключа комплементарности.

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

Похожие работы

Обґрунтовання застосування лікарських композицій на основі нанорозмірного кремнезему в комплексному лікуванні генералізованого пародонтиту

Скачать

59220

0

0

... на генералізований пародонтит / О. І. Кутельмах // Вісник стоматології. – 2007. - № 4. – С. 137-139. АНОТАЦІЯ Кутельмах О.І. Обґрунтування застосування лікарських композицій на основі нанорозмірного кремнезему в комплексному лікуванні генералізованого пародонтиту. – Рукопис. Дисертація на здобуття наукового ступеня кандидата медичних наук за спеціальністю 14.01.22-стоматологія. – Державна ...

Мат.моделирование (Программа СДКМС)

Скачать

45010

19

22

... X1, X2 – необходимое количество рекламных заказов 2X1+2X2 ≤ 7 X1 = 1 X2 = 2 F(X1, X2) = 7 1.4. Выбор и обоснование технических средств, программ и информационных средств для реализации математического моделирования. Для реализации математического моделирования в целях данной курсовой работы выбрана система проектирования и оценки качества и устойчивости экономических объектов – СДКМС. ...

Дисертація: вимоги до написання та захист

Скачать

245524

1

0

... ічного університету, доктором технічних наук, професором М-П.Зборщиком. Висновок установи, в якій виконано дисертацію, с першою і дуже важливою її експертизою з точки зору відповідності дисертації вимогам “Порядку”. Висновок затверджується ректором (директором) або проректором (заступником директора) з наукової роботи, які несуть персональну відповідальність за якість, об'єктивність і строки пі ...

Патентоведение и основы научных исследований

Скачать

146019

0

0

... . – СПб., Изд-во “Профессия”, 2000. – С. 54-90. Раздел II Методические указания по выполнению практических работ Введение Практические занятия по дисциплине “Патентоведение и основы научных исследований” для студентов специальности 271200 “Технология продуктов общественного питания”, направления 655700 “Технология продуктов специального назначения и общественного питания” предназначены ...