|
|
  |
Главная страница / Архитектура отрасли Алгоритм шифрования DES и его вариантыСуществуют и более интересные режимы работы алгоритма Triple DES. Например, группа ученых из IBM предложила режим CBCM – внешний CBC-режим с OFB-маскированием (рис. 12) [21]. Режим CBCM выполняет не три шифрования на обработку одного блока данных, а четыре, поэтому его отнесение к Triple DES выглядит достаточно условным. «Лишнее» шифрование необходимо для выработки псевдослучайной последовательности масок, которые накладываются операцией XOR на результат первого зашифрования и второго расшифрования двухключевого Triple-DES в варианте EDE. Третий подключ данного режима используется для получения маски. Таким образом, режим CBCM можно сформулировать следующим образом: Maskn = Ek3/3(Maskn-1), Cn = Ek1/3(MasknDk2/3(Maskn + +Ek1/3(Cn-1Mn))), где Maskn – маска, используемая для зашифрования n-го блока данных, а в качестве начальных значений Mask0 и C0 используются два независимых вектора инициализации IV1 и IV2. Маскирующая последовательность не зависит ни от открытого текста, ни от шифртекста, поэтому маски могут быть вычислены предварительно и использоваться по мере необходимости. В 1998 году Эли Бихам и Ларс Кнудсен опубликовали работу [15], в которой сформулированы две атаки на Triple DES в режиме CBCM: атака с выбранным открытым текстом, использующая 265 пар блоков и требующая порядка 258 вычислений для нахождения ключа шифрования; атака, позволяющая при известном IV и наличии известного блока открытого текста и результатов его зашифрования на 233 связанных ключах вычислить k3/3 выполнением не более 257 операций зашифрования. Там же [15] предложено несколько вариантов усиления режима CBCM для противостояния приведенным атакам, простейший из которых – использование четвертого подключа k4/4 вместо повторного использования k1/3 в третьем зашифровании. Режимы работы с маскированием существуют и для однократного и двукратного алгоритма DES, например, известный алгоритм Мэта Блейза (Matt Blaze) представляет собой однократный DES в режиме ECB, на который, аналогично режиму CBCM, накладывается OFB-маска [19, 21] (рис. 13). Зашифрование в алгоритме Мэта Блейза выполняется следующим образом: Maskn = Ek1/2(Maskn-1), Cn = Ek2/3(MasknMn), где в качестве начального значения Mask0 используется вектор инициализации. Алгоритм использует 112-битный ключ шифрования, половина которого используется для вычисления маскирующей последовательности. Автор данного алгоритма посчитал, что, помимо решения проблемы короткого ключа DES, его алгоритм имеет ряд преимуществ, благодаря которым алгоритм идеально подходит для прозрачного шифрования файлов в операционных системах семейства Unix. В своей работе [19] Мэт Блейз дает множество рекомендаций по построению криптографически защищенной файловой системы CFS (Cryptographic File System) на основе его алгоритма. Однако, в [21] была опубликована атака на данный алгоритм, требующая наличия всего двух блоков открытого текста и соответствующих им шифртекстов, причем, при их зашифровании использовалось одно и то же значение IV. При наличии этих данных достаточно выполнения 3 256 шифрований для вычисления ключа шифрования. В [21] упоминается алгоритм с аналогичным наложением масок на Double DES – алгоритм Джонса (Jones): Maskn = Ek1/3(Maskn-1), Cn = Dk3/3(MasknEk2/3(Mn)). Алгоритм Джонса в 1,5 раза медленнее, чем алгоритм Блейза, но так же легко вскрываем – 168-битный ключ данного алгоритма может быть получен выполнением 258 шифрований при наличии тех же исходных данных, которые требуются для вскрытия алгоритма Блейза [21]. Различные внутренние режимы работы и режимы с маскированием могут быть применены не только в вариантах многократного DES, но и аналогичным образом в любых других алгоритмах. В ряде источников упоминается об алгоритме QDES (Quadruple DES – «четверной» DES), например, в [8] и [9]. Однако, алгоритм QDES является очень медленным, поэтому неизвестны случаи широкого применения данного алгоритма. В 1994 году Терри Риттер (Terry Ritter) предложил алгоритм Four-Rung Ladder-DES (лестничный DES c четырьмя «ступеньками») [43]. Структура алгоритма приведена на рис. 14. Фактически, алгоритм выполняет 4 раунда преобразований, в каждом из которых выполняется однократное шифрование половины шифруемого блока данных обычным DES-ом на независимых ключах раунда. Таким образом, размер блока алгоритма Ladder-DES равен 128 бит, а используемый размер ключа шифрования – 224 бит, т. е. четырехкратное увеличение относительно ключа алгоритма DES. Данный алгоритм продолжил рассмотренную ранее концепцию увеличения размера ключа за счет многократного шифрования. Причем, Ladder-DES явно выигрывает в скорости у Triple DES, поскольку на двойной размер блока данных относительно Triple DES приходится 4 шифрования вместо трех (т. е. скорость Ladder-DES эквивалентна скорости Double DES). При этом, аналогично Double DES и Triple DES, в Ladder-DES может быть использована аппаратура или программное обеспечение, реализующее классический DES. Серьезная уязвимость в Ladder-DES была найдена в 1997 году [6]. Для вычисления ключа данного алгоритма криптоаналитику необходимо сгенерировать порядка 236 блоков открытого текста, которые имеют следующий вид: 64-битная правая половина блока (переменная a, рис. 14) является константой, а левые половины (b) для каждого из генерируемых блоков различны. Дальнейшая логика атаки такова: поскольку a, и K1 являются фиксированными величинами, результат операции DES1 также является константой для каждого из 236 текстов; b различны для каждого текста, а c – константа, поэтому значения d = b c также не повторяются в пределах выбранных 236 текстов; поскольку зашифрование операцией DES2 различных значений d выполняется на фиксированных ключах K2, значения e являются различными; значения f являются различными по той же причине, что и значения b, a g также различны аналогично e; поскольку i = DES(K4,h) f, то f = DES(K4,h) i, а пара (h, i) представляет собой блок шифртекста. Имея в виду все вышесказанное, криптоаналитик может выполнить следующие действия для каждого возможного значения ключа K4 (цикл по n1 от 0 до 256-1): 1. Для каждого из имеющихся в наличии шифртекстов (цикл по n2 от 1 до 236): вычисляется и записывается в некую временную таблицу значение: fn1,n2 = DES(Kn1,hn2) in2; если вычисленное значение совпадает с каким-либо из предыдущих значений f, вычисленных для того же ключа Kn1, то данный ключ считается неверным (поскольку возникает противоречие описанной выше логике), поэтому осуществляется переход к следующему значению K4, т. е. Kn1+1. 2. Если выяснилось, что для всех шифртекстов не обнаружилось совпадений f, то считается, что обнаружился правильный ключ, т. е.: K4 = Kn1. Аналогичным образом после нахождения K4 вычисляется K3, а K2 и K1 определяются полным перебором по 256 вариантов. В среднем, для обнаружения коллизии для каждого из ключей достаточно проверки 232 вариантов. 236 пар текстов не дают абсолютной гарантии нахождения верного ключа, но вероятность ошибки пренебрежимо мала и составляет порядка 2-129. Таким образом, сложность вычисления ключа составляет порядка 288 (256 232) операций, что несравнимо быстрее полного перебора 2224 ключей. В той же работе [43] был предложен «двукратный четырехступенчатый» Ladder-DES (2x Four-Rung Ladder-DES), его структура приведена на рис. 15. Данный алгоритм имеет двукратный размер блока по сравнению с описанным выше вариантом Ladder-DES. Двойные блоки данного алгоритма шифруются аналогично Ladder-DES на первых двух «ступеньках», затем происходит циклический сдвиг субблоков на один вправо, после чего снова выполняются две ступеньки обычного Ladder-DES. Как видно из схемы, ключ данного алгоритма имеет размер, в 8 раз превышающий размер ключа DES, однако, автор алгоритма предложил следующую схему использования 224-битного ключа вместо 448-битного: нечетные ключи раунда являются основными, четные вычисляются из них согласно следующим простым формулам: K2 = K1 K3 K4 = K3 K5 K6 = K5 K7 K8 = K7 K1 Данный вариант имеет абсолютно те же скоростные характеристики, что и «однократный» Ladder-DES, он подвержен той же, описанной выше, атаке. И так же, как «классический» Ladder-DES, 2x Four-Rung Ladder-DES не нашел широкого применения. Главная страница / Архитектура отрасли |