MARS — шифр-кандидат в AES, розроблений корпорацією IBM, яка створила у свій час DES. За заявою IBM, в алгоритм MARS вкладено 25-річний криптоаналітичний досвід фірми, і поряд з високою криптографічною стійкістю шифр допускає ефективну реалізацію навіть в таких обмежених рамках, які характерні для смарт-карт.
| Розробники | Керолін Барвік, Дон Копперсміт (IBM) |
|---|---|
| Уперше оприлюднений | 1998 р. |
| Раундів | 32 |
| Тип | Мережа Фейстеля |
У розробці шифру взяв участь Дон Копперсміт, один з авторів шифру Lucifer (DES), відомий низкою статей по криптології: поліпшення структури S-блоків проти диференціального криптоаналізу, метод швидкого перемножування матриць (алгоритм Копперсміта — Винограду), криптоаналіз RSA. Крім нього в розробці алгоритму взяли участь: Керолін Барвік, Едвард Д'Евіньон, Росаріо Женаро, Шай Халеві, Чаранжіт Джутла, Стівен M. Матьяс Мол., Люк О'Коннор, Мохамед Пер'євян, Девід Саффорд, Невенко Зуніч.
За правилами конкурсу AES, учасники могли вносити незначні зміни у свої алгоритми. Скориставшись цим правилом, автори MARSa змінили процедуру розширення ключа, що дозволило знизити вимоги до енергонезалежної і оперативної пам'яті. Нижче буде надана модифікована версія алгоритму.
За результатами конкурсу AES, MARS вийшов у фінал, але поступився Rijndael. Після оголошення результатів (19 травня 2000 року) група розробників склала свою власну думку про конкурс AES, де дала коментарі на претензії до свого дітища.
Зараз MARS поширюється по всьому світу під Royalty Free ліцензією.
Короткий опис алгоритму ред.
MARS є блочно-симетричним шифром з відкритим ключем. Розмір блоку при шифруванні 128 біта, розмір ключа може варіюватися від 128 до 448 біт включно (кратні 32 бітам). Творці прагнули поєднати в своєму алгоритмі швидкість кодування і стійкість шифру. В результаті вийшов один з самих криптостійкий алгоритм з алгоритмів, які брали участь в конкурсі AES.
Алгоритм унікальний тим, що використовував практично всі існуючі технології, застосовувані в криптоалгоритмах, а саме:
- Найпростіші операції (додавання, віднімання, виключаюче або)
- Підстановки з використанням таблиці замін
- Фіксований циклічний зсув
- Залежний від даних циклічний зсув
- Множення по модулю 2 32
- Ключове забілювання
Використання подвійного перемішування представляє складність для криптоаналіз а, що деякі відносять до недоліків алгоритму. У той же час на даний момент не існує будь-яких ефективних атак на алгоритм, хоча деякі ключі можуть генерувати слабкі підключі.
Структура алгоритму ред.
Автори шифру виходили з наступних припущень:
- Вибір операцій. MARS був спроектований для використання на найсучасніших комп'ютерах того часу. Для досягнення найкращих захисних характеристик в нього були включені самі «сильні операції» підтримувані в них. Це дозволило добитися більшого відносини securityper-instruction для різних реалізації шифру.
- Структура шифру. Двадцятирічний досвід роботи в області криптографії підштовхнув творців алгоритму до думки, що кожен раунд шифрування грає свою роль в забезпеченні безпеки шифру. Зокрема, ми можемо бачити, що перший і останній раунди зазвичай сильно відрізняються від проміжних («центральних») раундів алгоритму в плані захисту від криптоаналітичних атак. Таким чином, при створенні MARSa використовувалася змішана структура, де перший і останній раунди шифрування істотно відрізняються від проміжних.
- Аналіз. Швидше за все, алгоритм з гетерогенною структурою буде краще протистояти криптоаналітичних методам майбутнього, ніж алгоритм, всі раунди якого ідентичні. Розробники алгоритму MARS надали йому сильно гетерогенну структуру — раунди алгоритму дуже різняться між собою.
У шифрі MARS використовувалися такі методи шифрування:
- Робота з 32-х бітними словами. Всі операції застосовуються до 32-бітовим словами. тобто вся початкова інформація розбивається на блоки по 32 біта. (Якщо ж блок опинявся меншої довжини, то він доповнювався до 32 біт)
- Мережа Фейстеля. Творці шифру вважали, що це найкращий варіант поєднання швидкості шифрування і криптостійкості. В MARS використана мережа Фейстеля 3-го типу.
- Симетричність алгоритму. Для стійкості шифру до різних атакам всі його раунди були зроблені повністю симетричними, тобто друга частина раунду є дзеркальне повторення першої його частини.
Структуру алгоритму MARS можна описати таким чином:
- Попереднє накладення ключа: на 32-бітові субблоки A, B, C, D накладаються 4 фрагмента розширеного ключа k 0 … k 3 операцією складання по модулю 2 32 ;
- Виконуються 8 раундів прямого перемішування (без участі ключа шифрування);
- Виконуються 8 раундів прямого криптоперетворення;
- Виконуються 8 раундів зворотного криптоперетворення;
- Виконуються 8 раундів зворотного перемішування, також без участі ключа шифрування;
- Фінальне накладення фрагментів розширеного ключа k 36 … k 39 операцією віднімання по модулю 2 32 .
Пряме перемішування ред.
У першій фазі на кожне слово даних накладається слово ключа, а потім відбувається вісім раундів змішування згідно з мережею Фейстеля третього типу спільно з деякими додатковими змішування. У кожному раунді ми використовуємо одне слово даних (зване, вихідним словом) для модифікації трьох інших слів (звані, цільовими словами). Ми розглядаємо чотири байта вихідного слова як індексів на двох S-блоків, S 0 і S 1 , кожен, що складається з 256 32-розрядних слів, а далі проводимо операції XOR або додавання даних відповідного S-блоку в три інших слова.
Якщо чотири байти вихідного слова b 0 , b 1 , b 2 , b 3 (де b 0 є першим байтом, а b 3 є старшим байтом), то ми використовуємо b 0 , b 2 , як індекси в блоку S 0 і байти b 1 , b 3 , як індекси в S-блоці S 1 . Спочатку зробимо XOR S 0 до першого цільовим речі, а потім додамо S 1 до того ж слова. Ми також додаємо S 0 до другого цільовим слову і XOR блоку-S 1 до третього цільовим слову. У висновку, ми обертаємо вихідне слово на 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 біт вліво.
Для забезпечення, серйозного опору до криптоатаки, три вихідних значення Е-функції (O 1 , O 2 , O 3 ) використовуються в перших восьми раундах і в останніх восьми раундах в різних порядках. У перші вісім раундів ми додаємо O 1 і O 2 до першого і другого цільовим речі, відповідно, і XOR O 3 у третьому цільовим слову. За останні вісім раундів, ми додаємо O 1 і O 2 до третього і другого цільовим речі, відповідно, і XOR O 3 до першого цільовим слову.
Псевдокод ред.
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-блоків (яке виходить суміщенням S 0 і S 1 змішуванням фази), і зберігаємо в 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 0 , b 1 , b 2 , b 3 . Будемо використовувати b 0 , b 2 як індекс до S-блоку — S 1 , а b 1 b 3 для S 0 . Зробимо XOR S 1 [b 0 ] в перше цільове слово, віднімемо S 0 [b 3 ] з другого слова, віднімемо S 1 [b 2 ] з третього цільового слів і потім проробимо XOR S 0 [b 1 ] також до третього цільового слова. Нарешті, ми повертаємо початкове слово на 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-блоків ред.
Диференціальні властивості.
- S-блок не повинен містити слова, що складаються всі 0 або 1
- Кожні два S-блоку S 0 , S 1 повинні відрізнятися один від одного як мінімум в 3 з 4 байтах. (Так як виконання цієї умови для псевдовипадкових S-блоків вкрай малоймовірно, то один з двох S-блоків модифікується)
- S-блок не містить двох елементів таких, що або
- В S-блоці не існує двох пар елементів xor-відмінності яких рівні і двох пар елементів впорядкована різниця яких дорівнює
- Кожні два елементи S-блоку повинні відрізнятися хоча б 4 битами
Вимога № 4 не виконувалося в реалізації IBM для AES, але було виправлено відразу після фіналу. Було відмічено, що в S-блоках присутні наступні елементи, які суперечать цій вимозі:
| XOR | Віднімання |
|---|---|
Лінійні властивості
- Співвідношення зміщення: . Необхідно, щоб цей вислів було більше хоча б
- Однобітових зсув: Необхідно, щоб цей вислів було більше хоча б
- Двухбітовий зсув: . Необхідно, щоб цей вислів було більше хоча б
- Однобітові кореляції: . Необхідно мінімізувати цей вислів серед усіх можливих S-блоків, які задовольняють попереднім пунктам
Розширення ключа ред.
процедура розширення ключа розширює заданий масив ключів k [], що складається з n 32-бітових слів (де n ціле число від 4 до 14) в масив K [] з 40 елементів. Вихідний ключ не повинен дотримуватися будь-якої структури. На додаток, процедура розширення ключа гарантує такі властивості ключового слова, використовуваного при перемножуванні в криптографічному ядрі алгоритму:
- Два молодших біта ключового слова будуть завжди одиницями
- Жодне з ключових слів не міститиме десять поспіль йдуть 0 або 1
Опишемо алгоритм розширення ключа.
- Спочатку масив повністю переписується в проміжний масив , що складається з 15 елементів.
- Далі цей процес повторюється 4 рази. На кожній ітерації генеруються 10 слів розширеного ключа. мінлива відображає поточний номер ітерації. (для першої ітерації 0, для другої 1 і т. д.)
- # Масив T [] перетвориться за наступним правилом:
- # Далі ми перемішуємо масив за допомогою 4 раундів Мережі Фейстел 1-го типу. Повторюємо чотири рази наступну операцію:
- # Далі беремо десять слів з масиву T [] і вставляємо їх як наступних десяти слів в масив K [] ще раз перемішавши:
- Остаточно, ми пробігаємо по шістнадцяти словами, використовуваними для перемножування (K [5], K [7] … K [35]) і модифікуємо їх для того, щоб вони відповідали двом властивостям, описаним вище.
- # Записуємо два молодших біта K [i], за формулою , а потім записуємо замість цих двох біт одиниці, .
- # Збираємо маску M для бітів w, які належать послідовностей з десяти і більше нулів або одиниць. Приміром, , тоді і тільки тоді, коли належить послідовності з 10 або більше однакових елементів. Тоді ми скидаємо (виставляємо їх в 0) значення тих одиниць M, які знаходяться в кінцях нульових або одиничних послідовностей, а також тих одиниць, які знаходяться в старшому та молодшому бітах. Наприклад, нехай наше слово виглядає так: (вираз або ж означає, що 0 або 1 будуть повторені в слові і разів). Тоді маска M буде виглядати наступним чином: . А значить ми скидаємо біти в 4, 15, 16, 28 позиціях, тобто
- # Далі, для виправлення, ми використовуємо таблицю з чотирьох слів B []. Всі елементи таблиці B підібрані так, що для них і для всіх їх циклічних зрушень виконується властивість, що в них немає семи поспіль йдуть 0 або 1. У реалізації IBM використовувалася таблиця . Далі використовуються два записаних біта j для вибору слова з таблиці B, і використовуються молодші п'ять біт слова K [i-1] для обертання його елементів,
- # Остаточно, робиться XOR шаблону p на вихідне слово, при обліку маски М: . Варто зауважити, то що 2 молодших біта М є 0, то два молодших біта підсумкового слова будуть одиницями, а використання таблиці B дозволяє гарантувати, що в слові не буде 10 поспіль йдуть 0 або 1
Переваги і недоліки алгоритму ред.
Шифр був кандидатом AES, після невеликих змін в ході першого раунду конкурсу, пов'язаних зі зміною процедури розширення ключа, MARS успішно пройшов у фінал.
У фіналі конкурсу у MARS був виділений цілий ряд недоліків:
- Складна структура. Складна гетерогенна структура алгоритму ускладнювала не лише його аналіз, але і реалізацію.
- Реалізація. Виникали проблеми при реалізації шифру на платформах, які не підтримували операції 32-бітного множення і обертання на довільне число біт.
- Обмеженість ресурсів. Не можливість апаратно реалізувати алгоритм при малих ресурсах оперативної або ж енергонезалежній пам'яті.
- Захист. MARS виявився погано захищена від атак за часом виконання і споживаної потужності.
- Розширення ключа. MARS гірше інших фіналістів AES підтримував розширення ключа «на льоту».
- Розпаралелювання. Можна розпаралелити лише невелику частину алгоритму.
На всі ці недоліки експертна комісія виділила одне велике достоїнство даного алгоритму — його симетричність. Виходячи з виділених недоліків, MARS очікувано не став переможцем AES.
Відповідь аналітикам AES ред.
Після оголошення результатів конкурсу AES, група творців MARS випустила свою рецензію на весь конкурс. У ній були поставлені під сумнів критерії оцінки конкурсу. Вони вважали, що головною характеристикою шифру повинна бути саме надійність і його стійкість (наприклад, до brute-force атакам) Крім того вони відповіли на кожну претензію з боку журі до свого алгоритму.
1. MARS не підходить для апаратної реалізації Серед претензій до шифру були його важка апаратна реалізація, яка могла спричинити за собою ускладнення роботи Інтернету, а також впровадження великих, за своїми розмірами, схем.
2. MARS не підходить для реалізації на пристроях з малою пам'яттю Для реалізації на SMART картах є у алгоритмів є всього 128 байт пам'яті. Для процедури розширення ключа MARS вимагає 512 байт.
3. MARS не підходить для реалізації на ППВМ MARS не підходить для реалізації на платформах, де не дозволено обертання (залежать від сторонніх чинників).
4. Розширення ключа MARS є дуже важкою операцією
У висновку розробники приводять свій аналіз алгоритмів учасників AES, за результатами якого MARS, поряд з Serpent, був найкращим кандидатом на звання AES.
Аналіз безпеки алгоритму ред.
В даний час немає ефективних атак на даний алгоритм. Хоча у нього є кілька слабких сторін:
- Підключі з великою кількістю повторюваних нулів або одиниць можуть привести до ефективних атак на MARS, так як на їх підставі будуть згенеровані слабкі підключі.
- Два молодших біта, що використовуються при перемножуванні завжди одиниці. Таким чином завжди є два вхідних біта, які незмінні в ході процесу множення на ключ, а також два вихідних біти, незалежних від ключа.
Примітки ред.
Посилання ред.
- Специфікація алгоритму (AES версія) [ 19 листопада 2011 у Wayback Machine.]
- Вихідні тексти MARS-1248 на мові C
- Офіційна сторінка шифру
- Опис проблеми згенерованих S-блоків [ 23 травня 2009 у Wayback Machine.]
- Коментарі творців шифру [ 16 травня 2006 у Wayback Machine.]