Стандарт шифрования данных DES

    2.3. Криптоанализ DES 

  С самого начала использования алгоритма DES криптоаналитики всего мира прилагали  множество усилий по взлому алгоритма DES1. Фактически DES дал невиданный доселе толчок развитию криптоанализа (т. е. науки, посвященной поиску уязвимостей и, соответственно, взлому криптографических алгоритмов защиты информации). Вышли сотни трудов, посвященных различным методам криптоанализа именно в приложении к алгоритму DES, а также деталям самого алгоритма и их влиянию на криптостойкость DES. Можно утверждать, что именно благодаря DES появились целые направления криптоанализа, такие как:

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

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

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

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

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

    2.4. «Двойной» и «тройной» DES 

    Наиболее  логичным способом противодействия  полному перебору ключа DES выглядит многократное зашифрование данных алгоритмом DES с различными ключами. Следующий алгоритм получил название Double DES – двойной DES:

    C = Ek2/2(Ek1/2(M)), где k1/2 и k2/2 – половины  двойного ключа алгоритма Double DES, каждая из которых представляет собой обычный 56-битный ключ DES, а E – функция зашифрования блока данных обычным DES-ом.

    Если  бы при двойном шифровании DES выполнялось следующее свойство: C = Ek2/2(Ek1/2(M)) = Ek(M), для любых значений k1/2 и k2/2, то двойное шифрование не приводило бы к усилению против полного перебора ключа – всегда нашелся бы такой ключ k, однократное зашифрование которым было бы эквивалентно двукратному шифрованию на ключах k1/2 и k2/2, а для нахождения ключа k достаточно было бы перебрать 255 ключей. К счастью, DES не обладает таким свойством, поэтому Double DES действительно удваивает эффективный размер ключа – до 112 бит, а при современном развитии вычислительной техники полный перебор 112-битного ключа невозможен.

    Однако  у Double DES есть другая проблема – атака «встреча посередине», предложенная известными криптологами Ральфом Мерклем (Ralph Merkle) и Мартином Хеллманом (Martin Hellman). С помощью этой атаки криптоаналитик может получить k1/2 и k2/2 при наличии всего двух пар открытого текста и шифртекста (M1 – C1 и M2 – C2) . Такая атака, выполняющая, фактически, перебор половинок двойного ключа, как со стороны открытого текста, так и со стороны шифртекста, требует примерно в 2 раза больше вычислений, чем перебор обычного ключа DES, однако, требует также много памяти для хранения промежуточных результатов. Тем не менее, атака является реально осуществимой на практике, поэтому алгоритм Double DES не используется.

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

    Поскольку короткий ключ DES волновал криптологическое сообщество с момента принятия DES в качестве стандарта, уже в 1978 году была предложена схема тройного шифрования с двойным, 112-битным, ключом (2-key Triple DES): C = Ek1/2(Dk2/2(Ek1/2(M))).  (рис. 2.4 )

    Такая схема называется EDE (Encrypt-Decrypt-Encrypt –  «зашифрование-расшифрование-зашифрование»). Данная схема интересна тем, что  при использовании одинаковых половинок ключа (k1/2 = k2/2) зашифрование Triple DES-ом эквивалентно однократному шифрованию алгоритмом DES на том же ключе

  Ek1/2(Dk1/2(Ek1/2(M))) = Ek1/2(M). 

                                                                                                             зашифро-

   открытый                                                                                                                    ванный

         текст                                                                                                                    текст

                              К1                             К2                         К3 

  Рис. 2.4. Схема Triple DES 

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

  C = Ek3/3(Dk2/3(Ek1/3(M))),

  где k1/3, k2/3 и k3/3 – три обычных 56-битных ключа DES, в совокупности представляющие собой 168-битный ключ алгоритма Triple DES.

    Известный криптолог из Норвегии Ларс Кнудсен (Lars Knudsen) предложил схему трехключевого тройного DES со 112-битным ключом шифрования, которая называется TEMK (Triple Encryption with Minimum Key – тройное шифрование с минимальным ключом).

    В данной схеме 112-битный ключ шифрования (K1/2, K2/2) расширяется в три подключа Triple DES следующим образом:

  k1/3 = EK1/2(DK2/2(EK1/2(C1))),

  k2/3 = EK1/2(DK2/2(EK1/2(C2))),

  k3/3 = EK1/2(DK2/2(EK1/2(C3))),

где C1, C2 и C3 – несекретные константы, используемые для расширения ключа.

    Наиболее  широкое распространение получила схема Triple DES с тремя независимыми подключами. Ключ данного варианта Triple DES может быть раскрыт атакой на основе связанных ключей и выбранных открытых текстов, требующей выполнения от 256 до 272 операций шифрования алгоритмом DES Данная атака весьма сложна в применении, поэтому она не повлияла на распространенность алгоритма. Что интересно, на двухключевой Triple DES данная атака не распространяется, авторы отметили, что это единственный случай, когда двухключевой Triple DES оказался сильнее трехключевого.

    Аналогично  «одинарному» алгоритму DES, Double и Triple DES могут быть использованы в различных  режимах работы: ECB, CBC, CFB и OFB. Однако, например, Triple DES выполняет три раздельных шифрования каждого блока, поэтому различные связи между шифруемыми блоками данных (например, действие Ci = Ek(MiСi–1) в режиме CBC) могут быть установлены после выполнения каждого элементарного шифрования обычным DES-ом (это называется внутренним режимом), а не после завершения выполнения всех трех шифрований (для отличия от внутренних режимов классические режимы работы в применении к Double/Triple DES часто называют внешними).

    В качестве примера можно привести атаку на внутренний режим 3-key Triple DES ECB|ECB|OFB. 
 
 

    Выводы к разделу 2 

      Принятие стандарта шифрования DES явилось мощным толчком к широкому применению шифрования в коммерческих системах. Введение этого стандарта - отличный пример унификации и стандартизации средств защиты.  Примером системного подхода к созданию единой крупномасштабной системы защиты информации является  директива Министерства финансов США 1984 года, согласно которой все общественные и частные организации,  ведущие дела с правительством США,  обязаны внедрить процедуру шифрования DES;  крупнейшие банки - Citibank, Chase Manhattan Bank, Manufaktures Hannover Trust, Bank of America, Security Pacific Bank - также внедрили эту систему. Министерство энергетики  США  располагает более чем 30 действующими сетями, в которых используется алгоритм DES. Министерство юстиции устанавливает 20000  радиоустройств,  располагающих средствами защиты на базе DES.

      Стандартизация в последнее  время приобретает международный характер, подтверждение тому - международный стандарт 1987 года ISO 8372,

разработанный на основе криптоалгоритма DES.

      Итак,  алгоритм DES представляет собой основной механизм,применявшийся  частными  и  государственными учреждениями США для защиты информации.  В то же время  Агенство  национальной безопасности, выступающее  как эксперт по криптографическим алгоритмам, разрабатывает новые алгоритмы шифрования данных для  массового использования.  В  1987 году Национальное бюро стандартов после обсуждения подтвердило действие DES;  его пересмотр намечалось провести не позднее января 1992 года,  и на сегодняшний день действие DES ограничивается исключительно коммерческими системами. DES может  быть реализован аппаратно и программно, но базовый алгоритм всё же рассчитан на  реализацию  в  электронных устройствах специального назначения. 
 
 
 
 
 
 

ЗАКЛЮЧЕНИЕ 

    Из  всего изложенного следует, что  надежная криптографическая система должна удовлетворять таким требованиям:

• процедуры зашифровывания и расшифровывания должны быть "прозрачны" для пользователя;
• дешифрование закрытой информации должно быть максимально затруднено;
• содержание передаваемой информации не должно сказываться на эффективности криптографического алгоритма;
• надежность криптозащиты не должна зависеть от содержания в секрете самого алгоритма шифрования (примером этого является  алгоритм DES).

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

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