Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

У Вікіпедії є статті про інші значення цього терміна Марс значення MARS шифр кандидат в AES розроблений корпорацією IBM

MARS

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

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

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

У розробці шифру взяв участь Дон Копперсміт, один з авторів шифру (DES), відомий низкою статей по криптології: поліпшення структури S-блоків проти диференціального криптоаналізу, метод швидкого перемножування матриць (алгоритм Копперсміта — Винограду), криптоаналіз RSA. Крім нього в розробці алгоритму взяли участь: , , , , , , , , , .

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

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

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

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

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

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

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

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

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

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

  1. Вибір операцій. MARS був спроектований для використання на найсучасніших комп'ютерах того часу. Для досягнення найкращих захисних характеристик в нього були включені самі «сильні операції» підтримувані в них. Це дозволило добитися більшого відносини для різних реалізації шифру.
  2. Структура шифру. Двадцятирічний досвід роботи в області криптографії підштовхнув творців алгоритму до думки, що кожен раунд шифрування грає свою роль в забезпеченні безпеки шифру. Зокрема, ми можемо бачити, що перший і останній раунди зазвичай сильно відрізняються від проміжних («центральних») раундів алгоритму в плані захисту від криптоаналітичних атак. Таким чином, при створенні MARSa використовувалася змішана структура, де перший і останній раунди шифрування істотно відрізняються від проміжних.
  3. Аналіз. Швидше за все, алгоритм з гетерогенною структурою буде краще протистояти криптоаналітичних методам майбутнього, ніж алгоритм, всі раунди якого ідентичні. Розробники алгоритму MARS надали йому сильно гетерогенну структуру — раунди алгоритму дуже різняться між собою.

У шифрі MARS використовувалися такі методи шифрування:

  1. Робота з 32-х бітними словами. Всі операції застосовуються до 32-бітовим словами. тобто вся початкова інформація розбивається на блоки по 32 біта. (Якщо ж блок опинявся меншої довжини, то він доповнювався до 32 біт)
  2. Мережа Фейстеля. Творці шифру вважали, що це найкращий варіант поєднання швидкості шифрування і криптостійкості. В MARS використана мережа Фейстеля 3-го типу.
  3. Симетричність алгоритму. Для стійкості шифру до різних атакам всі його раунди були зроблені повністю симетричними, тобто друга частина раунду є дзеркальне повторення першої його частини.

Структуру алгоритму MARS можна описати таким чином:

  1. Попереднє накладення ключа: на 32-бітові субблоки A, B, C, D накладаються 4 фрагмента розширеного ключа k 0 … k 3 операцією складання по модулю 2 32 ;
  2. Виконуються 8 раундів прямого перемішування (без участі ключа шифрування);
  3. Виконуються 8 раундів прямого криптоперетворення;
  4. Виконуються 8 раундів зворотного криптоперетворення;
  5. Виконуються 8 раундів зворотного перемішування, також без участі ключа шифрування;
  6. Фінальне накладення фрагментів розширеного ключа 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. image 3. image 4. // Потім 8 раундів прямого перемішування 5. image // використовуємо D [0] для модифікування D [1]; D [2]; D [3] 6. // Звертаємося до 4-ем S-блокам 7. image 8. image 9. image 10. image 11. // І обертаємо вихідне слово вправо 12. image 13. // Також проробимо додаткові операції змішування 14. image 15. image / / додамо D [3] до вихідного слова 16. image 17. image / / додамо D [1] до вихідного слова 18. // Обертаємо масив D [] 19. image 20. image

Криптографічне ядро

Криптографічне ядро 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. image 3. image 4. image 5. image 6. image // спочатку 8 раундів прямого перетворення 7. image 8. image 9. image // потім 8 раундів зворотного перетворення 10. image 11. image 12. image 13. // Обертаємо масив D [] 14. image 15. image

Е-функція

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. image // додаємо першим ключовим словом 3. image / / множимо на друге ключове слово, яке повинно бути парним 4. image 5. image // взяття S-блоку 6. image 7. image // ці біти описують величину подальшого обертання 8. image // перша обертання на змінну величину 9. image 10. image 11. image 12. image // ці біти описують величину подальшого обертання 13. image // Друга обертання на змінну величину 14. image

Зворотне перемішування

Зворотне перемішування практично збігається з прямим перемішуванням, за винятком того факту, що дані обробляються в зворотному порядку. Тобто, якби ми поєднали пряме і зворотне перемішування так, щоб їх виходи і входи були б з'єднані в зворотному порядку (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. image 3. // Додаткові операції змішування 4. image 5. image // віднімаємо D [3] з вихідного слова 6. image 7. image // віднімаємо D [1] з вихідного слова 8. // Звертаємося до чотирьох елементів S-блоків 9. image 10. image 11. image 12. image 13. // І обертаємо вихідне слово вліво 14. image 15. // Обертаємо масив D [] 16. image 17. image 18. / / Віднімаємо ключове слово 19. image 20. image

Дешифрування

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

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

1. // Початкове накладення ключа 2. image 3. image 4. // Потім проводимо 8 раундів прямого перемішування 5. image 6. // Обертаємо масив D [] 7. image 8. // І обертаємо вихідне слово вправо 9. image 10. / / Звертаємося до 4-ем елементам S-блоків 11. image 12. image 13. image 14. image 15. // Додаткове змішування 16. image 17. image // додаємо D [3] до вихідного слова 18. image 29. image // додаємо D [1] до вихідного слова 20. image

Криптографічне ядро

1. // Проведемо 16 раундів при використання накладення ключа 2. image 3. // Обертаємо масив D [] 4. image 5. image 6. image 7. image 8. image // останні 8 раундів в прямому порядку 9. image 10. image 11. image // перші 8 раундів у зворотному порядку 12. image 13. image 14. image 15. image

Зворотне перемішування

1. // Проводимо 8 раундів зворотного перемішування 2. image 3. // Обертаємо масив D [] 4. image 5. // Додаткові операції переммешіванія 6. image 7. image // віднімаємо D [3] з вихідного слова 8. image 9. image // віднімаємо D [1] з вихідного слова 10. // Обертаємо вихідне слово вліво 11. image 12. // Звертаємося до чотирьох елементами S-блоків 13. image 14. image 15. image 16. image 17. image 18. // Віднімання підключа з даних 19. image 20. image

Особливості алгоритму

S-блоки

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

image

(Де image — є j-е слово на виході SHA-1) Тут вважається, що i — 32-бітове без знакове, ціле число, а c1, c2, c3 є деякі константи. У реалізації IBM: c1 = 0xb7e15162; c2 = 0x243f6a88 (які є двійковій записом дробової частини image і image відповідно). c3 змінювалося поки не були підібрані S-блоки з відповідними властивостями. SHA-1 працює над потоками даних і використовує прямий порядок байт.

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

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

  1. S-блок не повинен містити слова, що складаються всі 0 або 1
  2. Кожні два S-блоку S 0 , S 1 повинні відрізнятися один від одного як мінімум в 3 з 4 байтах. (Так як виконання цієї умови для псевдовипадкових S-блоків вкрай малоймовірно, то один з двох S-блоків модифікується)
  3. S-блок не містить двох елементів image таких, що image або image
  4. В S-блоці не існує двох пар елементів xor-відмінності яких рівні і двох пар елементів впорядкована різниця яких дорівнює
  5. Кожні два елементи S-блоку повинні відрізнятися хоча б 4 битами

Вимога № 4 не виконувалося в реалізації IBM для AES, але було виправлено відразу після фіналу. Було відмічено, що в S-блоках присутні наступні елементи, які суперечать цій вимозі:

XOR Віднімання
image image
image image
image image
image
image
image
image
image

Лінійні властивості

  1. Співвідношення зміщення: image. Необхідно, щоб цей вислів було більше хоча б image
  2. Однобітових зсув: image Необхідно, щоб цей вислів було більше хоча б image
  3. Двухбітовий зсув: image. Необхідно, щоб цей вислів було більше хоча б image
  4. Однобітові кореляції: image. Необхідно мінімізувати цей вислів серед усіх можливих S-блоків, які задовольняють попереднім пунктам

Розширення ключа

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

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

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

  1. Спочатку масив image повністю переписується в проміжний масив image, що складається з 15 елементів. image
  2. Далі цей процес повторюється 4 рази. На кожній ітерації генеруються 10 слів розширеного ключа. image мінлива відображає поточний номер ітерації. (для першої ітерації 0, для другої 1 і т. д.)
  3. # Масив T [] перетвориться за наступним правилом: image
  4. # Далі ми перемішуємо масив image за допомогою 4 раундів Мережі Фейстел 1-го типу. Повторюємо чотири рази наступну операцію: image
  5. # Далі беремо десять слів з масиву T [] і вставляємо їх як наступних десяти слів в масив K [] ще раз перемішавши: image
  6. Остаточно, ми пробігаємо по шістнадцяти словами, використовуваними для перемножування (K [5], K [7] … K [35]) і модифікуємо їх для того, щоб вони відповідали двом властивостям, описаним вище.
  7. # Записуємо два молодших біта K [i], за формулою image, а потім записуємо замість цих двох біт одиниці, image.
  8. # Збираємо маску M для бітів w, які належать послідовностей з десяти і більше нулів або одиниць. Приміром, image, тоді і тільки тоді, коли image належить послідовності з 10 або більше однакових елементів. Тоді ми скидаємо (виставляємо їх в 0) значення тих одиниць M, які знаходяться в кінцях нульових або одиничних послідовностей, а також тих одиниць, які знаходяться в старшому та молодшому бітах. Наприклад, нехай наше слово виглядає так: image (вираз image або ж image означає, що 0 або 1 будуть повторені в слові і разів). Тоді маска M буде виглядати наступним чином: image. А значить ми скидаємо біти в 4, 15, 16, 28 позиціях, тобто image
  9. # Далі, для виправлення, ми використовуємо таблицю з чотирьох слів B []. Всі елементи таблиці B підібрані так, що для них і для всіх їх циклічних зрушень виконується властивість, що в них немає семи поспіль йдуть 0 або 1. У реалізації IBM використовувалася таблиця image. Далі використовуються два записаних біта j для вибору слова з таблиці B, і використовуються молодші п'ять біт слова K [i-1] для обертання його елементів, image
  10. # Остаточно, робиться XOR шаблону p на вихідне слово, при обліку маски М: image. Варто зауважити, то що 2 молодших біта М є 0, то два молодших біта підсумкового слова будуть одиницями, а використання таблиці B дозволяє гарантувати, що в слові не буде 10 поспіль йдуть 0 або 1

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

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

У фіналі конкурсу у MARS був виділений цілий ряд недоліків:

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

На всі ці недоліки експертна комісія виділила одне велике достоїнство даного алгоритму — його симетричність. Виходячи з виділених недоліків, MARS очікувано не став переможцем AES.

Відповідь аналітикам AES

Після оголошення результатів конкурсу AES, група творців MARS випустила свою рецензію на весь конкурс. У ній були поставлені під сумнів критерії оцінки конкурсу. Вони вважали, що головною характеристикою шифру повинна бути саме надійність і його стійкість (наприклад, до атакам) Крім того вони відповіли на кожну претензію з боку журі до свого алгоритму.

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. Підключі з великою кількістю повторюваних нулів або одиниць можуть привести до ефективних атак на MARS, так як на їх підставі будуть згенеровані слабкі підключі.
  2. Два молодших біта, що використовуються при перемножуванні завжди одиниці. Таким чином завжди є два вхідних біта, які незмінні в ході процесу множення на ключ, а також два вихідних біти, незалежних від ключа.

Примітки

  1. (PDF). Архів оригіналу (PDF) за 16 травня 2006. Процитовано 17 червня 2012.
  2. Етапи 3 і 4 називаються «криптографічним ядром» алгоритму MARS
  3. . Архів оригіналу за 23 травня 2009. Процитовано 17 червня 2012.

Посилання

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

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

U Vikipediyi ye statti pro inshi znachennya cogo termina Mars znachennya MARS shifr kandidat v AES rozroblenij korporaciyeyu IBM yaka stvorila u svij chas DES Za zayavoyu IBM v algoritm MARS vkladeno 25 richnij kriptoanalitichnij dosvid firmi i poryad z visokoyu kriptografichnoyu stijkistyu shifr dopuskaye efektivnu realizaciyu navit v takih obmezhenih ramkah yaki harakterni dlya smart kart MARSRozrobniki Kerolin Barvik Don Koppersmit IBM Upershe oprilyudnenij 1998 r Raundiv 32Tip Merezha Fejstelya U rozrobci shifru vzyav uchast Don Koppersmit odin z avtoriv shifru DES vidomij nizkoyu statej po kriptologiyi polipshennya strukturi S blokiv proti diferencialnogo kriptoanalizu metod shvidkogo peremnozhuvannya matric algoritm Koppersmita Vinogradu kriptoanaliz RSA Krim nogo v rozrobci algoritmu vzyali uchast Za pravilami konkursu AES uchasniki mogli vnositi neznachni zmini u svoyi algoritmi Skoristavshis cim pravilom avtori MARSa zminili proceduru rozshirennya klyucha sho dozvolilo zniziti vimogi do energonezalezhnoyi i operativnoyi pam yati Nizhche bude nadana modifikovana versiya algoritmu Za rezultatami konkursu AES MARS vijshov u final ale postupivsya Rijndael Pislya ogoloshennya rezultativ 19 travnya 2000 roku grupa rozrobnikiv sklala svoyu vlasnu dumku pro konkurs AES de dala komentari na pretenziyi do svogo ditisha Zaraz MARS poshiryuyetsya po vsomu svitu pid Royalty Free licenziyeyu Korotkij opis algoritmuMARS ye blochno simetrichnim shifrom z vidkritim klyuchem Rozmir bloku pri shifruvanni 128 bita rozmir klyucha mozhe variyuvatisya vid 128 do 448 bit vklyuchno kratni 32 bitam Tvorci pragnuli poyednati v svoyemu algoritmi shvidkist koduvannya i stijkist shifru V rezultati vijshov odin z samih algoritm z algoritmiv yaki brali uchast v konkursi AES Algoritm unikalnij tim sho vikoristovuvav praktichno vsi isnuyuchi tehnologiyi zastosovuvani v kriptoalgoritmah a same Najprostishi operaciyi dodavannya vidnimannya viklyuchayuche abo Pidstanovki z vikoristannyam tablici zamin Fiksovanij ciklichnij zsuv Zalezhnij vid danih Mnozhennya po modulyu 2 32 Klyuchove zabilyuvannya Vikoristannya podvijnogo peremishuvannya predstavlyaye skladnist dlya kriptoanaliz a sho deyaki vidnosyat do nedolikiv algoritmu U toj zhe chas na danij moment ne isnuye bud yakih efektivnih atak na algoritm hocha deyaki klyuchi mozhut generuvati slabki pidklyuchi Struktura algoritmuAvtori shifru vihodili z nastupnih pripushen Vibir operacij MARS buv sproektovanij dlya vikoristannya na najsuchasnishih komp yuterah togo chasu Dlya dosyagnennya najkrashih zahisnih harakteristik v nogo buli vklyucheni sami silni operaciyi pidtrimuvani v nih Ce dozvolilo dobitisya bilshogo vidnosini dlya riznih realizaciyi shifru Struktura shifru Dvadcyatirichnij dosvid roboti v oblasti kriptografiyi pidshtovhnuv tvorciv algoritmu do dumki sho kozhen raund shifruvannya graye svoyu rol v zabezpechenni bezpeki shifru Zokrema mi mozhemo bachiti sho pershij i ostannij raundi zazvichaj silno vidriznyayutsya vid promizhnih centralnih raundiv algoritmu v plani zahistu vid kriptoanalitichnih atak Takim chinom pri stvorenni MARSa vikoristovuvalasya zmishana struktura de pershij i ostannij raundi shifruvannya istotno vidriznyayutsya vid promizhnih Analiz Shvidshe za vse algoritm z geterogennoyu strukturoyu bude krashe protistoyati kriptoanalitichnih metodam majbutnogo nizh algoritm vsi raundi yakogo identichni Rozrobniki algoritmu MARS nadali jomu silno geterogennu strukturu raundi algoritmu duzhe riznyatsya mizh soboyu U shifri MARS vikoristovuvalisya taki metodi shifruvannya Robota z 32 h bitnimi slovami Vsi operaciyi zastosovuyutsya do 32 bitovim slovami tobto vsya pochatkova informaciya rozbivayetsya na bloki po 32 bita Yaksho zh blok opinyavsya menshoyi dovzhini to vin dopovnyuvavsya do 32 bit Merezha Fejstelya Tvorci shifru vvazhali sho ce najkrashij variant poyednannya shvidkosti shifruvannya i kriptostijkosti V MARS vikoristana merezha Fejstelya 3 go tipu Simetrichnist algoritmu Dlya stijkosti shifru do riznih atakam vsi jogo raundi buli zrobleni povnistyu simetrichnimi tobto druga chastina raundu ye dzerkalne povtorennya pershoyi jogo chastini Strukturu algoritmu MARS mozhna opisati takim chinom Poperednye nakladennya klyucha na 32 bitovi subbloki A B C D nakladayutsya 4 fragmenta rozshirenogo klyucha k 0 k 3 operaciyeyu skladannya po modulyu 2 32 Vikonuyutsya 8 raundiv pryamogo peremishuvannya bez uchasti klyucha shifruvannya Vikonuyutsya 8 raundiv pryamogo kriptoperetvorennya Vikonuyutsya 8 raundiv zvorotnogo kriptoperetvorennya Vikonuyutsya 8 raundiv zvorotnogo peremishuvannya takozh bez uchasti klyucha shifruvannya Finalne nakladennya fragmentiv rozshirenogo klyucha k 36 k 39 operaciyeyu vidnimannya po modulyu 2 32 Pryame peremishuvannya U pershij fazi na kozhne slovo danih nakladayetsya slovo klyucha a potim vidbuvayetsya visim raundiv zmishuvannya zgidno z merezheyu Fejstelya tretogo tipu spilno z deyakimi dodatkovimi zmishuvannya U kozhnomu raundi mi vikoristovuyemo odne slovo danih zvane vihidnim slovom dlya modifikaciyi troh inshih sliv zvani cilovimi slovami Mi rozglyadayemo chotiri bajta vihidnogo slova yak indeksiv na dvoh S blokiv S 0 i S 1 kozhen sho skladayetsya z 256 32 rozryadnih sliv a dali provodimo operaciyi XOR abo dodavannya danih vidpovidnogo S bloku v tri inshih slova Yaksho chotiri bajti vihidnogo slova b 0 b 1 b 2 b 3 de b 0 ye pershim bajtom a b 3 ye starshim bajtom to mi vikoristovuyemo b 0 b 2 yak indeksi v bloku S 0 i bajti b 1 b 3 yak indeksi v S bloci S 1 Spochatku zrobimo XOR S 0 do pershogo cilovim rechi a potim dodamo S 1 do togo zh slova Mi takozh dodayemo S 0 do drugogo cilovim slovu i XOR bloku S 1 do tretogo cilovim slovu U visnovku mi obertayemo vihidne slovo na 24 bita vpravo U nastupnomu raundi mi obertayemo nayavni u nas chotiri slova takim chinom ninishni pershi cilove slovo staye nastupnim vihidnim slovom potochnim drugij cilove slovo staye novim pershim cilovim slovom tretye cilove slovo staye nastupnij drugij cilovim slovom i potochne vihidne slovo staye tretim cilovim slovom Bilsh togo pislya kozhnogo z chotiroh raundiv mi dodayemo odne z cilovih sliv nazad u vihidne slovo Zokrema pislya pershogo i p yatogo raundiv mi dodav tretyu cilove slovo nazad u vihidne slovo a pislya drugogo i shostogo raundu mi dodayemo pershoyi cilovoyi slovo nazad u vihidne slovo Prichinoyu cih dodatkovih operacij zmishuvannya ye likvidaciya dekilkoh prostih diferencialnih v fazi peremishuvannya shob porushiti simetriyu u fazi zmishuvannya ta otrimati shvidkij potik Psevdokod 1 Pershe nakladennya klyucha na dani 2 f o r i 0 t o 3 d o displaystyle for i 0 to 3 do 3 D i D i K i displaystyle D left i right D i K i 4 Potim 8 raundiv pryamogo peremishuvannya 5 f o r i 0 t o 7 d o displaystyle for i 0 to 7 do vikoristovuyemo D 0 dlya modifikuvannya D 1 D 2 D 3 6 Zvertayemosya do 4 em S blokam 7 D 1 D 1 S 0 l o w b y t e o f D 0 displaystyle D left 1 right D 1 oplus S0 low byte of D 0 8 D 1 D 1 S 1 2 n d b y t e o f D 0 displaystyle D left 1 right D 1 S1 2nd byte of D 0 9 D 2 D 2 S 0 3 r d b y t e o f D 0 displaystyle D left 2 right D 2 S0 3rd byte of D 0 10 D 3 D 3 S 1 h i g h b y t e o f D 0 displaystyle D 3 D 3 oplus S1 high byte of D 0 11 I obertayemo vihidne slovo vpravo 12 D 0 D 0 24 displaystyle D 0 D 0 ggg 24 13 Takozh prorobimo dodatkovi operaciyi zmishuvannya 14 i f i 0 o r 4 t h e n displaystyle if i 0 or 4 then 15 D 0 D 0 D 3 displaystyle D left 0 right D 0 D 3 dodamo D 3 do vihidnogo slova 16 i f i 1 o r 5 t h e n displaystyle if i 1 or 5 then 17 D 0 D 0 D 1 displaystyle D left 0 right D 0 D 1 dodamo D 1 do vihidnogo slova 18 Obertayemo masiv D 19 D 3 D 2 D 1 D 0 D 0 D 3 D 2 D 1 displaystyle D 3 D 2 D 1 D 0 leftarrow D 0 D 3 D 2 D 1 20 E n d f o r displaystyle End for Kriptografichne yadro Kriptografichne yadro MARS merezha Fejstelya 3 go tipu sho mistit v sobi 16 raundiv U kozhnomu raundi mi vikoristovuyemo klyuchovu E funkciyu yaka ye kombinaciyeyu mnozhen obertan a takozh zvernen do S blokiv Funkciya prijmaye na vhid slovo danih a povertaye tri slova z yakimi zgodom bude zdijsnena operaciya dodavannya abo XOR do inshih troh sliv danimi U dopovnenni vihidne slovo obertayetsya na 13 bit vlivo Dlya zabezpechennya serjoznogo oporu do kriptoataki tri vihidnih znachennya E funkciyi O 1 O 2 O 3 vikoristovuyutsya v pershih vosmi raundah i v ostannih vosmi raundah v riznih poryadkah U pershi visim raundiv mi dodayemo O 1 i O 2 do pershogo i drugogo cilovim rechi vidpovidno i XOR O 3 u tretomu cilovim slovu Za ostanni visim raundiv mi dodayemo O 1 i O 2 do tretogo i drugogo cilovim rechi vidpovidno i XOR O 3 do pershogo cilovim slovu Psevdokod 1 Prorobimo 16 raundiv shifruvannya pri vikoristanni klyucha 2 F o r i 0 t o 15 d o displaystyle For i 0 to 15 do 3 O u t 1 o u t 2 o u t 3 E f u n c t i o n D 0 K 2 i 4 K 2 i 5 displaystyle Out1 out2 out3 E function D 0 K 2i 4 K 2i 5 4 D 0 D 0 13 displaystyle D 0 D 0 lll 13 5 D 2 D 2 o u t 2 displaystyle D 2 D left 2 right out2 6 I f i lt 8 t h e n displaystyle If i lt 8 then spochatku 8 raundiv pryamogo peretvorennya 7 D 1 D 1 o u t 1 displaystyle D 1 D left 1 right out1 8 D 3 D 3 o u t 3 displaystyle D 3 D 3 oplus out3 9 E l s e displaystyle Else potim 8 raundiv zvorotnogo peretvorennya 10 D 3 D 3 o u t 1 displaystyle D 3 D left 3 right out1 11 D 1 D 1 o u t 3 displaystyle D 1 D 1 oplus out3 12 E n d i f displaystyle End if 13 Obertayemo masiv D 14 D 3 D 2 D 1 D 0 D 0 D 3 D 2 D 1 displaystyle D 3 D 2 D 1 D 0 leftarrow D 0 D 3 D 2 D 1 15 E n d f o r displaystyle End for E funkciya E funkciya prijmaye yak vhidni dani odne slovo danih i vikoristovuye she dva klyuchovih slova viroblyayuchi na vihodi tri slova U cij funkciyi mi vikoristovuyemo tri timchasovi zminni sho poznachayutsya L M i R dlya livoyi serednoyi ta pravoyi Spochatku mi vstanovlyuyemo v R znachennya vihidnogo slova zmishenogo na 13 bit vlivo a v M suma vihidnih sliv i pershogo klyuchovogo slova Potim mi vikoristovuyemo pershi dev yat bitiv M yak indeks do odniyeyi z 512 S blokiv yake vihodit sumishennyam S 0 i S 1 zmishuvannyam fazi i zberigayemo v L znachennya vidpovidnogo S bloku Potim pomnozhimo druge klyuchove slovo na R zberigshi znachennya v R Potim obertayemo R na 5 pozicij vlivo tak 5 starshih bitiv stayut 5 nizhnimi bitami R pislya obertannya Todi mi robimo XOR R v L a takozh pereglyadayemo p yat nizhnih bit R dlya viznachennya velichini zsuvu vid 0 do 31 i obertayemo M vlivo na cyu velichinu Dali mi obertayemo R she na 5 pozicij vlivo i robimo XOR v L U visnovku mi znovu divimosya na 5 molodshih bitiv R yak na velichinu obertannya i obertayemo L na cyu velichinu vlivo Takim chinom rezultat roboti E funkciyi 3 slova po poryadku L M R Psevdokod 1 Vikoristovuyemo 3 timchasovi zminni L M R 2 M i n k e y 1 displaystyle M in key1 dodayemo pershim klyuchovim slovom 3 R i n 13 k e y 2 displaystyle R in lll 13 otimes key2 mnozhimo na druge klyuchove slovo yake povinno buti parnim 4 I l o w e s t 9 b i t s o f M displaystyle I lowest 9 bits of M 5 L S i displaystyle L S left i right vzyattya S bloku 6 R R 5 displaystyle R R lll 5 7 R l o w e s t 5 b i t s o f R displaystyle R lowest 5 bits of R ci biti opisuyut velichinu podalshogo obertannya 8 M M r displaystyle M M lll r persha obertannya na zminnu velichinu 9 L L R displaystyle L L oplus R 10 R R 5 displaystyle R R lll 5 11 L L R displaystyle L L oplus R 12 R l o w e s t 5 b i t s o f R displaystyle R lowest 5 bits of R ci biti opisuyut velichinu podalshogo obertannya 13 L L r displaystyle L L lll r Druga obertannya na zminnu velichinu 14 O u t p u t L M R displaystyle Output L M R Zvorotne peremishuvannya Zvorotne peremishuvannya praktichno zbigayetsya z pryamim peremishuvannyam za vinyatkom togo faktu sho dani obroblyayutsya v zvorotnomu poryadku Tobto yakbi mi poyednali pryame i zvorotne peremishuvannya tak shob yih vihodi i vhodi buli b z yednani v zvorotnomu poryadku D 0 pryamogo i D 3 zvorotnogo D 1 pryamogo i D 2 zvorotnogo to ne pobachili b rezultatu peremishuvannya Yak i v pryamomu zmishuvannya tut mi tezh vikoristovuyemo odne vihidne slovo i tri cilovih Rozglyanemo chotiri pershih bajta vihidnogo slova b 0 b 1 b 2 b 3 Budemo vikoristovuvati b 0 b 2 yak indeks do S bloku S 1 a b 1 b 3 dlya S 0 Zrobimo XOR S 1 b 0 v pershe cilove slovo vidnimemo S 0 b 3 z drugogo slova vidnimemo S 1 b 2 z tretogo cilovogo sliv i potim prorobimo XOR S 0 b 1 takozh do tretogo cilovogo slova Nareshti mi povertayemo pochatkove slovo na 24 pozicij vlivo Dlya nastupnogo raundu mi obertayemo nayavni slova tak shob ninishnye pershe cilove slovo stalo nastupnim vihidnim slovom potochne druge cilove slovo stalo pershim cilovim slovom potochne tretye cilove slovo stalo drugim cilovim slovom i potochne vihidne slovo stalo tretim cilovim slovom Krim togo pered odnim z chotiroh osoblivih raundiv mi vidnimayemo odne z cilovih sliv z vihidnogo slova pered chetvertim i vosmim raundami mi vidnimayemo pershoyi cilovoyi slovo pered tretomu i somim raundami mi vidnimemo tretya cilova slovo z vihidnogo Psevdokod 1 Provodimo 8 raundiv zvorotnogo peremishuvannya 2 F o r i 0 t o 7 d o displaystyle For i 0 to 7 do 3 Dodatkovi operaciyi zmishuvannya 4 i f i 2 o r 6 t h e n displaystyle if i 2 or 6 then 5 D 0 D 0 D 3 displaystyle D 0 D 0 D 3 vidnimayemo D 3 z vihidnogo slova 6 i f i 3 o r 7 t h e n displaystyle if i 3 or 7 then 7 D 0 D 0 D 1 displaystyle D 0 D 0 D 1 vidnimayemo D 1 z vihidnogo slova 8 Zvertayemosya do chotiroh elementiv S blokiv 9 D 1 D 1 S 1 l o w b y t e o f D 0 displaystyle D 1 D 1 oplus S1 low byte of D 0 10 D 2 D 2 S 0 h i g h b y t e o f D 0 displaystyle D 2 D 2 S0 high byte of D 0 11 D 3 D 3 S 1 3 r d b y t e o f D 0 displaystyle D 3 D 3 oplus S1 3rd byte of D 0 12 D 3 D 3 S 0 2 n d b y t e o f D 0 displaystyle D 3 D 3 S0 2nd byte of D 0 13 I obertayemo vihidne slovo vlivo 14 D 0 D 0 24 displaystyle D 0 D 0 lll 24 15 Obertayemo masiv D 16 D 3 D 2 D 1 D 0 D 0 D 3 D 2 D 1 displaystyle D 3 D 2 D 1 D 0 leftarrow D 0 D 3 D 2 D 1 17 E n d f o r displaystyle End for 18 Vidnimayemo klyuchove slovo 19 F o r i 0 t o 3 d o displaystyle For i 0 to 3 do 20 D i D i K 36 i displaystyle D i D i K 36 i Deshifruvannya Proces dekoduvannya obernenij procesu koduvannya Kod deshifruvannya shozhij ale ne identichnij na kod shifruvannya Pryame peremishuvannya 1 Pochatkove nakladennya klyucha 2 F o r i 0 t o 3 d o displaystyle For i 0 to 3 do 3 D i D i K 36 i displaystyle D left i right D i K 36 i 4 Potim provodimo 8 raundiv pryamogo peremishuvannya 5 F o r i 7 d o w n t o 0 d o displaystyle For i 7 down to 0 do 6 Obertayemo masiv D 7 D 3 D 2 D 1 D 0 D 2 D 1 D 0 D 3 displaystyle D 3 D 2 D 1 D 0 leftarrow D 2 D 1 D 0 D 3 8 I obertayemo vihidne slovo vpravo 9 D 0 D 0 24 displaystyle D 0 D 0 ggg 24 10 Zvertayemosya do 4 em elementam S blokiv 11 D 3 D 3 S 0 2 n d b y t e o f D 0 displaystyle D 3 D 3 oplus S0 2nd byte of D 0 12 D 3 D 3 S 1 3 r d b y t e o f D 0 displaystyle D 3 D 3 S1 3rd byte of D 0 13 D 2 D 2 S 0 h i g h b y t e o f D 0 displaystyle D 2 D 2 S0 high byte of D 0 14 D 1 D 1 S 1 l o w b y t e o f D 0 displaystyle D 1 D 1 oplus S1 low byte of D 0 15 Dodatkove zmishuvannya 16 I f i 2 o r 6 t h e n displaystyle If i 2 or 6 then 17 D 0 D 0 D 3 displaystyle D 0 D left 0 right D 3 dodayemo D 3 do vihidnogo slova 18 I f i 3 o r 7 t h e n displaystyle If i 3 or 7 then 29 D 0 D 0 D 1 displaystyle D 0 D left 0 right D 1 dodayemo D 1 do vihidnogo slova 20 E n d f o r displaystyle End for Kriptografichne yadro 1 Provedemo 16 raundiv pri vikoristannya nakladennya klyucha 2 F o r i 15 d o w n t o 0 d o displaystyle For i 15 down to 0 do 3 Obertayemo masiv D 4 D 3 D 2 D 1 D 0 D 2 D 1 D 0 D 3 displaystyle D 3 D 2 D 1 D 0 leftarrow D 2 D 1 D 0 D 3 5 D 0 D 0 13 displaystyle D 0 D 0 ggg 13 6 O u t 1 o u t 2 o u t 3 E f u n c t i o n D 0 K 2 i 4 K 2 i 5 displaystyle Out1 out2 out3 E function D 0 K 2i 4 K 2i 5 7 D 2 D 2 o u t 2 displaystyle D 2 D left 2 right out2 8 I f i lt 8 t h e n displaystyle If i lt 8 then ostanni 8 raundiv v pryamomu poryadku 9 D 1 D 1 o u t 1 displaystyle D 1 D left 1 right out1 10 D 3 D 3 o u t 3 displaystyle D 3 D 3 oplus out3 11 E l s e displaystyle Else pershi 8 raundiv u zvorotnomu poryadku 12 D 3 D 3 o u t 1 displaystyle D 3 D left 3 right out1 13 D 1 D 1 o u t 3 displaystyle D 1 D 1 oplus out3 14 E n d i f displaystyle End if 15 E n d f o r displaystyle End for Zvorotne peremishuvannya 1 Provodimo 8 raundiv zvorotnogo peremishuvannya 2 f o r i 7 d o w n t o 0 d o displaystyle for i 7 down to 0 do 3 Obertayemo masiv D 4 D 3 D 2 D 1 D 0 D 2 D 1 D 0 D 3 displaystyle D 3 D 2 D 1 D 0 leftarrow D 2 D 1 D 0 D 3 5 Dodatkovi operaciyi peremmeshivaniya 6 I f i 0 o r 4 t h e n displaystyle If i 0 or 4 then 7 D 0 D 0 D 3 displaystyle D 0 D left 0 right D 3 vidnimayemo D 3 z vihidnogo slova 8 I f i 1 o r 5 t h e n displaystyle If i 1 or 5 then 9 D 0 D 0 D 1 displaystyle D 0 D left 0 right D 1 vidnimayemo D 1 z vihidnogo slova 10 Obertayemo vihidne slovo vlivo 11 D 0 D 0 24 displaystyle D 0 D 0 lll 24 12 Zvertayemosya do chotiroh elementami S blokiv 13 D 3 D 3 S 1 h i g h b y t e o f D 0 displaystyle D 3 D 3 oplus S1 high byte of D 0 14 D 2 D 2 S 0 3 r d b y t e o f D 0 displaystyle D 2 D 2 S0 3rd byte of D 0 15 D 1 D 1 S 1 2 n d b y t e o f D 0 displaystyle D 1 D 1 S1 2nd byte of D 0 16 D 1 D 1 S 0 l o w b y t e o f D 0 displaystyle D 1 D 1 oplus S0 low byte of D 0 17 E n d f o r displaystyle End for 18 Vidnimannya pidklyucha z danih 19 F o r i 0 t o 3 d o displaystyle For i 0 to 3 do 20 D i D i K i displaystyle D i D left i right K i Osoblivosti algoritmuS bloki Pri stvorenni S bloku S jogo elementi generuvalisya psevdovipadkovih generatorom pislya chogo testuvalisya na rizni linijni i diffirencialnie vlastivosti Psevdovipadkovi S bloki buli zgenerovani pri nastupnih parametrah i 0 102 j 0 4 S 5 i j S H A 1 5 i c 1 c 2 v e r t c 3 displaystyle i 0 ldots 102 j 0 ldots 4 S 5i j mathrm SHA 1 5i vert c1 vert c2 vertc3 De S H A 1 j displaystyle SHA 1 j ye j e slovo na vihodi SHA 1 Tut vvazhayetsya sho i 32 bitove bez znakove cile chislo a c1 c2 c3 ye deyaki konstanti U realizaciyi IBM c1 0xb7e15162 c2 0x243f6a88 yaki ye dvijkovij zapisom drobovoyi chastini e displaystyle e i p displaystyle pi vidpovidno c3 zminyuvalosya poki ne buli pidibrani S bloki z vidpovidnimi vlastivostyami SHA 1 pracyuye nad potokami danih i vikoristovuye pryamij poryadok bajt Vlastivosti S blokiv Diferencialni vlastivosti S blok ne povinen mistiti slova sho skladayutsya vsi 0 abo 1 Kozhni dva S bloku S 0 S 1 povinni vidriznyatisya odin vid odnogo yak minimum v 3 z 4 bajtah Tak yak vikonannya ciyeyi umovi dlya psevdovipadkovih S blokiv vkraj malojmovirno to odin z dvoh S blokiv modifikuyetsya S blok ne mistit dvoh elementiv S i S j i j displaystyle S i S j i neq j takih sho S i S j S i S j displaystyle S left i right S left j right S left i right S left j right abo S i S j displaystyle S left i right S left j right V S bloci ne isnuye dvoh par elementiv xor vidminnosti yakih rivni i dvoh par elementiv vporyadkovana riznicya yakih dorivnyuye Kozhni dva elementi S bloku povinni vidriznyatisya hocha b 4 bitami Vimoga 4 ne vikonuvalosya v realizaciyi IBM dlya AES ale bulo vipravleno vidrazu pislya finalu Bulo vidmicheno sho v S blokah prisutni nastupni elementi yaki superechat cij vimozi XOR Vidnimannya S 27 S 101 S 292 S 360 0 x 117 f 1 a 43 displaystyle S 27 oplus S 101 S 292 oplus S 360 0x117f1a43 S 13 S 138 S 364 S 297 0 x 75082 c 89 displaystyle S left 13 right S 138 S 364 S 297 0x75082c89 S 27 S 292 S 101 S 360 0 x 2 b 05 b 22 a displaystyle S 27 oplus S 292 S 101 oplus S 360 0x2b05b22a S 19 S 168 S 509 S 335 0 x 0 b 7 f c 4 b d displaystyle S left 19 right S 168 S 509 S 335 0x0b7fc4bd S 27 S 360 S 101 S 292 0 x 3 a 7 a a 869 displaystyle S 27 oplus S 360 S 101 oplus S 292 0x3a7aa869 S 49 S 97 S 142 S 392 0 x 725 c a 4 b e displaystyle S left 49 right S 97 S 142 S 392 0x725ca4be S 131 S 333 S 348 S 211 0 x c 73689 f e displaystyle S left 131 right S 333 S 348 S 211 0xc73689fe S 13 S 364 S 138 S 297 0 x 86 d e d c 7 c displaystyle S left 13 right S 364 S 138 S 297 0x86dedc7c S 131 S 348 S 333 S 211 0 x 22492124 displaystyle S left 131 right S 348 S 333 S 211 0x22492124 S 19 S 509 S 168 S 335 0 x 9 c e 0 e d 93 displaystyle S left 19 right S 509 S 168 S 335 0x9ce0ed93 S 49 S 142 S 97 S 392 0 x 5 d 91 f 03 a displaystyle S left 49 right S 142 S 97 S 392 0x5d91f03a Linijni vlastivosti Spivvidnoshennya zmishennya P r x p a r i t y S x 0 1 2 displaystyle left Pr x parity S x 0 1 2 right Neobhidno shob cej visliv bulo bilshe hocha b 1 32 displaystyle 1 32 Odnobitovih zsuv j P r x S x j 0 1 2 displaystyle forall j left Pr x S x j 0 1 2 right Neobhidno shob cej visliv bulo bilshe hocha b 1 30 displaystyle 1 30 Dvuhbitovij zsuv j P r x S x j S x j 1 0 1 2 displaystyle forall j left Pr x S x j oplus S x j 1 0 1 2 right Neobhidno shob cej visliv bulo bilshe hocha b 1 30 displaystyle 1 30 Odnobitovi korelyaciyi i j P r x S x j x i 1 2 displaystyle forall i j left Pr x S x j x i 1 2 right Neobhidno minimizuvati cej visliv sered usih mozhlivih S blokiv yaki zadovolnyayut poperednim punktam Rozshirennya klyucha procedura rozshirennya klyucha rozshiryuye zadanij masiv klyuchiv k sho skladayetsya z n 32 bitovih sliv de n cile chislo vid 4 do 14 v masiv K z 40 elementiv Vihidnij klyuch ne povinen dotrimuvatisya bud yakoyi strukturi Na dodatok procedura rozshirennya klyucha garantuye taki vlastivosti klyuchovogo slova vikoristovuvanogo pri peremnozhuvanni v kriptografichnomu yadri algoritmu Dva molodshih bita klyuchovogo slova budut zavzhdi odinicyami Zhodne z klyuchovih sliv ne mistitime desyat pospil jdut 0 abo 1 Opishemo algoritm rozshirennya klyucha Spochatku masiv k displaystyle k povnistyu perepisuyetsya v promizhnij masiv T displaystyle T sho skladayetsya z 15 elementiv T 0 n 1 k 0 n 1 T n n T n 1 14 0 displaystyle T 0 ldots n 1 k 0 ldots n 1 T n n T n 1 ldots 14 0 Dali cej proces povtoryuyetsya 4 razi Na kozhnij iteraciyi generuyutsya 10 sliv rozshirenogo klyucha j displaystyle j minliva vidobrazhaye potochnij nomer iteraciyi dlya pershoyi iteraciyi 0 dlya drugoyi 1 i t d Masiv T peretvoritsya za nastupnim pravilom i 0 14 T i T i T i 7 mod 15 T i 2 mod 15 l l l 3 4 i j 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 Dali mi peremishuyemo masiv T displaystyle T za dopomogoyu 4 raundiv Merezhi Fejstel 1 go tipu Povtoryuyemo chotiri razi nastupnu operaciyu T i T i S l o w 9 b i t s o f T i 1 mod 15 9 i 0 1 14 displaystyle T i T i S low 9 bits of T i 1 mod 15 lll 9 i 0 1 ldots 14 Dali beremo desyat sliv z masivu T i vstavlyayemo yih yak nastupnih desyati sliv v masiv K she raz peremishavshi K 10 j i T 4 i mod 15 i 0 1 9 displaystyle K 10j i T 4i mod 15 i 0 1 ldots 9 Ostatochno mi probigayemo po shistnadcyati slovami vikoristovuvanimi dlya peremnozhuvannya K 5 K 7 K 35 i modifikuyemo yih dlya togo shob voni vidpovidali dvom vlastivostyam opisanim vishe Zapisuyemo dva molodshih bita K i za formuloyu j K i 3 displaystyle j K i land 3 a potim zapisuyemo zamist cih dvoh bit odinici w K i 3 displaystyle w K i lor 3 Zbirayemo masku M dlya bitivw yaki nalezhat poslidovnostej z desyati i bilshe nuliv abo odinic Primirom M l 1 displaystyle M l 1 todi i tilki todi koli w l displaystyle w l nalezhit poslidovnosti z 10 abo bilshe odnakovih elementiv Todi mi skidayemo vistavlyayemo yih v 0 znachennya tih odinic M yaki znahodyatsya v kincyah nulovih abo odinichnih poslidovnostej a takozh tih odinic yaki znahodyatsya v starshomu ta molodshomu bitah Napriklad nehaj nashe slovo viglyadaye tak w 0 3 1 13 0 12 1011 displaystyle w 0 3 1 13 0 12 1011 viraz 0 i displaystyle 0 i abo zh 1 i displaystyle 1 i oznachaye sho 0 abo 1 budut povtoreni v slovi i raziv Todi maska M bude viglyadati nastupnim chinom 0 3 1 25 0 4 displaystyle 0 3 1 25 0 4 A znachit mi skidayemo biti v 4 15 16 28 poziciyah tobto M 0 4 1 11 001 10 0 5 displaystyle M 0 4 1 11 001 10 0 5 Dali dlya vipravlennya mi vikoristovuyemo tablicyu z chotiroh sliv B Vsi elementi tablici B pidibrani tak sho dlya nih i dlya vsih yih ciklichnih zrushen vikonuyetsya vlastivist sho v nih nemaye semi pospil jdut 0 abo 1 U realizaciyi IBM vikoristovuvalasya tablicya B 0 x a 4 a 8 d 57 b 0 x 5 b 5 d 193 b 0 x c 8 a 8309 b 0 x 73 f 9 a 978 displaystyle B left 0xa4a8d57b 0x5b5d193b 0xc8a8309b 0x73f9a978 right Dali vikoristovuyutsya dva zapisanih bita j dlya viboru slova z tablici B i vikoristovuyutsya molodshi p yat bit slova K i 1 dlya obertannya jogo elementiv p B j l l l l o w e s t 5 b i t s o f K i 1 displaystyle p B j lll lowest 5 bits of K i 1 Ostatochno robitsya XOR shablonu p na vihidne slovo pri obliku maski M K i w p M displaystyle K i w oplus p land M Varto zauvazhiti to sho 2 molodshih bita M ye 0 to dva molodshih bita pidsumkovogo slova budut odinicyami a vikoristannya tablici B dozvolyaye garantuvati sho v slovi ne bude 10 pospil jdut 0 abo 1Perevagi i nedoliki algoritmuShifr buv kandidatom AES pislya nevelikih zmin v hodi pershogo raundu konkursu pov yazanih zi zminoyu proceduri rozshirennya klyucha MARS uspishno projshov u final U finali konkursu u MARS buv vidilenij cilij ryad nedolikiv Skladna struktura Skladna geterogenna struktura algoritmu uskladnyuvala ne lishe jogo analiz ale i realizaciyu Realizaciya Vinikali problemi pri realizaciyi shifru na platformah yaki ne pidtrimuvali operaciyi 32 bitnogo mnozhennya i obertannya na dovilne chislo bit Obmezhenist resursiv Ne mozhlivist aparatno realizuvati algoritm pri malih resursah operativnoyi abo zh energonezalezhnij pam yati Zahist MARS viyavivsya pogano zahishena vid atak za chasom vikonannya i spozhivanoyi potuzhnosti Rozshirennya klyucha MARS girshe inshih finalistiv AES pidtrimuvav rozshirennya klyucha na lotu Rozparalelyuvannya Mozhna rozparaleliti lishe neveliku chastinu algoritmu Na vsi ci nedoliki ekspertna komisiya vidilila odne velike dostoyinstvo danogo algoritmu jogo simetrichnist Vihodyachi z vidilenih nedolikiv MARS ochikuvano ne stav peremozhcem AES Vidpovid analitikam AESPislya ogoloshennya rezultativ konkursu AES grupa tvorciv MARS vipustila svoyu recenziyu na ves konkurs U nij buli postavleni pid sumniv kriteriyi ocinki konkursu Voni vvazhali sho golovnoyu harakteristikoyu shifru povinna buti same nadijnist i jogo stijkist napriklad do atakam Krim togo voni vidpovili na kozhnu pretenziyu z boku zhuri do svogo algoritmu 1 MARS ne pidhodit dlya aparatnoyi realizaciyi Sered pretenzij do shifru buli jogo vazhka aparatna realizaciya yaka mogla sprichiniti za soboyu uskladnennya roboti Internetu a takozh vprovadzhennya velikih za svoyimi rozmirami shem Rozrobniki stverdzhuyut sho yih realizaciya zdatna pracyuvati zi shvidkistyu 1 28 Gbit sek sho ye prijnyatnim dlya internetu a vartist yih chipiv mozhe buti i visoka 13 za 12Gbit sek chip abo 1 za 1Gbit sek chip ale v majbutnomu yih cina znachno vpade 2 MARS ne pidhodit dlya realizaciyi na pristroyah z maloyu pam yattyu Dlya realizaciyi na SMART kartah ye u algoritmiv ye vsogo 128 bajt pam yati Dlya proceduri rozshirennya klyucha MARS vimagaye 512 bajt Rozrobniki vvazhayut sho nemaye prichini po yakij potribno realizovuvati AES na takomu vrazlivomu resursi z maloyu pam yattyu yak smart karti tomu sho vsi ci resursi mozhna prosto i shvidko pererobiti yih na sistemi z vidkritim klyuchem 3 MARS ne pidhodit dlya realizaciyi na MARS ne pidhodit dlya realizaciyi na platformah de ne dozvoleno obertannya zalezhat vid storonnih chinnikiv Rozrobniki vidznachayut sho cya problema ne ye fatalnoyu a vimagaye nebagato chasu dlya adaptaciyi algoritmu do ciyeyi platformi 4 Rozshirennya klyucha MARS ye duzhe vazhkoyu operaciyeyu Rozrobniki stverdzhuyut sho ce smishne tverdzhennya Voni stverdzhuyut sho u nih dotrimana idealna proporciya mizh dodatkovoyu pam yattyu na klyuch i propusknoyu zdatnistyu 25 bajt na klyuch U visnovku rozrobniki privodyat svij analiz algoritmiv uchasnikiv AES za rezultatami yakogo MARS poryad z Serpent buv najkrashim kandidatom na zvannya AES Analiz bezpeki algoritmuV danij chas nemaye efektivnih atak na danij algoritm Hocha u nogo ye kilka slabkih storin Pidklyuchi z velikoyu kilkistyu povtoryuvanih nuliv abo odinic mozhut privesti do efektivnih atak na MARS tak yak na yih pidstavi budut zgenerovani slabki pidklyuchi Dva molodshih bita sho vikoristovuyutsya pri peremnozhuvanni zavzhdi odinici Takim chinom zavzhdi ye dva vhidnih bita yaki nezminni v hodi procesu mnozhennya na klyuch a takozh dva vihidnih biti nezalezhnih vid klyucha Primitki PDF Arhiv originalu PDF za 16 travnya 2006 Procitovano 17 chervnya 2012 Etapi 3 i 4 nazivayutsya kriptografichnim yadrom algoritmu MARS Arhiv originalu za 23 travnya 2009 Procitovano 17 chervnya 2012 PosilannyaSpecifikaciya algoritmu AES versiya 19 listopada 2011 u Wayback Machine Vihidni teksti MARS 1248 na movi C Oficijna storinka shifru Opis problemi zgenerovanih S blokiv 23 travnya 2009 u Wayback Machine Komentari tvorciv shifru 16 travnya 2006 u Wayback Machine

Дата публікації:
Топ