Блочный алгоритм MARS

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

14.

15.

Е-функция

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

     Изначально  мы устанавливаем в R значение исходного  слова смещенного на 13 бит влево, а в M — сумма исходных слов и  первого ключевого слова. Затем  мы используем первые девять битов M как индекс к одной из 512 S-блоков (которое получается совмещением S₀ и S₁ смешиванием фазы), и сохраняем в 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] обратного), то не увидели бы результата перемешивания. Как и в прямом смешивание, здесь мы тоже используем одно исходное слово и три целевых. Рассмотрим четыре первых байта исходного слова: b₀, b₁, b₂, b₃. Будем использовать b₀, b₂ как индекс к S-блоку — S₁, а b₁ b₃ для S₀. Сделаем XOR S₁ [b0] в первое целевое слово, вычтем S₀[b₃] из второго слова, вычтем S₁ [b₂] из третьего целевого слов и затем проделаем XOR S₀[b₁] также к третьему целевому слову. Наконец, мы поворачиваем исходное слово на 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.  
 
 

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

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

     i=0…102; j=0…4,S[5i+j]=SHA-1(5i|c1|c2|c3)

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

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

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

1. S-блок не должен содержать слова, состоящие все 0 или 1.
2. Каждые два S-блока S₀, S₁должны отличаться друг от друга как минимум в 3 из 4 байтах.(так как выполнение этого условия для псевдослучайных S-блоков крайне маловероятно, то один из двух S-блоков модифицируется).
3. S-блок не содержит двух элементов S[ i ], S [j ] ( i≠j )  таких, что S[ i ]=S[ j ];           S[ i ]= - S[ j ] или S[ i ]= -S[ j ].
4. В S-блоке не существует двух пар элементов xor-отличия которых равны и двух пар элементов упорядоченная разность которых равна.
5. Каждые два элемента S-блока должны отличаться хотя бы 4 битами.

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

1. Соотношение смещения:

            Необходимо, чтобы это выражение было больше хотя бы

2. Однобитовое смещение:

      Необходимо, чтобы это выражение было больше хотя бы

3. Двухбитовое смещение:

      Необходимо, чтобы это выражение было больше хотя бы

4. Однобитовая корреляция:

            Необходимо минимизировать это выражение среди всех возможных S-блоков,                   

            которые удовлетворяют предыдущим пунктам 

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

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

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

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

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

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

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

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

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