бавлю вас от длительного изучения таблиц, наиболее смещенным S-блоком является пятый S-блок. Действ и-тельно, для 12 входов второй входной бит равен XOR всех четырех выходных битов. Это соответствует вероя т-ности 3/16 или смещению 5/16, что является самым большим смещением для всех S-блоков. (Шамир писал об этом в [1423], но не смог найти способа использовать.)

На 4-й показано, как воспользоваться этим для вскрытия функции этапа DES. Ь26 - это входной бит S-блока 5. (Я нумерую биты слева направо от 1 до 64. Мацуи игнорирует это принятое для DES соглашение и нумерует свои биты справа налево и от 0 до 63. Этого хватит, чтобы свести вас с ума.) c17, c18, c19, c20 - это 4 выходных бита S-блока 5. Мы можем проследить b26 в обратном направлении от входа в S-блок. Для получения b26 бит объединяется с помощью XOR с битом подключа Ki26. А бит X17 проходит через подстановку с расширением, чтобы превратиться в a26. После S-блока 4 выходных бита проходят через P-блок, превращаясь в четыре выхо д-ных бита функции этапа: Y3, Y8, Y14 и Y25. Это означает, что с вероятностью 1/2 - 5/6:

X17 © Y3 © Y © Y14 © Y25 = K.-26

C17,C18,C19, C20

Y3, Y8, Y14, Y25

Рис. 12-8. 1-этапное линейное приближение для DES.

Способ, которым можно объединить линейные приближения для различных этапов, похож на тот, который обсуждался для дифференциального криптоанализа. На 3-й показано 3-этапное линейное приближение с вероятностью 1/2+0.0061. Качество отдельных приближений различно: последнее очень хорошо, первое достаточно хорошо, а среднее - плохо. Но вместе эти три 1-этапных приближения дают очень хорошее трехэтапное пр и-ближение.

A=[3, 8, 14, 25]B=[8, 14, 25]

С вероятностью 1/2+6.1*10"

Рис. 12-9. 3-этапное линейное приближение DES.

Базовое вскрытие должно использовать наилучшее линейное приближение для 16-этапного DES. Для него требуется 247 известных открытых блоков, а результатом вскрытия является 1 бит ключа. Это не очень полезно. Если вы поменяете местами открытый текст и шифротекст и используете дешифрирование вместе с шифров а-нием, вы сможете получить 2 бита. Это все еще не очень полезно.

Существует ряд тонкостей. Используйте 14-этапное линейное приближение для этапов с 2 по 15. Попробуем угадать 6 битов подключа для S-блока 5 первого и последнего этапов (всего, таким образом, 12 битов ключа). Для эффективности выполняем линейный криптоанализ параллельно 2 12 раз и выбираем правильный вариант, основываясь на вероятностях. Это раскрывает 12 битов и b26, а поменяв местами открытый текст и шифротекст мы получим еще 13 битов. Для получения оставшихся 30 битов используйте исчерпывающий поиск. Существ уют и друге приемы, но описанный является основным.

При вскрытии таким образом полного 16 этапного DES ключ будет раскрыт в среднем с помощью 2 43 известных открытых текстов. Программная реализации этого вскрытия, работая на 12 рабочих станциях HP9735, раскрыла ключ DES за 50 дней [1019]. В момент написания этой книги это наиболее эффективный способ вскрытия DES.

Линейный криптоанализ сильно зависит от структуры S-блоков, оказалось, что S-блоки DES не оптимизир о-ваны против такого способа вскрытия. Действительно, смещение в S-блоках, выбранных для DES, находится между 9 и 16 процентами, что не обеспечивает надежной защиты против линейного криптоанализа [1018]. С о-гласно Дону Копперсмиту [373, 374] устойчивость к линейному криптоанализу "не входило в число критериев проектирования DES". Либо разработчикам не было известно о линейном криптоанализе, либо при проектир о-вании они отдали преимущество устойчив ости против известного им еще более мощного средства вскрытия.

Линейный криптоанализ новее, чем дифференциальный, и в ближайшее время возможно дальнейшее пр о-движение в этом направлении. Некоторые идеи выдвинуты в [1270, 811], но не ясно, можно ли их эффективно применить против полного DES. Однако они очень хорошо работают против вариантов с уменьшенным числом этапов.

Дальнейшие направления

Был предпринят ряд попыток расширить концепцию дифференциального криптоанализа на дифференциалы более высоких порядков [702, 161, 927, 858, 860]. Ларс Кнудсен (Lars Knudsen) использует нечто, называемое частичными дифференциалами для вскрытия 6-этапного DES. Этот метод требует 32 выбранных открытых те к-ста и 20000 шифрований [860]. Но этот метод слишком нов, чтобы можно было утверждать, что он облегчит вскрытие полного 16-этапного DES.

Другим способом вскрытия является дифференциально-линейный криптоанализ - объединение дифференц и-ального и линейного криптоанализа. Сьюзен Лангфорд (Susan Langford) и Хеллман предлагают вскрытие 8-этапного DES, которое раскрывает 10 битов ключа с вероятностью успеха 80 процентов, используя 512 в ы-бранных открытых текстов, и с вероятностью успеха 95 процентов, используя 768 выбранных открытых текстов [938]. После вскрытия необходим поиск грубой силой в оставшемся пространстве ключей (2 46 возможных ключей). Хотя по времени это вскрытие сравнимо с предыдущими способами, для него требуется намного меньше открытых текстов. Однако расширение этого метода на большее количество этапов легким не кажется.

Но этот метод нов, и работа продолжается. В ближайшие годы возможны заметные успехи. Может быть у спеха добьется сочетание этого вскрытия с дифференциальным криптоанализом более высоких порядков. Кто знает?

12.5 Реальные критерии проектирования

После появления публикаций о дифференциальном криптоанализе IBM раскрыла критерии проектирования S-блоков и Р-блока [373, 374]. Критериями проектирования S-блоков являлись:

-У каждого S-блока 6 входных битов и 4 выходных бита. (Это самый большой размер, который мог быть реализован в одной микросхеме по технологии 1974 года.)

-Ни один выходной бит S-блока не должен быть слишком близок к линейной функции входных битов.

-Если зафиксировать крайние левый и правый биты S-блока, изменяя 4 средних бита, то каждый возмо ж-ный 4-битовый результат получается только один раз.

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

-Если два входа S-блока отличаются только двумя центральными битами, результаты должны отличаться по крайней мере на 2 бита.

-Если два входа S-блока отличаются двумя первыми битами, а последние их последние 2 бита совпадают, результаты не должны быть одинаковыми.

-Для любого ненулевого 6-битового отличия между входами, не более, чем 8 из 32 пар входов могут пр и-водить на выходе к одинаковому различию.

-Аналогичный предыдущему критерий, но для случая трех активных S-блоков. Критериями проектирования Р-блока являлись:

-4 выходных бита каждого S-блока на этапе i распределены так, чтобы 2 из них влияют на средние биты S-блоков на этапе i + 1, а другие 2 бита влияют на п оследние биты.

-4 выходных бита каждого S-блока влияют на шесть различных S-блоков, никакие 2 не влияют на один и тот же S-блок.

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

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

12.6 Варианты DES

Многократный DES

В ряде реализаций DES используется трехкратный DES (см. 2-й) [55]. Так как DES е является группой, полученный шифротекст гораздо сложнее вскрыть, используя исчерпывающий поиск: 2 112 попыток вместо 256. Подробности можно найти в разделе 15.2.