CRYPTON

Алгоритм Crypton являє 128-бітовий блок шифруємих даних у вигляді байтового масиву 4×4, над якими в процесі шифрування проводиться кілька раундів перетворень. У кожному раунді передбачається послідовне виконання наступних операцій:

• Таблична заміна ${\displaystyle \gamma }$;
• Лінійне перетворення ${\displaystyle \pi }$;
• Байтова перестановка ${\displaystyle \tau }$;
• Операція ${\displaystyle \sigma }$.

Таблична заміна ${\displaystyle \gamma }$

Алгоритм Crypton використовує 4 таблиці замін. Кожна з яких заміщає 8-бітне вхідне значення на вихідне такого ж розміру.

Обчислення похідних таблиць замін (<<n - є циклічне зрушення вліво значення оброблюваного байта на n бітів)

Всі таблиці ${\displaystyle S_{0}...S_{3}}$ є похідними від основної таблиці ${\displaystyle S}$ (див. рисунок — обчислення похідних таблиць замін).

Нижче представлений приклад таблиць: Таблиця ${\displaystyle S_{0}}$:

Таблиця ${\displaystyle S_{1}}$

Таблиця ${\displaystyle S_{2}}$

Таблиця ${\displaystyle {\displaystyle S_{3}}}$:

У парних раундах використовується операція ${\displaystyle \gamma _{e}}$в непарних — ${\displaystyle \gamma _{o}}$. Ці операції і таблиці замін вволодіють рядом якостей, які є важливі, особливо для уніфікації операцій шифрування і розшифрування. Властивості таблиць і операцій:

${\displaystyle \gamma _{e}(\gamma _{o}(A))=\gamma _{o}(\gamma _{e}(A))=A;}$

${\displaystyle S^{-1}=S;}$

${\displaystyle S_{2}=S_{0}^{-1}4;}$

${\displaystyle S_{3}=S_{1}^{-1};}$

де ${\displaystyle A}$ — поточне значення блоку шифруємих даних. Операції ${\displaystyle \gamma _{e}}$ і ${\displaystyle \gamma _{o}}$ можна визначити наступним чином:

${\displaystyle \gamma _{e}:b_{ij}=S_{(j+2+imod4)}(a_{ij});}$

${\displaystyle \gamma _{o}:b_{ij}=S_{(j+imod4)}(a_{ij}).}$

де:

${\displaystyle a_{ij}}$— поточне значення конкретного байта даних;${\displaystyle b_{ij}}$${\displaystyle b_{ij}}$

${\displaystyle b_{ij}}$— значення байта даних після виконання операції;

Лінійне перетворення

Тут використовується 4 спеціальні константи, шістнадцяткові значення яких наведені нижче:

${\displaystyle {\displaystyle m_{0}=FC;}}$

${\displaystyle {\displaystyle m_{1}=F3;}}$

${\displaystyle {\displaystyle m_{2}=CF;}}$

${\displaystyle m_{3}=3F;}$

Ці константи об'єднані в маскуючі послідовності, наведені нижче:

${\displaystyle {\displaystyle M_{0}=m_{3}\bullet m_{2}\bullet m_{1}\bullet m_{0};}}$

${\displaystyle {\displaystyle M_{1}=m_{0}\bullet m_{3}\bullet m_{2}\bullet m_{1};}}$

${\displaystyle {\displaystyle M_{2}=m_{1}\bullet m_{0}\bullet m_{3}\bullet m_{2};}}$

${\displaystyle M_{3}=m_{2}\bullet m_{1}\bullet m_{0}\bullet m_{3};}$

де ${\displaystyle \bullet }$ — операція конкатенації.

Сама ж операція ${\displaystyle \pi }$ — являє собою бітову перестановку. У непарних раундах використовується операція ${\displaystyle \pi _{o}}$:

${\displaystyle B[0]=(A[3]\&M_{3})\oplus (A[2]\&M_{2})\oplus (A[1]\&M_{1})\oplus (A[0]\&M_{0});}$

${\displaystyle B[1]=(A[3]\&M_{0})\oplus (A[2]\&M_{3})\oplus (A[1]\&M_{2})\oplus (A[0]\&M_{1});}$

${\displaystyle B[2]=(A[3]\&M_{1})\oplus (A[2]\&M_{0})\oplus (A[1]\&M_{3})\oplus (A[0]\&M_{2});}$

${\displaystyle B[3]=(A[3]\&M_{2})\oplus (A[2]\&M_{1})\oplus (A[1]\&M_{0})\oplus (A[0]\&M_{3});}$

де:

${\displaystyle \&}$ — логічна побітова операція «і»;

${\displaystyle {\displaystyle A[i]}}$ і ${\displaystyle {\displaystyle B[i]}}$ — значення i-го рядка оброблюваних даних до і після виконання операції відповідно.

У парних раундах використовується операція ${\displaystyle \pi _{e}}$:

${\displaystyle B[0]=(A[3]\&M_{1})\oplus (A[2]\&M_{0})\oplus (A[1]\&M_{3})\oplus (A[0]\&M_{2});}$

${\displaystyle B[1]=(A[3]\&M_{2})\oplus (A[2]\&M_{1})\oplus (A[1]\&M_{0})\oplus (A[0]\&M_{3});}$

${\displaystyle B[2]=(A[3]\&M_{3})\oplus (A[2]\&M_{2})\oplus (A[1]\&M_{1})\oplus (A[0]\&M_{0});}$

${\displaystyle B[3]=(A[3]\&M_{0})\oplus (A[2]\&M_{3})\oplus (A[1]\&M_{2})\oplus (A[0]\&M_{1});}$

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

Байтова перестановка

Дана перестановка перетворює найпростішим чином рядок даних у стовпець:

${\displaystyle \tau :b_{ij}=a_{ij}}$

Побітове додавання всього масиву даних з ключем раунду

Дана операція є побітовим складанням всього масиву даних з ключем раунду:

${\displaystyle \sigma :B=A\oplus K_{r}}$

де: ${\displaystyle B}$ — нове значення блоку шифруємих даних; ${\displaystyle K_{r}}$ — ключ поточного раунду ${\displaystyle r}$.

Зауважимо, саме 12 раундів шифрування рекомендується автором алгоритму Чьо Хун Лімом, проте сувора кількість раундів не встановлена. Крім 12 раундів шифрування, перед першим раундом алгоритму виконується попередня операція ${\displaystyle \sigma }$, а по завершенні 12 раундів виконується вихідне перетворення ${\displaystyle \phi _{e}}$, що складається з послідовно виконуваних операцій ${\displaystyle \tau }$, ${\displaystyle \pi _{e}}$ і ${\displaystyle \tau }$.

Розшифрування виконується застосуванням зворотних операцій в зворотній послідовності. Всі операції, крім ${\displaystyle \gamma _{e}}$ і ${\displaystyle \gamma _{o}}$ є зворотними самим собі, а самі ${\displaystyle \gamma _{e}}$ і ${\displaystyle \gamma _{o}}$ зв'язані наступними співвідношеннями:

${\displaystyle \gamma _{e}^{-1}=\gamma _{o};}$

${\displaystyle \gamma _{o}^{-1}=\gamma _{e},}$

тому при дешифруванні ${\displaystyle \gamma _{o}}$ — використовується в парних раундах, а ${\displaystyle \gamma _{e}}$ — в непарних.

Варто відзначити ще одну особливість: кожен етап може бути виконуватися паралельно, що важливо при реалізації на сучасних багатоядерних і мультипоточних системах. Алгоритм має структуру SP-мережі, як і Rijndael (який є переможцем конкурсу AES) Також особливістю шифру є те, що для зашифрування та розшифрування може використовуватися одна і та ж процедура, але з різними підключами. Алгоритм ефективний як при програмній, так і апаратній реалізації. Шифр досить швидкий — на конкурсі AES при використанні компілятора Borland C показав найкращі результати серед всіх учасників.

Формування розширених ключів відбувається так:

• Якщо ключ шифрування має розмір, менший 256 біт, він доповнюється бітовими нулями, поки не досягне 32-байтового вихідного ключа ${\displaystyle K}$:

${\displaystyle K=k_{31}\bullet ...\bullet k_{1}\bullet k_{0}}$

• Ключ K розкладається на послідовності ${\displaystyle U}$ і ${\displaystyle V}$, перша з яких містить тільки парні байти ключа, друга — тільки непарні:

${\displaystyle U=U_{3}\bullet U_{2}\bullet U_{1}\bullet U_{0};}$

${\displaystyle U=k_{8i+6}\bullet k_{8i+4}\bullet k_{8i+2}\bullet k_{8i};}$

${\displaystyle U=k_{8i+6}\bullet k_{8i+4}\bullet k_{8i+2}\bullet k_{8i};}$

${\displaystyle V=k_{8i+7}\bullet k_{8i+5}\bullet k_{8i+3}\bullet k_{8i+1};}$

• Над послідовностями ${\displaystyle U}$ і ${\displaystyle V}$ виконується один раунд шифрування алгоритму Crypton з використанням ключа раунду, що складається з нульових бітів. Відповідно для ${\displaystyle U}$ виконуються перетворення непарного раунду, для ${\displaystyle V}$ відбувається перетворення парного раунду. Результуючі послідовності позначаються як ${\displaystyle U'}$ і ${\displaystyle V'}$.
• Відбувається обчислення 8 розширених ключів:

${\displaystyle Ke_{i}=U'_{i}\oplus T_{1};}$

${\displaystyle Ke_{i+4}=U'_{i}\oplus T_{0};}$

для ${\displaystyle i=0,1,2,3,}$ де ${\displaystyle T_{1}}$ і ${\displaystyle T_{0}}$ — послідовності, які визначаються наступними формулами:

${\displaystyle T_{0}=U'_{0}\oplus U'_{1}\oplus U'_{2}\oplus U'_{3};}$

${\displaystyle T_{1}=V'_{0}\oplus V'_{1}\oplus V'_{2}\oplus V'_{3}.}$

Для обчислення з розширених ключів — ключів раундів, використовуються наступні константи:

${\displaystyle C_{0}=A54FF53A;}$

${\displaystyle C_{i}=C{i-1}+3C6EF372mod2^{32};}$

${\displaystyle Mc_{0}=ACACACAC;}$

Зауважимо, що псевдовипадкові константи A54FF53A і 3C6EF372 утворюються з дробових частин від чисел ${\displaystyle {\sqrt {7}}}$ і ${\displaystyle {\sqrt {5}}}$ відповідно.

Спочатку обчислюються ключі для попередньої операції σ і першого раунду:

${\displaystyle K_{0}[i]=Ke_{i}\oplus C_{0}\oplus Mc_{i};}$

${\displaystyle K_{1}[i]=Ke_{i+4}\oplus C_{1}\oplus Mc_{i};}$

де ${\displaystyle K_{r}[i]}$ — i-ий рядок ключа раунду ${\displaystyle r}$. Як і для шифруємих даних, ключ надається у вигляді таблиці.

Подання ключа у вигляді таблиці аналогічно шифруємим даним

Константи ${\displaystyle Mc_{i}[i]}$ обчислюються шляхом побітового циклічного зрушення кожного байта константи ${\displaystyle Mc_{i-1}}$ на 1 біт вліво.

Для другого та кожного наступного парного раунду ключ обчислюється наступним чином:

• Виконується модифікація перших чотирьох розширених ключів:

${\displaystyle \{Ke_{3},Ke_{2},Ke_{1},Ke_{0}\}\leftarrow \{Ke_{0}<<<6,Ke_{3}<<<6,Ke_{2}<<16,Ke_{1}<<24\};}$

де знаком <<< позначена операція побітового циклічного зрушення кожного байта (роздільно) розширеного ключа на вказане число біт вліво, а << — побітового циклічного зрушення всього ключа на вказане число біт вліво.

• Обчислення ключа раунду за допомогою модифікованих розширених ключів:

${\displaystyle K_{r}[i]=Ke_{i}\oplus C_{r}\oplus Mc_{i};}$

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

${\displaystyle \{Ke_{7},Ke_{6},Ke_{5},Ke_{4}\}\leftarrow \{Ke_{6}<<16,Ke_{5}<<8,Ke_{4}<<<2,Ke_{7}<<<2\};}$

${\displaystyle K_{r}[i]=Ke_{i+4}\oplus C_{r}\oplus Mc_{i};}$

Процедура розширення ключа дозволяє генерувати ключі раундів «на льоту», тобто в процесі шифрування по мірі необхідності. Це явна перевага алгоритму, принаймні тому, що не потрібно пам'яті для зберігання ключів раундів. Для розшифрування можливо і виконання прямої процедури розширення ключа і використання отриманих ключів раундів у зворотному порядку.

При аналізі вихідної версії алгоритму, Crypton v0.5, відразу двоє експертів незалежно виявили клас слабких ключів: таких виявилося 2 в ступені 32 256-бітових ключів. Також, була виявлена атака на шестираундову версію алгоритму Crypton, схожа на атаку на алгоритм Square. Це було однією з причин появи нової версії алгоритму — Crypton v1.0.

Однак на думку експертів інституту NIST, перераховані вище недоліки не є грубими. Крім того, плюсів у алгоритму було цілком достатньо:

1. алгоритм ефективний на програмному та апаратному рівні завдяки високому ступені паралельності і використанні дуже простих логічних операцій ANDS/XORS;
2. алгоритм не піддається атакам по часу виконання і споживаної потужності;
3. хороша стійкість до існуючих атак;
4. можливість розпаралелювання операцій в процесі шифрування;
5. швидке розширення ключа, швидке формування ключів: шифрування з списоком ключів йде набагато швидше ніж шифрування з одним блоком, так що це дуже ефективно в додатках, що вимагають часті заміни ключів (наприклад, в хеш-режимі).
6. досить висока швидкість на всіх цільових платформах;
7. невеликі вимоги до оперативної пам'яті і можливість розширення ключа «на льоту» дозволяють використовувати алгоритм Crypton в смарткартах з мінімальними ресурсами;
8. алгоритм підтримує додаткові розміри ключів, крім тих, що були встановлені конкурсом (128, 192, 256 біт).

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

Аналіз безпеки блочно-симетричного шифру (БСШ) Crypton показує, що 12-раундовий самозамінюючий шифр (з однаковими процесами для шифрування та розшифрування) з довжиною блоку 128 біт і довжиною ключа до 128 бітів володіє гарною стійкістю до існуючих атак. Інтегральна атака на 4-х раундовий БСШ Crypton набагато ефективніша, ніж повний перебір по всьому ключовому простору.

Crypton являє собою блочний шифр. Довжина ключа і довжина блоку 128 біт. Чотири перетворення працюють з проміжним результатом, так званим Станом (State). Стан можна представити у вигляді прямокутного масиву з 16 байт:

${\displaystyle {\displaystyle (A_{i,j})}}$ де ${\displaystyle {\displaystyle A\in \{0,...,3\}}}$

Позначимо стовпець з 4 байт як ${\displaystyle {\displaystyle A_{j}=(A_{0j},A_{1j},A_{2j},A_{3j})}}$

Так само уявімо ключ шифрування:

${\displaystyle {\displaystyle (K_{i,j})}}$ де ${\displaystyle K\in \{0,...,3\}}$ і ${\displaystyle K_{j}=(K_{0j},K_{1j},K_{2j},K_{3j})}$.

У шифрі визначено поле Галуа ${\displaystyle GF(2^{8})}$, елементами якого є байти. Байти розглядаються як многочлени над ${\displaystyle {\displaystyle Z_{2}}}$

${\displaystyle b\leftrightarrow b_{7}x^{7}+b_{6}x^{6}+b_{5}x^{5}+b_{4}x^{4}+b_{3}x^{3}+b_{2}x^{2}+b_{1}x^{1}+b_{0}}$

Операція додавання ${\displaystyle \oplus }$ — при складанні байт відповідні їм многочлени складаються над  ${\displaystyle Z_{2}}$.

Операція множення — при множенні відповідні їм многочлени перемножуються над ${\displaystyle Z_{2}}$ і результуючий многочлен береться за модулем від простого многочлена

${\displaystyle m(x)=x^{8}+x^{4}+x^{3}+x^{1}+1}$

В процесі роботи алгоритму, ключ ${\displaystyle {\displaystyle (K_{i,j})}}$ розширюється (Key Schedule, Key Expansion). Перші 4 стовпців (по 4 байти) є вихідним ключем ${\displaystyle K^{0}}$. Кожний наступний ${\displaystyle r}$-й набір з 4 стовпчиків обчислюється з попереднього набору і використовується для ${\displaystyle r}$-ого раунду, позначимо його ${\displaystyle K^{r}=(K_{i,j}^{r})}$. Раунд складається з чотирьох різних елементарних перетворень, які перетворять стан ${\displaystyle A=(A_{i,j})}$у стан ${\displaystyle B=(B_{i,j})}$ :

• Заміна байт — BS (Byte Substitution): застосування перестановки ${\displaystyle S}$ або ${\displaystyle {\displaystyle B_{i,j}=S(A_{i,j})}}$
• Зрушення рядків — SR (Shift Rows): циклічне зрушення байт за правилом: ${\displaystyle {\displaystyle B_{i,j}=A_{i,(j+1)mod4}}}$
• Замішування стовпців — MC (Mix Columns: кожен стовпець стану змінюється лінійним перетворенням ${\displaystyle {\displaystyle \mu$ :(0,1)^{32}\rightarrow (0,1)^{32}}}

Інакше кажучи, це є ніщо інше, як множення стовпців на матрицю зліва: ${\displaystyle {\displaystyle B=\mu (A)=E={\begin{pmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{pmatrix}}}}$

Операція ${\displaystyle \mu }$ оборотна : ${\displaystyle {\displaystyle A_{j}=\mu ^{-1}(B_{j})}}$

• Додавання раундового ключа — KA (Key Addition): до поточного стану додається раундовий ключ.

Фінальний раунд не містить операції MC. Формули, що зв'язують стан ${\displaystyle A^{r}}$ і ${\displaystyle A^{r-1}}$:

${\displaystyle {\displaystyle A^{r}=MC(SR(S(A^{r-1})))\oplus K^{r-1}}}$;

${\displaystyle {\displaystyle A^{r-1}=S^{-1}(SR^{-1}(MC^{-1}(A^{r}\oplus K^{r-1})))}}$;

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

Введемо визначення.

${\displaystyle {\displaystyle \Lambda }}$ — набір з 256 вхідних блоків (масивів State), кожен з яких має байти (назвемо їх активними), значення яких різні для всіх 256 блоків. Інші байти (пасивні) залишаються однаковими для всіх 256 блоків з ${\displaystyle {\displaystyle \Lambda }}$-набору. Тобто для будь-яких ${\displaystyle A,B\in \Lambda }$ то ${\displaystyle A_{ij}\neq B_{ij}}$ якщо байт з індексом (i, j) активний і інакше ${\displaystyle A_{ij}=B_{ij}}$.

${\displaystyle {\displaystyle \Lambda ^{r}}}$ — ${\displaystyle {\displaystyle \Lambda }}$ k активними байтами.

${\displaystyle {\displaystyle P_{r}}}$ — множина станів в кінці раунду r.

${\displaystyle {\displaystyle \Lambda }}$-набір. Після елементарних перетворень BS і KA блоки ${\displaystyle {\displaystyle \Lambda }}$-набору дадуть в результаті інший ${\displaystyle {\displaystyle \Lambda }}$-набір з активними байтами в тих же позиціях, що й вихідний. Перетворення SR змістить ці байти відповідно заданим в ній зміщенням. Після перетворення MC ${\displaystyle {\displaystyle \Lambda }}$-набору в загальному випадку необов'язково залишиться ${\displaystyle {\displaystyle \Lambda }}$-набором (результат операції може перестати відповідати визначенню ${\displaystyle {\displaystyle \Lambda }}$-набору). Так як кожен байт ${\displaystyle B_{ij}}$ результату MC є лінійною комбінацією (з оборотними коефіцієнтами) чотирьох вхідних байт того ж стовпця ${\displaystyle B_{ij}=2A_{ij}\oplus 3A_{i+1mod4j}\oplus A_{i+2mod4j}\oplus A_{i+3mod4j}}$, то стовпець з єдиним активним байтом на вході дасть у результаті на виході стовпець з усіма чотирма активними байтами.

Розглянемо шифрування ${\displaystyle {\displaystyle \Lambda ^{1}}}$-набору. У всіх блоках буде активний тільки один байт. Значення цього байта по-різному у всіх 256 блоках, а інші байти однакові. У першому раунді перетворення MC перетворює один активний байт в стовпець з 4-ма активними байтами, тобто ${\displaystyle P_{1}}$ є ${\displaystyle \Lambda ^{4}}$. У другому раунді ці 4 байта розійдуться на 4 різні стовпці в результаті перетворення SR, ${\displaystyle P_{2}}$ є ${\displaystyle \Lambda ^{16}}$-набором. Перетворення MC наступного, третього раунду перетворює ці байти в 4 стовпці, що містять активні байти. Цей набір все ще залишається ${\displaystyle {\displaystyle \Lambda }}$-набором до того моменту, коли він надходить на вхід MC третього раунду.

Основна властивість ${\displaystyle {\displaystyle \Lambda }}$-набору — порозрядна сума за модулем 2 (${\displaystyle \oplus }$) всіх байтів, які перебувають на одних і тих же місцях, по всьому набору дорівнює нулю (порозрядна сума неактивних (з однаковими значеннями) байтів дорівнює нулю за визначенням операції «${\displaystyle \oplus }$», а активні байти, пробігаючи всі 256 значень, також при порозрядному додаванні дадуть нуль)

Результат перетворення MC в третьому раунді байтів вхідного масиву даних ${\displaystyle A}$ в байти вихідного масиву даних ${\displaystyle B}$ — порозрядна сума всіх блоків вихідного набору буде дорівнювати нулю:

${\displaystyle \oplus _{B=MC(A),A\in \Lambda ^{1}6}B_{ij}=\oplus _{A\in \Lambda ^{1}6}(2A_{ij}\oplus 3A_{i+1mod4j}\oplus A_{i+2mod4j}\oplus A_{i+3mod4j})=0}$

Таким чином ${\displaystyle P_{3}}$ є ${\displaystyle \Lambda ^{16}}$. Повна сума даних на вході дорівнює нулю. Ця рівність порушується подальшим перетворенням BS.

Ключ ${\displaystyle K^{r}}$ однозначно задається в R поданні:

${\displaystyle L^{r}=SR^{-1}(MC^{-1}(K^{r}))}$

${\displaystyle K^{r}=MC(SR(L^{r}))}$

Для проведення атаки потрібна множина ${\displaystyle Q_{4}}$, що складаються з 256 станів. ${\displaystyle Q_{r}=SR^{-1}(MC^{-1}(A)),A\in P_{r}}$ Множину ${\displaystyle Q_{4}}$ можна отримати застосуванням 2 зворотніх перетворень SR і MC з вхідних даних шифру ${\displaystyle P_{4}}$.

Схема базової інтегральної атаки на 4-раундовий Crypton: Для всіх ${\displaystyle {\displaystyle i,j\in {0,1,2,3}}}$

для ${\displaystyle {\displaystyle k\ inGF(2^{8})}}$

якщо ${\displaystyle \oplus _{Z\in Q}S^{-1}(Z_{ij}\oplus k)\neq 0}$,

то ${\displaystyle {\displaystyle L_{ij}^{4}\neq k}}$

У цій схемі інвертується 4-й раунд крок за кроком, щоб отримати байти ${\displaystyle {\displaystyle P_{3}}}$повна сума яких дорівнює 0. При ${\displaystyle L_{ij}^{4}=k}$ сума ${\displaystyle {\displaystyle \oplus _{Z\in Q}S^{-1}(Z_{ij}\oplus k)=0}}$

Якщо передбачуване значення байта ключа було вірне, то воно буде включене в можливі варіанти на місце ${\displaystyle {\displaystyle L^{4}}}$. Велика частина невірних значень байта буде відсіяною. За рахунок того, що пошук може проводитися окремо (паралельно) для кожного байта ключа, швидкість підбору всього значення раундового ключа досить велика. Далі за значенням ${\displaystyle L^{4}}$ можна знайти ${\displaystyle K^{4}}$, а потім і ${\displaystyle K^{0}}$ — вихідний ключ.