5.2. Криптографические свойства алгоритма des

Наиболее слабым звеном алгоритма является небольшая длина ключа.

Отметим, что в алгоритме Lucifer – прототипе DES, разработанном компанией IBM, длина ключа составляла 128 бит.

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

Еще в 1979 году У.Диффи и Д.Хеллманн (W.Diffe, D.Hellman) дали оценку стоимости специального вычислителя для вскрытия ключа за одни сутки:  20 миллионов долларов. В 1981 году этот результат был уточнен: стоимость вычислителя, решающего задачу за два дня не превышает $50 млн. Для современных специальных служб перебор ключей DES вполне реален.

Критичным для алгоритма является число раундов его работы. Почему используется именно 16 раундов, а не 8 или 32? А.Конхейм (A.Konheim) показал, что после 8 итераций шифрованный блок является практически случайной функцией любого бита текста и любого бита ключа. Тем не менее, ограничиться 8 раундами не представляется возможным исходя из ряда практических и теоретических результатов. В частности в 1982 году были получены результаты криптоанализа 4 раундового DES; через шесть лет был дешифрован 6 раундовый DES.

Разработанные в 1990 году Э.Бихамом (Е.Biham) и А.Шамиром (А.Shamir) методы дифференциального криптоанализа показали, что DES с меньшим чем 16 числом раундов может быть вскрыт с помощью атаки на основе известных открытых текстов (known-plaintext attack) более эффективно, чем на основе полного перебора ключей.

Стойкость алгоритма DES существенно зависит от структуры используемых ключей [11,12]. Схема формирования ключей для раундов допускает некоторые ключи, называемые слабыми.

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

Это может произойти, если ключ состоит только из 0, только из 1 или, если одна половина из 0, а другая из 1 (таблица 5.1).

Кроме того, существуют пары ключей, дающих одинаковый результат при шифровании открытых текстов (эквивалентные ключи). Это тоже связано с генерацией подключей: вместо 16, на самом деле, формируются только 2 различных, используемых по 8 раз в 16-ти раундах. Эти ключи называются полуслабыми. Есть также ключи, производящие только 4 подключа, каждый из которых используется по 4 раза в алгоритме шифрования.

В общем-то, 64 слабых ключа из 72 057 594 037 927 936 вариантов возможных ключей – это немного. Шансы получить такой ключ ничтожно малы. Других слабых ключей не найдено.

Таблица 5.1. Значения слабых ключей алгоритма DES (в 16 с/с)

Ключ 56 битов
28 бит(лев.)	28 бит(прав.)
0000000	0000000
0000000	FFFFFFF
FFFFFFF	0000000
FFFFFFF	FFFFFFF

Определенные слабости DES связаны со свойствами так называемых дополняющих (инверсных) ключей.

Пусть блок текста переходит в блок шифртекстапри ключе.

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

Это означает, что применение против DES атаки с заранее выбранным открытым текстом (chosen-plaintext attack) позволяет сократить вдвое перебор вариантов ключей, т.е. нужно проверить вариантов вместо.

Кроме того, Э.Бихам и А.Шамир показали также, что существует атака на основе известных открытых текстов (known-plaintext attack) той же сложности, при наличии как минимум известных пар открытых и шифрованных текстов.

Указанная слабость является скорее теоретической, т.к. вероятность появления у открытого сообщения дополнения в виде открытого текста очень низкая.

Вплоть до 1992 года оставался дискуссионным вопрос: является ли множество отображений, порождаемое алгоритмом DES группой? Суть проблемы заключается в следующем.

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

Каждое такое отображение определяется ключом, является подстановкой на множестве 64-битовых блоков и определяет операции зашифрования-расшифрования.

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

Рис. 5.5.Тройное шифрование с помощью DES

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

Если же является группой, то криптоанализ алгоритма упрощается, ибо тогда для любых ключей,существует бы ключ, такой, что, а это позволяет воспользоваться атакой типа «встреча посередине» (meet-in-the-middle) со сложностьювариантов вместов случае полного перебора ключей.

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

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

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

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

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

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

Для алгоритма DES, например, если разность между блоками открытых текстов (в смысле операции ) равна 0080 8200 6000 0000₁₆, то существует шанс, примерно в 5%, что разность между шифрованными блоками та же.

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

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

В стандарте алгоритма DES блоки замены оптимизированы против таких атак. В частности, при заданных блоках, для 16 раундов оценка сложности составляет порядка . Для алгоритма с 17-18 раундами время вскрытия ключа оказывается примерно равным времени полного перебора. При 19 раундах перебор становится выгоднее.

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

Для проведения атаки chosen plaintexts attack для получения необходимой информации требуется шифрование потока 1.5 Мбит/сек в течение 3 лет.

В большинстве раундов исходный ключ DES сдвигается на 2 бита, кроме 1, 2, 9 и 16 раундов, когда сдвиг равен 1 биту. Причина – появление регулярности в преобразовании, которая может быть использована для проведения криптоаналитических атак.

Модификация DES, путем введения постоянного сдвига ключа на 2 бита после любого раунда, приводит к снижению его стойкости.

Э.Бихаму принадлежит идея соответствующей эффективной атаки на основе связанных ключей (related-key criptanalysis). Эта атака реализуется в случае постоянного сдвига ключа и при наличии открытых текстов с выбранными ключами (chosen-key plaintexts) или в случае известных пар открытых и шифрованных текстов (known-plaintexts).

Для проведения атаки проводится анализ разностей между парами ключей и парами открытых и шифрованных текстов.

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