Криптографические свойства алгоритма 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 существенно зависит от структуры используемых ключей. Схема формирования ключей для раундов допускает некоторые ключи, называемые слабыми.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: