Алгоритм Biham-DES

Криптолог, несомненно, добившийся наиболее значимых и известных результатов в деле криптоанализа DES и его вариантов, Эли Бихам, совместно с Алексом Бирюковым предложил свой вариант алгоритма DES, известный как Biham-DES.

Бихам и Бирюков утверждают, что большинство реализаций алгоритма DES, в том числе аппаратных, позволяют загружать значения таблиц замен. Согласно многим работам Эли Бихама и других исследователей, таблицы замен являются наиболее значащей частью преобразований, выполняемых алгоритмом DES. Поэтому эксперты продолжили анализ таблиц замен.

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

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

В результате дальнейших усилий появился алгоритм Biham-DES. Данный алгоритм использует 119-битный ключ (Ka, Kb, Кс, Kd), подключи которого применяются следующим образом:
16-битный подключ Ка определенным образом расширяется до 48 битов и в каждом раунде накладывается операцией XOR на 48-битное входное значение таблиц замен;
32-битный подключ Kb аналогичным образом накладывается на выходное значение таблиц замен;
15-битный подключ Кс определенным образом изменяет порядок таблиц замен, в качестве которых используются таблицы алгоритма s3DES с переставленными таблицами Si и S2;
Kd— 56-битный ключ, используемый аналогично обычному алгоритму DES.

Существует вариант алгоритма Biham-DES с таблицами замен классического DES; в этом случае подключ Кс имеет размер 5 битов.

Также авторы предложили вариант алгоритма с таблицами s3DES со 104-битным ключом без использования ключа Кс, т. е. без перестановок таблиц.

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

Из всех вариантов алгоритма Biham-DES наиболее стойким является вариант со 119-битным ключом и таблицами замен s3DES. Сложность дифференциального и линейного криптоанализа такого алгоритма составляет, соответственно, 266 и 264 операций, т. е. стойкость алгоритма существенно выше стойкости DES, но криптоанализ требует несравнимо меньших затрат, чем полный перебор ключа. Кроме того, все варианты алгоритма Biham-DES оказались относительно слабыми по отношению к атаке на связанных ключах— вариант с таблицами замен DES (109-битный ключ) вскрывается при наличии 231 выбранных открытых текстов и соответствующих им шифртекстов, зашифрованных на 32 связанных ключах.

По материалам книги Сергея Панасенко «Алгоритмы шифрования»

Алгоритмы шифрования