Алгоритми шифрування? фіналісти конкурсу AES. Частина 2

  1. структура алгоритму
  2. Процедура розширення ключа
  3. структура алгоритму
  4. Процедура розширення ключа

алгоритм MARS

Алгоритм MARS був розроблений колективом криптологів з корпорації IBM. Саме IBM свого часу розробила сімейство алгоритмів Lucifer, яке лягло в основу минулого стандарту шифрування США - DES. З авторів Lucifer в розробці алгоритму MARS взяв участь Дон Копперсміт (Don Coppersmith), відомий також і іншими роботами в області криптології.

За правилами конкурсу AES дозволялося вносити незначні зміни в які брали участь в конкурсі алгоритми протягом першого раунду конкурсу. Користуючись цим правилом, автори алгоритму MARS змінили процедуру розширення ключа, в результаті чого істотно знизилися вимоги, що пред'являються алгоритмом до незалежної і оперативної пам'яті [ 13 ]. Розглянемо тут саме модифіковану версію алгоритму.

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

Виходячи з двох наступних припущень [ 6 ]:

  1. Багато відомих криптоаналітичних методи відрізняють перший і останній раунди алгоритму (або кілька перших і / або декілька останніх раундів) від інших і застосовують до них інші прийоми, ніж до «центральним» раундів алгоритму. Таким чином, різні раунди алгоритму шифрування грають різне значення в забезпечується алгоритмом криптостойкости.
  2. Швидше за все, алгоритм з гетерогенною структурою буде краще протистояти криптоаналітичних методам майбутнього, ніж алгоритм, всі раунди якого ідентичні.

- розробники алгоритму MARS надали йому сильно гетерогенну структуру - раунди алгоритму дуже різняться між собою. Алгоритм MARS можна описати таким чином (див. Рис. 6):

Мал. 6. Структура алгоритму MARS.

  1. Попереднє накладення ключа: на 32-бітові субблоки A, B, C, D накладаються 4 фрагмента розширеного ключа k0 ... k3 операцією додавання по модулю 232.
  2. Виконуються 8 раундів прямого перемішування (без участі ключа шифрування).
  3. Виконуються 8 раундів прямого криптоперетворень.
  4. Виконуються 8 раундів зворотного криптоперетворень. Етапи 3 і 4 називаються «криптографічним ядром» алгоритму MARS.
  5. Виконуються 8 раундів зворотного перемішування, також без участі ключа шифрування.
  6. Фінальне накладення фрагментів розширеного ключа k36 ... k39 операцією віднімання по модулю 232.

Алгоритм являє собою розширену мережу Фейстеля. У кожному раунді виконується обробка одного з субблоков і накладення результатів обробки на інші субблоки, після чого субблоки міняються місцями. Конкретні перетворення залежать від типу раунду і будуть розглянуті нижче. Крім того, між раундами можуть виконуватися різні додаткові дії, які також будуть описані далі.

Мал. 7. Раунд прямого перемішування алгоритму MARS.

Раунд прямого перемішування показаний на рис. 7. Як видно з малюнка, в раунді виконуються наступні дії:

  1. Значення субблока A проганяється через таблицю замін S0 і накладається на субблок B операцією XOR.
  2. Початкове значення субблока A обертається на 8 біт вправо.
  3. Результат попереднього кроку обробляється таблицею замін S1 і знову накладається на субблок B операцією додавання по модулю 232.
  4. Результат кроку 2 обертається на 8 біт вправо.
  5. Результат попереднього кроку обробляється таблицею замін S0 і накладається на субблок З операцією додавання по модулю 232.
  6. Результат кроку 4 обертається на 8 біт вправо.
  7. Результат попереднього кроку обробляється таблицею замін S1 і накладається на субблок D операцією XOR.
  8. Субблоки міняються місцями, як показано на рис. 7.

Крім того, в деяких раундах прямого перемішування виконуються наступні додаткові операції (не наведено на рис. 7):

  1. В раундах 0 і 4 після кроку 7 виконується накладення значення субблока D на субблок A операцією додавання по модулю 232.
  2. В раундах 1 і 5 субблок B аналогічним чином накладається на субблок A.

За словами авторів алгоритму, ці операції істотно посилюють алгоритм MARS проти диференціального криптоаналізу.

Таблиці замін S0 і S1 визначені в специфікації алгоритму [ 6 ] наступним чином:

S0:

09D0C479 28C8FFE0 84AA6C39 9DAD7287 7DFF9BE3 D4268361 C96DA1D4 7974CC93 85D0582E 2A4B5705 1CA16A62 C3BD279D 0F1F25E5 5160372F C695C1FB 4D7FF1E4 AE5F6BF4 0D72EE46 FF23DE8A B1CF8E83 F14902E2 3E981E42 8BF53EB6 7F4BF8AC 83631F83 25970205 76AFE784 3A7931D4 4F846450 5C64C3F6 210A5F18 C6986A26 28F4E826 3A60A81C D340A664 7EA820C4 526687C5 7EDDD12B 32A11D1D 9C9EF086 80F6E831 AB6F04AD 56FB9B53 8B2E095C B68556AE D2250B0D 294A7721 E21FB253 AE136749 E82AAE86 93365104 99404A66 78A784DC B69BA84B 04046793 23DB5C1E 46CAE1D6 2FE28134 5A223942 1863CD5B C190C6E3 07DFB846 6EB88816 2D0DCC4A A4CCAE59 3798670D CBFA9493 4F481D45 EAFC5CA5 DB1129D6 B0449E20 0F5407FB 6167D9A8 D1F45763 4DAA96C3 3BEC5958 ABABA014 B6CCD201 38D6279F 02682215 8F376CD5 092C237E BFC56593 32889D2C 854B3E95 05BB5B43 7DCD5DCD A02E926C FAE527E5 36A1C330 3412E1AE F257F462 3C4F1D71 30A2E809 68E5F551 9C61BA44 5DED0AB8 75CE09C8 9654F93E 698C0CCA 243CB3E4 2B062B97 0F3B8D9E 00E050DF FC5D6166 E35F9288 C079550D 0591AEE8 8E531E74 75FE3578 2F6D829A F 60B21AE 95E8EB8D 6699486B 901D7D9B FD6D6E31 1090ACEF E0670DD8 DAB2E692 CD6D4365 E5393514 3AF345F0 6241FC4D 460DA3A3 7BCF3729 5BF1D1E0 14AAC070 1587ED55 3AFD7D3E D2F29E01 29A9D1F6 EFB10C53 CF3B870F B414935C 664465ED 024ACAC7 59A744C1 1D2936A7 DC580AA6 CF574CA8 040A7A10 6CD81807 8A98BE4C AССЕА063 C33E92B5 D1E0E03D B322517E 2092BD13 386B2C4A 52E8DD58 58656DFB 50820371 41811896 E337EF7E D39FB119 C97F0DF6 68FEA01B A150A6E5 55258962 EB6FF41B D7C9CD7A A619CD9E BCF09576 2672C073 F003FB3C 4AB7A50B 1484126A 487BA9B1 A64FC9C6 F6957D49 38B06A75 DD805FCD 63D094CF F51C999E 1AA4D343 B8495294 CE9F8E99 BFFCD770 C7C275CC 378453A7 7B21BE33 397F41BD 4E94D131 92CC1F98 5915EA51 99F861B7 C9980A88 1D74FD5F B0A495F8 614DEED0 B5778EEA 5941792D FA90C1F8 33F824B4 C4965372 3FF6D550 4CA5FEC0 8630E964 5B3FBBD6 7DA26A48 B203231A 04297514 2D639306 2EB13149 16A45272 532459A0 8E5F4872 F966C7D9 07128DC0 0D44DB62 AFC8D52D 06316131 D838E7CE 1BC41D00 3A2E8C0F EA83837E B984737D 13BA4891 C4F8B949 A6D6ACB3 A215CDCE 8359838 B 6BD1AA31 F579DD52 21B93F93 F5176781 187DFDDE E94AEB76 2B38FD54 431DE1DA AB394825 9AD3048F DFEA32AA 659473E3 623F7863 F3346C59 AB3AB685 3346A90B 6B56443E C6DE01F8 8D421FC0 9B0ED10C 88F1A1E9 54C1F029 7DEAD57B 8D7BA426 4CF5178A 551A7CCA 1A9A5F08 FCD651B9 25605182 E11FC6C3 B6FD9676 337B3027 B7C8EB14 9E5FD030

В якості вхідного значення S0 (аналогічно і S1) приймає 8 молодших біт вхідного слова. Таблиця змінює значення 0 на 09D0C479, значення 1 - на 28C8FFE0 і т. Д.

S1:

6B57E354 AD913CF7 7E16688D 58872A69 2C2FC7DF E389CCC6 30738DF1 0824A734 E1797A8B A4A8D57B 5B5D193B C8A8309B 73F9A978 73398D32 0F59573E E9DF2B03 E8A5B6C8 848D0704 98DF93C2 720A1DC3 684F259A 943BA848 A6370152 863B5EA3 D17B978B 6D9B58EF 0A700DD4 A73D36BF 8E6A0829 8695BC14 E35B3447 933AC568 8894B022 2F511C27 DDFBCC3C 006662B6 117C83FE 4E12B414 C2BCA766 3A2FEC10 F4562420 55792E2A 46F5D857 CEDA25CE C3601D3B 6C00AB46 EFAC9C28 B3C35047 611DFEE3 257C3207 FDD58482 3B14D84F 23BECB64 A075F3A3 088F8EAD 07ADF158 7796943C FACABF3D C09730CD F7679969 DA44E9ED 2C854C12 35935FA3 2F057D9F 690624F8 1CB0BAFD 7B0DBDC6 810F23BB FA929A1A 6D969A17 6742979B 74AC7D05 010E65C4 86A3D963 F907B5A0 D0042BD3 158D7D03 287A8255 BBA8366F 096EDC33 21916A7B 77B56B86 951622F9 A6C5E650 8CEA17D1 CD8C62BC A3D63433 358A68FD 0F9B9D3C D6AA295B FE33384A C000738E CD67EB2F E2EB6DC2 97338B02 06C9F246 419CF1AD 2B83C045 3723F18A CB5B3089 160BEAD7 5D494656 35F8A74B 1E4E6C9E 000399BD 67466880 B4174831 ACF423B2 CA815AB3 5A6395E7 302A67C5 8 BDB446B 108F8FA4 10223EDA 92B8B48B 7F38D0EE AB2701D4 0262D415 AF224A30 B3D88ABA F8B2C3AF DAF7EF70 CC97D3B7 E9614B6C 2BAEBFF4 70F687CF 386C9156 CE092EE5 01E87DA6 6CE91E6A BB7BCC84 C7922C20 9D3B71FD 060E41C6 D7590F15 4E03BB47 183C198E 63EEB240 2DDBF49A 6D5CBA54 923750AF F9E14236 7838162B 59726C72 81B66760 BB2926C1 48A0CE0D A6C0496D AD43507B 718D496A 9DF057AF 44B1BDE6 054356DC DE7CED35 D51A138B 62088CC9 35830311 C96EFCA2 686F86EC 8E77CB68 63E1D6B8 C80F9778 79C491FD 1B4C67F2 72698D7D 5E368C31 F7D95E2E A1D3493F DCD9433E 896F1552 4BC4CA7A A6D1BAF4 A5A96DCC 0BEF8B46 A169FDA7 74DF40B7 4E208804 9A756607 038E87C8 20211E44 8B7AD4BF C6403F35 1848E36D 80BDB038 1E62891C 643D2107 BF04D6F8 21092C8C F644F389 0778404E 7B78ADB8 A2C52D53 42157ABE A2253E2E 7BF3F4AE 80F594F9 953194E7 77EB92ED B3816930 DA8D9336 BF447469 F26D9483 EE6FAED5 71371235 DE425F73 B4E59F43 7DBE2D4E 2D37B185 49DC9A63 98C39D98 1301C9A2 389B1BBF 0C18588D A421C1BA 7AA3865C 71E08558 3C5CFCAA 7D239CA4 0297D9DD D7DC2830 4B37802B 7428AB54 AE EE0347 4B3FBB85 692F2F08 134E578E 36D9E0BF AE8B5FCF EDB93ECF 2B27248E 170EB1EF 7DC57FD6 1E760F16 B1136601 864E1B9B D7EA7319 3AB871BD CFA4D76F E31BD782 0DBEB469 ABB96061 5370F85D FFB07E37 DA50D0FB EBC977B6 0B98B40F 3A4D0FE6 DF4FC26B 159CF22A C298D6E2 2B78EF6A 61A94AC0 AB561187 14EEA0F0 DF0D4164 19AF70EE

Структура раунду прямого криптоперетворень приведена на рис. 8.

Мал. 8. Раунд прямого криптоперетворень алгоритму MARS.

Основою раунду є розширює криптоперетворень E, перетворює 32-бітове вхідний слово A в три вихідних 32-бітних значення, кожне з яких певним чином накладається на інші субблоки (див. Рис. 8). Після цього субблок A обертається вліво на 13 біт, потім субблоки міняються місцями аналогічно раунду прямого перемішування.

Перетворення E показано на рис. 9.

Мал. 9. Операція E алгоритму MARS.
Клацніть по картинці, щоб збільшити.

З вхідного значення формуються три потоки O1 ... O3, над якими проводяться наступні дії:

O2 = I,
O3 = O2 O2 = O2 + k2r + 4 mod 232,
O3 = O3 * k2r + 5 mod 232,
O3 = O3 O1 = S (O2),
O1 = O1 Å O3,
O2 = O23 ',
O3 = O3 O1 = O1 Å O3,
O1 = O13 ',

де I - вхідний значення,
r - номер поточного раунду, вважаючи з 0-го (при нумерації раундів в даному випадку враховуються тільки раунди кріптоядра алгоритму),
S - таблична заміна для операції E, являє собою об'єднання описаних вище таблиць S0 і S1; об'єднана таблиця містить 512 значень, вихідне значення вибирається за значенням 9 молодших біт вхідного слова.

Варто звернути увагу на те, що в перетворенні E використовуються операції обертання на змінне число біт; в цьому випадку запис O3 'позначає, що число біт обертання визначається значенням молодших п'яти біт поточного значення O3.

Структура зворотного кріптораунда показана на рис. 10.

Мал. 10. Раунд зворотного криптоперетворень алгоритму MARS.

Від прямого кріптораунда його відрізняє лише змінений порядок накладення вихідних значень перетворення E O1 ... O3 на слова B, C і D.

Мал. 11. Раунд зворотного перемішування алгоритму MARS.

Раунд зворотного перемішування (див. Рис. 11) більш істотно відрізняється від прямого. Фактично, зворотне перемішування виконує зворотні операції в зворотній послідовності (див. Рис. 7 і 11):

  1. Значення субблока A проганяється через таблицю замін S1 і накладається на субблок B операцією XOR.
  2. Початкове значення субблока A обертається на 8 біт вліво.
  3. Результат попереднього кроку обробляється таблицею замін S0 і накладається на субблок C операцією віднімання по модулю 232.
  4. Результат кроку 2 обертається на 8 біт вліво.
  5. Результат попереднього кроку обробляється таблицею замін S1 і накладається на субблок D операцією віднімання по модулю 232.
  6. Результат кроку 4 обертається на 8 біт вліво.
  7. Результат попереднього кроку обробляється таблицею замін S0 і накладається на субблок D операцією XOR.
  8. Субблоки міняються місцями, як показано на рис. 11.

Аналогічно прямому перемішуванню, в деяких раундах виконуються наступні додаткові операції, не показані на рис. 11:

  1. В раундах 1 і 5 після кроку 7 виконується накладення значення субблока A на субблок B операцією віднімання по модулю 232.
  2. В раундах 2 і 6 субблок C аналогічним чином накладається на субблок B.

Розшифрування виконується застосуванням зворотних операцій в зворотній послідовності; детально розшифрування описано в специфікації алгоритму [ 6 ].

Процедура розширення ключа

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

  1. Формується тимчасовий масив T0 ... T14:

    T0 = KI0,
    T1 = KI1,
    ...
    Tn-1 = KIn-1,
    Tn = n,
    Tn + 1 = Tn + 2 = ... = T14 = 0,

    де KI0 ... KIn-1 - повернути ключ шифрування,
    n - його розмір в 32-бітових словах - від 4 до 14 включно.

  2. Даний крок повторюється 4 рази (кожна ітерація дає 10 обчислених фрагментів розширеного ключа) і містить наступні операції:
  3. Накладення на обчислені підключи додаткових вимог, які перебувають в наступному:
    1. Кожен підключ, який використовується для множення в операції E (тобто підключи з непарними індексами від k5 до k35 включно), повинен мати непарне значення. Мало того, одиничними повинні бути два молодших біта підключа, а не один.
    2. Ті ж підключи не повинні містити 10 нульових або 10 одиничних біт поспіль.
    Модифікація подключей відповідно до даних вимог виконується в такий спосіб:
    1. 2 молодших біти оброблюваного підключа встановлюються в поодинокі значення; старе значення запам'ятовується у змінній j (воно буде використано згодом). Результуюче значення підключа позначається як W.
    2. Обчислюється 32-бітна маска M, яка буде використана для модифікації підключа - для забезпечення відсутності в ньому 10 поспіль нульових або одиничних біт. Маска обчислюється таким чином:
      A) Встановлюються в 1 біти M, відповідні тим бітам оброблюваного підключа, які входять в послідовності з 10 нульових або 10 одиничних біт. Решта біти встановлюються в 0.
      B) обнуляє ті поодинокі біти маски M, які відповідають будь-якому з умов:

      ii = 31,
      Wi! = Wi-1,
      Wi! = Wi + 1,

      де i - номер біта, починаючи з 0, а Wi - значення i -го біта.
    3. Використовується таблиця коригувальних значень B, певна в такий спосіб:

      B0 = A4A8D57B,
      B1 = 5B5D193B,
      B2 = C8A8309B,
      B3 = 73F9A978.


      Елементи таблиці B еквівалентні елементам з 265-го по 268-й включно об'єднаної таблиці S; саме ці елементи використовуються для корекції подключей завдяки їх специфічним властивостям.
      За допомогою даної таблиці наступним чином обчислюється фінальне значення підключа Ki:

      Ki = W Å ((Bji-1) & M),

      де & - логічна побітова операція «і», а обертання Bj визначається п'ятьма молодшими бітами попереднього підключа Ki-1.

Описана процедура гарантує необхідні властивості у подключей [ 6 ] .Алгорітм RC6

Алгоритм RC6 був розроблений в 1998 р поруч фахівців наукового підрозділу відомої фірми RSA Data Security - RSA Laboratories: Рональдом Ривестом (Ronald Rivest, засновник RSA Data Security), Меттом Робшоу (Matt Robshaw), Реєм Сідні (Ray Sidney) і Іква Лайзой Ін (Yiqun Lisa Yin) спеціально для участі в конкурсі AES [ 17 ]. Алгоритм багато в чому успадкував риси попереднього алгоритму Рональда Ривеста - 64-бітного блочного шифру RC5, розробленого в 1997 р (докладний опис RC5 російською мовою можна знайти в [ 19 ]). Фактично, алгоритм зазнав дві принципові зміни:

  • на відміну від RC5, в алгоритмі використовується множення по модулю 232;
  • для збереження 32-бітових обчислень замість розбиття шифруемого блоку даних (128 біт згідно принципового вимогу конкурсу AES) на два 64-бітних субблока виконується його розбиття на 4 32-бітових субблока і їх обробка за кілька зміненою схемою [ 17 ].

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

Як і алгоритм RC5, RC6 має гнучку структуру: крім секретного ключа, параметрами алгоритму є наступні:

  • розмір слова w; RC6 шифрує блоками по 4 слова;
  • кількість раундів алгоритму R;
  • розмір секретного ключа в байтах b.

Аналогічно RC5, для уточнення параметрів алгоритму, використовуваних в його конкретної реалізації, застосовується позначення RC6- w / R / b. Оскільки в конкурсі AES 128-біт блок є обов'язковим, значення w фіксоване і дорівнює 32. У специфікації алгоритму [ 14 ] Фіксується також кількість раундів: R = 20. Оскільки конкурс AES передбачає використання трьох фіксованих розмірів ключів, розглянемо три наступні варіанти алгоритму: RC6-32 / 20/16, RC6-32 / 20/24 і RC6-32 / 20/32, сукупність яких і буде матися на увазі далі під назвою «RC6».

Структура алгоритму представлена ​​на рис. 12.

Мал. 12. Структура алгоритму RC6.
Клацніть по картинці, щоб збільшити.

Як було сказано вище, в алгоритмі використовується 20 раундів перетворень, перед якими виконується часткове вхідний відбілювання:

B = B + K0 mod 232,
D = D + K1 mod 232,

де A, B, C, D - поточні значення оброблюваних 32-бітних субблоков,
K0 ... K43 - фрагменти розширеного ключа.

Аналогічним чином виконується часткове вихідний відбілювання:

A = A + K42 mod 232,
C = C + K43 mod 232.

У кожному раунді алгоритму виконуються наступні дії:

t1 = f (B) t2 = f (D) A = ((A Å t1) 2) + K2i mod 232,
C = ((C Å t2) 1) + K2i + 1 mod 232,

де t1 і t2 - тимчасові змінні,
кількість біт обертання на змінне число біт визначається значенням 5 молодших біт параметра (t1 або t2),
функція f () виконує наступне квадратичне перетворення:

f (x) = x * (2x + 1) mod 232.

В кінці кожного раунду виконується зрушення субблоков - см. Рис. 12.

При розшифрування підключи використовуються в зворотному порядку, накладення подключей замість складання по модулю 232 виконується відніманням, а також зрушення субблоков виконується на початку раунду і в зворотний бік. Перетворення f () не зазнало змін (див. Рис. 13).

Мал. 13. Розшифрування алгоритмом RC6.
Клацніть по картинці, щоб збільшити.

Процедура розширення ключа

Процедура розширення ключа RC6 аналогічна RC5, за винятком того, що RC6 потрібно істотно більше згенерованих подключей, а саме 2 R +4, тобто K0 ... K43 для 20 раундів. Розглянемо цю процедуру для алгоритму RC6 в варіанті для конкурсу AES, тобто з зазначеними вище фіксованими параметрами.

Розширення ключа виконується в два етапи:

  1. Ініціалізація масиву розширених ключів K0 ... K43, яка виробляється в такий спосіб:

    K0 = P32,
    Ki + 1 = Ki + Q32 mod 232,

    де P32 і Q32 - псевдовипадкові константи, утворені шляхом множення на 232 дробової частини і подальшого округлення до найближчого непарного цілого двох математичних констант (e і f відповідно):

    P32 = B7E15163,
    Q32 = 9E3779B9,

    Автори алгоритму в його специфікації [ 14 ] Стверджують, що вибір даних значень не є важливим. Відповідно, аналогічно описаному вище алгоритму Twofish-FK, при необхідності створення реалізації алгоритму RC6, не сумісною зі стандартною, слід змінити значення P32 і Q32.
  2. Циклічно виконуються наступні дії:

    A = Ki = (Ki + A + B mod 232) B = KIj = (KIj + A + B mod 232) i = i + 1 mod 44,
    j = j + 1 mod c,

    де i, j, A і B - тимчасові змінні, їх початкові значення рівні нулю,
    KI - повернути ключ шифрування, представлений у вигляді c 32-бітних слів.
    Виконується 3c ітерацій циклу.
Переваги та недоліки алгоритмів-фіналістів

Результати виконаної аналітиками роботи з вивчення алгоритмів-фіналістів NIST сформулював у вигляді звіту [ 12 ]. Даний звіт містить як результати аналізу алгоритмів, так і обгрунтування критеріїв, за якими виконувалася оцінка. Автор даної статті дозволив собі на основі звіту [ 12 ] Коротко сформулювати порівняльні оцінки п'яти алгоритмів-фіналістів конкурсу AES за основними критеріями у вигляді такої таблиці:

№ Категорія Serpent Twofish MARS RC6 Rijndael 1 Крипостійкість + + + + + 2 Запас криптостойкости ++ ++ ++ + + 3 Швидкість шифрування при програмної реалізації - ± ± + + 4 Швидкість розширення ключа при програмної реалізації ± - ± ± + 5 ​​Смарт -карти з великим об'ємом ресурсів + + - ± ++ 6 Смарт-карти з обмеженим обсягом ресурсів ± + - ± ++ 7 Апаратна реалізація (ПЛІС) + + - ± + 8 Апаратна реалізація (спеціалізована мікросхема) + ± - - + 9 захист від атак за часом виконання і споживаної потужності 3 + ± - - + 10 Захист від атак по споживаної потужності на процедуру розширення ключа ± ± ± ± - 11 Захист від атак по споживаної потужності на реалізації в смарт-картах ± + - ± + 12 Можливість розширення ключа «на льоту» + + ± ± ± 13 Наявність варіантів реалізації (без втрат в сумісності) + + ± ± + 14 Можливість паралельних обчислень ± ± ± ± +

Варто прокоментувати деякі рядки наведеної таблиці:

  1. Крипостійкість всіх алгоритмів-фіналістів виявилася достатньою - в процесі досліджень не було виявлено будь-яких реально реалізованих атак на повноцінні і полнораундовие версії алгоритмів. В даному випадку криптоаналитики зазвичай досліджують варіанти алгоритмів з усіченим числом раундів, або з деякими внесеними змінами, незначними, але ослабляють алгоритм. Під запасом криптостойкости (security margin) експерти NIST мають на увазі співвідношення повного (передбаченого в специфікаціях алгоритмів) числа раундів і максимального з тих варіантів, проти яких діють будь-які криптоаналітичних атаки. Наприклад, за допомогою диференційно-лінійного криптоаналізу розкривається 11-раундовий Serpent [ 5 ], Тоді як в оригінальному алгоритмі виконується 32 раунду. Експерти NIST в звіті [ 12 ] Попередили, що дана оцінка є дуже поверхневою і не може бути значущою при виборі алгоритму-переможця конкурсу, але, тим не менше, відзначили, що запас криптостойкости у Rijndael і RC6 трохи нижче, ніж у інших алгоритмів-фіналістів.
  2. В пп. 5-8 наведено порівняльну оцінку можливості та ефективності реалізації алгоритмів в перерахованих пристроях.
  3. В пп. 9-11 мається на увазі, наскільки операції, виконувані конкретним алгоритмом, можуть бути схильні до аналізу зазначеним методом. При цьому приймалося до уваги те, що операції можуть бути модифіковані з метою ускладнення криптоанализа за рахунок втрати в швидкості шифрування (наприклад, проблемне в цьому сенсі обертання на змінне число біт може примусово виконуватися за рівне число тактів - тобто максимально можливе для даної операції; саме такі заходи протидії атакам по часу виконання і споживаної потужності рекомендує їх винахідник Пол Кохер (Paul C. Kocher) [ 11 ]).
  4. З описів алгоритмів видно, що всі вони підтримують розширення ключа «на льоту» (тобто підключи можуть генеруватися безпосередньо в процесі шифрування - в міру необхідності), однак, тільки Serpent і Twofish підтримують таку можливість без будь-яких обмежень.
  5. Під наявністю варіантів реалізації (implementation flexibility) мається на увазі можливість різним чином реалізовувати будь-які операції алгоритму з оптимізацією під конкретні цілі. Найбільш показовими в цьому сенсі є згадані раніше варіанти процедури розширення ключа алгоритму Twofish [ 16 ], Що дозволяють оптимізувати реалізацію алгоритму в залежності, насамперед, від частоти зміни ключа.

Сформулюємо основні переваги та недоліки кожного з розглянутих в даній статті алгоритмів-фіналістів [ 12 ]:

Алгоритм Переваги Недоліки Serpent
  1. Проста структура алгоритму полегшує його аналіз з метою знаходження можливих вразливостей.
  2. Serpent ефективно реалізуємо апаратно і в умовах обмежених ресурсів.
  3. Serpent легко модифікується з метою захисту від атак з часу виконання і споживаної потужності (проте, за рахунок зниження швидкості).
  1. Є найповільнішим з алгоритмів-фіналістів в програмних реалізаціях.
  2. Процедури шифрування і розшифрування абсолютно різні, тобто вимагають роздільної реалізації.
  3. Розпаралелювання обчислень при шифруванні алгоритмом Serpent піддається реалізації з обмеженнями.
Twofish
  1. Twofish ефективно реалізуємо апаратно і в умовах обмежених ресурсів.
  2. Зашифрування і розшифрування в алгоритмі Twofish практично ідентичні.
  3. Є кращим з алгоритмів-фіналістів з точки зору підтримки розширення ключа «на льоту».
  4. Кілька варіантів реалізації дозволяють оптимізувати алгоритм для конкретних застосувань.
  1. Складність структури алгоритму ускладнює його аналіз.
  2. Складна і повільна процедура розширення ключа.
  3. Щодо складно захищається від атак за часом виконання і споживаної потужності.
  4. Розпаралелювання обчислень при шифруванні алгоритмом Twofish піддається реалізації з обмеженнями.
MARS Зашифрування і розшифрування в алгоритмі MARS практично ідентичні.
  1. Виключно складна структура алгоритму з раундами різних типів ускладнює як аналіз алгоритму, так і його реалізацію.
  2. Виникають проблеми при програмної реалізації на тих платформах, які не підтримують 32-бітове множення і обертання на змінне число біт.
  3. Алгоритм MARS не може бути ефективно реалізований апаратно і в умовах обмежених ресурсів.
  4. Складно захищається від атак за часом виконання і споживаної потужності.
  5. MARS гірше інших алгоритмів-фіналістів підтримує розширення ключів «на льоту».
  6. Розпаралелювання обчислень при шифруванні алгоритмом MARS піддається реалізації з обмеженнями.
RC6
  1. Проста структура алгоритму полегшує його аналіз. Крім того, алгоритм успадкував частину перетворень від свого попередника - алгоритму RC5, ретельно проаналізованого до конкурсу AES.
  2. Найшвидший з алгоритмів-фіналістів на 32-бітних платформах.
  3. Зашифрування і розшифрування в алгоритмі RC6 практично ідентичні.
  1. Швидкість шифрування при програмної реалізації сильно залежить від того, чи підтримує платформа 32-бітове множення і обертання на змінне число біт.
  2. RC6 складно реалізуємо апаратно і в умовах обмежених ресурсів.
  3. Досить складно захищається від атак за часом виконання і споживаної потужності.
  4. Недостатньо повно підтримує розширення ключів «на льоту».
  5. Розпаралелювання обчислень при шифруванні алгоритмом RC6 піддається реалізації з обмеженнями.
Висновок

Як відомо, проаналізувавши результати всіх досліджень, експерти вибрали в якості стандарту AES алгоритм Rijndael. Що не виглядає дивним - в таблиці з характеристиками алгоритмів чітко видно, що практично за всіма параметрами Rindael, як мінімум, не поступається іншим алгоритмам-фіналістам.

Що стосується алгоритмів Serpent, Twofish, MARS і RC6, то видно, що вони практично рівнозначні за сукупністю характеристик, за винятком алгоритму MARS, має значно більше недоліків, в тому числі, алгоритм практично не реалізовується в умовах обмежених ресурсов.Література, джерела

  1. AES Round 1 Information. // http://csrc.nist.gov - January 26, 2001..
  2. Anderson R., Biham E. Two Practical and Provably Secure Block Ciphers: BEAR and LION. // http://citeseer.ist.psu.edu - 1995.
  3. Anderson R., Biham E., Knudsen L. Serpent: A Proposal for the Advanced Encryption Standard. // http://csrc.nist.gov .
  4. Announcing Request for Candidate Algorithm Nominations for the Advanced Encryption Standard (AES). // http://csrc.nist.gov - Department of Commerce - National Institute of Standards and Technology - Federal Register: September 12, 1997..
  5. Biham E., Dunkelman O., Keller N. Differential-Linear Cryptanalysis of Serpent. // http://citeseer.ist.psu.edu - Technion, Haifa, Israel.
  6. Burwick C., Coppersmith D., D'Avignon E., Gennaro R., Halevi S., Jutla C., Matyas SMJr., O'Connor L., Peyravian M., Safford D., Zunic N. MARS - a candidate cipher for AES. // http://www.ibm.com - IBM Corporation - Revised, September, 22 1999.
  7. Courtois N., Castagnos G., Goubin L. What do DES S-boxes Say to Each Other? // http://eprint.iacr.org - Axalto Cryptographic Research & Advanced Security, Cedex, France.
  8. Daemen J., Knudsen L., Rijmen V. The Block Cipher Square. // http://www.esat.kuleuven.ac.be .
  9. FIPS 46-3. Data Encryption Standard (DES). // http://csrc.nist.gov - Reaffirmed 1999 October 25.
  10. FIPS 81. DES Modes of Operation. // http://csrc.nist.gov - 1980 December 2.
  11. Kocher PC Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. // http://citeseer.ist.psu.edu - Cryptography Research, Inc., San Francisco, USA.
  12. Nechvatal J., Barker E., Bassham L., Burr W., Dworkin M., Foti J., Roback E. Report on the Development of the Advanced Encryption Standard (AES). // http://csrc.nist.gov - National Institute of Standards and Technology.
  13. Nechvatal J., Barker E., Dodson D., Dworkin M., Foti J., Roback E. Status report on the first round of the development of the advanced encryption standard. // http://csrc.nist.gov - National Institute of Standards and Technology.
  14. Rivest RL, Robshaw MJB, Sidney R., Lin YL The RC6 Block Cipher. // http://www.rsasecurity.com - Version 1.1 - August 20, 1998..
  15. Schneier B. Description of a new variable-length key 64-bit block cipher (blowfish). // http://www.schneier.com .
  16. Schneier B., Kelsey J., Whiting D., Wagner D., Hall C., Ferguson N. Twofish: A 128-bit Block Cipher. // http://www.schneier.com - 15 June 1998.
  17. What are RC5 and RC6? // http://www.rsasecurity.com .
  18. Панасенко С. Алгоритм шифрування DES і його варіанти. // Connect! Світ зв'язку. - 2006 - №№ 3-6.
  19. Панасенко С. Цікаві алгоритми шифрування, частина 2. // BYTE / Росія. - 2006 - № 5 - с. 74-79.
  20. Панасенко С.П., Батура В.П. Основи криптографії для економістів: навчальний посібник. Під ред. Л.Г. Гагаріної. - М .: Фінанси і статистика, 2005 - 176 с.
  21. Соколов О.В., Шаньгина В.Ф. Захист інформації в розподілених корпоративних мережах і системах. - М .: ДМК Пресс, 2002 - 656 с.
  22. Шнайер Б. Прикладна криптографія. Протоколи, алгоритми, вихідні тексти на мові Сі. - Пер. з англ .: М .: Видавництво ТРІУМФ, 2002 - 816 с.

What do DES S-boxes Say to Each Other?