Методы и средства криптографической защиты информации

12. Алгоритм должен позволять эффективную программную реализацию на больших мэйнфреймах, миникомпьютерах, микрокомпьютерах и с помощью дискретной логики. (По сути используемые в алгоритме функции ограничены XOR и битовым сдвигом.)

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

Описание Madryga

Madryga состоит из двух вложенных циклов. Внешний цикл повторяется восемь раз (но это количество может быть увеличено для повышения) и содержит применение внутреннего цикла к открытому тексту. Внутренний цикл превращает открытый текст в шифротекст, повторяясь для каждого 8-битового блока (байта) открытого текста. Следовательно, весь открытый текст восемь раз последовательно обрабатывается алгоритмом.

Итерация внутреннего цикла оперирует с 3-байтовым окном данных, называемым рабочим кадром. Это окно смещается на 1 байт за итерацию. (При работе с последними 2 байтами данные считаются циклически замкнутыми.) Первые два байта рабочего кадра циклически сдвигаются на переменное число позиций, а для последнего байта выполняется XOR с некоторыми битами ключа. По мере продвижения рабочего кадра все байты последовательно "вращаются" и подвергаются операции XOR с частями ключа. Последовательные вращения перемешивают результаты предыдущих операций XOR и вращения, а результат XOR влияет на вращение. Это делает весь процесс обратимым.

Рис. 22 Одна итерация Madryga.

Так как каждый байт данных влияет на два байта слева от себя и на один байт справа, после восьми проходов каждый байт шифротекста зависит от 16 байтов слева и от восьми байтов справа.

При шифровании каждая итерация внутреннего цикла устанавливает рабочий кадр на предпоследний байт открытого текста и циклически перемещает его к байту открытого текста, третьему слева от последнего. Сначала весь ключ подвергается операции XOR со случайной константой и затем циклически смещается влево на 3 бита. Младшие три бита младшего байта рабочего кадра сохраняются, они определяют вращение остальных двух байтов. Затем для младшего байта рабочего кадра выполняется операция XOR с младшим байтом ключа. Далее объединение двух старших байтов циклически смещается влево на переменное число битов (от 0 до 7). Наконец рабочий кадр смещается вправо на один байт и весь процесс повторяется.

Смысл случайной константы в том, чтобы превратить ключ в псевдослучайную последовательность. Длина константы должна быть равна длине ключа. При обмене данными абоненты должны пользоваться константой одинаковой длины. Для 64-битового ключа Мадрига рекомендует константу 0x0fle2d3c4b5a6978.

При дешифрировании процесс инвертируется. При каждой итерации внутреннего цикла рабочий кадр устанавливается на байт, третий слева от последнего байта шифротекста, и циклически перемещается в обратном направлении до байта, который находится на 2 байта левее последнего байта шифротекста. И ключ, и 2 байта шифротекста в процессе циклически смещаются направо, а XOR выполняется перед циклическими сдвигами.

Криптоанализ Madryga

Исследователи из Технического университета в Квинсланде (Queensland University of Technology) исследовали Madryga вместе с некоторыми другими блочными шифрами. Они обнаружили, что в этом алгоритме не проявляется лавинный эффект для преобразования открытого текста в шифротекст. Кроме того, во многих шифротекстах процент единиц был выше, чем процент нулей.

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

Алгоритм состоит только из линейных операций (циклическое смещение и XOR), незначительно изменяемых в зависимости от данных.

В этом нет ничего похожего на мощь S-блоков DES.

Четность всех битов шифротекста и открытого текста неизменна и зависит только от ключа. Поэтому, обладая открытым текстом и соответствующим шифротекстом, можно предсказать четность шифротекста для любого открытого текста.

2.5.3 Алгоритмы KHUFU и KHAFRE

В 1990 году Ральф Меркл (Ralph Merkle) предложил два алгоритма. В основе их проектирования лежали следующие принципы:

1. 56-битовый размер ключа DES слишком мал. Так как стоимость увеличения размера ключа пренебрежимо мала (компьютерная память недорога и доступна), он должен быть увеличен.

2. Интенсивное использование перестановок в DES хотя и удобно для аппаратных реализаций, чрезвычайно затрудняет программные реализации. Наиболее быстрые реализации DES выполняют перестановки табличным образом. Просмотр таблицы может обеспечить те же характеристики "рассеяния", что и собственно перестановки, и может сделать реализацию намного более гибкой.

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

4. Широко признано, что начальная и заключительная перестановки криптографически бессмысленны, поэтому они должны быть устранены.

5. Все быстрые реализации DES заранее рассчитывают ключи для каждого этапа. При данном условии нет смысла усложнять эти вычисления.

6. В отличие от DES критерии проектирования S-блоков должны быть общедоступны.

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

Khufu

Khufu - это 64-битовый блочный шифр. 64-битовый открытый тест сначала разбивается на две 32-битовые половины, L и R. Над обеими половинами и определенными частями ключа выполняется операция XOR. Затем, аналогично DES, результаты проходят через некоторую последовательность этапов. На каждом этапе младший значащий байт L используется в качестве входных данных S-блока. У каждого S-блока 8 входных битов и 32 выходных бита. Далее выбранный в S-блоке 32-битовый элемент подвергается операции XOR с R. Затем L циклически сдвигается не несколько из восьми битов, L и R меняются местами, и этап заканчивается. Сам S-блок не является статическим, но меняется каждые восемь этапов. Наконец после последнего этапа над L и R выполняется операция XOR с другими частями ключа, и половины объединяются, образуя блок шифротекста.

Хотя части ключа используются для XOR с блоком шифрования в начале и в конце алгоритма, главная цель ключа - генерация S-блоков. Эти S-блоки - секретны, по сути являются они являются частью ключа. Полный размер ключа Khufu равен 512 битам (64 байтам), алгоритм предоставляет способ генерации S-блоков по ключу. Количество этапов алгоритма остается открытым. Меркл упомянул, что 8-этапный Khufu чувствителен к вскрытию с выбранным открытым текстом и рекомендует 16, 24 или 32 этапа. (Он ограничивает выбор количества этапов числами, кратными восьми.)

Так как в Khufu используются зависимые от ключа и секретные S-блоки, он устойчив к дифференциальному криптоанализу. Существует дифференциальное вскрытие 16-этапного Khufu, которое раскрывает ключ после 2³¹ выбранных открытых текстов, но его не удалось расширить на большее количество этапов. Если лучшим способом вскрыть Khufu является грубая сила, то его надежность производит сильное впечатление. 512-битовый ключ обеспечивает сложность 2⁵¹² - огромное число при любых условиях.

Khafre

Khafre - это вторая из криптосистем, предложенных Мерклом. (Khufu (Хуфу) и Khafre (Хафр) - это имена египетских фараонов.) По конструкции этот алгоритм похож на Khufu, но он спроектирован для приложений, не использующих предварительных вычислений. S-блоки не зависят от ключа. Вместо этого Khafre использует фиксированные S-блоки. Блок шифрования подвергается операции XOR с ключом не только перед первым этапом и после последнего, но и после каждых 8 этапов шифрования.

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

В 1990 году Бихам и Шамир применили свой метод дифференциального анализа против Khafre. Им удалось взломать 16-этапный Khafre с помощью вскрытия с выбранным открытым текстом после 1500 различных шифрований. На их персональном компьютере это заняло около часа. Преобразование этого вскрытия во вскрытие с известным открытым текстом потребует около 238 шифрований. Khafre с 24 этапами может быть вскрыт с помощью вскрытия с выбранным открытым текстом за 253 шифрования, а с помощью вскрытия с известным открытым текстом - за 259 шифрования.

2.5.4 Алгоритм RC2

RC2 представляет собой алгоритм с переменной длиной ключа, спроектированный Роном Ривестом (Ron Rivest) для RSA Data Security, Inc. (RSADSI). Очевидно "RC" - это сокращенное "Ron's Code" ("Код Рона"), хотя официально это "Rivest Cipher" ("Шифр Ривеста"). (RC3 был взломан в RSADSI в процессе разработки, RC1 не вышел за пределы записной книжки Ривеста.) Он представляет собой частную собственность, и его детали не были опубликованы. RC2 уже появился в коммерческих продуктах. RC2 не был запатентован и защищен только как торговый секрет.

RC2 - это шифр с 64-битовым блоком и переменной длиной ключа, предназначенный заменить DES. В соответствии с утверждениями компании программные реализации RC2 в три раза быстрее DES. Алгоритм может использовать ключ переменной длины, от 0 байтов до максимальной длины строки, поддерживаемой компьютерной системой, скорость шифрования не зависит от размера ключа. Этот ключ предварительно используется для заполнения 128-байтовой таблицы, зависящей от ключа. Поэтому множество действительно различных ключей составляет 21024. RC2 не использует S-блоков, используются две операции - "смешивание" и "перемешивание" ("mix" и "mash"), для каждого этапа выбирается одна из них. В соответствии с литературой:

. . . RC2 не является итеративным блочным шифром. Это предполагает, что RC2 более устойчив к дифференциальному и линейному криптоанализу, чем другие блочные шифры, безопасность которых опирается на копирование схемы DES.

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

RC4, также являющийся интеллектуальной собственностью RSADSI, был опубликован в Internet, и, вероятно, опубликование RC2 является только вопросом времени.

По соглашению между Ассоциацией издателей программного обеспечения (Software Publishers Association, SPA) и правительством США RC2 и RC4 получили специальный экспортный статус. Процесс получения разрешения на экспорт продуктов, реализующих один из этих двух алгоритмов, значительно упрощен при условии, что длина ключа не превышает 40 битов.

Достаточен ли 40-битовый ключ? Существует всего один триллион возможных ключей. При условии, что наиболее эффективным методом криптоанализа является вскрытие грубой силой (большое допущение, ведь алгоритм никогда не был опубликован), и что микросхема грубого вскрытия может проверить миллион ключей в секунду, поиск правильного ключа займет 12.7 дней. Тысяча машин, работающих параллельно, смогут раскрыть ключ за двадцать минут.

RSA Data Security, Inc., утверждает, что, хотя шифрование и дешифрирования выполняются для быстро, исчерпывающего поиска потребуется намного больше времени. Заметное количество времени тратится на формирование плана использования ключа. Хотя это время пренебрежимо мало при шифровании и дешифрировании сообщений, это не так при проверке каждого возможного ключа.

Правительство США никогда не позволило бы экспортировать любой алгоритм, который оно, по крайней мере в теории, не смогло бы вскрыть. Оно может создать магнитную ленту или CD с конкретным блоком открытого текста, зашифрованным каждым возможным ключом. Для вскрытия сообщения остается только вставить ленту и сравнить блоки шифротекста в сообщении с блоками шифротекста на ленте. При совпадении можно проверить возможный ключ и посмотреть, имеет ли сообщение какой-нибудь смысл. Если они выберут часто встречающийся блок (все нули, ASCII-символы пробела, и т.д.), этот метод будет работать. Объем данных, нужный для хранения результатов шифрования 64-битового блока открытого текста всеми 10¹² возможными ключами, составляет 8 терабайтов - вполне реально.

2.5 Алгоритм MMB

Недовольство использованием в IDEA 64-битового блока шифрования привело к созданию Джоном Дэймоном алгоритма под названием MMB (Modular Multiplication-based Block cipher, модульный блочный шифр, использующий умножения). В основе ММВ лежит теория, используемая и в IDEA: перемешивающие операции из различных групп. ММВ - это итеративный алгоритм, главным образом состоящий из линейных действий (XOR и использование ключа) и параллельное использование четырех больших нелинейных изменяющих обычный порядок подстановок. Эти подстановки определяются с помощью умножения по модулю 2³²-1 с постоянными множителями. Результатом применения этих действий является алгоритм, использующий и 128-битовый ключ и 128-битовый блок.

ММВ оперирует 32-битовыми подблоками текста (x₀, x₁, x₂, x₃) и 32-битовыми подблоками ключа (k₀, k₁, k₂, k₃). Это делает удобным реализацию алгоритма на современных 32-битовых процессорах. Чередуясь с XOR, шесть раз используется нелинейная функция f. Вот этот алгоритм (все операции с индексами выполняются по модулю 3):

x_i = x_i k_i, для i = 0 до 3

f(x₀, х₁ х₂, х₃)

x_i = x_i k_i+1, для i = 0 до 3

f(x₀, x , x₂, x₃)

x_i = x_i k_i+2, для i = 0 до 3

f(x₀, x , x₂, x₃)

x_i = x_i k_i для i = 0 до 3

f(x₀, x₁, x₂, x₃)

x_i = x_i k_i+1, для i = 0 до 3

f(x₀, x₁, x₂, x₃)

x_i = x_i k_i+2, для i = 0 до 3

f(x₀, x₁, x₂, x₃)

У функции f три этапа:

(1) x₁ = c_i*x_i, для i = 0 до 3 (Если на входе умножения одни единицы, то на выходе - тоже одни единицы.)

(2) Если младший значащий бит х₀= 1, то x₀ = х₀ С. Если младший значащий бит х₃ = 0, то х₃ = х₃ С.

(3) x_i = х_i-1 x_i x_i+1, для i = 0 до 3

Все операции с индексами выполняются по модулю 3. Операция умножения на этапе (1) выполняется по модулю 2³²-1. В данном алгоритме если второй операнд - это 2³²-1, то результат также равен 2³²-1. В алгоритме используются следующие константы:

С = 2ааааааа

с₀= 025flcdb

c₁ = 2 * с₀

с₂= 2³ * с₀ с₃ = 2⁷ * с₀

Константа С - это "простейшая" константа с высоким троичным весом, нулевым младшим значащим битом и без круговой симметрии. У константы с₀ несколько иные характеристики. Константы с₁, c₂ и c₃ являются смещенными версиями c₀, и используются для предотвращения вскрытий основанных на симметрии.

Дешифрирование является обратным процессом. Этапы (2) и (3) заменяются на свою инверсию. На этапе (1) вместо с,^-1 используется с_i с_i^-1 = 0dad4694.

Безопасность ММВ

Схема ММВ обеспечивает на каждом этапе значительное и независимое от ключа рассеяние. В IDEA pa c-сеяние до определенной степени зависит от конкретных подключей. В отличие от IDEA у ММВ нет слабых ключей.

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

Во вторых, Эли Бихам реализовал эффективное вскрытие с выбранным ключом, использующеее тот факт, что все этапы идентичны, а ключ при использовании просто циклически сдвигается на 32 бита. В третьих, несмотря на то, что программные реализации ММВ были бы очень эффективны, в аппаратном исполнении алгоритм менее эффективен, чем DES.

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

2.5.6 Алгоритм СА-1.1

СА - это блочный шифр, основанный на клеточных автоматах и разработанный Говардом Гутовицом (Howard Gutowitz). Он шифрует 384-битовые блоки открытого текста 1088-битовым ключом (на самом деле используется два ключа - 1024-битовый и 64- битовый). Из-за природы клеточных автоматов алгоритм наиболее эффективен при реализации в больших параллельных интегрированных схемах.

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

Обратимые правила (простые параллельные перестановки подблоков состояния) нелинейны. Необратимые правила полностью определяются ключом, а обратимые зависят как от ключа, так и от случайной информации, вставленной в ходе шифрования необратимыми правилами.

СА-1.1 основан на структуре блочных связей. То есть, обработка блока сообщения частично отделена от обработки потока случайной информации, вставленной при шифровании. Эта случайная информация служит для связи друг с другом стадий шифрования. Она также может быть использована для связи с потоком шифротекста. Информация связи генерируется как часть шифрования.

Так как СА-1.1 представляет собой новый алгоритм, слишком рано делать какие-либо заявления о его безопасности. Гутовиц упоминает некоторые возможные вскрытия, включая дифференциальный криптоанализ, но ему не удалось вскрыть алгоритм. В качестве стимула Гутовиц предложил награду в 1000 долларов для "первого человека, который разработает доступную процедуру вскрытия СА-1.1."

СА-1.1 запатентован, но доступен для некоммерческого использования.

2.5.7 Алгоритм SKIPJACK

Skipjack разработан NSA в качестве алгоритма шифрования для микросхем Clipper и Capstone. Так как этот алгоритм объявлен секретным, его подробности никогда не публиковались. Он будет реализован только как защищенная от взлома аппаратура.

Этот алгоритм объявлен секретным не потому, что это повышает его надежность, а потому что NSA не хочет, чтобы Skipjack использовался без механизма условного вручения ключей Clipper. Агентство не хочет, чтобы программные реализации алгоритма распространились по всему миру.

Безопасен ли Skipjack? Если NSA захочет создать безопасный алгоритм, оно, скорее всего, это сделает. С другой стороны, если NSA захочет создать алгоритм с лазейкой, то оно сможет сделать и это. Вот что было опубликовано.

-- Это итеративный блочный шифр.

-- Размер блока - 64 бита.

-- Алгоритм использует 80-битовый ключ.

-- Он может быть использован в режимах ЕСВ, СВС, 64-битовый OFB, либо 1-, 8-, 16-, 32- или 64-битовый CFB.

-- Операция шифрования или дешифрирования состоит из 32 этапов.

-- NSA начало работу над ним в 1985 и завершило проверку в 1990.

В документации на микросхему Mykotronx Clipper утверждается, что задержка в выдаче результата, присущая алгоритму Skipjack, составляет 64 такта. Это означает, что на каждый этап приходится два такта: один предположительно для подстановки с помощью S-блока, а другой - для заключительного XOR в конце каждого этапа. (Не забывайте, перестановки при аппаратных реализациях не занимают времени.) В документации Mykotronx эта двухтактная операция называется "G-блоком", а все вместе - "сдвигом". (Часть G-блока носит название "F-таблицы" и является таблицей констант, а может быть таблицей функций.)

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

Еще один слух утверждает, что этапы Skipjack, в отличие от DES, работают не с половиной блока. Это вместе с замечанием о "сдвигах" и случайном заявлении на Crypto '94 о том, что в Skipjack применяется "48-битовая внутренняя структура", позволяет сделать вывод, что алгоритм по своей схеме похож на SHA, но использует четыре 16-битовых подблока. Три подблока, обработанные зависящей от ключа однонаправленной функцией, дают 16 битов, которые подвергаются операции XOR с оставшимся подблоком. Затем весь блок циклически сдвигается на 16 битов и поступает на вход следующего этапа, или сдвига. При этом также используются 128 байтов данных S-блока.

По своей структуре Skipjack вероятно похож на DES. NSA понимает, что его защищенная от взлома аппаратура в конце концов будет вскрыта и исследована, они не будут рисковать никакими передовыми криптографическими методами.

То, что NSA планирует использовать алгоритм Skipjack для шифрования своей Системы защиты сообщений (Defense Messaging System, DMS), свидетельствует о безопасности алгоритма. Чтобы убедить скептиков, NIST разрешил комиссии "уважаемых неправительственных экспертов . . . получить доступ к конфиденциальным подробностям алгоритма, чтобы они исследовали его возможности и опубликовали результаты своих исследований".

В предварительном отчете этой комиссии экспертов (окончательного отчета не было, и возможно никогда не будет) сообщалось:

Принимая во внимание, что стоимость вычислительных мощностей уменьшается в два раза каждые 18 месяцев, cложность вскрытия Skipjack сравняется с сегодняшней сложностью вскрытия DES только через 36 лет. Следовательно, риск, что Skipjack будет взломан в ближайшие 30-40 лет, незначителен.

Незначителен и риск взлома Skipjack с помощью более быстрых способов вскрытия, включая дифференциальный криптоанализ. У алгоритма не слабых ключей, отсутствует и свойство комплиментарности. Эксперты в отсутствие времени для самостоятельного большого исследования алгоритма изучили представленное NSA описание разработки и проверки алгоритма

Устойчивость Skipjack к криптоанализу не зависит от хранения в тайне самого алгоритма.

Итак, участники дискуссии не смогли поработать с алгоритмом достаточно долго, чтобы прийти к каким-нибудь выводам самостоятельно. Все, что они смогли сделать - это взглянуть на результаты, показанные им NSA.

Остался без ответа вопрос, является ли плоским пространство ключей Skipjack. Даже если у Skipjack нет ключей, слабых в смысле DES, ряд особенностей процесса использования ключа может сделать одни ключи сильнее других. У Skipjack может быть 2⁷⁰ сильных ключей, гораздо больше чем у DES, вероятность случайно выбрать один из этих сильных ключей будет приблизительно 1 к 1000.

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

2.6 Объединение блочных шифров

Существует множество способов объединять блочные алгоритмы для получения новых алгоритмов. Стимулом создавать подобные схемы является желание повысить безопасность, не пробираясь через тернии создания нового алгоритма. DES является безопасным алгоритмом, он подвергался криптоанализу добрых 20 лет и, тем не менее, наилучшим способом вскрытия остается грубая сила. Однако ключ слишком короток. Разве не хорошо было бы использовать DES в качестве компонента другого алгоритма с более длинным ключом? Это позволило бы получить преимущества длинного ключа с гарантией двух десятилетий криптоанализа.

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

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

2.6.1 Двойное шифрование

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

C = E_K2(E_K1(P))

P = D_K1(D_K2(C))

Если блочный алгоритм образует группу, то всегда существует К₃, для которого

C = E_K2(E_K1(P))= E_K3(P)

Если алгоритм не образует группу, то при помощи исчерпывающего поиска взломать получающийся дважды зашифрованный блок шифротекста намного сложнее. Вместо 2ⁿ (где п - длина ключа в битах), потребуется 2²ⁿ попыток. Если алгоритм использует 64-битовый ключ, для обнаружения ключей, которыми дважды зашифрован шифротекст, потребуется 2¹²⁸ попыток.

Но при вскрытии с известным открытым текстом это не так. Меркл и Хеллман придумали способ обменять память на время, который позволяет вскрыть такую схему двойного шифрования за 2ⁿ⁺¹ шифрований, а не за 2²ⁿ. (Они использовали эту схему против DES, но результаты можно обобщить на все блочные алгоритмы.) Это вскрытие называется "встреча посередине", с одной стороны выполняется шифрование а с другой - дешифрирование, получившиеся посередине результаты сравниваются.

В этом вскрытии криптоаналитику известны Р₁, С₁, Р₂ и С₂, такие что

C₁=E_K2(E_K1(P₁))

C₂=E_K2(E_K1(P₂))

Для каждого возможного К (или К₁, или К₂), криптоаналитик рассчитывает E_K(P₁) и сохраняет результат в памяти. Собрав все результаты, он для каждого К вычисляет D_K(C₁) и ищет в памяти такой же результат. Если такой результат обнаружен, то возможно, что текущий ключ - К₂, а ключ для результата в памяти - К₁. Затем криптоаналитик шифрует Р₁ с помощью К₁ и К₂. Если он получает С₂, то он может гарантировать (с вероятностью успеха 1 к 2^2п-2т, где т - размер блока), что он узнал и К₁, и К₂. Если это не так, он продолжает поиск. Максимальное количество попыток шифрования, которое ему, возможно, придется предпринять, равно 2*2ⁿ, или 2ⁿ⁺¹. Если вероятность ошибки слишком велика, он может использовать третий блок шифротекста, обеспечивая вероятность успеха 1 к 2^2п-3т. Существуют и другие способы оптимизации.

Для такого вскрытия нужен большой объем памяти: 2ⁿ блоков. Для 56-битового ключа нужно хранить 2⁵⁶ 64-битовых блоков, или 10¹⁷ байтов. Такой объем памяти пока еще трудно себе представить, но этого хватает, чтобы убедить криптографов в том, что двойным шифрованием пользоваться не стоит.

При 128-битовом ключе для хранения промежуточных результатов потребуется 10³⁹ байтов. Вскрытие "встреча посередине" кажется невозможным для ключей такого размера.

Другим способом двойного шифрования, который иногда называют Davies-Price, является вариантом СВС.

С_i=Е_К1(PЕ_Кг(C_i-1)) Р_i=D_К1(С_i) Е_К2(С_i-1))

Утверждается, что "у этого режима нет никаких особых достоинств", к тому же он, по видимому, так же чувствителен ко вскрытию "встреча посередине" как и другие режимы двойного шифрования.

2.6.2 Тройное шифрование

Тройное шифрование с двумя ключами. Воспользуемся [17]. В более интересном методе, предложенном Тачменом, блок обрабатывается три раза с помощью двух ключей: первым ключом, вторым ключом и снова первым ключом. Он предлагает, чтобы отправитель сначала шифровал первым ключом, затем дешифрировал вторым, и окончательно шифровал первым ключом. Получатель расшифровывает первым ключом, затем шифрует вторым и, наконец, дешифрирует первым.

C = E_K1(D_K2(E_K1(P))) P = D_K1(E_K2(D_K1(C)))

Иногда такой режим называют шифрование-дешифрирование-шифрование (encrypt-decrypt-encrypt, EDE). Если блочный алгоритм использует n-битовый ключ, то длина ключа описанной схемы составляет 2n бит. Любопытный вариант схемы шифрование-дешифрирование-шифрование был разработан в IBМ для совместимости с существующими реализациями алгоритма: задание двух одинаковых ключей эквивалентно одинарному шифрованию, этим ключом. Схема шифрование-дешифрирование-шифрование сама по себе не обладает никакой безопасностью, но этот режим был использован для улучшения алгоритма DES в стандартах Х9.7 и ISO 8732.

Ключи К₁ и К₂ чередуются для предотвращения описанного выше вскрытия "встреча посередине". Если С = Е_K1 (Е_K1 (Е_K1 (Р))), то криптоаналитик для любого возможного К₁ может заранее вычислить Е_K1 (Е_K1 (P)) и затем выполнить вскрытие. Для этого потребуется только 2ⁿ⁺² шифрований.

Тройное шифрование с двумя ключами устойчиво к такому вскрытию. Но Меркл и Хеллман разработали другой способ размена памяти на время, который позволяет взломать этот метод шифрования за 2^n-1 действий, используя 2ⁿ блоков памяти.

Для каждого возможного К₂ расшифруйте 0 и сохраните результат. Затем расшифруйте 0 для каждого возможного K₁, чтобы получить Р. Выполните тройное шифрование Р, чтобы получить С, и затем расшифруйте С ключом К₁. Если полученное значение совпадает с значением (хранящемся в памяти), полученным при дешифрировании 0 ключом К₂, то пара К₁ К₂ является возможным результатом поиска. Проверьте, так ли это. Если нет, продолжайте поиск.

Выполнение этого вскрытия с выбранным открытым текстом требует огромного объема памяти. Понадобится 2ⁿ времени и памяти, а также 2^т выбранных открытых текстов. Вскрытие не очень практично, но все же чувствительность к нему является слабостью алгоритма.

Пауль ван Оорсчот (Paul van Oorschot) и Майкл Винер (Michael Wiener) преобразовали это вскрытие ко вскрытию с известным открытым текстом, для которого нужно р известных открытых текстов. В примере предполагается, что используется режим EDE.

(1) Предположить первое промежуточное значения а.

(2) Используя известный открытый текст, свести в таблицу для каждого возможного К₁ второе промежуточное значение b, при первом промежуточном значении, равном а:

b=D_K1(C)

где С - это шифротекст, полученный по известному открытому тексту.

(3) Для каждого возможного К₂ найти в таблице элементы с совпадающим вторым промежуточным значение

b: b=E_K2(a)

(4) Вероятность успеха равно р/т, где р - число известных открытых текстов, a m - размер блока. Если совпадения не обнаружены, выберите другое а и начните сначала.

Вскрытие требует 2^п+т/р времени и р - памяти. Для DES это равно 2¹²⁰/р. Для р, больших 256, это вскрытие быстрее, чем исчерпывающий поиск.

Тройное шифрование с тремя ключами

Если вы собираетесь использовать тройное шифрование, рекомендуются три различных ключа. Общая длина ключа больше, но хранение ключа обычно не является проблемой. Биты дешевы.

С = Е_К3(D_Кг(Е_К1{Р)))

P = D_K1(E_K2(D_K3(C))

Для наилучшего вскрытия с разменом памяти на время, которым является "встреча посередине", потребуется 2^2п действий и 2ⁿ блоков памяти. Тройное шифрование с тремя независимыми ключами безопасно настолько, насколько на первый взгляд кажется безопасным двойное шифрование.

Тройное шифрование с минимальным ключом (ТЕМК)

Существует безопасный способ использовать тройное шифрование с двумя ключами, противостоящий описанному вскрытию и называемый Тройным шифрованием с минимальным ключом (Triple Encryption with Minimum Key, ТЕМК). Фокус в той, чтобы получить три ключа из: Х₁ и Х₂.

K₁=E_X1(D_X2(E_X1(T₁))) K₂=E_X1(D_X2(E_X2(T₂))) K₃ = E_X1(D_X2(E_X1(T₃)))

Т₁, Т₂и Т₃ представляют собой константы, которые необязательно хранить в секрете. Эта схема гарантирует, что для любой конкретной пары ключей наилучшим будет вскрытие с известным открытым текстом

Режимы тройного шифрования

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

Внутренний СВС: Файл три раза шифруется в режиме СВС. Для этого нужно три различных IV.

C₀, S₀ и Т₀ являются IV.

Внешний СВС: Файл троекратно шифруется в режиме СВС. Для этого нужен один IV.

C_i = E_K3(D_K2(E_K1(P_iC_i-1)))

P_i = C_i-1D_K1(E_K2(D_K3(C_i)))

Рис. 25 Тройное шифрование в режиме СВС [17].

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

Напротив, во внешнем СВС обратная связь находится снаружи по отношению к трем шифрованиям. Это означает, что даже с тремя микросхемами производительность будет равна только одной трети производительности при однократном шифровании. Чтобы получить ту же производительность для внешнего СВС, потребуется чередование IV:

C_i=E_K3{D_K2(E_K1(P_iC_i-3)))

В этом случае С₀, C_-1 и С_-2 являются IV. Это не поможет при программной реализации, разве только при использовании параллельного компьютера.

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

Кроме этих существуют и другие режимы. Можно зашифровать файл один раз в режиме ЕСВ, затем дважды в СВС, или один раз в СВС, один в ЕСВ и еще раз в СВС, или дважды в СВС и один раз в ЕСВ. Бихам показал, что эти варианты не безопаснее, чем однократный DES, против вскрытия дифференциальным криптоанализом с выбранным открытым текстом. Он не оставил больших надежд и для других вариантов.

Варианты тройного шифрования

Прежде, чем появились доказательства того, что DES не образует группу, для многократного шифрования предлагались различные схемы. Одним из способов обеспечить то, что тройное шифрование не выродится в однократное, было изменение эффективной дины блока. Простым методом является добавление бита-заполнителя. Между первым и вторым, а также между вторым и третьим шифрованиями текст дополняется строкой случайных битов. Если РР - это функция дополнения, то: C = E_K3(PP(E_K2(PP(E_K1(P))))).

Это дополнение не только разрушает шаблоны, но также обеспечивает перекрытие блоков шифрования, как кирпичей в стене. К длине сообщения добавляется только один блок.

Рис. 26 Тройное шифрование с заполнением.

Другой метод, предложенный Карлом Эллисоном (Carl Ellison), использует некоторую функцию независимой от ключа перестановки между тремя шифрованиями. Перестановка должна работать с большими блоками - 8 Кбайт или около этого, что делает эффективный размер блока для этого варианта равным 8 Кбайтам. При условии, что перестановка выполняется быстро, этот вариант ненамного медленнее, чем базовое тройное шифрование.

C = E_K3(T(E_K2(T(E_K1(P)))))

Т собирает входные блоки (до 8 Кбайт в длину) и использует генератор псевдослучайных чисел для их перемешивания. Изменение одного бита входа приводит к изменению 8 байтов результата первого шифрования, к изменению до 64 байтов результата второго шифрования и к изменению до 512 байтов результата третьего шифрования. Если каждый блочный алгоритм работает в режиме СВС, как было первоначально предложено, то изменение единичного бита входа скорее всего приведет к изменению всего 8-килобайтового блока, даже если этот блок не является первым.

Самый последний вариант этой схемы отвечает на вскрытие внутреннего СВС, выполненное Бихамом, добавлением процедуры отбеливания, чтобы замаскировать структуру открытых текстов. Эта процедура представляет собой потоковую операцию XOR с криптографически безопасным генератором псевдослучайных чисел и ниже обозначена как R. T мешает криптоаналитику определить a priori, какой ключ используется для шифрования любого заданного байта входа последнего шифрования. Второе шифрование обозначено пЕ (шифрование с циклическим использованием п различных ключей):

C = E_K3(R(T(nE_K2(T(E_K1(P))))))

Все шифрования выполняются в режиме ЕСВ, используется не меньше n+2 ключей шифрования и криптографически безопасный генератор псевдослучайных чисел.

Эта схема была предложена для использования вместе с DES, но она работает с любым блочным алгоритмом.

2.6.3 Другие схемы многократного шифрования

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

Удвоение длины блока. Существуют предложения удваивать длину блока алгоритма с помощью многократного шифрования. Прежде, чем реализовывать одно из них, оцените возможность вскрытия "встреча посередине". Схема Ричарда Аутбриджа (Richard Outerbridge), не более безопасна, чем тройное шифрование с одинарным блоком и двумя ключами.

Рис. 27 Удвоение длины блока.

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

Двойной OFB/счетчик

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

S_i=E_K1(S_i-1I₁); I₁=I₁+1 Т_i = Е_К2(Т_i-1I₂); I₂=I₂+1

C_i= P_iS_iT_i

S_i и T_i - внутренние переменные, а I₁ и I₂ - счетчики. Две копии блочного алгоритма работают в некотором гибридном режиме OFB/счетчик, а открытый текст, S_i и T_i, объединяются с помощью XOR. Ключи К₁ и К₂ независимы.

ЕСВ + OFB

Этот метод был разработан для шифрования нескольких сообщений фиксированной длины, например, блоков диска. Используются два ключа: К₁ и К₂. Сначала для генерации маски для блока нужной длины используется выбранный алгоритм и ключ. Эта маска будет использована повторно для шифрования сообщений теми же ключами. Затем выполняется XOR открытого текста сообщения и маски. Наконец результат XOR шифруется с помощью выбранного алгоритма и ключа К₂ в режиме ЕСВ.

Как отмечает Шнайер в [17], анализ этого метода проводился только в той работе, в которой он и был опубликован. Он не слабее одинарного шифрования ЕСВ и возможно также силен, как и двойное применение алгоритма. Вероятно, криптоаналитик может выполнять поиск ключей независимо, если он получит несколько открытых текстов файлов, зашифрованных одним ключом.

Чтобы затруднить анализ идентичных блоков в одних и тех же местах различных сообщений, можно использовать IV. В отличии от использования IV в других режимах в данном случае перед шифрованием ЕСВ выполняется XOR каждого блока сообщения с IV.

Мэтт Блэйз (Matt Blaze) разработал этот режим для своей UNIX Cryptographic File System (CFS, криптографическая файловая система). Это хороший режим, поскольку скрытым состоянием является только одно шифрование в режиме ЕСВ, маска может быть сгенерирована только один раз и сохранена. В CFS в качестве блочного алгоритма используется DES.

xDES¹

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

Первый, xDES¹, представляет собой просто схему Luby-Rackoff с блочным шифром в качестве базовой функции. Размер блока в два раза больше размера блока используемого блочного фильтра, а размер ключа в три раза больше, чем у используемого блочного фильтра. В каждом из 3 этапов правая половина шифруется блочным алгоритмом и одним из ключей, затем выполняется XOR результата и левой половины, и половины переставляются.

Это быстрее, чем обычное тройное шифрование, так как тремя шифрованиями шифруется блок, длина которого в два раза больше длины блока используемого блочного алгоритма. Но при этом существует простое вскрытие "встреча посередине", которое позволяет найти ключ с помощью таблицы размером 2^k, где k - это размер ключа блочного алгоритма. Правая половина блока открытого текста шифруется с помощью всех возможных значений К₁, выполняется XOR с левой половиной открытого текста и полученные значения сохраняются в таблице. Затем правая половина шифротекста шифруется с помощью всех возможных значений К₃, и выполняется поиск совпадений в таблице. При совпадении пара ключей К₁ и К₃ - возможный вариант правого ключа. После нескольких повторений вскрытия останется только один кандидат. Таким образом, xDES¹ не является идеальным решением. Существует вскрытие с выбранным открытым текстом, доказывающее, что xDES¹ не намного сильнее используемого в нем блочного алгоритма.

В xDES² эта идея расширяется до 5-этапного алгоритма, размер блока которого в 4 раза, а размер ключа в 10 раз превышают размеры блока и ключа используемого блочного шифра. Каждый из четырех подблоков по размеру равен блоку используемого блочного шифра, а все 10 ключей независимы.

Рис. 28 Один 3TanxDES².

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

Для i3 xDES' вероятно слишком велик, чтобы использовать его в качестве блочного алгоритма. Например, размер блока для xDES³ в 6 раз больше, чем у лежащего в основе блочного шифра, ключ в 21 раз длиннее, а для шифрования блока, который в 6 раз длиннее блока лежащего в основе блочного шифра, нужно 21 шифрование. Это медленнее, чем тройное шифрование.

Пятикратное шифрование

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

C = E_K1(D_K2(E_K3(D_K2(E_K1(P)))))

P = D_K1(E_K2(D_K3(E_K2(D_K1(C))))

Эта схема обратно совместима с тройным шифрованием, если К₁ = К₂, и с однократным шифрованием, если К₁= К₂ = К₃. Конечно, она будет еще надежней, если использовать пять независимых ключей.

Уменьшение длины ключа в CDMF

Этот метод был разработан IBM для продукта CDMF (Commercial Data Masking Facility, Коммерческое средство маскирования данных), чтобы превратить 56-битовый ключ DES в 40-битовый, разрешенный для экспорта. Предполагается, что первоначальный ключ DES содержит биты четности.

(1) Обнуляются биты четности: биты 8, 16, 24, 32,40, 48, 56, 64.

(2) Результат этапа (1) шифруется с помощью DES ключом 0xc408b0540bale0ae, результат шифрования объединяется посредством XOR с результатом этапа (1).

(3) В результате этапа (2) обнуляются следующие биты: 1, 2, 3, 4, 8, 16, 17, 18, 19, 2.0, 2.4, 32, 33, 34, 35, 36, 40,48,49,50,51,52,56,64.

(4) Результат этапа (3) шифруется с помощью DES ключом 0xef2c041ce6382fe6. Полученный ключ используется для шифрования сообщения.

Однако этот метод укорачивает ключ и, следовательно, ослабляет алгоритм.

Отбеливание

Отбеливанием (whitening) называется способ, при котором выполняется XOR части ключа с входом блочного алгоритма и XOR другой части ключа с выходом блочного алгоритма. Впервые этот метод был применен для варианта DESX, разработанного RSA Data Security, Inc., а затем (по-видимому, независимо) в Khufu и Khafre. (Ривест и дал имя этому методу)

Смысл этих действий в том, чтобы помешать криптоаналитику получить пару "открытый текст/шифротекст" для лежащего в основе блочного алгоритма. Метод заставляет криптоаналитика угадывать не только ключ алгоритма, но и одно из значений отбеливания. Так как XOR выполняется и перед, и после блочного алгоритма, считается, что этот метод устойчив против вскрытия "встреча посередине".

С = К₃Е_К2(РК₁)

P = K₁D_K2(CK₃)

Если К₁ = К₂, то для вскрытия грубой силой потребуется 2^п+т/р действий, где п - размер ключа, т - размер блока, и р - количество известных открытых текстов. Если К₁ и К₂ различны, то для вскрытия грубой силой с тремя известными открытыми текстами потребуется 2^n+m+1 действий. Против дифференциального и линейного криптоанализа, такие меры обеспечивают защиту только для нескольких битов ключа. Но с вычислительной точки зрения это очень дешевый способ повысить безопасность блочного алгоритма.

2.6.4 Многократное последовательное использование блочных алгоритмов

А как насчет шифрования сначала алгоритмом А и ключом К_А, а затем еще раз алгоритмом В и ключом К_B? Может быть у А и В различные представления о том, какой алгоритм безопаснее: А хочет пользоваться алгоритмом А, а В - алгоритмом В. Этот прием, иногда называемый последовательным использованием (cascading), можно распространить и на большее количество алгоритмов и ключей.

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