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

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

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

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

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

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

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

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

(L_i , R_i) = (R_i-1 , L_i-1 Å f(R_i-1 , К_i)).

Учитывая подстановку F_i (×) и перестановку T_i (×), цикл преобразования можно представить так, как это сделано на рисунке 3.3.

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

Рисунок 3.1 - Схема DES - преобразования

Рисунок 3.2 – Общий вид цикла DES - преобразования

Рисунок 3.3 – Цикл DES с учётом перестановки и подстановки

Подстановка

F_i (L_i-1 , R_i-1) = (R_i-1 , L_i-1 Å f(R_i-1 , К_i))

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

F_i (F_i (L_i-1 , R_i-1)) = F_i ((R_i-1 , L_i-1 Å f(R_i-1 , К_i)))

= ((R_i-1 , L_i-1 Å f (R_{i -1} , К_i)) Å (f(R_i-1 , К_i))

= (L_i-1 , R_i-1).

В свою очередь, подстановка T (L^‘_i, R_i^’) = (R_i^’, L^‘_i) так­же является инволюцией,

поскольку

T (T (L^‘_i , R_i^’)) = T (R_i^’, L^‘_i)

= (L^‘_i , R_i^’)

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

DES = (IP) F₁TF₂T... F₁₅TF₁₆ (IP)^-1

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

DES ^-l = (IP)^-l F _l6 TF ₁₅ T... F ₂ TF ₁(IP).

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

Рисунок 3.4 – Один цикл DES – преобразования

То есть если при шифровании ис­пользовались ключи К ₁, К ₂, К ₃,… К ₁₆ ,

то ключами дешифрования будут K ₁₆, K ₁₅, К ₁₄, …, К ₁ Алгоритм исполь­зует только стандартную арифметик 64-битовых чисел и логические опера­ции, поэтому легко реализуется на ап­паратном уровне.

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

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

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

Таблица 3.1 - DES — начальная перестановка

Таблица 3.2 - DES — преобразование ключа

Эту и все другие таблицы настоящей главы

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

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

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

Таблица П.З. DES — сдвиг ключа в зависимости от номера цикла

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

Таблица П.4 - DES — перестановка со сжатием

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

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

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

Рисунок 3.5 - DES — схема перестановки с расширением

Таблица 3.5 - DES — перестановка с расширением

Хотя выходной блок больше входного, каждый входной блок генерирует уникальный выходной блок.

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

48 битов делятся на восемь 6-битных подбло­ков. Каждый отдельный подблок обрабатывается отдельным S -блоком: первый подблок - первым S -блоком, второй - вторым S-блоком и так далее (см. рисунок 3.6).

Рисунок 3.6 - DES — подстановка при помощи S-блоков

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

Таблица 3.6 - DES — S-блок 1

Таблица 3.7 - DES — S-блок 2

Таблица 3.8 - DES — S-блок 3

Таблица 3.9 - DES — S-блок 4

Таблица 3.10 - DES — S-блок 5

Таблица 3.11 - DES — S-блок 6

Таблица 3.12 - DES — S-блок 7

Таблица 3.13 - DES — S-блок 8

Таблица 3.14 - DES — перестановка с помощью Р -блоков

Таблица 3.15 - DES — заключительная перестановка

Входные биты особым образом определяют элемент S -блока. Рассмотрим 6-битовый вход S -блока: b₁, b₂, b₃, b₄, b₅, и b₆. Биты b₁ и b₆ объединяются, образуя 2-битное число от нуля до трех, соответствующее строке таблицы. Средние четыре бита, с b₂ по b₅, объединяются, об­разуя 4-битное число от нуля до пятнадцати, соответствующее столбцу таблицы. Например, пусть на вход шестого S -блока (то есть биты функции XOR с 31 по 36) попадает 110011. Первый и последний биты, объединяясь, образуют 11, что соответствует строке три шестого S -блока. Средние четыре бита образуют 1001, что соответствует столбцу девять того же S -блока. Элемент шестого S -блока, находящийся на пересечении строки три и столбца де­вять, - это 14 (строки и столбцы нумеруются с нуля, а не с единицы). Вместо 110011 подста­вляется 1110. Намного легче реализовать S -блоки программно в виде массивов с 64 элемен­тами. Для этого потребуется переупорядочить элементы. Такой способ описания S -блоков помогает понять, как они работают. Каждый S -блок можно рассматривать как функцию подстановки 4-битного элемента: b₂ по b₅ являются входом, а некоторое 4-битное число - результатом. Биты b₁ и b₆ определяются соседними блоками, они определяют одну из четы­рех функций подстановки, возможных в данном S -блоке. Подстановка с помощью S -блоков является ключевым этапом DES. Другие действия алгоритма линейны и легко поддаются анализу. S -блоки нелинейны, и именно они в большей степени, чем всё остальное, обеспе­чивают криптостойкость DES. В результате этой подстановки получаются восемь 4-битных блоков, которые вновь объединяются в единый 32-битный блок. Этот блок поступает на вход следующего этапа — перестановки с помощью Р -блоков.

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

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

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

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

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

Криптостандарт DES стал объектом скрупулезных криптоаналитических исследований с момента его публикации в 1977 г. [15]. В том же году Диффи и Хеллман предложили вариант специализированного компьютера стоимостью двадцать млн. долл., гарантирующе­го раскрытие ключа DES методом силовой атаки в течение одних суток. В 1993 г. Винер (М. J. Wiener) спроектировал специализированную компьютерную архитектуру стоимостью в один млн. долл., позволяющую раскрывать ключ DES в среднем за 3,5 час. [399]. Реализа­ция идей Винера на современном технологическом уровне позволяет раскрывать ключ DES в среднем за 35 мин [400J. Силовая атака на основе метода распределенных вычислений обес­печивает раскрытие ключа в течение 90 и даже 40 календарных дней [390,392]. В 90-е годы были разработаны и применены для атаки на DES методы дифференциального и линейного криптоанализа [260,377].

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

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

Расстояние Хэмминга dist (x, y) между двумя двоичными векторами х = х ₁,..., х _n и у = y ₁,…, y _n, равно числу позиций, в которых они различаются. Например. dist(10111,00101) = 2. Вес Хэмминга wt (x) вектора х = х ₁,..., х _n равен числу ненулевых компонентов х _i, напри­мер wt(101110) = 4. Очевидно, что dist(x, y) = wt (x Å y), где х Å у покомпонентная сумма по модулю 2 (операция XOR) векторов х и у.

Таким образом, расстояние Хэмминга i -го и j -ro блоков открытого текста равно расстоя­нию Хэмминга (i - 1)-го и (j - 1)- го блоков шифротекста, поскольку Р _i Å Р _j = С _i-1 Å С _j-1. При длине блока n совпадения пары можно ожидать на множестве из 2 ^{n / 2} блоков шифротекст. Для DES это 2³² блоков.

Для обеспечения высокого уровня криптостойкости рекомендуют применять тройное DES-шифрование на трех [391] или на двух раз­личных ключах [191|. Такие режимы извест­ны под общим названием EDE (encrypt-decrypt-encrypt). Так, при двух различных ключах блок открытого текста сначала шифруется на ключе К ₁, дешифруется на ключе К ₂ и за­тем опять шифруется на ключе К ₁. При трех различных ключах данный метод позволяет увеличить размер ключевого пространства до 2¹⁶⁸, при двух до 2¹¹². Однако угроза атаки на основе сопоставления образцов шифротек­ста при этом сохраняется, так как длина блока DES фиксирована (64 бита).

В течение ряда лет комитет X9.F.1 Американского национального института стандартов (National Institute of Standards and Technology, NIST) занимался исследованием различных режимов для метода тройного DES-шифрования [382]. Основу предложенной NIST разработ­ки составили известные режимы ЕСВ, СВС, OFB и CFB с заменой базовой операции одно­кратного шифрования на тройное DES-шифрование.

Рисунок 3.7 – DES – режим TCBC

В режиме Обратной связи но шифротексту для тройного DES (Triple DES Cipher Block Chaining, ТСВС) блок шифротекста, сум­мируемый с блоком открытого текста, получается в результате тройного DES-шифрования. ТСВС называют также внешним СВС-режимом (outer-CBC mode) [138], подразумевая под этим, что блок шифротекста берется с выхода тройного DES-шифратора. Схема режима ТСВС представлена на рис. 3.7. Данный режим уязвим с точки зрения атаки на основе

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

Рисунок 3.8 - DES – режим ICBC

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

Тем не менее, проанализировав большое число различных режимов шифрования [383. 384, 386], Бихам (Е. Biham) продемонстрировал уязвимость режима ICBC [384]. Трудоем­кость атаки Бихама лишь незначительно превышает трудоемкость атаки на однократный DES. Исходное предположение заключается в возможности контроля обратных связей со стороны криптоаналитика. Атакующий выбирает шифротекст вида (С,С,С,С), где все че­тыре блока идентичны. После дешифрования на одном СВС-уровне исходный шифротекст принимает вид (?,Х,Х,Х), где блоки X идентичны, но не известны криптоаналитику. По­сле дешифрования на двух уровнях получаем (?,?,У, У), где блоки У идентичны, а после дешифрования на всех трех уровнях получаем (?,?,?, Z) для некоторого Z. Для успешного осуществления атаки необходимо 2³³ шифротекстов для различных С. Вероятность того, что два шифротекста, например С₁ и С₂, приведут к одному и тому же значению X и, следова­тельно, одним и тем же значениям У и Z, достаточно велика (парадокс «дня рождения» - разновидность силовой атаки, основанной на следующем известном факте: вероятность совпадения дней рождения двух и более человек в группе из 23 человек превышает 1/2. Так. если на вход некоторой функции подается случайное значение, а на выходе наблюдается одно из к возможных независимых значений с рав­номерным распределением, то, подавая на вход различные значения, можно ожидать появления одинаковых значений на выходе функции с вероятностью 1,2Ök).

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

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

Режим СВСМ аналогичен СВС с базовой операцией трехкратного шифрования на двух различных ключах, при этом промежуточные блоки шифротекста между первым и вторым, а также вторым и третьим уровнями маскируются блоками шифротекста, полученными в результате DES-шифрования на третьем ключе в режиме OFB (рис. 3.9, где М ₁, М ₂,... и т.д. — выходные блоки OFB-режима, полученные в результате шифрования на ключе К₃, и IV ₁ — вектор инициализации).

Рисунок 3.9 - DES – режим CBCМ

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

Криптостойкость СВСМ при различ­ных атаках, описанных в [384]. доказана в статье [388].

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

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

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

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

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

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

Таблица 3.16. Использование подключей в ГОСТе 28147-89

Таблица 3.17. S-блоки ГОСТа 28147-89

Дата добавления: 2014-01-05