4. Симметричные криптосистемы и блочные шифры

4.1. Определение блочного шифра

Криптографическое преобразование составляет основу любого блочного шифра. Прян криптографическое преобразование (шифрование) переводит блок открытого текста в бл шифротекста той же длины. Обратное криптографическое преобразование дешифрование переводит блок шифротекста в исходный блок открытого текста. Необходимое условие выполнения как прямого, так и обратного криптографического преобразования — наличие каретного ключа. Шифры, в которых прямое и обратное преобразования выполняются над блоками фиксированной длины, называются блочными. Для многих блочных шифров раз рядность блока составляет 64 бита. Прямое криптографическое преобразование обладает дующим свойством: различные блоки открытого текста отображаются в различные блоки шифротекста. При обратном преобразовании соответствие сохраняется. Прямое преобразований можно рассматривать как перестановку на множестве сообщений с фиксированным размером блока. Результат перестановки носит секретный характер, что обеспечивается секретным компонентом — ключом.

4.2. Принцип итерирования

Принцип итерирования является основным при разработке криптографических преобразований и заключается в многократной, состоящей из нескольких циклов обработке одного блока открытого текста. На каждом цикле данные подвергаются специальному преобразованию при участии вспомогательного ключа, полученного из заданного секретного ключа. Выбор числа циклов определяется требованиями криптостойкости и эффективности реализации блочного шифра. Как правило, чем больше циклов, тем выше криптостойкости и ниже эффективность реализации (больше задержка при шифровании/дешифровании) блочного шифра, и наоборот. Так, например, в случае DES (федеральный криптостандарт США) для того, чтобы все ты шифротекста зависели от всех битов ключа и всех битов открытого текста, необходимо 5циклов криптографического преобразования [196,197]. DES с 16 циклами обладает высокой криптостойкостью по отношению к ряду криптоаналитических атак.

4.3. Конструкция Фейстеля

Конструкция Фейстеля (Н. Feistel), или сеть Фейстеля, представляет собой разновидность итерированного блочнoгo шифра [194, 195]. При шифровании блок открыто- ro текста разбивается на две равные части — правую и левую. Очевидно, что длина блока при этом должна быть четной. На каждом цикле одна из частей подвергается преобразованию при помощи функции f и вспомогательного ключа  полученного из исходного секретно- ro ключа. Результат операции суммируется по модулю 2 (операция XOR) с другой частью. Затем левая и правая части меняются местами. Схема конструкции Фейстеля представлена на рис. II.5. Преобразования на каждом цикле идентичны, но на последнем не выполняется перестановка. Процедура дешифрования аналогична процедуре шифрования, однако  выбираются в обратном порядке. Конструкция Фейстеля хороша тем, что прямое и обратное криптографические преобразования для такого блочного шифра имеют идентичную структуру.

Конструкция Фейстеля применяется в криптоалгоритмах DES, ГОСТ 28147-89, Lucifer, FEAL, Khufu, Khafre, LOKI, COST, САSТ, Blowfish, и др. Блочный шифр, использующий такую конструкцию, является обратимым и гарантирует возможность восстановления входных данных функции f на каждом цикле. Сама функция f не обязательно должна быть обратимой. При задании произвольной функции f не потребуется peализовывать две различные процедуры — одну для шифрования, а другую для дешифрования. Структура сети Фейстеля автоматически позаботится об этом.

Существует еще одно объяснение идеи конструкции Фейстеля. В своих лекциях извести криптограф Дж. Мэсси (J. L. Massey) вводит понятие иволютивного отображения. Т некоторая функция f является инволюцией, если f (f (х)) = х для всех х. Для такой функции область определения (множество аргументов х) и область значений (множество значений f(х)) совпадают. Например, функция f(х) = ¬х является инволюцией, так как f(f(х))=f(¬х) = ¬ (¬х) = х. Другой пример инволюции: f(х) = хс, где с — некоторая константа Действительно, f (f (x)) = /(х с) = х с с = х.

Инволюция является полезным свойством при конструировании блочных шифров. Рассмотрим композиционный блочный шифр, включающий и последовательных хрип графических преобразований на ключе K (рис. 11.6).

Тогда шифротекст C получается в результате прео6разования

где P — открытый текст (рис. П.7). Если функция является инволюцией, открытый текст может быть восстановлен в результате преобразования

))

Действительно, согласно описанному выше свойству имеем:

так как  и так далее вплоть до получения тождества P =P

4.4. Режимы шифрования блочных шифров

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

4.4.1. Шифрование в режимах ЕСВ и СВС

 Стандарт режимов шифрования для блочных шифров (применительно к криптоалгоритм DES) опубликован в материалах Национального института стандартов США [185] и ANSI Х3.106 [24]. В более общем виде, применительно к произвольному блочному шифру с переменной длиной блока, стандарт опубликован в материалах [186] и включает шифрование в следующих режимах: Электронной кодовой книги (Electronic Code Book, ECB), Сцепления блоков шифра (Cipher Block Chaining, СВС), Обратной связи по шифротексту (Cipher Feedback, CFB) и Обратной связи по выходу (Output Feedback, OFB). В режиме ECB (рис. II.8) шифрование/дешифрование i-го блока открытого текста/шифротексту выполняется независимо: тi, = Dk(сi,), сi, = Еk(тi;), где через Еk и Dk обозначены процедуры шифрования/дешифрования на секретном ключе k.

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

В режиме СВС каждый й блок открытого текста суммируется по модулю 2 (операция XOR) с (i — 1)-м блоком шифротекста и затем шифруется (рис. II.9). Начальное значение (в наших обозначениях со) задается вектором инициализации.

Криптостойкость режима СВС определяется криптостойкостью используемого блочного шифра. Применение режима СВС позволяет устранить недостаток режима ЕСВ: каждый блок открытого текста “маскируется” блоком шифротекста, полученным на предыдущем этапе. Таким образом, возможность изменения открытого текста при использовании режима СВС весьма ограничена — любые манипуляции с блоками шифротекста, за исключением удаления первого и последнего блоков, будут обнаружены. Скорость обработки в данном режиме не ниже производительности блочного шифра — задержка при выполнении операции XOR пренебрежимо мала. Процедура шифрования в режиме СВС с трудом поддается распараллеливанию, процедуру дешифрования распараллелить значительно проще

4.4.2. Шифрование в режимах CFB и OFB

В режиме CFB й блок шифротекста формируется путем шифрования (i — 1)-го блока шифротекста и его суммированием (операция XOR) с -м блоком открытого текста (рис. П.10).

Режим CFB можно задать таким образ, что обратная связь будет захватывать целый битный блок, а только  бит предыдущего блока, Начальное значение так же, как в режиме СВС, задается при мощи вектора инициализации.

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

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

 (операция XOR) -го блока открытого текста с  из независимой последовательности блоков (рис. II.11).

 Обратная связь по выходу на разрядов не рекомендуется из соображений крипто стойкости [187, 188]. Режим OFB имеет следующее преимущество по сравнению с режимом CFB: ошибки, возникающие в результате передачи по каналу с шумом, при дешифровании не «размазываются» по всему шифротексту, а локализуются в пределах одного  блока. Однако открытый текст может быть изменен путем определенных манипуляций с блоками шифротекста. Скорость шифрования в режиме OFB та же, что и у блочного шифра. Несмотря на то, что OFB-шифрование не поддается распараллеливанию, эффективность процедуры может быть повышена за счет предварительной генерации независимой последовательности блоков.

4.4.3. Шифрование в режимах усовершенствованного OFB и PCBC

Известные недостатки привели к появлению усовершенствованного варианта шифрования в режиме OFB [189]. Основные изменения касаются метода генерации независимой последовательности блоков: для получения очередного блока предлагается шифровать не s_i, а s_i + IV(mod 2⁶⁴), где IV — некоторый вектор инициализации.

Режим шифрования РОВС (Propagating Cipher Block Chaining) применяется в протоколе Kerberos (версия 4) и позволяет обнаруживать ошибки. Данный режим шифрования не является федеральным или международным стандартом. Режим РОВС — вариант режима СВС, обладающий специфическим свойством, — в результате дешифрования единичная ошибка распространяется на весь шифротекст (решается обратная задача с точки зрения режима OFB). Данное свойство позволяет с высокой надежностью обнаруживать ошибки, возникающие при передаче сообщений по каналам с шумом. Шифрование в режиме РОВС выполняется по правилу:

с_i = E_k(m_im_i-1c_i-1),

дешифрование:

т_i = D_k(с_i) с_i-1m_i-1

где m_o с_о — вектор инициализации.

4.4.4. Другие режимы шифрования

Интуитивные рассуждения приводят к выводу, что двойное шифрование фиксированного открытого текста одним и тем же блочным шифром (на одном или двух различных ключах) позволяет повысить криптостойкость. Однако это не всегда так. Рассмотрим некоторые режимы многократного шифрования. Основная идея заключается в многократном (два, три и более раз) применении алгоритма шифрования к фиксированному блоку открытого текста на нескольких секретных ключах. Дешифрование блока шифротекста выполняется в обратном порядке. Для начала рассмотрим режим двойного шифрования. Обозначим через С, P, К шифротекст, открытый текст и секретный ключ соответственно. Для процедуры шифрования и дешифрования на ключе К введем обозначения Е_k и D_k. Тогда двойное шифрование/дешифрование на двух различных ключах выполняется по правилу:

С = E_K2 (Е_K1 (Р)),

 P =D _K2 (D _K1 (С)).

В случае если криптографическое преобразование обладает свойством С = E_K2 (Е_K1 (Р)) = E_K3 (Р), двойное шифрование на двух различных ключах не имеет никаких преимуществ по сравнению с однократным. Доказательство данного факта (групповых свойств блочного шифра) требует теоретических исследований. Трудоемкость силовой атаки — исчерпывающего перебора ключей при наличии пары С и Р и отбора вариантов по результатам шифрования дешифрования — возрастет в 2ⁿ раз и составит 2²ⁿ попыток (где  длина ключа в битах). Действительно, в начале фиксируется первый претендент на ключ и выполняется шифрование Р, затем результат шифруется на всевозможных ключах — претендентах на до тех пор, пока не будет получен шифротекст С. Существует  претендентов на ключ и столько же на . Следовательно, объем перебора при поиске ключей составит в худшем случае попыток шифрования. Меркль (R.С. Merkle) и Хеллман (М.Е. Hellman) дожили вариант силовой атаки, позволяющий раскрывать ключи за  попыток вместо Идея атаки заключается в обмене времени (числа попыток) на память. Предполагается, что криптоаналитику противника известны две пары «открытый текст/шифротекст»— и  такие что

,

,

Сначала выполняется шифрование блока открытого текста на всевозможных ключах- претендентах на . Полученные в результате блоки шифротекста сохраняются в памяти их хранения потребуется ячеек памяти, где  — длина блока в битах. Далее для каждого претендента на ключ выполняется дешифрование блока шифротекста .Затем выполняется поиск результата дешифрования среди сохраненных ранее в памяти блок- шифротекста. Если результат обнаружен, то, возможно, текущий претендент на и ключ, соответствующий шифротексту в памяти, — истинные ключи и . Для проверки претендентов выполняется шифрование Если полученный в результате шифротекст идентичен  — ключи раскрыты, если нет, — поиск ключей продолжается. Для поиска результат в памяти применяется хэш-функция (не путать с криптографическими приложениями хеш-функций), отображающая аргумент в некоторый адрес памяти. Число операций при реализации хэш-функции не зависит от объема памяти и поэтому не учитывается при оценке трудоемкости атаки. Максимальное число попыток, которое, возможно, придется предпринять , равно 2 х 2, или 2. Для двух пар вероятность успеха оценивается как 2 Естественно, чем больше пар используется для проверки ключей, тем выше вероятность успеха Таким образом, вероятность успеха для  пар — 2 Описанный вариант атаки требует большого объема памяти. Так, при 128-битном ключе для хранения  промежуточных  результатов потребуется 10байтов памяти. В своей книге «Прикладная криптография» Шнайер (В. Shneier) приводит следующее сравнение: «Если предположить, что существует способ хранения бита информации, используя один-единственный атом алюминия, устройство памяти, необходимое для выполнения атаки такого рода, будет представлять собой алюминиевый куб с ребром в 1 км».

В 1979 г. Тачмен (W. Tuchman) предложил метод тройного шифрования на двух различных  ключах [191]:

С = Ек, (Da., (Esc. (P)))

Р = Рк, (Ер(, (Рк, (С)) ).

Такой режим называют «шифрование-дешифрование-шифрование» (encrypt-decrypt-encrypt,EDE). При n-битных ключах данная схема шифрования эквивалентна схеме с 2п-битным ключом. Операция Dпри шифровании (соответственно при дешифровании) не влияет на криптостойкость и необходима для совместимости с режимом однократного шифрования. Действительно, при  При равных ключах трудоемкость атаки возрастает в два раза — можно вычислить и сохранить в памяти результаты дешифрования  для всех претендентов на , для этого потребуется  попыток. При двух различных ключах объем перебора в худшем случае составляет 2попыток. Однако Меркль и Хеллман разработали вариант силовой атаки на схему тройного шифрования [190]. В ходе атаки необходимо выполнить 2попыток дешифрования; для хранения промежуточных результатов потребуется 2ячеек памяти.

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

Очевидное усовершенствование схемы тройного шифрования заключается в использовании трех различных ключей:

Силовая атака для такой схемы сводится к 2г" попыткам дешифрования и ячейка памяти [190].

Существует криптостойкий метод тройного шифрования с двумя ключами, известный названием ТЕМК — Triple Encryption with Minimum Кеу. Идея заключается в том, ч получить три различных ключа  из двух секретных ключей и . Для необходимо выполнить следующие вычисления:

T1, Т2 и Т3 представляют собой константы, которые необязательно хранить в секрете.

 Еще один известный способ шифрования на трех различных ключах сводится к предварительному суммированию по модулю 2 (операция XOR) ключа и блока открытого текста, шифрованию на ключе  с последующим суммированием по модулю 2 получен на предыдущем шаге блока шифротекста и ключа ;

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

Впервые этот метод был применен Ривестом в криптоалгоритме DESX, предложен компанией RSA Data Security, Inc. для усиления федерального стандарта DES, а затем блочных шифрах Khufu и Khafre. Смысл описанных действий заключается в том, чтоб мешать криптоаналитику получить пару «открытый текст/шифротекст». Метод заставляет криптоаналитика угадывать не только ключ , но и один из маскирующих ключей. как суммирование по модулю 2 (операция XOR) выполняется и до и после шифрования считается, что криптостойкость метода достаточно высока.

Если , то для силовой атаки потребуется (2)/р попыток дешифрования, где  разрядность ключа,  разрядность блока и р — количество известных открытых текстов. Если , то для атаки с тремя известными открытыми текстами потребу 2попыток. С точки зрения дифференциального и линейного криптоанализа такие, меры обеспечивают защиту только для нескольких бит ключа. Но с вычислительной точки зрения это очень дешевый способ повысить криптостойкость блочного шифра.

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

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

4.5. Стандарты блочного шифрования

4.5.1. Федеральный стандарт США — DES

Стандарт шифрования данных DES (Data Encryption Standard), который ANSI называет Алгоритмом шифрования данных DEA (Data Encryption Algorithm), а ISO — DEA-1, за 20 лет стал мировым стандартом [21,22]. За годы своего существования он выдержал натиск различных атак и при известных ограничениях все еще считается криптостойким.

DES представляет собой блочный шифр, шифрующий данные 64-битовыми блоками. С одного конца алгоритма вводится 64-битовый блок открытого текста, а с другого конца выходит 64-битовый блок шифротекста.

DES является симметричным алгоритмом: для шифрования и дешифрования используются одинаковые алгоритм и ключ (за исключением небольших различий в использовании ключа). Длина ключа равна 56 битам. (Ключ обычно представляется 64-битовым числом, но каждый восьмой бит используется для проверки четности и игнорируется. Биты четности являются наименьшими значащими битами байтов ключа.)

Ключ, который может быть любым 56-битовым числом, можно изменить в любой момент времени.

Криптостойкость полностью определяется ключом. Фундаментальным строительным блоком DES является комбинация подстановок и перестановок. DES состоит из 16 циклов (рис. 11.12).

В общем виде цикл преобразования представлен на рис. П.13.

Если и  — левая и правая половины, полученные в результате й итерации,  — 48-битный ключ для цикла, а  функция, выполняющая все подстановки, перестановки и XOR с ключом, то один цикл преобразования можно представить как

Учитывая подстановку Fi( • ) и перестановку Т(. ), цикл преобразования можно представить так, как это сделано на рис. II.14.

Из рис. П.14 видно, что каждый цикл DES представляет собой композиционный шифр с двумя последовательными преобразованиями — подстановкой  и перестановкой Т(.) (за исключением последнего, шестнадцатого цикла, где перестановка опускается

Подстановка

является инволюцией, так как

В свою очередь, подстановка T(L'_i, R'_i) = (R'_i ,L'_i) также является инволюцией, поскольку

Рис. II.14. Цикл DES с учетом перестановки и подстановки

Если обозначить начальную и завершающую перестановки как (IP) и (IP)^-1, то прямое DES- преобразование (шифрование) реализует функцию

а обратное DES-преобразование (дешифрование) реализует функцию

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

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

DES работает с 64-битовым блоком открытого текста. После первоначальной перестановки блок разбивается на правую и левую половины длиной по 32 бита. Затем выполняется 16 преобразований (функция f), в которых данные о6ьединяются с ключом. После шестнадцатого цикла правая и левая половины объединяются, и алгоритм завершается заключительной перестановкой (обратной по отношению к первоначальной). На каждом цикле (см. рис. И.13) биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Правая половину данных увеличивается до 48 битов с помощью перестановки с расширением, объединяется посредством XOR с 48 битами смещенного и переставленного ключа, проходит черен B S-блоков, образуя 32 новых бита, и переставляется снова. Эти четыре операции и выполняются функцией f.

Затем результат функции / объединяется с левой половиной с помощью другого XOR. B итоге этих действий появляется новая правая половина, а старая правая становится новой левой половиной. Эти действия повторяются 16 раз, образуя 16 циклов DES.

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

следует читать слева направо и сверху вниз. Например, начальная перестановка перемещает бит 58 в позицию 1, бит 50 — в позицию 2, бит 42 — в позицию 3 и так далее.

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

Процедура преобразования ключа сводится к следующим действиям. Сначала 64-битовый ключ DES уменьшается до 56-битового ключа отбрасыванием каждого восьмого бита, как показано в табл. И.2. Эти биты используются только для контроля четности, позволяя проверять правильность ключа. После извлечения 56-битного ключа для каждого из 16 циклов генерируется новый 48-битный подключ. Эти подключи, определяются следующим образом. Сначала 56-битный ключ делится на две 28-битные половины. Затем половины циклически сдвигаются влево на один или два бита в зависимости от номера цикла. Этот сдвиг показан в табл. П.З.

После сдвига выбирается 48 из 56 битов. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, эта операция получила название перестановка со сжатием. Ее результатом является набор из 48 битов. Перестановка со сжатием определена в табл. II.4. Например, бит сдвинутого ключа в позиции 33 перемещается в позици1о 35 результата, а 18-й бит сдвинутого ключа отбрасывается.

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

Операция перестановки с расширением правой половины данных,  от 32 до 48 битов и изменением их, порядка, называется перестановкой с рением

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

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

исходных данных. Данная зависимость называется лавинным эффектом. DES спроектирован так, чтобы как можно быстрее добиться зависимости каждого бита шифротекста от каждого бита открытого текста и каждого бита ключа. Перестановка с расширением показана рис. II.16. Иногда она называется Е-блоком (от expansion). Для каждого 4-битного входного блока первый и четвертый биты представляют собой два бита выходного блока, а второй и третий биты — один бит выходного блока. В табл. II.5 показано соответствие позиций результата и исходных данных. Например, бит входного блока в позиции 3 переместит позицию 4 выходного блока, а бит входного блока в позиции 21 — в позиции 30 и 32 выходи блока. Хотя выходной блок больше входного, каждый входной блок генерирует уникален выходной блок.

После объединения сжатого блок расширенным блоком с помощью ХОR

над 48-битным результатом выполняется

операция подстановки. Подстановки производятся в восьми блоках подстановки, или S-блоках (от substitution). У каждого подстановка при помощи каждого 8-блока есть 6-битный вход S-блоков 4-битный выход, всего используется восемь различных S-блоков. (Для восьми S-блоков DES потребуется 256 байтов памяти.) 48 битов делятся на восемь 6-битных под

ков. Каждый отдельный подблок обрабатывается отдельным S-блоком: первый подблок первым S-блоком, второй — вторым S-блоком и так далее (см. рис. II.17).

Каждый S-блок представляет собой таблицу из двух строк и шестнадцати столбцов. Каждый элемент в блоке является 4-битным числом. По шести входным битам S-блока определяется, под какими номерами столбцов и строк следует искать выходное значение. Все восемь S-блоков показаны в табл. II.6 — И.13.

Входные биты особым образом определяют элемент S-блока. Рассмотрим 6-битовый вход S-блока: и Биты и объединяются, образуя 2-битное число от нуля  трех, соответствующее строке таблицы. Средние четыре бита, с  по объединяются, образуя 4-битное число от нуля до пятнадцати, соответствующее столбцу таблицы. Например пусть на вход шестого S-блока (то есть биты функции XOR с 31 по 36) попадает 1100 Первый и последний биты, объединяясь, образуют 11, что соответствует строке три шестого

Таблица II.6. DES — S-блок 1

го S-блока. Средние четыре бита образуют 1001, что соответствует столбцу девять S-блока. Элемент шестого S-блока, находящийся на пересечении строки три и столбца — это 14. (Строки и столбцы нумеруются с нуля, а не с единицы.) Вместо 110011 подставляется 1110. Намного легче реализовать S-блоки программно в виде массивов с 64 элементами. Для этого потребуется переупорядочить элементы. Такой способ описания S помогает понять, как они работают. Каждый S-блок можно рассматривать как функцию подстановки 4-битного элемента:по  являются входом, а некоторое 4-битное число результатом. Биты  и определяются соседними блоками, они определяют одну из четырех функций подстановки, возможных в данном S-блоке. Подстановка с помощью S- является ключевым этапом DES. Другие действия алгоритма линейны и легко по анализу. S-блоки нелинейны, и именно они в большей степени, чем все остальное, обеспечивают криптостойкость DES. В результате этой подстановки получаются восемь 4-5 блоков, которые вновь объединяются в единый 32-битный блок. Этот блок поступает следующего этапа — перестановки с помощью P-блоков.

32-битовый выход подстановки с помощью 8-блоков перетасовывается в соответствии P-блоком. Эта перестановка перемещает каждый входной бит в другую позицию, ни о

не используется дважды, и ни один бит не игнорируется. Этот процесс называется п перестановкой, или просто перестановкой. Позиции, в которые перемещаются биты, по в табл. П.14. Например, двадцать первый бит перемещается в позицию четыре, а чет бит — в позицию тридцать один.

Наконец, результат перестановки с помощью P-блока объединяется посредством левой половиной первоначального 64-битового блока. Затем левая и правая половины меняются местами, и начинается следующий цикл криптографического преобразования.

Заключительная перестановка является обратной по отношению к начальной перестановке и описана в табл. II.15. Отметим, что левая и правая половины не меняются местами завершения последнего цикла DES, вместо этого объединенный блок В₁₆L₁₆ используется как вход заключительной перестановки. Перестановка половин с последующим циклическим сдвигом привела бы к точно такому же результату. Это сделано для того, чтобы алгоритм можно было использовать как для шифрования, так и для дешифрования.

Алгоритм, который создает ключ для каждого цикла, также цикличен. Ключ сдвигается направо, а число позиций сдвига равно 0,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1.

FIPS PUB 81 определяет четыре режима работы: ЕСВ, СВС, OFB и CFB [23-25, Банковские стандарты ANSI определяют для шифрования ЕСВ и СВС, а для проверки подлинности — СВС и -битовый CFB [26,186]. Из-за простоты реализации в большинстве существующих коммерческих программ используется ЕСВ, хотя этот режим наиболее у СВС используется редко, несмотря на то, что он лишь незначительно более сложен, чем и обеспечивает большую криптостойкость.

Криптостандарт DES стал объектом скрупулезных криптоаналитических исследований с момента его публикации в 1977 г. [15]. В том же году Диффи и Хеллман предложили вариант специализированного компьютера стоимостью двадцать млн. долл., гарантии го раскрытие ключа DES методом силовой атаки в течение одних суток. В 1993 г. Винер (M.J.Wiener)спроектировал специализированную компьютерную архитектуру стоимостью долл., позволяющую раскрывать ключ DES в среднем за 3,5 час. [399]. Реализация

идей Винера на современном технологическом уровне позволяет раскрывать ключ DES в среднем за 35 мин [400]. Силовая атака на основе метода распределенных вычислений обеспечивает раскрытие ключа в течение 90 и даже 40 календарных дней [390,392]. В 90-е годы были разработаны и применены для атаки на DES методы дифференциального и линейного криптоанализа [260, 377].

Однако известны и другие разновидности атак, позволяющие при заданном шифротексте открытый текст, не раскрывая при этом секретного ключа. Примером является основе сопоставления образцов шифротекста (matching ciphertext attack), эффективность которой зависит исключительно от длины блока шифра [348,389]. Основная идея

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

СВС и CFВ.

Рассмотрим режим СВС. Обозначим через Р_i и Сi блоки открытого текста и шифротекста соответственно. Тогда С_i, = E_k(P_i С_i-1) — перед шифрованием текущий блок открытого текста суммируется (по модулю 2, операция XOR) с полученным на предыдущем шаге блоком шифротекста. Из равенства Сi = С_j следует, что P_i С_i-1=P_j С_j-1. Для дальнейших рассуждений необходимо ввести понятие расстояния Хэмминга.

Расстояние Хэмминга dist(x,у) между двумя двоичными векторами x = х₁,..., хи у =у_1,…., у_n, равно числу позиций, в которых они различаются, Например, dist(10111,00101)

2.Вес Хэмминга wt(x) вектора х =х₁,...,x_n равен числу ненулевых компонентов х_i, например 01110) = 4. Очевидно, что dist(x,y) = wt(x  у), где х  у — покомпонентная сумма по модулю 2 (операция XOR) векторов х и у.

Taким образом, расстояние Хэмминга го блоков открытого текста равно расстоянию Хэмминга (i — 1)-го и (j — 1)-го блоков шифротекста, поскольку  При длине блока  совпадения пары можно ожидать на множестве из 2^n/2 блоков шифротекста, Для DES- это 2³² блоков.

Для обеспечения высокого уровня криптостойкости рекомендуют применять тройное DES шифрование на трех [391] или на двух различных ключах [191]. Однако угроза атаки на основе сопоставления образцов шифротекста при этом сохраняется, так как длина блока Рис. II.18. DES фиксирована (64 бита).

В течение ряда лет комитет Х9.F.1 Американского национального института стандартов Institute of Standards and Technology, NIST) занимался исследованием различных для метода тройного DES-шифрования [382]. Основу предложенной NIST разработки составили известные режимы ЕСВ, СВС, OFB и CFB с заменой базовой операции одношифрования на тройное DES-шифрование. В режиме Обратной связи по шифротексту для тройного DES (Triple DES Cipher Block Chaining, ТСВС) блок шифротекста, суммируемый с блоком открытого текста, получается в результате тройного DES-шифрования. называют также внешним СВС-режимом (outer-СВС mode) [138], подразумевая под этим, что блок шифротекста берется с выхода тройного DES-шифратора. Схема режима ТСВС представлена на рис. II.18. Данный режим уязвим с. точки зрения атаки на основе

 сопоставления образцов шифротекста и по очевидным причинам в три раза менее производителен, чем однократный DES. Недостатки ТСВС стали причиной разработки внутреннего СВС-режима (inner-СВС mode, 1СВС) (рис. II.19).

В этом режиме обратная связь реализм при помощи блоков шифротекста с выхода ночного DES-шифратора. Режим ICBC мю интерпретировать как трехкратное применение стандартного СВС-режима на трех различных ключах. Разработчики предполагали, что жим ICBC обеспечивает высокую криптостойкость кость при атаке на основе сопоставления о6разцов шифротекста и не менее криптостоек, режим трехкратного DES-шифрования на т различных ключах. Результаты последний следований показали, что объем перебора режима EDE не превосходит 2¹⁰⁹ [394]. Кроме того, режим ICBC допускает эффективную конвейерную аппаратную реализацию и позволяет достичь той же производительности, и однократный DES.

Тем не менее, проанализировав большое число различных режимов шифрования [383,384,386], Бихам (Е. Вiham) продемонстрировал уязвимость режима ICBC [384]. Трудоемкость атаки Бихама лишь незначительно превышает трудоемкость атаки на однократный сходное предположение заключается в возможности контроля обратных связей I криптоаналитика. Атакующий выбирает шифротекст вида (С,С, С,С), где все четыре блока идентичны. После дешифрования на одном СВС-уровне исходный шифротекст принимает вид (?, Х, Х, Х), где блоки Х идентичны, но не известны криптоаналитику. После дешифрования на двух уровнях получаем (?,?, Y, Y), где блоки Y идентичны, а п звания на всех трех уровнях получаем (?,?,?, Z) для некоторого Z. Для успешного осуществления атаки необходимо 2шифротекстов для различных С. Вероятность того, что два шифротекста, например С₁ и С₂, приведут к одному и тому же значению Х и, следе одним и тем же значениям Y и Z, достаточно велика (парадокс «дня рождения⁴

При заданной паре С₁ и С₂ криптоаналитик может раскрыть ключ К₃ методом силовой атаки, используя в качестве критерия условие D При заданном Неся ключи раскрываются аналогичным образом. Общая трудоемкость атаки всего в несколько раз выше, чем трудоемкость силовой атаки на однократный DES и не сравним  дикостью атаки на DES в режиме EDE.

В статьях [388,389] Копперсмит (D. Coppersmith), Джонсон (D. В. Johnson) и Матиас (S.M.Matyas)  предложили тройное DES-шифрование в режиме CBC c OFB-маскированием  (CBC with OFB Masking, CBCM). Основная цель при проектировании CBCM заключалась в обеспечении адекватной криптостойкости при атаках, описанных в [384,385], атаке на основе сопоставления образцов шифротекста и ряда других.

Режим СВСМ аналогичен СВС с базовой операцией трехкратного шифрования на двух различных ключах, при этом промежуточные блоки шифротекста между первым и вторым и третьим уровнями маскируются блоками шифротекста, полученным в результате DES шифрования на третьем ключе в режиме ОРВ (рис. П.20, где М₁, М₂, и т.д. выходные блоки OFB-режима, полученные в результате шифрования на ключеи IV₁ — вектор инициализации). Основной недостаток режима — низкая производительность 1а один 64-битный блок открытого текста приходится четыре DES-шифрования на трех различных ключах. Анализируя варианты использования внутренней обратной связи с учетом  возможностей описанной выше атаки Бихама [384], авторы статей [388,389] приходят своду о бесперспективности дальнейших разработок режимов шифрования с внутренней обратной связью. При этом применение только внешней обратной связи также нельзя звать удовлетворительным. Приведенные аргументы стали причиной разработки режима СВСМ, включающего как внешние, так и внутренние обратные связи, причем последние не могут контролироваться криптоаналитиком, так как являются выходом DES-шифратора OFВ-режиме.

Криптостойкость СВСМ при различных атаках, описанных в [384], доказана в статье [388]. В результате режим СВСМ был принят в качестве стандарта включен в документ [382]. Однако сразу же вслед за принятием стандарта Бихам и Кнудсен (l .R. Knudsen) предложили оригинальный вариант атаки на режим СВСМ.

Суть предложенной атаки заключается в том, что вместо контроля обратных связей можно воспользоваться их структурой. Для этого вводится понятие фиксированной точки в криптографическом преобразовании. Фиксированная точка функции f есть значение х, такое что f (x)=x.Важное наблюдение заключается в том, что, когда вход среднего дешифратора является фиксированной точкой, результаты дешифрования и маскирования на втором (среднем) уровне взаимно уничтожаются и трехкратное шифрование сводится к двухкратному с использованием одного и того же ключа дважды. При большом количестве блоков открытого текста и шифротекста вероятность обнаружения преобразований с фиксированной точкой достаточно велика. Основная задача заключается в определении блоков с фиксированной точкой. Следующее наблюдение указывает на то, что для большинства функций f существует в точности одна фиксированная точка х. Для реализации атаки необходимо огромное количество выборочных блоков шифротекста, превышаю- . период OFB потока. В качестве исходного материала было выбрано 2⁶⁴ фиксированных блоков шифротекста С₁ и столько же блоков С_2, С₂ С₁. При заданном открытом тексте можно определить период OFB-потока. Поиск ключа К₁ выполняется путем дешифровании блоков С₁ и С₂ на ключе К, при этом претенденты выбираются из ключевого пространства 2⁵⁶ .Блоки с фиксированной точкой определяются путем сравнения результатов с блоками открытого текста. Поскольку фиксированная точка уникальна, пара шифрований на втором уровне имеет одинаковые данные, что позволяет установить различие между двумя дополнительными блоками с одинаковыми масками. Дополнительные блоки используются затем для проверки ключа-претендента К. Детальное описание атаки приводится в статье [387]. Для осуществления атаки достаточно 2⁶⁵ блоков выборочного шифротекста, в ходе атаки необходима выполнить 2⁵⁸ попыток трехкратного DES-шифрования, кроме того, необходима дополнительная память для хранения блоков открытого текста. Описанная атака имеет теоретический характер и вряд ли будет реализована на практике. Однако ее трудоемкость значительно ниже трудоемкости известных атак на режим EDE.

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

Один из очевидных способов заключается в замене ключа К₁ на третьем уровне на ключ К_4,К₄К₁.При этом авторы атаки не рекомендуют изменять способ OFB-маскирования между вторым и третьим уровнями [401], так как существует эффективная а Возможное решение заключается также в разработке нового режима шифрования например, Бихам предложил следующее преобразование — OFB[CBC, СВС, СВС^-1] ( открытый текст суммируется по модулю 2 (операция XOR) с OFB-потоком, генерируемым однократным DES, затем шифруется в режиме СВС на третьем ключе, снова суммируется  OFB-потоком, дешифруется в режиме СВС на четвертом ключе и опять суммируется с тем же OFB-потоком), вектор инициализации вычисляется как КАС от некоторого на значения, передаваемого в открытом виде от отправителя к получателю [387]. Криптостойкость этого режима шифрования пока не скомпрометирована, трудоемкость атаки оценивается как 2¹¹² попыток дешифрования, даже при условии, что криптоаналитик м лучить неограниченное количество выборочных шифротекстов с фиксированным инициализации [398]. Данный режим допускает эффективную аппаратную реализацию по конвейерному принципу и может гарантировать то же быстродействие, что и один DES при аппаратной реализации и режим СВСМ при программной реализации.

Еще одно решение заключается в разработке нового блочного шифра. В статье [393] Кнудсен предложил новый блочный шифр DEAL и выполнил анализ его криптостойкости оценкам автора трудоемкость любой атаки на DEAL оценивается как 2¹²⁰ попыток дешифрования в худшем случае. DEAL имеет простую конструкцию. Цикл криптограф преобразования сводится к следующему: открытый текст делится на блоки по 128 6ит каждый; левая и правая половины поступают на вход DES и шифруются на ключе К₁, результат шифрования суммируется по модулю 2 (операция XOR) с правой половиной, затем п меняются местами. Результирующий шифротекст получается после шести циклов преобразования, причем на каждом цикле используется новый ключ. Таким образом DEAL является шифром Фейстеля с шестью циклами и криптоалгоритмов DES в качестве фукции f (рис. П.5). Для получения двух 64-битных блоков шифротекста необходимо выполнить шесть DES-шифрований, поэтому DEAL имеет ту же производительность, что и режим EDЕ. Шесть 56-битных подключей генерируются из секретного ключа длиной 128, 192 или 256 бит.

Все рассмотренные выше режимы шифрования и другие методы являются попыткой компенсации известных недостатков DES, связанных с коротким ключом и блоком. В настоящее время стало ясно, что принципиальное решение заключается в разработке нового стандарта шифрования с большей длиной ключа и блока, обеспечивающего высокую криптостойкость по отношению ко всем известным атакам на блочные шифры. Американский национальный институт стандартов выступил с инициативой по разработке нового альтернативного стандарта AES (Advanced Encryption Standard, AES) [395]. NIST выражает надежду, что стандарт AES обеспечит высокий уровень криптостойкости на ближайшие 20-30 лет. В своем проекте NIST выдвигает ряд требований; так, например, предлагаем  в качестве кандидата блочный шифр должен иметь 128-битный блок и оперировать с длиной 128, 192 и 256 бит. Как отмечается в комментарии NIST, блочный шифр с у ми параметрами «должен гарантировать адекватную криптостойкость — не ниже, ч режиме EDE, и обеспечивать высокое быстродействие». Действительно, при 128-битном блоке для реализации атаки на основе сопоставления образцов шифротекста понадобится около 2⁶⁴ блоков шифротекста. Еще одно требование заключается в представлении трех различных программных реализаций шифра-кандидата на двух языках программирования а так же оценке числа логических элементов, необходимых для его аппаратной реализации. После отбора претендентов NIST готов представить их для широкого обсуждения и сравнения по ряду параметров — быстродействию, криптостойкости, простоте реализации, модульности т.д. Ожидается, что при сравнимом с DES быстродействии криптостойкость AES несколько порядков выше.

4.5 2. Стандарт России — ГОСТ 28147-89

ГОСТ 28147-89 — это блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками [10 — 14]. В криптоалгоритме также используется дополнительный ключ, который рассматривается ниже. Для шифрования открытый текст сначала разбивается на левую и правую половины L и R На i-м цикле используется подключ К_i:

Один из криптографическо преобразования на рис.II.21

 Функция f реализована следующим образом. Сначала правая половина и i-й подключ складываются по модулю 2³². Результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего S- блока. ГОСТ использует восемь различных S- блоков, первые 4 бита попадают в первый S-блок, вторые 4 бита — во второй S-блок и т.д. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Например, S-блок может выглядеть как:7,10,2,4,15,9,0,3,6,12,5,13,1,8,11. В этом случае, если на входе S-блока О, то на выходе

7. Если на входе 1, на выходе 10 и т.д. Все восемь S-блоков различны, они фактически являются дополнительным ключевым материалом. Выходы всех восьми S-блоков объединяются в 32-битовое слово, затем все слово циклически сдвигается влево на 11 битов. Наконец, результат объединяется с помощью операции XOR с левой половиной, и получается новая правая половина, а правая половина становится новой левой половиной. Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: k₁, k₂,..., k₈ . на дом цикле, как показано в табл. II.16 используется  свой подключ. Дешифрование выполняется так же, как и шифрование, но инвертируется порядок подключей k_i. Стандарт не определяет способ генерации S-блоков.

Набор S-блоков, указанный в табл. II.17, рекомендуется стандартом ГОСТ Р 34.11-94 [( Приложение 1) [17].

Главные различия между DES и ГОСТом заключаются в следующем:

— DES использует сложную процедуру для генерации подключей из ключей. В Г эта процедура очень проста;

— в DES 56-битный ключ, а в ГОСТе — 256-битный. Если добавить секретные перестановки S-блоков, то полный объем секретной информации ГОСТа составит примерно 610 бит;

— у S-блоков DES 6-битные входы и 4-битные выходы, а у S-блоков ГОСТа 4-би

входы и выходы. В обоих алгоритмах используется по восемь S-блоков, но размер блока ГОСТа равен четверти размера S-блока DES;

— в DES используются нерегулярные перестановки, названные Р-блоком, а в ГОСТ пользуется 11-битный циклический сдвиг влево;

— в DES 16 циклов, а в ГОСТе — 32.

Силовая атака на ГОСТ абсолютно бесперспективна. ГОСТ использует 256-битовый ключ, а если учитывать секретные S-блоки, то длина ключа будет еще больше. ГОСТ по-видимому, более устойчив к дифференциальному и линейному криптоанализу, чем DES  Хотя случайные S-блоки ГОСТа при некотором выборе не гарантируют высокой криптостойкости по сравнению с фиксированными S-блоками DES, их секретность увеличивает устойчивость ГОСТа к дифференциальному и линейному криптоанализу. К тому же эффективность этих криптоаналитических методов зависит от количества циклов преобразования — чем больше циклов, тем труднее криптоанализ. ГОСТ использует в два раза больше циклов, чем DES, что, возможно, приводит к несостоятельности дифференциального и линейно криптоанализа. ГОСТ не использует существующую в DES перестановку с расширение Удаление этой перестановки из DES ослабляет его из-за уменьшения лавинного эффекта разумно предположить, что отсутствие такой операции в ГОСТе отрицательно сказывается на его криптостойкости. С точки зрения криптостойкости операция арифметического сложения, используемая в ГОСТе, не хуже, чем операция XOR в DES. Основным различи представляется использование в ГОСТе циклического сдвига вместо перестановки. Перестановка DES увеличивает лавинный эффект. В ГОСТе изменение одного входного бита повлияет на один S-блок одного цикла преобразования, который затем влияет на два S-блока а дующего цикла, затем на три блока следующего цикла и т.д. Потребуется восемь цикла прежде чем изменение одного входного бита повлияет на каждый бит результата; в DES для этого нужно только пять циклов. Однако ГОСТ состоит из 32 циклов, а DES таль из 16. Разработчики ГОСТа пытались достигнуть равновесия между криптостойкостью эффективностью. Взяв за основу конструкцию Фейстеля, они разработали криптоалгоритм, который лучше, чем DES, подходит для программной реализации. Для повышения криптостойкости введен сверхдлинный ключ и удвоено количество циклов. Однако вопрос, увенчались ли усилия разработчиков созданием более криптостойкого, чем DES, криптоалгоритм остается открытым.

4.6. Атаки на блочные шифры

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

Метод дифференциального криптоанализа впервые был применен дня атаки на блочный шифр РЕА?4 [169]. Впоследствии метод был усовершенствован и успешно применен

криптоанализа DES [170,258-260]. Метод дифференциального криптоанализа позволил п лучить ответ на вопрос о числе циклов криптографического преобразования стандарта DES. Этот ответ важен с точки зрения разработки эффективных методов криптоанализа произвольных итерированных блочных шифров конструкции Фейстеля. Вопрос формулировала следующим образом: почему число циклов преобразования равно шестнадцати, не больше И не меньше? Известно, что после пяти циклов каждый бит шифротекста является функцией всех битов открытого текста и ключа [196,261]. После восьми циклов наблюдается пик лавинного эффекта — шифротекст представляет собой случайную функцию всех битов от- го текста и ключа [262]. Успешные атаки на DES с тремя, четырьмя и шестью циклами подтвердили результаты исследований лавинного эффекта [263]. На первый взгляд, криптографическое преобразование с большим числом циклов (> 8) представляется необоснованным зрения эффективности реализации. Однако успешный дифференциальный крипто- DES доказал: трудоемкость (объем перебора) атаки на открытом тексте для DES c количеством циклов, меньшим шестнадцати, ниже, чем трудоемкость силовой атаки При этом необходимо отметить, что вероятность успеха при силовой атаке выше, чем атаке методом дифференциального криптоанализа. Тот факт, что метод дифференциального криптоанализа был известен в момент разработки DES, но засекречен по очевидным ям, подтвержден публичными заявлениями самих разработчиков [264,265]. метода составляет атака на основе выборочного открытого текста. Идея заключается в анализе процесса изменения несходства для пары открытых текстов, имеющих определен- исходные различия, в процессе прохождения через циклы шифрования с одним и тем же ключом. Не существует каких-либо ограничений на выбор открытых текстов. Достаточно различия в некоторых позициях. В качестве меры несходства, как правило, используют е Хэмминга.

Исходя из различий в получившихся шифротекстах ключам присваиваются различные . Истинный ключ определяется в процессе дальнейшего анализа пар шифротекстов- это наиболее вероятный ключ среди множества претендентов. Для пояснения рассмотрим один  цикл криптографического преобразования DES (рис. П.22).

Пусть задана пара входов, X и Х¹, с несходством DХ. Выходы, Y и Y¹, — известны, следовательно, известно и несходство DУ. Известны перестановка с расширением Е и Р-блок, следовательно, известны DА и DC. Значения на выходе сумматора по модулю 2 не известны, однако их несходство DВ известно и равно DА. Доказано, что для любого заданного DА не все значения DС равновероятны. Комбинация DА и DС позволяет предположить значения битов для E(X) К_i и Е(Х¹) К_i. То, что Е(Х) и Е(Х¹) известны, дает нам информацию о К_i.

На каждом цикле в преобразовании участвует 48-битный подключ исходного

56-битного секретного ключа. Таким образом, раскрытие K₁₆ позволяет восстановить 48 бит ключа. Остальные восемь можно восстановить при помощи силовой атаки.

Несходство различных пар открытых текстов приводит к несходству получаемых шифротекстов с определенной вероятностью. Вероятности можно оценить, построив таблицу, строки которой представляют собой возможные входы сумматора по модулю 2 (XOR двух различных наборов входных битов), столбцы — возможные результаты операции XOR, а элемент на пересечении строк и столбцов — частота появления конкретного результата суммирования. для заданного входа. Таблицу можно построить для каждого из восьми S-блоков DES. Различные несходства на отдельных циклах можно объединять. Кроме того, при условии, что циклы независимы, вероятности могут перемножаться.

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

Таблица П.18. Дифференциальный криптоанализ: результаты атаки на DE3

для успешного раскрытия необходимо достаточное количество данных — помимо статистического материала необходимо хранить частотную таблицу; для этого понадобится не бол бит памяти. В ходе дифференциального криптоанализа DES был использован ряд приемов позволивших сократить объем памяти и оптимизировать некоторые вычисления.

В табл. П.18 приводится обзор наилучших результатов успешного дифференциал криптоанализа DES с различным количеством циклов [260]. Первый столбец содержит количество циклов. Два следующих столбца содержат нижнюю оценку числа выборочных или заданных (известных) открытых текстов, необходимых для осуществления атаки. Четвертый столбец содержит количество действительно проанализированных открытых текстов В последнем столбце приведена оценка трудоемкости атаки после обнаружения требу пары.

Наилучший известный результат успешного дифференциального криптоанализа DЕS с шестнадцатью циклами требует 24~ выборочных открытых текстов. Можно воспользоваться атакой на известном открытом тексте, но для этого потребуется уже2⁵⁵ известных образ Трудоемкость атаки — 2з" DES-шифрований. Дифференциальный криптоанализ эффективен против DES и аналогичных алгоритмов с постоянными 8-блоками. Трудоемкость а зависит от структуры S-блоков. Для всех режимов шифрования — ЕСВ, СВС; CFB и OFВ атака имеет одинаковую трудоемкость [260]. Криптостойкость DES может быть повышена путем увеличения числа циклов. Трудоемкость дифференциального криптоанализа D семнадцатью или восемнадцатью циклами эквивалентна трудоемкости силовой атаки. П девятнадцати и более циклах дифференциальный криптоанализ невозможен в принцип. для его реализации потребуется более 2⁶⁴ выборочных открытых текстов (DES опери блоками по 64 бита, следовательно, существует 2⁶⁴ различных открытых текстов). В об случае доказательство криптостойкости по отношению к атаке методом дифференциального криптоанализа заключается в оценке числа открытых текстов, необходимых для выполню атаки. Атака невозможна, если полученная оценка превышает 2^b, где b — разрядность бл в битах.

4.6.2. Дифференциальный криптоанализ на основе отказов устройства

В сентябре 1996 г. группа специалистов из компании Bellcore объявила о новом методе криптоанализа, позволяющем эффективно раскрывать секретный ключ, хранящийся в памяти портативного шифрующего/дешифрующего устройства, например Smart Card или PCMClА Сохранность ключа в подобных устройствах обеспечивается за счет уникальных характеристик технологии TEMPEST. Впервые метод был успешно применен для раскрытия ключа криптосистемы RSA. Дальнейшие исследования нового метода, получившего название дифференциального криптоанализа на основе сбоев устройства (Differential Fault Analysis DFА), продемонстрировали его эффективность при атаке на DES и другие блочные шифры. Так, для раскрытия ключа DES понадобилось проанализировать двести шифротекстов,

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

Известно, что некоторые виды излучения (например, ионизирующее или радиоактивное) водят к сбоям в работе электронного оборудования. Именно эта идея и легла в основу криптоаналитической атаки, разработанной криптоаналитиками компании Bellcore. Предполагается, что криптоаналитик имеет неограниченный доступ к шифрующему/дешифрующему устройству. Открытый текст и секретный ключ хранятся в памяти устройства и недоступны. Криптоаналитик искусственно вызывает сбои в работе устройства, подвергая его облучению. Облучение приводит к инверсии бита (или битов) в одном из регистров на некотором промежуточном этапе криптографического преобразования. Для блочных шифров конструкции Фейстеля инверсия возникает на одном из циклов преобразования. Позиция инвертированного бита и номер цикла криптоаналитику также не известны. Сбой в работе приводит к искажению шифротекста на выходе устройства. Криптоаналитик пытается раскрыть секретный ключ, анализируя неискаженные и неискаженные шифротексты.

 Рассмотрим описанный метод на примере криптоанализа DES. Предположим, что имеется два различных шифротекста, полученных при шифровании одного и того же открытого текста на фиксированном ключе. Известно, какой шифротекст получен в результате инверсии одиночного бита в процессе шифрования. Под инверсией подразумевается следующее: пят правой половины входного блока на одном из 16 циклов DES-преобразования меняет выходное значение 0 на значение 1, или наоборот. Причем позиция бита и номер цикла пре- 4разования выбираются случайно и имеют равномерное распределение.

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

Рассмотрим случай, когда инверсия возникает на пятнадцатом цикле. Для раскрытия бит ключа необходимо участие более двух S-блоков в последнем цикле преобразования: различие в правой половине блоков шифротекста эквивалентно различиям на выходе F-функции пред- последнего цикла. По зафиксированным выходным изменениям можно. установить позицию одиночного инвертированного бита. Кроме того, можно определить, какое изменение правой половины блока шифротекста приводит к соответствующему изменению выхода F-функции на последнем цикле (суммы по модулю 2 левой половины шифротекста и инвертированного бита).

Для раскрытия подключа последнего цикла преобразования достаточно проанализировать менее двухсот шифротекстов. Дальнейшее развитие атаки возможно в двух направлениях. Первый вариант — поиск секретного ключа путем исчерпывающей проверки 2⁸ = 256 кандидатов при заданном подключе (напомним, что разрядность подключа — 48 бит). Альтернативный вариант заключается в использовании знания о подключе, полученного на последнем цикле, для анализа предшествующих циклов. Последний вариант позволяет успешно атаковать DES в режиме EDE-шифрования на трех различных ключах. Описанный метод работает и в тех случаях, когда инверсия возникает внутри F-функции или процедуры генерации подключей.

 Метод дифференциального криптоанализа на основе отказов устройства можно применять для атаки на такие блочные шифры, как IDEA, RC5 и Feal. Некоторые блочные шифры, например Khufu, Khafre и Blowfish, используют заданный секретный ключ для генерации 5-блоков. В этом случае описанный метод позволяет раскрывать не только ключи, но и сами S-блоки.

Рассмотренный выше криптоаналитический метод позволяет эффективно раскрывать секретный ключ, хранящийся в памяти устройства, даже тогда, когда сам алгоритм криптографического преобразования неизвестен. Так, например, детали криптоалгоритма составляют государственную тайну и засекречены Агентством национальной безопасности США. Однако аппаратная реализация криптоалгоритма в виде микросхемы Clippers входит в состав многих коммерческих устройств шифрования, например Fortezza PCMCIA.

Предполагается, что криптографические ключи хранятся в памяти с асимметричной динамикой сбоев. Это означает, например, что переход из состояния 1 в состояние 0 происходит с большей вероятностью, чем противоположное событие. Ячейки CMOS имеют симметричную динамику сбоев — все переходы равновероятны. Однако для некоторых видов энергонезависимой памяти это не так. Например, при воздействии ультрафиолетового излучения ячейки EEPROM памяти принимают значение 0 с большей вероятностью, чем значение 1.

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

Криптоаналитическая атака включает два этапа:

1) на первом этапе неизвестный секретный ключ k, хранящийся в памяти устройства, пользуется для серии шифрований фиксированного открытого текста т₀. После каждого шифрования устройство подвергается облучению. В результате последовательность шифротекстов на выходе устройства будет состоять из нескольких различных подпоследовательностей с_о, с₁, с₂,..., с_f. Изменение шифротекста — переход от с_i к с_i+1- обусловлено направленной инверсией (из 1 в О) некоторых бит ключа, иными словами- заменой ключа k_i; на k_i+1, k_ik_i+1 .Поскольку wt(k) = n/2, можно предположить, что f = n/2 и шифротекст с_f представляет собой результат шифрования т₀ на нулевом ключе k_f.. Отсутствие изменений в шифротексте после облучения — естественным признак вырождения ключа до нулевого состояния;

2) на втором этапе выполняется восстановление исходного секретного ключа k₀ по нулевому ключу k_f. Пусть известен некоторый промежуточный ключ k_i+1, тогда, модели сбоев, разумно предположить, что ключ k_i отличается от k_i+1 в одной позиции, wt(k_ik_i+1) = 1. Тогда для раскрытия ключа k_i достаточно зашифровать m₀  на последовательности ключей k_i+1,получаемых из k_i+1, последовательной заменой на нули. Если результат шифрования равен с_i — ключ восстановлен.

Так как алгоритм шифрования неизвестен, то для проверки ключей придется воспользоваться устройством шифрования. Как было отмечено выше, устройство позволяет различные ключи. Следовательно, для восстановления неизвестного ключа k₀ по известному k_f понадобится проверить O(n) ключей на каждом из О(п) шагов. Таким образом, кость метода оценивается как O(n²) операций шифрования.

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

Рассмотрим метод идентификации исходя из предположения, что реализованный устройстве криптоалгоритм соответствует конструкции Фейстеля.

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

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

После определения бит правого и левого подблоков можно установить их функционально зависимость. Предположим, что в криптоалгоритме применяется F-функция, состоящая из набора S-блоков. Некоторые биты правого подблока поступают на вход S-блока; выходное значение формирует биты левого подблока. Для определения входных и выходных бит, а также номера каждого S-блока достаточно выбрать все пары шифротекстов, различающихся в одном бите в правом подблоке. Информации о различиях в левых подблоках для каждого номера позиции в правом подблоке достаточно для определения номеров S-блоков, их размеров, а также входных и выходных битов.

Содержимое S-блоков можно восстановить, построив таблицу Т(х) = S(х k) и, где k — подключ, а неизвестное значение и получено из правого подблока предыдущего цикла. Например, если в качестве неизвестного криптоалгоритма используется DES, можно восстановить содержимое S-блоков, за исключением 6+4 = 10 из 64 х 4 = 256 неизвестных бит в каждом  блоке. Для LOKI удается восстановить 2¹² х 8 - (12+ 8) = 32 748 неизвестных бит в каждом блоке. Недостающие биты могут быть восстановлены в результате обработки данных, приученных на последнем цикле преобразования. Описанный метод позволяет восстановить не сами S-блоки, а их сумму по модулю 2 (операция XOR) с подключами. Восстановление S-блоков и подключей возможно путем анализа отличий результатов шифрования на нескольких ключах и данных из таблицы Т. Описанный метод был успешно применен для реконструкции S- блоков и алгоритма генерации подключей для DES и LOKI.

В некоторых блочных шифрах нелинейная функция F может быть реализована не в виде набора констант — S-блоков (как в DES и LOKI), а как последовательность различных арифметических операций, сдвигов, логических операций И, ИЛИ, НЕ и т.д. Подобные функции также поддаются восстановлению. Можно восстановить F-функцию более общего вида с произвольно заданной операцией суммирования (XOR) правой половины бит подключа и некоторой функцией на выходе. В целях упрощения анализа можно интерпретировать такую F-функцию как один большой S-блок. Несмотря на высокую трудоемкость, задача восстановления такого S-блока практически реализуема — число входных и выходных бит S-блока не превышает половины размера блока шифротекста. Эффективность такого подхода очевидна — другой метод идентификации блочного шифра на основе исчерпывающего перебора известных шифров и возможных ключей имеет практически неограниченную трудоемкость. Описанная атака применялась для идентификации DES в качестве неизвестного блочного шифра. Для идентификации бит правой половины, а также входных и выходных бит и содержимого S-блоков потребовалось проанализировать около пятисот и пяти тысяч искаженных шифротекстов соответственно. Для восстановления входных значений S-блоков потребовалось проанализировать около десяти тысяч искаженных шифротекстов.

Отметим, что трудоемкость восстановления содержимого S-блоков существенно зависит от их размеров. Поскольку S-блок DES имеет 6-битный вход, то для его реконструкции достаточно проанализировать не более 64 входных значений, полученных из искаженных блоков шифротекста. Трудоемкость аналогичной реконструкции для LOKI значительно выше— S-блоки имеют 12-битный вход (4096 различных значений).