WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте
MARS
Создатель Кэролин Барвик, Дон Копперсмит
Создан 1998 г.
Опубликован 1998 г.
Размер ключа 128—448 бит
Размер блока 128 бит
Число раундов 32
Тип Сеть Фейстеля

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

В разработке шифра принял участие Дон Копперсмит, один из авторов шифра Lucifer (DES), известный рядом статей по криптологии: улучшение структуры S-блоков против дифференциального криптоанализа, метод быстрого перемножения матриц(алгоритм Копперсмита — Винограда), криптоанализ RSA. Кроме него в разработке алгоритма приняли участие: Кэролин Барвик, Эдвард Д’Эвиньон, Росарио Женаро, Шай Халеви, Чаранжит Джутла, Стивен M. Матьяс Мл., Люк О'Коннор, Мохамед Перьевян, Дэвид Саффорд, Невенко Зунич.

По правилам конкурса AES, участники могли вносить незначительные изменения в свои алгоритмы. Воспользовавшись этим правилом, авторы MARSa изменили процедуру расширения ключа, что позволило снизить требования к энергонезависимой и оперативной памяти. Ниже будет предоставлена модифицированная версия алгоритма.

По результатам конкурса AES, MARS вышел в финал, но уступил Rijndael. После объявления результатов (19 Мая 2000 года) группа разработчиков составила своё собственное мнение о конкурсе AES[1], где дала комментарии на претензии к своему детищу.

Сейчас MARS распространяется по всему миру под лицензией Royalty-free.

Краткое описание алгоритма

MARS является блочно-симметричным шифром с секретным ключом. Размер блока при шифровании 128 бита, размер ключа может варьироваться от 128 до 448 бит включительно (кратные 32 битам). Создатели стремились совместить в своём алгоритме быстроту кодирования и стойкость шифра. В результате получился один из самых криптостойких алгоритмов, участвовавших в конкурсе AES.

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

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

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

Авторы шифра исходили из следующих предположений:

  1. Выбор операций. MARS был спроектирован для использования на самых современных компьютерах того времени. Для достижения лучших защитных характеристик в него были включены самые «сильные операции» поддерживаемые в них. Это позволило добиться большего отношения securityper-instruction для различных реализации шифра.
  2. Структура шифра. Двадцатилетний опыт работы в области криптографии подтолкнул создателей алгоритма к мысли, что каждый раунд шифрования играет свою роль в обеспечении безопасности шифра. В частности, мы можем видеть, что первый и последний раунды обычно сильно отличаются от промежуточных(«центральных») раундов алгоритма в плане защиты от криптоаналитических атак. Таким образом, при создании MARSa использовалась смешанная структура, где первый и последний раунды шифрования существенно отличаются от промежуточных.
  3. Анализ. Скорее всего, алгоритм с гетерогенной структурой будет лучше противостоять криптоаналитическим методам будущего, чем алгоритм, все раунды которого идентичны. Разработчики алгоритма MARS придали ему сильно гетерогенную структуру — раунды алгоритма весьма различаются между собой.

В шифре MARS использовались следующие методы шифрования:

  1. Работа с 32-битными словами. Все операции применяются к 32-битным словам. то есть вся исходная информация разбивается на блоки по 32 бита. (если же блок оказывался меньшей длины, то он дополнялся до 32 бит)
  2. Сеть Фейстеля. Создатели шифра считали, что это лучший вариант совмещения скорости шифрования и криптостойкости. В MARS использована сеть Фейстеля 3-го типа.
  3. Симметричность алгоритма. Для стойкости шифра к различным атакам все его раунды были сделаны полностью симметричными, то есть вторая часть раунда есть зеркальное повторение первой его части.

Структуру алгоритма MARS можно описать следующим образом:

  1. Предварительное наложение ключа: на 32-битные субблоки A, B, C, D накладываются 4 фрагмента расширенного ключа k0…k3 операцией сложения по модулю 232;
  2. Выполняются 8 раундов прямого перемешивания (без участия ключа шифрования);
  3. Выполняются 8 раундов прямого криптопреобразования;
  4. Выполняются 8 раундов обратного криптопреобразования;[2]
  5. Выполняются 8 раундов обратного перемешивания, также без участия ключа шифрования;
  6. Финальное наложение фрагментов расширенного ключа k36…k39 операцией вычитания по модулю 232.

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

В первой фазе на каждое слово данных накладывается слово ключа, а затем происходит восемь раундов смешивания согласно сети Фейстеля третьего типа совместно с некоторыми дополнительными смешиваниями. В каждом раунде мы используем одно слово данных (называемое, исходным словом) для модификации трёх других слов(называемые, целевыми словами). Мы рассматриваем четыре байта исходного слова в качестве индексов на двух S-блоков, S0 и S1, каждый, состоящий из 256 32-разрядных слов, а далее проводим операции XOR или добавления данных соответствующего S-блока в три других слова.

Если четыре байта исходного слова b0, b1, b2, b3 (где b0 является первым байтом, а b3 является старшим байтом), то мы используем b0, b2, как индексы в блока S0 и байты b1, b3, как индексы в S-блоке S1. Сначала сделаем XOR S0 к первому целевому слову, а затем прибавим S1 к тому же слову. Мы также добавляем S0 ко второму целевому слову и XOR блока-S1 к третьему целевому слову. В заключении, мы вращаем исходное слово на 24 бита вправо.

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

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

Псевдокод

1. // Первое наложение ключа на данные
2. 

3. 

4. // Затем 8 раундов прямого перемешивания
5. 
  // используем D[0] для модифицирования D[1]; D[2]; D[3]
6. // обращаемся к 4-ем S-блокам
7.

8.

9.

10.

11. // и вращаем исходное слово вправо
12.

13. // также проделаем дополнительные операции смешивания
14. 

15.     
 // добавим D[3] к исходному слову
16. 

17.     
 // добавим D[1] к исходному слову
18. // вращаем массив D[ ]
19.

20.

Криптографическое ядро

Криптографическое ядро MARS — сеть Фейстеля 3-го типа, содержащая в себе 16 раундов. В каждом раунде мы используем ключевую Е-функцию, которая является комбинацией умножений, вращений, а также обращений к S-блокам. Функция принимает на вход одно слово данных, а возвращает три слова, с которыми впоследствии будет осуществлена операция сложения или XOR к другим трем словам данным. В дополнении исходное слово вращается на 13 бит влево.

Для обеспечения, серьёзного сопротивления к криптоатакам, три выходных значения Е-функции(O1, O2, O3) используются в первых восьми раундах и в последних восьми раундах в разных порядках. В первые восемь раундов мы добавляем O1 и O2 к первому и второму целевому слову, соответственно, и XOR O3 к третьему целевому слову. За последние восемь раундов, мы добавляем O1 и O2 к третьему и второму целевому слову, соответственно, и XOR O3 к первому целевому слову.

Псевдокод

1. // Проделаем 16 раундов шифрования при использовании ключа
2.

3.

4.

5.

6.
 // сначала 8 раундов прямого преобразования
7.     

8.     

9.
 // потом 8 раундов обратного преобразования
10.    

11.    

12.

13. // вращаем массив D[ ]
14.

15.

Е-функция

E-функция принимает в качестве входных данных одно слово данных и использует ещё два ключевых слов, производя на выходе три слова. В этой функции мы используем три временные переменные, обозначаемые L, M и R (для левой, средней и правой).

Изначально мы устанавливаем в R значение исходного слова смещенного на 13 бит влево, а в M — сумма исходных слов и первого ключевого слова. Затем мы используем первые девять битов M как индекс к одной из 512 S-блоков (которое получается совмещением S0 и S1 смешиванием фазы), и сохраняем в L значение соответствующего S-блока.

Затем умножим второе ключевое слово на R, сохранив значение в R. Затем вращаем R на 5 позиций влево (так, 5 старших битов становятся 5 нижними битами R после вращения). Тогда мы делаем XOR R в L, а также просматриваем пять нижних бит R для определения величины сдвига (от 0 до 31), и вращаем M влево на эту величину. Далее мы вращаем R ещё на 5 позиций влево и делаем XOR в L. В заключении, мы вновь смотрим на 5 младших битов R, как на величину вращения и вращаем L на эту величину влево. Таким образом результат работы E-функции — 3 слова (по порядку): L, M, R.

Псевдокод
1. // используем 3 временные переменные L; M; R
2.
 //добавляем первое ключевое слово
3.
 // умножаем на второе ключевое слово, которое должно быть четным
4.

5.
 // взятие S-блока
6.

7.
 // эти биты описывают величину последующего вращения
8.
 // первое вращение на переменную величину
9.

10.

11.

12.
 // эти биты описывают величину последующего вращения
13.
 // второе вращение на переменную величину
14.

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

Обратное перемешивание практически совпадает с прямым перемешиванием, за исключением того факта, что данные обрабатываются в обратном порядке. То есть, если бы мы совместили прямое и обратное перемешивание так, чтобы их выходы и входы были бы соединены в обратном порядке (D[0] прямого и D[3] обратного, D[1] прямого и D[2] обратного), то не увидели бы результата перемешивания. Как и в прямом смешивание, здесь мы тоже используем одно исходное слово и три целевых. Рассмотрим четыре первых байта исходного слова: b0, b1, b2, b3. Будем использовать b0, b2 как индекс к S-блоку — S1, а b1b3 для S0. Сделаем XOR S1[b0] в первое целевое слово, вычтем S0[b3] из второго слова, вычтем S1[b2] из третьего целевого слов и затем проделаем XOR S0[b1] также к третьему целевому слову. Наконец, мы поворачиваем исходное слово на 24 позиций влево. Для следующего раунда мы вращаем имеющиеся слова так, чтобы нынешнее первое целевое слово стало следующим исходным словом, текущее второе целевое слово стало первым целевым словом, текущее третье целевое слово стало вторым целевым словом, и текущее исходное слово стало третьим целевым словом. Кроме того, перед одним из четырёх «особенных» раундов мы вычитаем одно из целевых слов из исходного слова: перед четвёртым и восьмым раундами мы вычитаем первое целевое слово, перед третьем и седьмым раундами мы вычтем третье целевое слово из исходного.

Псевдокод

1. // Проводим 8 раундов обратного перемешивания
2.

3. // дополнительные операции смешивания
4. 

5.      
 //вычитаем D[3] из исходного слова
6. 

7.     
 // вычитаем D[1] из исходного слова
8. // обращаемся к четырём элементам S-блоков
9.

10.

11.

12.

13. // и вращаем исходное слово влево
14.

15. // вращаем массив D[]
16.

17.

18. // Вычитаем ключевое слово
19.

20.

Дешифрование

Процесс декодирования обратен процессу кодирования. Код дешифрования похож (но не идентичен) на код шифрования.

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

1. // Начальное наложение ключа 
2.

3.

4. // Затем проводим 8 раундов прямого перемешивания
5.

6. // вращаем массив D[]
7.

8. // и вращаем исходное слово вправо
9.

10. // обращаемся к 4-ем элементам S-блоков
11.

12.

13.

14.

15. // дополнительное смешивание
16.

17.      
 // добавляем D[3] к исходному слову
18.

29.      
 // добавляем D[1] к исходному слову
20.

Криптографическое ядро

1. // Проведем 16 раундов при использование наложения ключа
2.

3. // вращаем массив D[]
4.

5.

6.

7.

8.
 // последние 8 раундов в прямом порядке
9.      

10.     

11.
 // первые 8 раундов в обратном порядке
12.     

13.     

14.

15.


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

1. // Проводим 8 раундов обратного перемешивания
2. 

3. // Вращаем массив D[]
4.

5. // дополнительные операции переммешивания
6.

7.      
 // вычитаем D[3] из исходного слова
8.

9.      
 // вычитаем D[1] из исходного слова
10. // вращаем исходное слово влево
11.

12. // обращаемся к четырём элементами S-блоков
13.

14.

15.

16.

17.

18. // вычитание подключа из данных
19.

20.

Особенности алгоритма

S-блоки

При создании S-блока S, его элементы генерировались псевдослучайным генератором, после чего тестировались на различные линейные и диффиренциальные свойства. Псевдослучайные S-блоки были сгенерированы при следующих параметрах:

(где  — есть j-ое слово на выходе SHA-1) Здесь считается, что i — 32-битное без знаковое, целое число, а c1, c2, c3 есть некоторые константы. В реализации IBM: c1 = 0xb7e15162; c2 = 0x243f6a88 (которые являются двоичной записью дробной части и соответственно). c3 изменялось пока не были подобраны S-блоки с подходящими свойствами. SHA-1 работает над потоками данных и использует прямой порядок байт.

Свойства S-блоков

Дифференциальные свойства.

  1. S-блок не должен содержать слова, состоящие все 0 или 1
  2. Каждые два S-блока S0, S1 должны отличаться друг от друга как минимум в 3 из 4 байтах.(так как выполнение этого условия для псевдослучайных S-блоков крайне маловероятно, то один из двух S-блоков модифицируется)
  3. S-блок не содержит двух элементов таких, что или
  4. В S-блоке не существует двух пар элементов xor-отличия которых равны и двух пар элементов упорядоченная разность которых равна
  5. Каждые два элемента S-блока должны отличаться хотя бы 4 битами
Требование №4 не выполнялось в реализации IBM для AES, но было поправлено сразу после финала.
Было замечено, что в S-блоках присутствуют следующие элементы, противоречащие этому требованию[3]:
XORВычитание

Линейные свойства

  1. Соотношение смещения: . Необходимо, чтобы это выражение было больше хотя бы
  2. Однобитовое смещение: Необходимо, чтобы это выражение было больше хотя бы
  3. Двухбитовое смещение: . Необходимо, чтобы это выражение было больше хотя бы
  4. Однобитовая корреляция: . Необходимо минимизировать это выражение среди всех возможных S-блоков, которые удовлетворяют предыдущим пунктам

Расширение ключа

процедура расширения ключа расширяет заданный массив ключей k[], состоящий из n 32-битных слов (где n целое число от 4 до 14) в массив K[] из 40 элементов. Исходный ключ не должен придерживаться какой-либо структуры. В дополнение, процедура расширения ключа гарантирует следующие свойства ключевого слова, используемого при перемножении в криптографическом ядре алгоритма:

  1. два младших бита ключевого слова будут всегда единицами
  2. ни одно из ключевых слов не будет содержать десять подряд идущих 0 или 1

Опишем алгоритм расширения ключа.

  1. Сначала массив полностью переписывается в промежуточный массив , состоящий из 15 элементов.
  2. Далее данный процесс повторяется 4 раза. На каждой итерации генерируются 10 слов расширенного ключа. переменная отображающая текущий номер итерации.(для первой итерации 0, для второй 1 и т. д.)
    1. Массив T[] преобразуется по следующему правилу:
    2. Далее мы перемешиваем массив при помощи 4 раундов Сети Фейстеля 1-го типа. Повторяем четыре раза следующую операцию:
    3. Далее берем десять слов из массива T[] и вставляем их в качестве следующих десяти слов в массив K[] ещё раз перемешав:
  3. Окончательно, мы пробегаемся по шестнадцати словам, используемыми для перемножения(K[5],K[7]…K[35]) и модифицируем их для того, чтобы они соответствовали двум свойствам, описанным выше.
    1. Записываем два младших бита K[i], по формуле , а затем записываем вместо этих двух бит единицы, .
    2. Собираем маску M для битов w, которые принадлежат последовательностям из десяти и более нулей или единиц. К примеру, , тогда и только тогда, когда принадлежит последовательности из 10 или более одинаковых элементов. Тогда мы сбрасываем (выставляем их в 0) значения тех единиц M, которые находятся в концах нулевых или единичных последовательностей, а также тех единиц, которые находятся в старшем и младшем битах. К примеру, пусть наше слово выглядит так: (выражение или же обозначает, что 0 или 1 будут повторены в слове i раз). Тогда маска M будет выглядеть следующим образом: . А значит мы сбрасываем биты в 4, 15, 16, 28 позициях, то есть
    3. Далее, для исправления, мы используем таблицу из четырёх слов B[]. Все элементы таблицы B подобраны так, что для них и для всех их цикличных сдвигов выполняется свойство, что в них нет семи подряд идущих 0 или 1. В реализации IBM использовалась таблица . Далее используются два записанных бита j для выбора слова из таблицы B, и используются младшие пять бит слова K[i-1] для вращения его элементов,
    4. Окончательно, делается XOR шаблона p на исходное слово, при учете маски М: . Стоит заметить, то что 2 младших бита М являются 0, то два младших бита итогового слова будут единицами, а использование таблицы B позволяет гарантировать, что в слове не будет 10 подряд идущих 0 или 1

Преимущества и недостатки алгоритма

Шифр был кандидатом AES, после небольших изменений в ходе первого раунда конкурса, связанных с изменением процедуры расширения ключа, MARS успешно прошёл в финал.

В финале конкурса у MARS был выделен целый ряд недостатков:

  1. Сложная структура. Сложная гетерогенная структура алгоритма затрудняла не только его анализ, но и реализацию.
  2. Реализация. Возникали проблемы при реализации шифра на платформах, которые не поддерживали операции 32-битного умножения и вращения на произвольное число бит.
  3. Ограниченность ресурсов. Невозможность аппаратно реализовать алгоритм при малых ресурсах оперативной или же энергонезависимой памяти.
  4. Защита. MARS оказался плохо защищен от атак по времени выполнения и потребляемой мощности.
  5. Расширение ключа. MARS хуже других финалистов AES поддерживал расширение ключа «на лету».
  6. Распараллеливаемость. Можно распараллелить лишь небольшую часть алгоритма.

На все эти недостатки экспертная комиссия выделила одно крупное достоинство данного алгоритма — его симметричность. Исходя из выделенных недостатков, MARS ожидаемо не стал победителем AES.

Ответ аналитикам AES

После оглашения результатов конкурса AES, группа создателей MARS выпустила свою рецензию на весь конкурс. В ней были поставлены под сомнение критерии оценки конкурса. Они считали, что главной характеристикой шифра должна быть именно надёжность и его стойкость (к примеру, к brute-force атакам) Кроме того они ответили на каждую претензию со стороны жюри к своему алгоритму.

1. MARS не подходит для аппаратной реализации Среди претензий к шифру были его трудная аппаратная реализация, которая могла повлечь за собой утяжеление работы Интернета, а также внедрение больших, по своим размерам, схем.

Разработчики утверждают, что их реализация способна работать со скоростью 1,28Гбит/сек, что является приемлемым для интернета, а стоимость их чипов может быть и высокая (13$ за 12Гбит/сек чип или 1$ за 1Гбит/сек чип), но в будущем их цена значительно упадет.

2. MARS не подходит для реализации на устройствах с малой памятью Для реализации на SMART картах есть у алгоритмов есть всего 128 байт памяти. Для процедуры расширения ключа MARS требует 512 байт.

Разработчики считают, что нет причины, по которой нужно реализовывать AES на таком уязвимом ресурсе с малой памятью, как смарт-карты, так как все эти ресурсы можно просто и быстро переделать их на системы с открытым ключом.

3. MARS не подходит для реализации на ППВМ MARS не подходит для реализации на платформах, где не разрешено вращение(зависящих от сторонних факторов).

Разработчики отмечают, что эта проблема не является фатальной, а требует немного времени, для адаптации алгоритма к этой платформе

4. Расширение ключа MARS является очень тяжёлой операцией

Разработчики утверждают, что это смешное утверждение. Они утверждают, что у них соблюдена «идеальная» пропорция между дополнительной памятью на ключ и пропускной способностью(25 байт на ключ)

В заключении разработчики приводят свой анализ алгоритмов участников AES,по результатам которого MARS, наряду с Serpent, являлся лучшим кандидатом на звание AES.[1]

Анализ безопасности алгоритма

В настоящее время нет эффективных атак на данный алгоритм. Хотя у него есть несколько слабых сторон[1]:

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

Литература

Примечания

  1. 1 2 3 Cryptography Research
  2. ↑ Этапы 3 и 4 называются «криптографическим ядром» алгоритма MARS
  3. ↑ Cryptography Research

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .



Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

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

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии