Введение в современную криптографию
Атака на однораундовую SPN
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Атака на однораундовую SPN. Теперь у нас есть полный раунд, за которым
следует шаг смешения ключей. Для конкретики, мы предположим 64-битную длину блока и S-блоки с входной/выходной длиной в 8 бит (1 байт). Мы предпо- ложим, что 64-битные подключи k1, k2 используются для двх шагов смешения ключей, поэтому мастер-ключ k1||k2 SPN будет длиной 128 бит. Первое наблюдение заключается в том, что мы можем расширить атаку из тривиального случая, описанного выше, чтобы получилась атака с восстановле- нием ключа, выполнив работы намного меньше, чем 2128 . Идея такова: Полу- чив одну входную/выходную пару (x, y), как и ранее, атакующий перебирает все возможные значения для подключа второго раунда k2. Для каждого такого значения атакующий может инвертировать последний шаг сме- шения ключей, чтобы получить вероятное промежуточное значение yr. Мы увидели выше, что, имея входной элемент x и выходной элемент yr (целого) раунда SPN, воз- можный уникальный подключ k1 может быть с легкостью идентифицирован. Таким образом, для каждого возможного выбора k2 атакующий извлекает соответствующий уникальный k1 , для которого k1||k2 может быть мастер-ключом. Следовательно, ата- кующий получает (за время 264 ) список из 264 вариантов мастер-ключа. Его можно сузить с использованием дополнительной входной/выходной пары за дополнительное время 264 приблизительно; см. также ниже. Возможно провести еще лучшую атаку, заметив, что индивидуальные биты выходного элемента зависят только от мастер-ключа. Зафиксируем полученную входную/выходную пару (x, y), как и ранее. Теперь злоумышленник будет пере- бирать все возможные значения первого байта , принадлежащего k2. Он может сложить по модулю 2 каждое такое значение с первым байтом y , чтобы полу- 230 чить вероятное значение выходного элемента первого S-блока. Инвертируя этот S-блок, атакующий узнает вероятное значение входного элемента в этот S-блок. Так как входной элемент в этот S-блок является XOR из 8 бит x и 8 бит k1 (где позиции этих битов зависят от смешивающей перстановки первого раунда и известны атакующему), это дает вероятное значение для 8 бит k1. Подводя итого, отметим, что для каждого вероятного значения первого байта k2 суще- ствует вероятное соотвествующее уникальное значение для каких-либо 8 бит k1. Ины- ми словами, это означает, что для каких-то 16 бит мастер-ключа атакующий уменьшил количество вероятных значений для битов от 216 до 28. Атакующий может свести все те вероятные значения за время 28. Это можно повторить для каждого байта из k2, давая 8 списков, каждый из которых содержит 28 значений, которые вместе характеризуют возможные значения всего мастер-ключа. Атакующий, таким образом, уменьшил ко- личество возможных мастер-ключей до (28)8 = 264, как и в предыдущей атаке. Общее время, затраченное на все это, теперь 8 • 28 = 211, что есть резкое улучшение. Атакующий может использовать дополнительную входную/выходную пару, чтобы еще больше уменьшить пространство возможных ключей. Рассмотрим лист с 28 вероятными значениями какого-то набора из 16 бит мастер-ключа. Атакующему известно, что правильное значение из этого списка должно со- гласовываться с любой из дополнительных входных/выходных пар, которые из- вестны атакующему. Эвристически, любое неправильное значение из списка согласуется с какой-то дополнительной входной/выходной парой (xr , yr) веро- ятностью, которая не лучше, чем случайное гадание; так как 16-битное значение из таблицы может быть использовано для вычисления 1 байта выходного эле- мента при наличии входного элемента xr, мы прогнозируем, что неправильное значение будет согласовываться с реальным действующим выходным элемен- том yr с вероятностью 2−8. Маленькое количество дополнительных входных/ выходных пар, таким образом, помогает сузить все таблицы до одного значения в каждой, и на этом этапе мастер-ключ уже можно считать найденным. Отсюда необходимо извлечь важный урок. Атака возможна, если разные ча- сти ключа могут быть изолированы от других частей. Таким образом, необхо- димо дальнейшее рассеивание , чтобы убедиться, что все биты ключа влияют на все биты выходного результата. Чтобы это произошло, нужно больше раундов. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|