CAST-256

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Алгоритм блочного шифрування
Назва: CAST-256
Розробник: канадська компанія Entrust Technologies
Створений: 1998 р.
Опублікований: 1998 р.
Розмір ключа: 128/160/192/224/256 біт
Розмір блоку: 128 біт
Число раундів: 48
Тип: Мережа Фейстеля

CAST-256 (або CAST6) в криптографії — блоковий алгоритм симетричного шифрування на основі мережі Фейстеля, опублікований у червні 1998 року у якості кандидата на участь в конкурсі AES. Алгоритм розроблений фахівцями канадської компанії Entrust Technologies.

Основні відомості[ред.ред. код]

Цей алгоритм заснований на більш ранньому алгоритмі 'CAST-128'. Обидва шифру побудовані на основі методології CAST, запропонованої Карлайлом Адамсом (англ. Carlisle Adams) і Стаффордом Таварес (англ. Stafford Tavares), перші дві букви імені яких формують назву методології. У створенні «дизайну» шифру брали участь також Хейз Говард і Майкл Вінер.

CAST-256 побудований з тих же елементів, що і CAST-128, включаючи S-бокси, але розмір блоку збільшено вдвічі і дорівнює 128 бітам. Це впливає на дифузійні властивості і захист шифру.

В RFC 2612 зазначено, що CAST-256 можна вільно використовувати в усьому світі в комерційних і некомерційних цілях.

Характеристики і структура алгоритму[ред.ред. код]

Алгоритм CAST 256
раундова функція CAST256

Алгоритм шифрує інформацію 128-бітними блоками і використовує кілька фіксованих розмірів ключа шифрування: 128, 160, 192, 224 або 256 бітів.

В алгоритмі CAST-256 48 раундів. Розглянемо першу половину шифру. 128-бітний вхідний блок може бути розділений на чотири 32-бітних субблока A in , B in , C in і D in . Субблок C in складається по модулю 2 з D in , видозміненого в залежності від раундової функції f. В результаті, отримуємо субблок D out . Після зсуву вхідних субблоків вправо на одну позицію, отримуємо чотири вихідних субблока: A out , B out , C out і D out . Для другої половини шифру розглядається зрушення субблоків на одну позицію вліво.

Нелінійні функції S j (де 1 <j <4) є підстановками з таблиці (S-бокс) 8x32 (в результаті, відбувається заміна 8-бітного вхідного значення на 32-бітове). Через нелінійну природу, S-функції є невід'ємною складовою безпеки шифру.

Операції «b», «c», і «d» являють собою операції додавання і віднімання, які виконуються з 32-бітними операндами по модулю  2 ^ {32} . Операція «a» представляє собою накладення вхідного 32-бітного субблока і 32-бітного підключа (який називається маскуючим підключеням). Ця операція, використовуючи одну з 3 операцій («b», «c», або «d»), виробляє обертання залежно від 5-бітного підключа (який називається підключем зсуву). Раундові функції CAST-256 відрізняються між раундами, тому що об'єднання операцій, що використовуються для «a», «b», «c» і «d», по-різному.

Математично, типова раундова функція виглядає наступним чином:

 W = ((K_ {m_i} + X_i) \ lll K_ {r_i}) ~ ~ ~ (1)
 Y_i = ((S_1 \left [W_1 \right] \oplus S_2 \left [W_2 \right]) + S_3 \left [W_3 \right]-S_4 \left [W_4 \right]

де X i представляє вхідні 32-біта даних, W j вхідні 8-біт даних в S j функції, K mi і K ri представляють маскує з'єднання і з'єднання зсуву відповідно, Y i , є вихідні 32-біт даних, після впливу раундової функції, « \oplus  »операції «+» і «-», являють собою додавання і віднімання відповідно по модулю 2. Позначення « V \ lll U » представляє лівий зсув V по відношенню до U. W, X i , Y i і K mi , всі вони являють собою 32-бітові субблоки. K ri має довжину 5 біт. Розшифрування здійснюється за аналогією з шифруванням, з тією лише різницею, що підключи використовуються в зворотній послідовності.

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

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

Зазначимо, що XOR операція не невирождена, так як тільки один біт з кожного субблока впливає на вихідний біт. При розгляді диференціальних властивостей CAST-256, отримуємо, що вихідний субблок D out у першому раунді залежить від всіх вхідних біт субблока D in . Вихідні біти субблоків A out , B out і C out не залежать від відповідних вхідних біт субблоків A in , B in і C in .

В результаті, отримуємо таблицю (таблиця № 1), яка показує залежність шифру даних на виході від зазначених раундів. Нехай чотирьом 32-бітовим вхідним субблокам A in , B in , C in і D in відповідають P 1 , P 2 , P 3 і P 4 .

Таблиця № 1: Залежність шифру від раунду[ред.ред. код]

Раунд
Залежності
1 P_3(P_4)
2 P_2(P_3, P_4)
3 P_1(P_2, P_3, P_4)
4 P_4(P_1, P_2, P_3, P_4)
5 P_3(P_1, P_2, P_3, P_4)
6 P_2(P_1, P_2, P_3, P_4)
7 P_1(P_1, P_2, P_3, P_4)


Після одного раунду біти, відповідні P 3 субблоки відкритого тексту тепер невирождені в біти перетвореного відкритого тексту субблока P 4 . Аналогічно після двох раундів субблок P 2 невирождений в біти перетворених P 3 і P 4 . Після 4 раундів субблок, відповідний субблоку P 4 , залежить від усіх біт всіх субблоків тексту. Після 7 раунду отримуємо повну залежність вихідних бітів від вхідних, так як всі чотири субблока P 1 , P 2 , P 3 і P 4 залежать від всіх біт перетвореного відкритого тексту.

Захист від лінійного криптоаналізу[ред.ред. код]

Лінійний криптоаналіз використовує побудову співвідношень між відкритим текстом, шифротекста і ключем, які справедливі з високою ймовірністю у раундовій функції повторного шифрування. Основним принципом лінійного криптоаналізу є пошук апроксимацій у вигляді:

 P_ {i_1} \oplus P_ {i_2} \oplus ... \oplus P_ {i_a} \oplus C_ {j_1} \oplus C_ {j_2} \oplus ... \oplus C_ {i_b} = K_ {k_1} \oplus K_ {k_2} \oplus ... \oplus K_ {k_c} ~ ~ ~ (2)

де i 1 , i 2 , ..., i a позиції біт відкритого тексту P, j 1 , j 2 , ..., j b позиції зашифрованого тексту C і k 1 , k 2 , ..., k c позиції ключа К. Ймовірність співвідношень для раундів шифру оцінюється наступним чином:

 | P_L - \frac {1} {2} | \leqslant 2 ^ {a-1} \cdot | p_B - \frac {1} {2} | ~ ~ ~ (3)

де p L ймовірність того, що лінійне вираз (2) виконано, p B ймовірність найкращою лінійної апроксимації будь S-функції, і a кількість S-функцій, що беруть участь в лінійному апроксимації. Стійкість до лінійного криптоаналізу строго залежить від загального лінійного вираження, що обмежує ймовірність (яке також називають «лінійної оболонкою»). Лінійні атаки будуються на основі лінійного вираження, що включає біти відкритого тексту і шифротекста (як показано в лівій частині (2)). У правій частині рівності (2) обчислюється XOR сума бітів ключа. Для цього потрібно, приблизно, наступне число відкритих текстів:

 N_L = | p_L - \frac {1} {2} | ^ {-2} ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ (4)

Найкращу лінійну апроксимацію визначає:

 | P_B - \frac {1} {2} | = \frac {2 ^ {m-1}-NL_min} {2 ^ {m}} ~ ~ ~ (5)

де m кількість біт вхідних текстів і NL min нелінійність S-функції. Для S-функцій CAST-256, m = 8 і NL min = 74. У кожному раунді вихідний біт даних раундової функції дорівнює XOR сумі всіх біт 4-х вхідних подблоків даних (кожен підблок розміром m). Тому лінійна апроксимація вихідних біт повинна складатися з лінійних апроксимацій біт всіх вхідних подблоков. На практиці ймовірність лінійних апроксимацій CAST-256 набагато більше 1/2.

Нехай для r-раундів шифру a = r. При r = 48, NL min = 74, число відомих відкритих текстів, яке потрібно для лінійного криптоаналізу, становить близько  2 ^ {122} . Зауважимо, що це майже дорівнює загальній кількості заданих відкритих текстів ( 2 ^ {128} ) і виступає практичності проти лінійного нападу на цей шифр.

Точнішу оцінку числа відкритих текстів, для лінійного криптоаналізу шифру CAST, можна отримати, розглядаючи об'єднання S-функцій в раундової функції. За рахунок об'єднання S-функцій в результаті XOR операції нелінійність NL min S-боксу (який складається з S-функцій) вище 74. Розглянемо 32х32 S-бокс, тоді m = 32 і а = r / 4 (так як ми апроксимируємо раундові функції кожен 4-й раунд). Таким чином, отримуємо число відкритих текстів, необхідних для лінійного криптоаналізу 48-раундового шифру, більш ніж  2 ^ {176} (більше ніж кількість заданих відкритих текстів). Експериментальні дані свідчать про те, що об'єднання S-функції, використовуючи такі операції, як додавання або віднімання, а не XOR, може збільшити нелінійність S-боксу ще більше.

Захист від диференціального криптоаналізу[ред.ред. код]

Диференціальний криптоаналіз заснований на вивченні перетворення різниць між шифрованими значеннями на різних раундах шифрування. Блокові шифри стійкі по відношенню до диференціального криптоаналізу, якщо в кожному раунді для заданих різниць вхідних відкритих текстів та вихідних шіфротекста існує єдина пара різниць. Такі відмінності називають характеристиками. Як правило, найефективніші відмінності в разі розгляду XOR двох блоків даних. У хорошому шифрі ймовірність всіх відмінностей повинна бути  2 ^ {-N} , де N розмір блоку. Для отримання загальної характеристики на вході і відповідної їй характеристики на виході XOR, складається ряд характеристик, які залежать від вхідних, вихідних даних, які зазнали операції XOR, в кожному раунді.

Аналіз тут заснований на припущеннях, що всі ключі раундів незалежні і, що вихід XOR (результат, отриманий після перетворення вхідних даних операцією XOR), відповідний конкретному входу XOR (вхідні дані), незалежні на різних раундах. При таких умовах, r-раундова характеристика представляється у вигляді:

 P_ {w_r} = \ prod_ {i = 1} ^ {r} p_i ~ ~ ~ (6)

де p i ймовірність різниць виходу XOR, відповідні різниці входу XOR в раунді i.

Шифр CAST-256 з R раундами, показаний у таблиці № 2, заснований на переборі 4-раудовой характеристики.

Таблиця № 2: Найкраща r-раундова характеристика R-раундового шифру[ред.ред. код]

(0, 0, 0, \Delta) [input ~XOR~ to~ round ~1]
0\leftarrow\Delta [round 1]
0\leftarrow0 [round 2]
0\leftarrow0 [round 3]
0\leftarrow0 [round 4]
(0, 0, 0, \Delta) [input ~XOR~ to~ round~ 5]
0\leftarrow\Delta [round 5]
0\leftarrow0 [round 6]
0\leftarrow0 [round 7]
0\leftarrow0 [round 8]
... repeat~ up ~to~ R/2 ~rounds
(0, 0, 0, \Delta) [input ~XOR~ to ~round~ R/2+1]
0\leftarrow\Delta [round R/2+1]
0\leftarrow0 [round R/2+2]
0\leftarrow0 [round R/2+3]
0\leftarrow0 [round R/2+4]
... repeat ~up~ to~ r~ rounds


XOR вектор (0, 0, 0,  \ Delta ) заданих різниць, для 4 вхідних 32-бітних субблоків, де 3 перших субблока (A in </ sub>, B in і C in ) мають нульові XOR різниці, а 4-й вхідний субблок (D in в раунді) має деяку відмінну від нуля XOR різницю,  \ Delta .

У таблиці показана характеристика загального R-раундового шифру, вхід XOR раунду R / 2 + 1 являє собою вектор, в якому різниця одного з субблоків не дорівнює нулю, а різниці інших трьох субблоків дорівнюють нулю. Вектор (0, 0, 0,  \Delta ), представлений в таблиці, відповідає шифру CAST-256 з R = 48.

Ненульова різниця на вході XOR відповідає нульової різниці виходу XOR кожен 4 раунд характеристики в таблиці № 2 (як показано в 1, 5 і т. д. раундах). Імовірність, з якою заданим різницями відкритих текстів і заданим різницями шіфротекста відповідає єдина пара різниць, для CAST  p \leqslant 2 ^ {-14} . Це засновано на тому факті, що всі чотири S-функції в раундової функції CAST ін'ектівни і XOR пари відкритих текстів і шіфротекста мають різниці, рівні 0. В результаті раундової функції, що використовує поєднання таких операцій, як додавання і віднімання, буде зменшена ймовірність існування пари різниць відкритих текстів і шіфротекста. Найкраща r-раунд характеристика, як показано в таблиці № 2 і на основі припущень, описаних вище, визначається ймовірністю:

 P_ {w_r} \leqslant (2 ^ {-14}) ^ {r / 4} ~ ~ ~ ~ (4)

Зокрема для 40-раундової характеристики (яка потенційно могла б бути використана для атаки 48-раундового шифру) ймовірність повинна бути менше або дорівнює  2 ^ {-140} . Отже, число обраних відкритих текстів, необхідних для цієї атаки, має бути більше, ніж  2 ^ {140} для 48-раундового шифру (істотно більше, ніж кількість відкритих текстів для 128-бітового розміру блоку).

Розширення ключа[ред.ред. код]

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

Процедура розширення ключа складніша ніж саме шифрування даних. Нехай масив ключів k = (ABCDEFGH) представляє собою 256-бітний блок, де фрагменти A, B, ..., H кожен довжиною по 32 біта. Нехай «k ← w i (k)», де w ( \cdot ) є функція розширення і представима в наступному вигляді:

 G = G \oplus f_1 (H, t_ {r_0}, t_ {m_0})
 F = F \oplus f_2 (G, t_ {r_1}, t_ {m_1})
 E = E \oplus f_3 (F, t_ {r_2}, t_ {m_2})
 D = D \oplus f_1 (E, t_ {r_3}, t_ {m_3})
 C = C \oplus f_2 (D, t_ {r_4}, t_ {m_4})
 B = B \oplus f_3 (C, t_ {r_5}, t_ {m_5})
 A = A \oplus f_1 (B, t_ {r_6}, t_ {m_6})
 H = H \oplus f_2 (A, t_ {r_7}, t_ {m_7})

В результаті 4 перетворень  k ^ {(i)} _r \leftarrow k по 5 молодших біта утворюються підключи зсуву:

 K ^ {(i)} _ {r_0} = 5LSB (A), k ^ {(i)} _ {r_1} = 5LSB (C), k ^ {(i)} _ {r_2} = 5LSB (E), k ^ {(i)} _ {r_3} = 5LSB (G)

де 5LSB (x) означає утворення 5 молодших біт в результаті операції x. Аналогічно  k ^ {(i)} _m \leftarrow k утворюються маскуючі підключи:

 K ^ {(i)} _ {m_0} = H, k ^ {(i)} _ {m_1} = F, k ^ {(i)} _ {m_2} = D, k ^ {( i)} _ {m_3} = B

Реалізація процедури розширення ключа[ред.ред. код]

У кожному раунді функції розширення ключа використовуються по 8 додаткових змінних  T ^ {(i)} mj і  T ^ {(i)} rj .

1. Ініціалізація

 Cm = 2 ^ {30} \sqrt {2} = 5A827999_16
 Mm = 2 ^ {30} \sqrt {3} = 6ED9EBA1_16
 Cr = 19
 Mr = 17

Нехай  T ^ {(i)} mj = Tmij,  T ^ {(i)} rj = Trij.

 for (i = 0; i <24; i + +) 
     for (j = 0; j <8; j + +) { 
                Tmij = Cm 
                Cm = (Cm + Mm) mod2 ^ 32 
                Trij = Cr 
                Cr = (Cr + Mm) mod32 
          } 

2. Ключ розширення:

K = ABCDEFGH = 256 біт вихідного ключа K. Нехай " k \leftarrow w_ {2_i} (k) "  ~ \sim ~ " W2i (k) ", " k \leftarrow w_ {2i +1} (k) " ~ \sim ~ "  W2i +1 (k) ","  k ^ { i} _r \leftarrow k " ~ \sim ~ "  kr ","  k ^ {i} _m \leftarrow k " ~ \sim ~ "  km "
 for (j = 0; j <12; j + +) { 
               W2i (k) 
               W2i +1 (k) 
               kr 
               km 
         } 

Якщо розмір ключа k менше 256 біт, то «зайві» фрагменти ключа вважаються нульовими:

 (| K | = 128) \rightarrow \, (E = F = G = H = 0)
 (| K | = 160) \rightarrow \, (F = G = H = 0)
 (| K | = 192) \rightarrow \, (G = H = 0)
 (| K | = 224) \rightarrow \, (H = 0)

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

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

Основними перевагами є:

  • Відсутність вразливостей.
  • Можливість швидкого виконання розширення ключа, тобто в процесі операції кодування, але не декодування.

В алгоритмі було знайдено ряд недоліків, через які він не увійшов до другого раунду конкурсу:

  • Швидкість шифрування алгоритму невисока в порівнянні з рядом алгоритмів - учасників конкурсу, в тому числі всіх фіналістів конкурсу.
  • Високі вимоги до оперативної і енергозалежною пам'яті.

Література[ред.ред. код]

  • Сергій Панасенко Алгоритми шифрування.

Посилання[ред.ред. код]