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

Был предпринят ряд попыток расширить концепцию дифференциального криптоанализа на дифференциалы более высоких порядков [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 ⁴⁶ возможных клю­чей). Хотя по времени это вскрытие сравнимо с предыдущими способами, для него требуется намного меньше открытых текстов. Однако расширение этого метода на большее количество этапов легким не кажется.

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

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