Криптостойкость алгоритма

Нелинейность преобразований в DES средствами только S-блоков, в случае, если они имеют слабину, позволяет осуществлять контроль над шифрованной перепиской. Выбор S-блоков требует соблюдения нескольких условий:

· Каждая строка каждого блока должна быть перестановкой множества {0,1,2,……,15}

· S-блоки не должны являться линейной или афинной функцией своих аргументов.

· Изменение одного бита на входе S-блока должно приводить к изменению по крайней мере двух битов на выходе.

· Для каждого S-блока и любого аргумента х значение и должны различаться по крайней мере двумя битами.

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

В алгоритме DES существуют слабые и частично-слабые ключи. Слабыми ключами называется ключи k такие что DES_k (DES_k (x)) = x, x — блок 64 бит. Частично-слабые ключи — пары ключей (k ₁, k ₂) такие, что DES_{k 1}(DES_{k 2}(x))= x. Известны 4 слабых ключа. Для каждого слабого ключа существует 2³² «постоянные точки», то есть таких 64-битовых блоков х, в которых DES_k (x) = x. Существуют 6 частично-слабых пар ключей. Для каждого из 12 частично-слабых ключей существуют 2³² «анти-постоянные точки», то есть такие блоки х, что .

Основными методами взлома алгоритма являются:

· Метод полного поиска требует одну известную пару шифрованного и расшифрованного текста, незначительный объём памяти, и для его выполнения нужны 2⁵⁵ шагов.

· Дифференциальный криптоанализ — эта атака требует шифрования 2⁴⁷ открытых текстов, выбранных нападающим, и для её выполнения нужны 2⁴⁷ шагов. Теоретически являясь точкой разрыва, эта атака непрактична из-за чрезмерных требований к подбору данных и сложности организации атаки по выбранному открытому тексту.

· Линейный криптоанализ разработан Матсуи. Этот метод позволяет восстановить ключ DES с помощью анализа 2⁴³ известных открытых текстов, при этом требуется 2⁴³ шагов для выполнения.

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

Увеличение криптостойкости алгоритма (модификации DES)

С целью увеличения криптостойкости флгоритма DES было разработано несколько его модификаций: double DES (2DES), triple DES (3DES), DESX, G-DES.

Методы 2DES и 3DES основаны на DES, но увеличивают длину ключей (2DES — 112 бит, 3DES — 168 бит) чем и увеличивают криптостойкость.

Схема 3DES имеет вид DES (k ₃, DES (k ₂, DES (k ₁, M))), где k ₁, k ₂, k ₃ ключи для каждого шифра DES. Это вариант известен как ЕЕЕ, так как три DES-операции осуществляют шифрование. Существует 3 типа алгоритма 3DES:

DES-EEE3: Шифруется три раза с 3 разными ключами.

DES-EDE3: 3DES операции шифровка-расшифровка-шифровка с 3 разными ключами.

DES-EEE2 и DES-EDE2: Как и предыдущие, за исключением того, который первая и третья операции используют одинаковый ключ.

При выполнении алгоритма 3DES ключи могут выбрать так:

k ₁, k ₂, k ₃ независимы.

k ₁, k ₂ независимы, а k ₁ = k ₃

k ₁ = k ₂ = k ₃.

Метод DESX создан Рональдом Ривестом. Этод метод — усиленный вариант DES, поддерживаемый инструментарием RSA Security. DESX отличается от DES тем, что каждый бит входного открытого текста DESX логически суммируется по модулю 2 с 64 битами дополнительного ключа, а затем шифруется по алгоритму DES. Каждый бит результата также логически суммируется по модулю 2 с другими 64 битами ключа. Главной причиной использования DESX является простой в вычислительном смысле способ значительного повысить стойкость DES к атакам полного перебора ключа.

Метод G-DES разработан для повышения производительности DES на основе увеличения размером шифрованного блока. Заявлялось, что G-DES защищен так же, как и DES. Однако Бихам и Шамир показали, что G-DES с рекомендуемыми параметрами легко взламывается, а при любых изменениях параметров шифр становится ещё менее защищен, чем DES.

Ещё другой вариант DES использует независимые суб-ключи. Различно от алгоритма DES, в котором на основе 56-битового секретного ключа пользователя алгоритм DES получает шестнадцать 48-битных суб-ключей для использования в каждом из 16 раундов, в этом варианте использует 768-битный ключа (разделенного на 16 48-битных подключей) вместо 16 зависимых 48-битных ключей, создаваемых по ключевому графику алгоритма DES. Хотя очевидно, что использование независимых суб-ключей значительно усложнит полный поиск ключа, но стойкость к атаке дифференциальным или линейным криптоанализом не намного превысит стойкость обычного DES. По оценке Бихама для дифференциального криптоанализа DES с независимыми подключами требуется 2⁶¹ выбранных открытых текстов, в то время как для линейного криптоанализа требуется 2⁶⁰ известных открытых текстов.