MARS (криптография)

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

Если четыре байта исходного слова b₀, b₁, b₂, b₃ (где b₀ является первым байтом, а b₃ является старшим байтом), то мы используем b₀, b₂, как индексы в блока S₀ и байты b₁, b₃, как индексы в S-блоке S₁. Сначала сделаем XOR S₀ к первому целевому слову, а затем прибавим S₁ к тому же слову. Мы также добавляем S₀ ко второму целевому слову и XOR блока-S₁ к третьему целевому слову. В заключении, мы вращаем исходное слово на 24 бита вправо.

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

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

1. // Первое наложение ключа на данные
2. ${\displaystyle for~i~=~0~to~3~do}$
3. ${\displaystyle D\left[i\right]=D[i]+K[i]}$
4. // Затем 8 раундов прямого перемешивания
5. ${\displaystyle for~i=~0~to~7~do}$  // используем D[0] для модифицирования D[1]; D[2]; D[3]
6. // обращаемся к 4-ем S-блокам
7.${\displaystyle D\left[1\right]=D[1]\oplus S0[~low~byte~of~D[0]]}$
8.${\displaystyle D\left[1\right]=D[1]+S1[~2nd~byte~of~D[0]]}$
9.${\displaystyle D\left[2\right]=D[2]+S0[~3rd~byte~of~D[0]]}$
10.${\displaystyle D[3]=D[3]\oplus S1[~high~byte~of~D[0]]}$
11. // и вращаем исходное слово вправо
12.${\displaystyle D[0]=D[0]\ggg 24}$
13. // также проделаем дополнительные операции смешивания
14. ${\displaystyle if~i~=~0~or~4~then}$
15.     ${\displaystyle D\left[0\right]=D[0]+D[3]}$ // добавим D[3] к исходному слову
16. ${\displaystyle if~i~=~1~or~5~then}$
17.     ${\displaystyle D\left[0\right]=D[0]+D[1]}$ // добавим D[1] к исходному слову
18. // вращаем массив D[ ]
19.${\displaystyle (D[3];D[2];D[1];D[0])\leftarrow (D[0];D[3];D[2];D[1])}$
20.${\displaystyle end-for}$

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

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

1. // Проделаем 16 раундов шифрования при использовании ключа
2.${\displaystyle for~i~=~0~to~15~do}$
3.${\displaystyle (out1;~out2;~out3)~=~E-function(D[0];~K[2i+4];~K[2i+5])}$
4.${\displaystyle D[0]=D[0]\lll 13}$
5.${\displaystyle D[2]=D\left[2\right]+out2}$
6.${\displaystyle if~i~<~8~then}$ // сначала 8 раундов прямого преобразования
7.     ${\displaystyle D[1]=D\left[1\right]+out1}$
8.     ${\displaystyle D[3]=D[3]\oplus out3}$
9.${\displaystyle else}$ // потом 8 раундов обратного преобразования
10.    ${\displaystyle D[3]=D\left[3\right]+out1}$
11.    ${\displaystyle D[1]=D[1]\oplus out3}$
12.${\displaystyle end-if}$
13. // вращаем массив D[ ]
14.${\displaystyle (D[3];~D[2];~D[1];~D[0])\leftarrow (D[0];~D[3];~D[2];~D[1])}$
15.${\displaystyle end-for}$

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.${\displaystyle M=~in+~key1}$ //добавляем первое ключевое слово
3.${\displaystyle R=(in\lll 13)\otimes key2}$ // умножаем на второе ключевое слово, которое должно быть четным
4.${\displaystyle i=~lowest~9~bits~of~M}$
5.${\displaystyle L=S\left[i\right]}$ // взятие S-блока
6.${\displaystyle R=R\lll 5}$
7.${\displaystyle r=~lowest~5~bits~of~R}$ // эти биты описывают величину последующего вращения
8.${\displaystyle M=M\lll r}$ // первое вращение на переменную величину
9.${\displaystyle L=L\oplus R}$
10.${\displaystyle R=R\lll 5}$
11.${\displaystyle L=L\oplus R}$
12.${\displaystyle r=~lowest~5~bits~of~R}$ // эти биты описывают величину последующего вращения
13.${\displaystyle L=L\lll r}$ // второе вращение на переменную величину
14.${\displaystyle output(L;~M;~R)}$

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

1. // Проводим 8 раундов обратного перемешивания
2.${\displaystyle for~i~=~0~to~7~do}$
3. // дополнительные операции смешивания
4. ${\displaystyle if~i~=~2~or~6~then}$
5.      ${\displaystyle D[0]=D[0]-~D[3]}$ //вычитаем D[3] из исходного слова
6. ${\displaystyle if~i~=~3~or~7~then}$
7.     ${\displaystyle D[0]=D[0]-~D[1]}$ // вычитаем D[1] из исходного слова
8. // обращаемся к четырём элементам S-блоков
9.${\displaystyle D[1]=D[1]\oplus S1[~low~byte~of~D[0]]}$
10.${\displaystyle D[2]=D[2]-~S0[~high~byte~of~D[0]]}$
11.${\displaystyle D[3]=D[3]\oplus S1[~3rd~byte~of~D[0]]}$
12.${\displaystyle D[3]=D[3]-~S0[~2nd~byte~of~D[0]]}$
13. // и вращаем исходное слово влево
14.${\displaystyle D[0]=D[0]\lll 24}$
15. // вращаем массив D[]
16.${\displaystyle (D[3];D[2];D[1];D[0])\leftarrow (D[0];D[3];D[2];D[1])}$
17.${\displaystyle end-for}$
18. // Вычитаем ключевое слово
19.${\displaystyle for~i~=~0~to~3~do}$
20.        ${\displaystyle D[i]=D[i]-~K[36+i]}$

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

1. // Начальное наложение ключа 
2.${\displaystyle for~i~=~0~to~3~do}$
3.${\displaystyle D\left[i\right]=D[i]+K[36+i]}$
4. // Затем проводим 8 раундов прямого перемешивания
5.${\displaystyle for~i~=~7~down~to~0~do}$
6. // вращаем массив D[]
7.${\displaystyle (D[3];~D[2];~D[1];~D[0])\leftarrow (D[2];~D[1];~D[0];~D[3])}$
8. // и вращаем исходное слово вправо
9.${\displaystyle D[0]=D[0]\ggg 24}$
10. // обращаемся к 4-ем элементам S-блоков
11.${\displaystyle D[3]=D[3]\oplus S0[~2nd~byte~of~D[0]]}$
12.${\displaystyle D[3]=D[3]+S1[~3rd~byte~of~D[0]]}$
13.${\displaystyle D[2]=D[2]+S0[~high~byte~of~D[0]]}$
14.${\displaystyle D[1]=D[1]\oplus S1[~low~byte~of~D[0]]}$
15. // дополнительное смешивание
16.${\displaystyle if~i~=~2~or~6~then}$
17.      ${\displaystyle D[0]=D\left[0\right]+D[3]}$ // добавляем D[3] к исходному слову
18.${\displaystyle if~i~=~3~or~7~then}$
29.      ${\displaystyle D[0]=D\left[0\right]+D[1]}$ // добавляем D[1] к исходному слову
20.${\displaystyle end-for}$

1. // Проведем 16 раундов при использование наложения ключа
2.${\displaystyle for~i~=~15~down~to~0~do}$
3. // вращаем массив D[]
4.${\displaystyle (D[3];~D[2];~D[1];~D[0])\leftarrow (D[2];~D[1];~D[0];~D[3])}$
5.${\displaystyle D[0]=D[0]\ggg 13}$
6.${\displaystyle (out1;~out2;~out3)=E-function(D[0];~K[2i+4];~K[2i+5])}$
7.${\displaystyle D[2]=D\left[2\right]-out2}$
8.${\displaystyle if~i~<~8~then}$ // последние 8 раундов в прямом порядке
9.      ${\displaystyle D[1]=D\left[1\right]-out1}$
10.     ${\displaystyle D[3]=D[3]\oplus out3}$
11.${\displaystyle else}$ // первые 8 раундов в обратном порядке
12.     ${\displaystyle D[3]=D\left[3\right]-out1}$
13.     ${\displaystyle D[1]=D[1]\oplus out3}$
14.${\displaystyle end-if}$
15.${\displaystyle end-for}$

1. // Проводим 8 раундов обратного перемешивания
2. ${\displaystyle for~i~=~7~down~to~0~do}$
3. // Вращаем массив D[]
4.${\displaystyle (D[3];~D[2];~D[1];~D[0])\leftarrow (D[2];~D[1];~D[0];~D[3])}$
5. // дополнительные операции переммешивания
6.${\displaystyle if~i~=~0~or~4~then}$
7.      ${\displaystyle D[0]=D\left[0\right]-D[3]}$ // вычитаем D[3] из исходного слова
8.${\displaystyle if~i~=~1~or~5~then}$
9.      ${\displaystyle D[0]=D\left[0\right]-D[1]}$ // вычитаем D[1] из исходного слова
10. // вращаем исходное слово влево
11.${\displaystyle D[0]=D[0]\lll 24}$
12. // обращаемся к четырём элементами S-блоков
13.${\displaystyle D[3]=D[3]\oplus S1[~high~byte~of~D[0]]}$
14.${\displaystyle D[2]=D[2]-S0[~3rd~byte~of~D[0]]}$
15.${\displaystyle D[1]=D[1]-S1[~2nd~byte~of~D[0]]}$
16.${\displaystyle D[1]=D[1]\oplus S0[~low~byte~of~D[0]]}$
17.${\displaystyle end-for}$
18. // вычитание подключа из данных
19.${\displaystyle for~i~=~0~to~3~do}$
20.     ${\displaystyle D[i]=D\left[i\right]-K[i]}$

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

${\displaystyle i=0\ldots 102;j=0\ldots 4,S[5i+j]=\mathrm {SHA-1} (5i\vert c1\vert c2\vert c3)}$

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

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

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

Требование №4 не выполнялось в реализации IBM для AES, но было поправлено сразу после финала.
Было замечено, что в S-блоках присутствуют следующие элементы, противоречащие этому требованию[3]:  

XOR	Вычитание
${\displaystyle S[27]\oplus S[101]=S[292]\oplus S[360]=0x117f1a43}$	${\displaystyle S\left[13\right]-S[138]=S[364]-S[297]=0x75082c89}$
${\displaystyle S[27]\oplus S[292]=S[101]\oplus S[360]=0x2b05b22a}$	${\displaystyle S\left[19\right]-S[168]=S[509]-S[335]=0x0b7fc4bd}$
${\displaystyle S[27]\oplus S[360]=S[101]\oplus S[292]=0x3a7aa869}$	${\displaystyle S\left[49\right]-S[97]=S[142]-S[392]=0x725ca4be}$
	${\displaystyle S\left[131\right]-S[333]=S[348]-S[211]=0xc73689fe}$
	${\displaystyle S\left[13\right]-S[364]=S[138]-S[297]=0x86dedc7c}$
	${\displaystyle S\left[131\right]-S[348]=S[333]-S[211]=0x22492124}$
	${\displaystyle S\left[19\right]-S[509]=S[168]-S[335]=0x9ce0ed93}$
	${\displaystyle S\left[49\right]-S[142]=S[97]-S[392]=0x5d91f03a}$

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

1. Соотношение смещения: ${\displaystyle \left|Pr_{x}[parity(S[x])=0]-1/2\right|}$. Необходимо, чтобы это выражение было больше хотя бы ${\displaystyle 1/32}$
2. Однобитовое смещение: ${\displaystyle \forall j\left|Pr_{x}[S[x]_{j}=0]-1/2\right|}$ Необходимо, чтобы это выражение было больше хотя бы ${\displaystyle 1/30}$
3. Двухбитовое смещение: ${\displaystyle \forall j\left|Pr_{x}[S[x]_{j}\oplus S[x]_{j+1}=0]-1/2\right|}$. Необходимо, чтобы это выражение было больше хотя бы ${\displaystyle 1/30}$
4. Однобитовая корреляция:${\displaystyle \forall i,j\left|Pr_{x}[S[x]_{j}=x_{i}]-1/2\right|}$. Необходимо минимизировать это выражение среди всех возможных S-блоков, которые удовлетворяют предыдущим пунктам

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

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

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

1. Сначала массив ${\displaystyle k[]}$ полностью переписывается в промежуточный массив ${\displaystyle T[]}$, состоящий из 15 элементов. ${\displaystyle T[0\ldots n-1]=k[0\ldots n-1];T[n]=n;T[n+1\ldots 14]=0}$
2. Далее данный процесс повторяется 4 раза. На каждой итерации генерируются 10 слов расширенного ключа. ${\displaystyle j}$ переменная отображающая текущий номер итерации.(для первой итерации 0, для второй 1 и т. д.)
   1. Массив T[] преобразуется по следующему правилу:${\displaystyle i=0\ldots 14,T[i]=T[i]\oplus ((T[i-7\mod 15]\oplus T[i-2\mod 15])\lll 3)\oplus (4i+j)}$
   2. Далее мы перемешиваем массив ${\displaystyle T[]}$ при помощи 4 раундов Сети Фейстеля 1-го типа. Повторяем четыре раза следующую операцию: ${\displaystyle T[i]=(T[i]+S[low~9~bits~of~T[i-1\mod 15]])\lll 9;i=0,1\ldots 14}$
   3. Далее берем десять слов из массива T[] и вставляем их в качестве следующих десяти слов в массив K[] ещё раз перемешав: ${\displaystyle K[10j+i]=T[4i\mod 15];i=0,1\ldots 9}$
3. Окончательно, мы пробегаемся по шестнадцати словам, используемыми для перемножения(K[5],K[7]…K[35]) и модифицируем их для того, чтобы они соответствовали двум свойствам, описанным выше.
   1. Записываем два младших бита K[i], по формуле ${\displaystyle j=K[i]\land 3}$, а затем записываем вместо этих двух бит единицы, ${\displaystyle w=K[i]\lor 3}$.
   2. Собираем маску M для битов w, которые принадлежат последовательностям из десяти и более нулей или единиц. К примеру, ${\displaystyle M_{l}=1}$, тогда и только тогда, когда ${\displaystyle w_{l}}$ принадлежит последовательности из 10 или более одинаковых элементов. Тогда мы сбрасываем (выставляем их в 0) значения тех единиц M, которые находятся в концах нулевых или единичных последовательностей, а также тех единиц, которые находятся в старшем и младшем битах. К примеру, пусть наше слово выглядит так: ${\displaystyle w=0^{3}1^{13}0^{12}1011}$ (выражение ${\displaystyle 0^{i}}$ или же ${\displaystyle 1^{i}}$ обозначает, что 0 или 1 будут повторены в слове i раз). Тогда маска M будет выглядеть следующим образом: ${\displaystyle 0^{3}1^{25}0^{4}}$. А значит мы сбрасываем биты в 4, 15, 16, 28 позициях, то есть ${\displaystyle M=0^{4}1^{11}001^{10}0^{5}}$
   3. Далее, для исправления, мы используем таблицу из четырёх слов B[]. Все элементы таблицы B подобраны так, что для них и для всех их цикличных сдвигов выполняется свойство, что в них нет семи подряд идущих 0 или 1. В реализации IBM использовалась таблица ${\displaystyle B[]=\left\{0xa4a8d57b,0x5b5d193b,0xc8a8309b,0x73f9a978\right\}}$. Далее используются два записанных бита j для выбора слова из таблицы B, и используются младшие пять бит слова K[i-1] для вращения его элементов, ${\displaystyle p=B[j]\lll (lowest~5~bits~of~K[i-1]).}$
   4. Окончательно, делается XOR шаблона p на исходное слово, при учете маски М: ${\displaystyle K[i]=w\oplus (p\land M)}$. Стоит заметить, то что 2 младших бита М являются 0, то два младших бита итогового слова будут единицами, а использование таблицы B позволяет гарантировать, что в слове не будет 10 подряд идущих 0 или 1