Эти возможно слабые ключи перечислены в -1-й.

Табл. 12-13.

Возможно слабые ключи DES

Прежде, чем порицать DES слабые ключи, обратите внимание на то, что эти 64 ключа - это крошечная часть полного набора из 72057594037927936 возможных ключей. Если вы выбираете ключ случайно, вероятность выбрать один из слабых ключей пренебрежимо мала. Если вы настоящий параноик, можете всегда проверять "на слабость" сгенерированный ключ. Некоторые думают, что нечего и беспокоиться на этот счет. Другие у т-верждают, что проверка очень легка, почему бы ее и не в ыполнить.

Дальнейший анализ слабых и полуслабых ключей приведен в [1116]. Других слабых ключей в процессе и с-следований найдено не было.

Ключи-дополнения

Выполним побитное дополнение ключа, заменяя все 0 на 1 и все 1 - на 0. Теперь, если блок открытого текста зашифрован оригинальным ключом, то дополнение ключа при шифровании превратит дополнение блока о т-крытого текста в дополнение блока шифротекста. Если x обозначает дополнение x, то следующее верно:

Ek(P) = C

В этом нет ничего таинственного. На каждом этапе после перестановки с расширением подключи подверг а-ются операции XOR с правой половиной. Прямым следствием этого факта и является приведенное свойство комплиментарности.

Это означает, что при выполнении вскрытия DES с выбранным открытым текстом нужно проверять только половину возможных ключей: 255 вместо 256 [1080]. Эли Бихам (Eli Biham) и Ади Шамир показали [172], что существует вскрытие с известным открытым текстом, имеющее ту же сложность, для которого нужно не меньше 233 известных открытых текстов.

0стается вопросом, является ли такое свойство слабостью, так как в большинстве сообщений нет компл и-ментарных блоков открытого текста (для случайного открытого текста шансы "против" чрезвычайно велики), а пользователей можно предупредить не пользоваться дополняющими.

Алгебраическая структура

Все возможные 64-битовые блоки открытого текста можно отобразить на 64-битовые блоки шифротекста

264! Различными способами. Алгоритм DES, используя 56-битовый ключ, предоставляет нам 2 56 (приблизительно 1017) таких отображений. Использование многократного шифрования на первый взгляд позв о-ляет значительно увеличить долю возможных отображений. Но это правильно только, если действие DES не обладает определенной алгебраической структурой.

Если бы DES был замкнутым, то для любых K1 и K2 всегда существовало бы такое K3, что

Другими словами, операция шифрования DES образовала бы группу, и шифрование набора блоков открыт ого текста последовательно с помощью K1 и K2 было бы идентично шифрованию блоков ключом K3. Что еще хуже, DES был бы чувствителен к вскрытию "встреча посередине" с известным открытым текстом, для которого потребовалось бы только 228 этапов [807].

Если бы DES был чистым, то для любых K1, K2 и K3 всегда существовало бы такое K4, что

Ek3( Ek2( P))) = Ek4( P)

Тройное шифрование было бы бесполезным. (Заметьте, что замкнутый шифр обязательно является и чи с-тым, но чистый шифр не обязательно является замкнутым.)

Ряд подсказок можно найти в ранней теоретической работе Дона Копперсмита, но этого недостаточно [377]. Различные криптографы пытались решить эту проблему [588, 427, 431, 527, 723, 789]. В повторяющихся эксп е-риментах собирались "неопровержимые доказательства" того, что DES не является группой [807, 371, 808, 1116, 809], но только в 1992 году криптографам удалось это доказать окончательно [293]. Копперсмит утве р-ждает, что команда IBM знала об этом с самого н ачала.

Длина ключа

В оригинальной заявке фирмы IBM в NBS предполагалось использовать 112-битовый ключ. К тому времени, когда DES стандартом, длина ключа уменьшилась до 56 бит. Многие криптографы настаивали на более дли н-ном ключе. Основным их аргументом было вскрытие грубой силой (см. раздел 7.1).

В 1976 и 1977 гг. Диффи и Хеллман утверждали, что специализированный параллельный компьютер для вскрытия DES, стоящий 20 миллионов долларов, сможет раскрыть ключ за день. В 1981 году Диффи увеличил время поиска до двух дней, а стоимость - до 50 миллионов долларов [491]. Диффи и Хеллман утверждали, что вскрытие в тот момент времени находилось за пределами возможностей любой организации, кроме подобных NSA, но что к 1990 году DES должен полностью утратить свою безопасность [714].

Хеллман [716] продемонстрировал еще один аргумент против малого размера ключа: разменивая объем п а-мяти на время, можно ускорить процесс поиска. Он предложил вычислять и хранить 2 56 возможных результатов шифрования каждым возможным ключом единственного блока открытого текста. Тогда для взлома неизвестн ого ключа криптоаналитику потребуется только вставить блок открытого текста в шифруемый поток, вскрыть получившийся результат и найти ключ. Хеллман оценил стоимость такого устройства вскрытия в 5 миллионов долларов.

Аргументы за и против существования в каком-нибудь тайном бункере правительственного устройства вскрытия DES продолжают появляться. Многие указывают на то, что среднее время наработки на отказ для микросхем DES никогда не было большим настолько, чтобы обеспечивать работу устройства. В [1278] было показано, что этого возражения более чем достаточно. Другие исследователи предлагают способы еще больше ускорить процесс и уменьшить эффект отказа микросхем.

Между тем, аппаратные реализации DES постепенно приблизились к реализации требования о миллионе шифрований в секунду, предъявляемого специализированной машиной Диффи и Хеллмана. В 1984 году были выпущены микросхемы DES, способные выполнять 256000 шифрования в секунду [533, 534]. К 1987 году были разработаны микросхемы DES, выполняющие 512000 шифрований в секунду, и стало возможным появление варианта, способного проверять свыше миллиона ключей в секунду [738, 1573]. А в 1993 Майкл Винер (Michael Wiener) спроектировал машину стоимостью 1 миллион долларов, которая может выполнить вскрытие DES гр убой силой в среднем за 3.5 часа (см. раздел 7.1).

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

В 1990 году два израильских математика, Бихам (Biham) и Шамир, открыли дифференциальный криптоанализ, метод, который позволил оставить в покое вопрос длины ключа. Прежде, чем мы рассмотрим этот метод, вернемся к некоторым другим критическим замечаниям в адрес DES.

Количество этапов

Почему 16 этапов? Почему не 32? После пяти этапов каждый бит шифротекста является функцией всех б и-тов открытого текста и всех битов ключа [1078, 1080], а после восьми этапов шифротекст по сути представляет собой случайную функцию всех битов открытого текста и всех битов ключа [880]. (Это называется лавинным эффектом.) Так почему не остановиться после восьми этапов?

В течение многих лет версии DES с уменьшенным числом этапов успешно вскрывались. DES с тремя и ч е-тырьмя этапами был легко взломан в 1982 году [49]. DES с шестью этапами пал несколькими годами позже [336]. Дифференциальный криптоанализ Бихама и Шамира объяснил и это: DES с любым количеством этапов, меньшим 16, может быть взломан с помощью вскрытия с известным открытым текстом быстрее, чем с пом о-щью вскрытия грубой силой. Конечно грубый взлом является более вероятным способом вскрытия, но интер е-сен тот факт, что алгоритм содержит ровно 16 этапов.

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

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

С момента появления алгоритма для анализа схемы и работы S-блоков были предприняты значительные усилия. В середине 70-х Lexar Corporation [961, 721] и Bell Laboratories [1120] исследовали работу S-блоков. Ни одно из исследований не обнаружило никаких слабостей, хотя оба исследования обнаружили непонятный сво й-ства. S-блоки имеют больше свойств, общих с линейным преобразованием, чем можно было ожидать при их формировании случайным образом. Команда Bell Laboratories констатировала, что S-блоки могут содержать скрытые лазейки, а доклад Lexar завершался следующей фразой:

В DES были найдены структуры, несомненно вставленные для повышения устойчивости системы к определенным типам вскрытия. Также были найдены структуры, кот орые, по видимому, ослабили систему.

С другой стороны этот доклад также содержал следующее предупреждение:

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

На втором симпозиуме по DES Агентство национальной безопасности раскрыло ряд критериев проектиров а-ния S-блоков [229]. Но это не смогло снять всех подозрений, и спор продолжился [228, 422, 714, 1506, 1551].

В литературе про S-блоки писались удивительные вещи. Последние три бита результата четвертого S-блока могут быть получены тем же способом, что и первые, при помощи дополнения некоторых из входных битов [436, 438]. Различные, но тщательно подобранные входные данные для S-блоков могут давать одинаковый р е-зультат [436]. Можно получить результат одного этапа DES, меняя биты только в трех соседних S-блоках [487]. Шамир заметил, что элементы S-блоков, казалось, б1ли несколько неустойчивы, но не собирался использовать эту неустойчивость для вскрытия [1423]. (0н упомянул об особенности пятого S-блока, но только спустя восемь лет линейный криптоанализ воспользовался этой особенностью.) Другие исследователи показали, что для пол учения S-блоков с наблюдаемыми характеристиками могли использоваться общеизвестные принципы проект и-рования [266).

Дополнительные результаты

Были предприняты и другие попытки криптоанализировать DES. 0дин из криптографов искал закономерн ости, используя спектральные тесты [559]. Другие анализировали последовательность линейных множителей, но их вскрытие потерпело неудачу после восьми этапов [1297, 336, 531]. Неопубликованное вскрытие, выполне н-ное в 1987 году Дональдом Дэвисом (Donald Davies), использовало способ, с помощью которого перестановка с расширением повторяет биты в соседних S-блоках, это вскрытие также оказалось бесполезным после восьми этапов [172, 429].

12.4 Дифференциальный и линейный криптоанализ

Дифференциальный криптоанализ

В 1990 году Эли Бихам и Ади Шамир ввели понятие дифференциального криптоанализа [167, 168, 171, 172]. Это б1л новый, ранее неизвестный метод криптоанализа. Используя этот метод, Бихам и Шамир нашли способ вскрытия DES с использованием выбранного открытого текста, который был эффективнее вскрытия гр убой силой.

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