Криптоанализ и Madryga

Исследователи из Технического университета в Квинсланде (Queensland University of Technology) [675] исследовали Madryga вместе с некоторыми другими блочными шифрами. Они обнаружили, что в этом алгоритме не проявляется лавинный эффект для преобразования открытого текста в шифротекст. Кроме того, во многих шифротекстах процент единиц был выше, чем процент нулей.

Хотя у меня нет сведений о проведении формального анализа этого алгоритма, он не производит впечатление супернадежного. При поверхностном знакомстве с ним Эли Бихам пришел к следующим выводам [160]:

Алгоритм состоит только из линейных операций (циклическое смещение и XOR), незначительно изменяемых в зависимости от данных.

В этом нет ничего похожего на мощь S-блоков DES.

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

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

NewDES

NewDES (новый DES) был спроектирован в 1985 году Робертом Скоттом (Robert Scott) как возможная замена DES [1405, 364]. Алгоритм не является модификацией DES, как может показаться из его названия. Он оперирует 64-битовыми блоками шифротекста, но использует 120-битовый ключ. NewDES проще, чем DES, в нем нет начальной и заключительной перестановок. Все операции выполняются над целыми байтами. (На самом деле NewDES ни коим образом не является новой версией DES, название было выбрано неудачно.)

Блок открытого текста делится на восемь 1-байтовых подблоков: B0, B1, . . ., B6, B7. Затем подблоки проходят через 17 этапов. В каждом этапе восемь действий. В каждом действии один из подблоков подвергается операции XOR с частью ключа (есть одно исключение), заменяется другим байтом с помощью функции f и затем подвергается операции XOR с другим подблоком, который и заменяется результатом. 120-битовый ключ делится на 15 подблоков ключа: K0, K1, . . ., K13, K14. Процесс легче понять, увидев его схему, чем прочитав его описание. Алгоритм шифрования NewDES показан на Рис. 13-2.

[image]

Рис. 13-2. NewDES.

Функция f выводится из Декларации независимости. Подробности можно найти в [1405].

Скотт показал, что каждый бит блока открытого текста влияет на каждый бит шифротекста уже после 7 этапов. Он также проанализировал функцию f и не нашел каких-либо очевидных проблем. NewDES обладает той же комплиментарностью, что и DES [364]: если EK(P} = C, то EK'(P'} = C'. Это уменьшает объем работы, необходимой для вскрытия грубой силой, с 2110 действий до 2119. Бихам заметил, что любое изменение полного байта, примененное ко всем байтам ключа и данных, также приводит к комплиментарности [160]. Это уменьшает объем грубого вскрытия до 2112 действий.

Это не является критичным, но предложенное Бихамом криптоаналитическое вскрытие со связанными ключами может вскрыть NewDES с помощью 233 выбранных открытых текстов для выбранных ключей за 248 действий [160]. Хотя такое вскрытие требует много времени и в большой степени является теоретическим, оно показывает, что NewDES слабее, чем DES.