MARS — алгоритм шифрования, разработанный корпорацией IBM, создавшей в свое время DES. По заявлению IBM, в алгоритм MARS вложен 25-летний криптоаналитический опыт фирмы, и наряду с высокой криптографической стойкостью шифр допускает эффективную реализацию даже в таких ограниченных рамках, какие характерны для смарт-карт.

Алгоритм уникален тем, что использовал практически все существующие технологии, применяемые в криптоалгоритмах, а именно:

• простейшие операции (сложение, вычитание, исключающее или)
• подстановки с использованием таблицы замен
• фиксированный циклический сдвиг
• зависимый от данных циклический сдвиг
• умножение по модулю 2³²
• ключевое забеливание

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

Структура алгоритма

Исходя из двух следующих предположений:

1. Многие известные криптоаналитические методы отличают первый и последний раунды алгоритма (или несколько первых и/или несколько последних раундов) от остальных и применяют к ним другие приемы, нежели к «центральным» раундам алгоритма. Таким образом, различные раунды алгоритма шифрования играют различное значение в обеспечиваемой алгоритмом криптостойкости;
2. Скорее всего, алгоритм с гетерогенной структурой будет лучше противостоять криптоаналитическим методам будущего, чем алгоритм, все раунды которого идентичны.

— разработчики алгоритма MARS придали ему сильно гетерогенную структуру — раунды алгоритма весьма различаются между собой. Алгоритм MARS можно описать следующим образом:

1. Предварительное наложение ключа: на 32-битные субблоки A, B, C, D накладываются 4 фрагмента расширенного ключа k₀…k₃ операцией сложения по модулю 2³²;
2. Выполняются 8 раундов прямого перемешивания (без участия ключа шифрования);
3. Выполняются 8 раундов прямого криптопреобразования;
4. Выполняются 8 раундов обратного криптопреобразования. Этапы 3 и 4 называются «криптографическим ядром» алгоритма MARS;
5. Выполняются 8 раундов обратного перемешивания, также без участия ключа шифрования;
6. Финальное наложение фрагментов расширенного ключа k₃₆…k₃₉ операцией вычитания по модулю 2³².

Прямое перемешивание

В раунде прямого перемешивания выполняются следующие действия:

1. Значение субблока A прогоняется через таблицу замен S₀ и накладывается на субблок B операцией XOR;
2. Исходное значение субблока A вращается на 8 бит вправо;
3. Результат предыдущего шага обрабатывается таблицей замен S₁ и снова накладывается на субблок B операцией сложения по модулю 2³²;
4. Результат шага 2 вращается на 8 бит вправо;
5. Результат предыдущего шага обрабатывается таблицей замен S₀ и накладывается на субблок С операцией сложения по модулю 2³²;
6. Результат шага 4 вращается на 8 бит вправо;
7. Результат предыдущего шага обрабатывается таблицей замен S₁ и накладывается на субблок D операцией XOR;
8. Субблоки меняются местами.

Кроме того, в некоторых раундах прямого перемешивания выполняются следующие дополнительные операции:

1. В раундах 0 и 4 после шага 7 выполняется наложение значения субблока D на субблок A операцией сложения по модулю 2³²;
2. В раундах 1 и 5 субблок B аналогичным образом накладывается на субблок A.

По словам авторов алгоритма, эти операции существенно усиливают алгоритм MARS против дифференциального криптоанализа.

Прямое криптопреобразование

Основой раунда прямого криптопреобразования является расширяющее криптопреобразование E, преобразующее 32-битное входное слово A в три выходных 32-битных значения, каждое из которых определенным образом накладывается на остальные субблоки. После этого субблок A вращается влево на 13 бит, затем субблоки меняются местами аналогично раунду прямого перемешивания.

Из входного значения формируются три потока O₁…O₃, над которыми производятся следующие действия:

O₂ = I

O₃ = O₂ <<< 13

O₂ = O₂ + k_2r+4 mod 2³²

O₃ = O₃ * k_2r+5 mod 2³²

O₃ = O₃ <<< 5

O₁ = S(O₂)

O₁ = O₁ Å O₃

O₂ = O₂ <<< O₃^'

O₃ = O₃ <<< 5

O₁ = O₁ Å O₃

O₁ = O₁ <<< O₃^'

где I — входное значение, r — номер текущего раунда, считая с 0-го (при нумерации раундов в данном случае учитываются только раунды криптоядра алгоритма), S — табличная замена для операции E, представляет собой объединение таблиц S₀ и S₁; объединенная таблица содержит 512 значений, выходное значение выбирается по значению 9 младших бит входного слова.

Стоит обратить внимание на то, что в преобразовании E используются операции вращения на переменное число бит; в этом случае запись O₃^' обозначает, что число бит вращения определяется значением младших пяти бит текущего значения O₃.

Обратное криптопреобразование

Структуру обратного криптораунда от прямого отличает лишь измененный порядок наложения выходных значений преобразования E O₁…O₃ на слова B, C и D.

Обратное перемешивание

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

1. Значение субблока A прогоняется через таблицу замен S₁ и накладывается на субблок B операцией XOR;
2. Исходное значение субблока A вращается на 8 бит влево;
3. Результат предыдущего шага обрабатывается таблицей замен S₀ и накладывается на субблок C операцией вычитания по модулю 2³²;
4. Результат шага 2 вращается на 8 бит влево;
5. Результат предыдущего шага обрабатывается таблицей замен S₁ и накладывается на субблок D операцией вычитания по модулю 2³²;
6. Результат шага 4 вращается на 8 бит влево;
7. Результат предыдущего шага обрабатывается таблицей замен S₀ и накладывается на субблок D операцией XOR;
8. Субблоки меняются местами.

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

1. В раундах 1 и 5 после шага 7 выполняется наложение значения субблока A на субблок B операцией вычитания по модулю 2³²;
2. В раундах 2 и 6 субблок C аналогичным образом накладывается на субблок B.

Примечания

Ссылки

• Спецификация алгоритма
• Исходные тексты MARS-1248 на языке C