Addition modulo 2 in block ciphers.pdf Составной частью любого блочного шифра является процедура смешения с ключом. Обычно данная процедура представляет собой сложение по модулю 2 (XOR) промежуточного информационного блока c раундовым ключом (как в алгоритмах DES, AES и др.), однако ничто не мешает использовать любую другую операцию, например сложение по модулю 2n (как в алгоритме ГОСТ 28147-89). С учётом современной элементной базы и структуры большинства блочных шифров замена операции XOR на сложение по модулю 2n не приведёт к существенному возрастанию сложности как программной, так и аппаратной реализации шифра. Работа посвящена анализу стойкости алгоритмов блочного шифрования, в которых операция смешения с ключом реализована как операция сложения по модулю 2n. Произведён анализ криптографических свойств операции A + B = D mod 2n, где A = (an-1,..., a0), B = (bn-1,..., bo), D = (dn-1,..., d0). В частности, рассмотрены линейные и нелинейные аппроксимации для выходных битов dj и доказано, что для любого i > 0 функции aj ф bj ф aj-1 и aj ф bj ф bj-1 являются наилучшими линейными аппроксимациями для dj, а именно: если aj, bj, j = 0,... , n - 1, являются независимыми случайными величинами, принимающими все свои значения с равной вероятностью, то линейные соотношения dj = aj ф bj ф aj-1, (1) dj = aj ф bj ф bj-1 (2) выполняются с вероятностью 0,75. Рассмотрим особенности использования данных линейных аппроксимаций при проведении линейного криптоанализа блочных шифров, в которых для смешения с ключом используется операция Y = X + K mod 2n. При проведении линейного криптоанализа [1] считается, что ключ фиксирован и аналитик располагает некоторым количеством пар открытый текст/шифртекст (материалом), полученных на этом ключе. Показано, что при фиксированном ключе вероятность выполнения соотношений (1), (2) может сильно отличаться от 0,75, а именно она колеблется в интервале от 0,5 до 1, причём границы достижимы. Таким образом, если при проведении линейного криптоанализа использовать аппроксимации (1), (2) для конкретного ключа, вероятность их выполнения может оказаться равной 0,5, и анализ будет невозможен. Предложено новое решение - нелинейные соотношения, выполняющиеся с преобладанием не меньше 0,25 для любого фиксированного ключа. Точнее, доказано: Vi > 0 VK 3z (P{y = xi 0 zxi-i} = 1/2 + e, |e| ^ 1/4; (3) Vi > 0 VK 3z (P{yi 0 yi-i = xi 0 zxi-i} = 1/2 + e, |e| ^ 1/4. (4) Изучена возможность применения соотношений (3), (4) для анализа блочных шифров, использующих операцию + mod 2n. Предложена модификация линейного метода криптоанализа, которая в ряде случаев позволяет провести более эффективные атаки. В частности, аппроксимации (3), (4) использованы для проведения атаки с известным открытым текстом на конкретный шифр, имеющий структуру SP-сети, в котором для смешения с ключом используется операция + mod 2n. Эта атака позволяет восстановить ключ быстрее полного перебора, что подтверждено моделированием на ЭВМ. Далее был проанализирован шифр, имеющий аналогичное строение, но использующий для смешения с ключом операцию XOR. Сравнительный анализ показал, что замена операции XOR на + mod 2n приводит к существенному увеличению стойкости шифра. При проведении атаки на шифр, использующий + mod 2n вместо XOR, помимо S-блоков необходимо аппроксимировать блок смешения с ключом, поэтому в большинстве случаев абсолютная величина преобладания итогового соотношения, связывающего некоторые биты открытого текста, шифртекста и ключа, становится гораздо ниже, из-за чего для проведения атаки требуется существенно больше материала. Проведена атака с известным открытым текстом на алгоритм ГОСТ 28147-89 с сокращённым числом раундов и S-блоками специального вида. В [2] доказана стойкость алгоритма ГОСТ 28147-89 с не менее чем пятью раундами шифрования относительно линейного метода криптоанализа. Предложенный метод позволил провести атаку на алгоритм ГОСТ 28147-89 с восемью раундами шифрования.

Скачать электронную версию публикации