227
бого блочного шифра является то, что изменение входного элемента должно
«повлиять» на каждый бит результата. Мы назовем это явление лавинным эф-
фектом. Один из способов вызвать лавинный эффект в подстановочно-переста-
новочной сети - это обеспечить наличие следующих двух свойств (при макси-
мальном количестве раундов):
1.
S-блоки разработаны так, чтобы, изменяя один бит входного элемента,
S-блок меняет как минимум два бита в выходном элементе S-блока.
2. Смешивающие перестановки разработаны так, чтобы выходные биты лю-
бого доступного S-блока использовались как входные элементы в множествен-
ные S-блоки в следующем раунде.
Чтобы увидеть, как это производит лавинный эффект, по крайней мере эвристи-
чески, предположим, что S-блоки все такие, что изменение одного бита входного
элемента S-блока выливается в изменение ровно двух битов выходного элемента
S-блока, и что смешивающие перестановки выбраны, как указано выше. Для кон-
кретики, предположим, что S-блоки имеют входной/выходной размер в 8 бит, и
что длина блока шифра - 128 бит. Рассмотрим сейчас, что случится, когда блочный
шифр примениться к
двум входным элементам, которые отличаются одним битом:
1. После первого раунда промежуточные значения отличаются ровно в двух
положениях битов. Это потому что сложение по модулю 2, текущего ключа
сохраняет 1-битную разницу в промежуточных значениях, и поэтому входные
элементы во все S-блоки, кроме одного, - идентичны. В одном S-блоке, в ко-
тором входные элементы отличаются, выходной результат S-блока показывает
2-битную разницу. Смешивающая перестановка, применяемая к результатам,
меняет
позиции эти изменений, но сохраняет 2-битную разницу.
2. Смешивающая перестановка, применяемая в конце первого раунда, рас-
пространяет две позиции битов, в которых промежуточные результаты отлича-
ются, в два различных S-блока во втором раунде. Это остается истинным, даже
после того, как соответствующий ключ складывается по модулю 2 с результа-
том предыдущего раунда. Итак, во втором раунде у нас теперь два S-блока, ко-
торые получили входные элементы, отличающиеся на один бит. Таким образом,
в конце второго раунда промежуточные значения отличаются на 4 бита.
3. Продолжая тот же аргумент, мы прогнозируем 8 бит промежуточного зна-
чения после третьего раунда, 16 бит - после четвертого раунда и все 128 бит
выходного результата в конце седьмого раунда.
Последняя точка не очень точная, и определенно есть вероятность, что будет не-
которые отличия результатов какого-либо из раундов от прогнозируемых. (Факти-
чески, так и должно быть, потому что результаты не должны отличаться по всем
битам.) Однако, вышеописанный анализ, дает нижнюю границу по количеству
228
раундов: если используется менее 7 раундов, тогда должен быть некий набор вы-
ходных битов, которые не затронет однобитное изменение во входных данных,
вызвав тем самым возможность распознать шифр из случайной перестановки.
Можно ожидать, что «наилучшим» способом разработать S-блоки было бы вы-
брать их случайным образом (учитывая то ограничение, что они являются пере-
становками). Интересно, что это нам не подходит, по крайней мере, если мы хо-
тим удовлетворить коректный критерий, упомянутый ранее. Рассмотрим случай,
когда S-блок, работающий с 4-битными входными данными, и пусть x и xr будут
двумя разными значениями. Пусть y = S(x), и теперь рассмотрим выбор универ-
сального yr ƒ= y в качестве значения S(xr). Имеется 4 строки, отличающиеся от
y только
лишь одним битом, и поэтому с вероятностью 4/15 мы выберем yr , ко-
торое не отличается от y на два или более бита. Проблемаусугубляется, если при-
нять во внимание все пары входных элементов, которые отличаются на один бит.
Сделаем вывод,
основанный на этом примере, что, как правило, S-boxes
должны быть тщательно разработы, а не просто выбраны случайным образом.
Случайные S-блоки - это также нехорошо для защиты от атак, как и блоки, ко-
торые мы покажем в Разделе 6.2.6.
Если блочный шифр должен также быть строго псевдослучайным, тогда лавин-
ный эффект должен обязательно применяться к его обратному варианту. То есть из-
менение одного бита выходного элемента должно влиять на каждый бит входного
элемента. Поэтому это очень полезно, если S-блоки разрабатываются так, чтобы,
меняя один бит выходного элемента S-блока, менялись по крайней мере два бита
входного элемента в S-блоке . Достижение лавинного эффекта в обоих направлени-
ях - это еще одна причина для дальнейшего увеличения количества раундов.
Достарыңызбен бөлісу: