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

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

EKi( EKi( P)) = ЕКъ( P)

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

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

Ek3( Ek2( Ek1( 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-блоков, казалось, были несколько неустойчивы, но не собирался использовать эту неустойчивость для вскрытия [1423]. (Он упомянул об особенности пятого S-блока, но только спустя восемь лет линейный криптоанализ воспользовался этой особенностью.) Другие исследователи показали, что для пол учения S-блоков с наблюдаемыми характеристиками могли использоваться общеизвестные принципы проект и-рования [266).

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

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

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

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

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

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

через этапы DES при шифровании одним и тем же ключом.

Просто выберем пару открытых текстов с фиксированным различием. Можно выбрать два открытых текста случайным образом, лишь бы они отличались друг от друга определенным образом, криптоаналитику даже не нужно знать их значений. (Для DES термин "различие" определяется с помощью XOR. Для других алгоритмов этот термин может определяться по другому.) Затем, используя различия в получившихся шифротекстах, пр и-своим различные вероятности различным ключам. В процессе дальнейшего анализа следующих пар шифроте к-стов один из ключей станет наиболее вероятным. Это и есть правильный ключ.

Подробности гораздо сложнее. На 7-й представлена функция одного этапа DES. Представьте себе пару вх о-дов, X и X, с различием AX. Выходы, Y и Y известны, следовательно, известно и различие между ними AY. Известны и перестановка с расширением, и P-блок, поэтому известны AA и AC. B и B неизвестны, но их разность AB известна и равна AA. (При рассмотрении различия XOR K с A и A нейтрализуются.) Пока все просто. Фокус вот в чем: для любого заданного AA не все значения AC равновероятны. Комбинация AA и AC позволяет предположить значения битов для A XOR К,- и A XOR K Так как A и A известны, это дает нам информацию о K

Рис. 12-5. Функция этапа DES.

Взглянем на последний этап DES. (При дифференциальном криптоанализе начальная и заключительная п е-рестановки игнорируются. Они не влияют на вскрытие, только затрудняя объяснение.) Если мы сможем опред е-лить K16, то мы получим 48 битов ключа. (Не забывайте, на каждом этапе подключ состоит из 48 битов 56-битового ключа.) Оставшиеся 8 битов мы можем получить грубым взломом. K16 даст нам дифференциальный криптоанализ.

Определенные различия пар открытых текстов обладают высокой вероятностью вызвать определенные ра з-личия получаемых шифротекстов. Эти различия называются характеристиками. Характеристики распространяются на определенное количество этапов и по существу определяют прохождение этих этапов. Существуют входное различие, различие на каждом этапе и выходное различие - с определенной вероятностью.

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

Например, на 6-йа показана характеристика одного этапа. Входное различие слева равно L, оно может быть произвольным. Входное различие справа равно 0. (У двух входов одинаковая правая половина, поэтому их ра з-личие - 0.) Так как на входе функции этапа нет никаких различий, то нет различий и на выходе функции этапа. Следовательно, выходное различие левой части - L © 0 = L, а выходное различие правой части - 0. Это трив и-альная характеристика, она истинна с вероятностью 1.