CAST-256

CAST-256
Розробники	канадська компанія Entrust Technologies
Уперше оприлюднений	1998 р.
Раундів	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 можна вільно використовувати в усьому світі в комерційних і некомерційних цілях.

Характеристики і структура алгоритму

Алгоритм шифрує інформацію 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})\ lllK_{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\ lllU$ » представляє лівий зсув 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 ₁, P ₂, P ₃ і P ₄.

Таблиця № 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 ₃ субблоки відкритого тексту тепер невирождені в біти перетвореного відкритого тексту субблока P ₄. Аналогічно після двох раундів субблок P ₂ невирождений в біти перетворених P ₃ і P ₄. Після 4 раундів субблок, відповідний субблоку P ₄, залежить від усіх біт всіх субблоків тексту. Після 7 раунду отримуємо повну залежність вихідних бітів від вхідних, так як всі чотири субблока P ₁, P ₂, P ₃ і P ₄ залежать від всіх біт перетвореного відкритого тексту.

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

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

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 ₁, i ₂, ..., i _a позиції біт відкритого тексту P, j ₁, j ₂, ..., j _b позиції зашифрованого тексту C і k ₁, k ₂, ..., 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_{m}in}{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$	$[round1]$
$0\leftarrow 0$	$[round2]$
$0\leftarrow 0$	$[round3]$
$0\leftarrow 0$	$[round4]$
(0, 0, 0, $\Delta$ )	$[input~XOR~to~round~5]$
$0\leftarrow \Delta$	$[round5]$
$0\leftarrow 0$	$[round6]$
$0\leftarrow 0$	$[round7]$
$0\leftarrow 0$	$[round8]$
$...$	$repeat~up~to~R/2~rounds$
(0, 0, 0, $\Delta$ )	$[input~XOR~to~round~R/2+1]$
$0\leftarrow \Delta$	$[roundR/2+1]$
$0\leftarrow 0$	$[roundR/2+2]$
$0\leftarrow 0$	$[roundR/2+3]$
$0\leftarrow 0$	$[roundR/2+4]$
$...$	$repeat~up~to~r~rounds$

XOR вектор (0, 0, 0, $\ Delta$ ) заданих різниць, для 4 вхідних 32-бітних субблоків, де 3 перших субблока (A _in, 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_{r}^{(i)}\leftarrow k$ по 5 молодших біта утворюються підключи зсуву:

K_{r_{0}}^{(i)}=5LSB(A),k_{r_{1}}^{(i)}=5LSB(C),k_{r_{2}}^{(i)}=5LSB(E),k_{r_{3}}^{(i)}=5LSB(G)

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

K_{m_{0}}^{(i)}=H,k_{m_{1}}^{(i)}=F,k_{m_{2}}^{(i)}=D,k_{m_{3}}^{(i)}=B

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

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

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

Cm=2^{30}{\sqrt {2}}=5A827999_{1}6

Mm=2^{30}{\sqrt {3}}=6ED9EBA1_{1}6

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_{r}^{i}\leftarrow k

"

~\sim ~

"

kr

","

k_{m}^{i}\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 шифру.

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

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

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

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

Література

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

Посилання

RFC 2612 [Архівовано 1 липня 2012 у Wayback Machine.]
The CAST-256 Encryption Algorithm Carlisle Adams
~ howard/PAPERS/cast256.pdf An Analysis of the CAST-256 Cipher [Архівовано 5 серпня 2014 у Wayback Machine.]
Конкурс AES [Архівовано 30 січня 2012 у Wayback Machine.]

п о р Блокові алгоритми шифрування
SP-мережа, блок 64 біт : SAFER \| SHARK
Мережа Файстеля, блок 64 біт : ГОСТ 28147-89 (Magma) \| 3-DES \| Blowfish \| DES \| FEAL \| IDEA \| KASUMI \| RC5 \| TEA
SP-мережа, блок від 128 біт : Калина \| AES \| Anubis \| CRYPTON \| Hierocrypt-3 \| Kuznechik \| PRESENT \| SQUARE \| Serpent \| Threefish
Мережа Файстеля, блок від 128 біт : Camellia \| CAST-256 \| MARS \| RC6 \| Sinople \| Twofish