MARS

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

У Вікіпедії є статті про інші значення цього терміна: Марс (значення).

MARS

Розробники	Керолін Барвік, Дон Копперсміт (IBM)
Уперше оприлюднений	1998 р.
Раундів	32
Тип	Мережа Фейстеля

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

За правилами конкурсу AES, учасники могли вносити незначні зміни у свої алгоритми. Скориставшись цим правилом, автори MARSa змінили процедуру розширення ключа, що дозволило знизити вимоги до енергонезалежної і оперативної пам'яті. Нижче буде надана модифікована версія алгоритму.

За результатами конкурсу AES, MARS вийшов у фінал, але поступився Rijndael. Після оголошення результатів (19 травня 2000 року) група розробників склала свою власну думку про конкурс AES^[1], де дала коментарі на претензії до свого дітища.

Зараз MARS поширюється по всьому світу під Royalty Free ліцензією.

Короткий опис алгоритму

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

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

• Найпростіші операції (додавання, віднімання, виключаюче або)
• Підстановки з використанням таблиці замін
• Фіксований циклічний зсув
• Залежний від даних циклічний зсув
• Множення по модулю 2 ³²
• Ключове забілювання

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

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

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

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 фрагмента розширеного ключа k ₀ … k ₃ операцією складання по модулю 2 ³² ;
2. Виконуються 8 раундів прямого перемішування (без участі ключа шифрування);
3. Виконуються 8 раундів прямого криптоперетворення;
4. Виконуються 8 раундів зворотного криптоперетворення;^[2]
5. Виконуються 8 раундів зворотного перемішування, також без участі ключа шифрування;
6. Фінальне накладення фрагментів розширеного ключа k ₃₆ … k ₃₉ операцією віднімання по модулю 2 ³² .

Пряме перемішування

У першій фазі на кожне слово даних накладається слово ключа, а потім відбувається вісім раундів змішування згідно з мережею Фейстеля третього типу спільно з деякими додатковими змішування. У кожному раунді ми використовуємо одне слово даних (зване, вихідним словом) для модифікації трьох інших слів (звані, цільовими словами). Ми розглядаємо чотири байта вихідного слова як індексів на двох 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, його елементи генерувалися псевдовипадкових генератором, після чого тестувалися на різні лінійні і діффіренціальние властивості. Псевдовипадкові 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 працює над потоками даних і використовує прямий порядок байт.

Властивості S-блоків

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

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

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

Шифр був кандидатом 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. Cryptography Research (PDF). Архів оригіналу (PDF) за 16 травня 2006. Процитовано 17 червня 2012.
2. Етапи 3 і 4 називаються «криптографічним ядром» алгоритму MARS
3. Cryptography Research. Архів оригіналу за 23 травня 2009. Процитовано 17 червня 2012.

Посилання

• Специфікація алгоритму (AES версія) [Архівовано 19 листопада 2011 у Wayback Machine.]
• Вихідні тексти MARS-1248 на мові C
• Офіційна сторінка шифру
• Опис проблеми згенерованих S-блоків [Архівовано 23 травня 2009 у Wayback Machine.]
• Коментарі творців шифру [Архівовано 16 травня 2006 у Wayback Machine.]