На 6-йб показана менее очевидная характеристика. Снова, различие L левых частей произвольно. Входное различие правых частей равно 0x60000000, два входа отличаются только первым и третьим битами. С вероя т-ностью 14/64 различие на выходе функции этапа равно L © 0x00808200. Это означает, что выходное различие левых половин равно L © 0x00808200, а выходное различие правых половин - 0x60000000 (с вероятностью

А = L т

*- f \<-

А = 0-1 А = 0

А = L © 0

А = L т

А = L © 0

X = 0x60000000 Y = 0x00808200

С вероятностью 1С вероятностью 14/64

Рис. 12-6. Характеристики DES.

Различные характеристики можно объединять. Также, при условии, что этапы независимы, вероятности м о-гут перемножаться. На 5-й объединяются две ранее описанных характеристики. Входное различие слева равно 0x00808200, а справа - 0x60000000. В конце первого этапа входное различие и результат функции этапа нейтр а-лизуют друг друга, и выходное различие равно 0. Это различие поступает на вход второго этапа, окончательное выходное различие слева равно 0x60000000, а справа - 0. Вероятность этой двухэтапной характерист ики - 14/64.

А = Y т

А = Y1-1 А = X

X = 0x60000000 Y = 0x00808200

С вероятностью 14/64

Рис. 12-7. Двухэтапная характеристика DES.

Пара открытых текстов, соответствующих характеристике, называется правильной парой, а пара открытых текстов, несоответствующих характеристике - неправильной парой. Правильная пара подсказывает правильный ключ этапа (для последнего этапа характеристики), неправильная пара - случайный ключ этапа.

Чтобы найти правильный ключ этапа, нужно просто собрать достаточное количество предположений. Один

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

Итак, дифференциальное основное вскрытие n-этапного DES дает 48-битовый подключ, используемый на этапе n, а оставшиеся 8 битов ключа получаются с помощью грубого взлома.

Но ряд заметных проблем все же остается. Во первых, пока вы не перейдете через некоторое пороговое зн а-чение, вероятность успеха пренебрежимо мала. То есть, пока не будет накоплено достаточное количество да н-ных, выделить правильный подключ из шума невозможно. Кроме того, такое вскрытие не практично. Для хр а-нения вероятностей 248 возможных ключей необходимо использовать счетчики, и к тому же для вскрытия п о-требуется слишком много данных.

Бихам и Шамир предложили свой способ вскрытия. Вместо использования 15-этапной характеристики 16-этапного DES, они использовали 13-этапную характеристику и ряд приемов для получения последних нескол ь-ких этапов. Более короткая характеристика с большей вероятностью будет работать лучше. Они также испол ь-зовали некоторые сложные математические приемы для получения вероятных 56-битовых ключей, которые и проверялись немедленно, таким образом устранялась потребность в счетчиках. Такое вскрытие достигает усп е-ха, как только находится правильная пара. Это позволяет избежать порогового эффекта и получить линейную зависимость для вероятности успеха. Если у вас в 1000 раз меньше пар, то вероятность успеха в 1000 раз мен ь-ше. Это звучит ужасно, но это намного лучше, чем порог. Всегда есть некоторая вероятность немедленной уд а-чи.

Результаты являются весьма интересными. В -2-й проведен обзор лучших дифференциальных вскрытий DES с различным количеством этапов [172]. Первый столбец содержит количество этапов. Элементы следующих двух столбца представляют собой количество выбранных или известных открытых текстов, которые должны быть проверены для вскрытия, а четвертый столбец содержит количество действительно проанализированных открытых текстов. В последнем столбце приведена сложность анализа, после обнаружения требуемой пары.

Табл. 12-14. Вскрытие с помощью дифференциального криптоанализа

f Сложность анализа для этих вариантов может быть значительно уменьшена за счет использования примерно в четыре раза большего количество открытых текстов и метода группировок.

Наилучшее вскрытие полного 16-этапного DES требует 2 47 выбранных открытых текстов. Можно преобразовать его к вскрытию с известным открытым текстом, но для него потребуется уже 2 55 известных открытых текстов. При анализе потребуется 237 операций DES.

Дифференциальный криптоанализ эффективен против DES и аналогичных алгоритмов с постоянными S-блоками. Эффективность вскрытие сильно зависит от структуры S-блоков, блоки DES по счастливой случайн ости были оптимизированы против дифференциального криптоанализа. Для всех режимов работы DES - ECB, CBC, CFB и OFB - вскрытие с дифференциальным криптоанализом имеет одинаковую сложность [172].

Устойчивость DES может быть повышена путем увеличения количества этапов. Дифференциальный кри п-тоанализ с выбранным открытым текстом для DES с 17 или 18 этапами потребует столько же времени, сколько нужно для вскрытия грубой силой [160]. При 19 и более этапах дифференциальный криптоанализ становится невозможным, так как для него потребуется более, чем 2 64 выбранных открытых текстов - не забудьте, DES и с-пользует блоки размером 64 битов, поэтому для него существует только 2 64 возможных открытых текстов. (В общем случае, вы можете доказать устойчивость алгоритма к дифференциальному криптоанализу, показав, что количество открытых текстов, необходимых для выполнения вскрытия, превышает количество возможных о т-крытых текстов.)

Нужно отметить ряд важных моментов. Во первых, это вскрытие в значительной степени теоретическое. О г-ромные требования к времени и объему данных, необходимых для выполнения вскрытия с помощью дифф е-ренциального криптоанализа, находятся почти для всех вне пределов досягаемости. Чтобы получить нужные данные для выполнения такого вскрытия полного DES, вам придется почти три года шифровать поток выбра н-ных шифротекстов 1.5 Мегабит/с. Во вторых, это в первую очередь вскрытие с выбранным открытым текстом. Оно может быть преобразовано к вскрытию с известным открытым текстом, но вам придется просмотреть все пары "открытый текст/шифротекст" в поисках полезных. В случае полного 16-этапного DES это делает вскр ы-тие чуть менее эффективным по сравнению с грубой силой (вскрытие дифференциальным криптоанализом тр е-бует 255.1 операций, а вскрытие грубой силой - 255). Таким образом, правильно реализованный DES сохраняет устойчивость к дифф еренциальному криптоанализу.

Почему DES так устойчив к дифференциальному криптоанализу? Почему S-блоки оптимизированы так, что усложняют такое вскрытие насколько возможно? Почему используется ровно столько, а не больше этапов? П о-тому что создатели DES знали о дифференциальном анализе. Дон Копперсмит из IBM недавно писал [373, 374]:

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

Ади Шамир откликнулся, предложив Копперсмиту признаться, что с тех пор ему не удалось найти эффе к-тивного способа вскрытия DES. Копперсмит предпочел отмолчат ься [1426].

Криптоанализ со связанными ключами

В 9-й показано количество битов, на которые циклически смещается ключ DES на каждом этапе: на 2 бита на каждом этапе, кроме этапов 1, 2, 9 и 16, когда ключ сдвигается на 1 бит. Почему?

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

Модифицированный DES, в котором ключ сдвигается на два бита после каждого этапа, менее безопасен. Криптоанализ со связанными ключами может взломать такой вариант алгоритма, использовав только 2 17 выбранных открытых текстов для выбранных ключей или 2 33 известных открытых текстов для выбранных ключей [158, 163].

Такое вскрытие также не реализуемо на практике, но оно интересно по трем причинам. Во первых, это пе р-вая попытка криптоаналитического вскрытия алгоритма генерации подключей в DES. Во вторых, это вскрытие не зависит от количества этапов криптографического алгоритма, он одинаково эффективен против DES с 16, 32 или 1000 этапами. И в третьих, DES невосприимчив к такому вскрытию. Изменение количества битов циклич е-ского сдвига мешает криптоанализу со связанными ключами.

Линейный криптоанализ

Линейный криптоанализ представляет собой другой тип криптоаналитического вскрытия, изобретенный Мицуру Мацуи (Mitsuru Matsui) [1016, 1015, 1017]. Это вскрытие использует линейные приближения для оп и-сания работы блочного шифра (в данном случае DES.)

Это означает, что если вы выполните операцию XOR над некоторыми битами открытого текста, затем над некоторыми битами шифротекста, а затем над результатами, вы получите бит, который представляет собой XOR некоторых битов ключа. Это называется линейным приближением, которое может быть верным с некот о-рой вероятностью p. Если p ф 1/2, то это смещение можно использовать. Используйте собранные открытые те к-сты и связанные шифротексты для предположения о значениях битов ключа. Чем больше у вас данных, тем вернее предположение. Чем больше смещение, тем б ыстрее вскрытие увенчается успехом.

Как определить хорошее линейное приближение для DES? Найдите хорошие одноэтапные линейные пр и-ближения и объедините их. (Начальная и заключительная перестановки снова игнорируются, так как они не влияют на вскрытие.) Взгляните на S-блоки. У них 6 входных битов и 4 выходных. Входные биты можно объ единить с помощью операции XOR 63 способами (2 6 - 1), а выходные биты - 15 способами. Теперь для каждого S-блока можно оценить вероятность того, что для случайно выбранного входа входная комбинация XOR равна некоторой выходной комбинации XOR. Если существует комбинация с достаточно большим смещением, то л и-нейный криптоанализ может сработать.

Если линейные приближения не смещены, то они будут выполняться для 32 из 64 возможных входов. Я из-