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\ vertc3)}$

(Де ${\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 і т. д.)
3. # Масив T [] перетвориться за наступним правилом: ${\displaystyle i=0\ldots 14,T[i]=T[i]\oplus ((T[i-7\mod 15]\oplus T[i-2\mod 15])\ lll3)\oplus (4i+j)}$
4. # Далі ми перемішуємо масив ${\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}$
5. # Далі беремо десять слів з масиву T [] і вставляємо їх як наступних десяти слів в масив K [] ще раз перемішавши: ${\displaystyle K[10j+i]=T[4i\mod 15];i=0,1\ldots 9}$
6. Остаточно, ми пробігаємо по шістнадцяти словами, використовуваними для перемножування (K [5], K [7] … K [35]) і модифікуємо їх для того, щоб вони відповідали двом властивостям, описаним вище.
7. # Записуємо два молодших біта K [i], за формулою ${\displaystyle j=K[i]\land 3}$, а потім записуємо замість цих двох біт одиниці, ${\displaystyle w=K[i]\lor 3}$.
8. # Збираємо маску 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 будуть повторені в слові і разів). Тоді маска M буде виглядати наступним чином: ${\displaystyle 0^{3}1^{25}0^{4}}$. А значить ми скидаємо біти в 4, 15, 16, 28 позиціях, тобто ${\displaystyle M=0^{4}1^{11}001^{10}0^{5}}$
9. # Далі, для виправлення, ми використовуємо таблицю з чотирьох слів 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]).}$
10. # Остаточно, робиться XOR шаблону p на вихідне слово, при обліку маски М: ${\displaystyle K[i]=w\oplus (p\land M)}$. Варто зауважити, то що 2 молодших біта М є 0, то два молодших біта підсумкового слова будуть одиницями, а використання таблиці B дозволяє гарантувати, що в слові не буде 10 поспіль йдуть 0 або 1