Twofish

Відбілювання — це процедура xor'а даних з підключами перед першим раундом і після останнього раунду. Вперше ця техніка була використана в шифрі Khufu/Khare і, незалежно, Рональдом Рівестом (англ. Ron Rivest) в алгоритмі шифрування DESX. Joe Killian (NEC) і Phillip Rogaway (Каліфорнійський університет) показали, що відбілювання дійсно ускладнює завдання пошуку ключа повним перебором (exhaustive key-search) в DESX[3] . Розробники Twofish стверджують[4], що в Twofish відбілювання також істотно ускладнює завдання підбору ключа, оскільки криптоаналітика не може дізнатися, які дані потрапляють на вхід функції F першого раунду.

Тим не менш, виявилися і негативні сторони. Цікаве дослідження провели фахівці дослідницького центру компанії IBM.[5] Вони виконали реалізацію алгоритму Twofish для типової смарт-карти з CMOS-архітектурою і проаналізували можливість атаки за допомогою диференціального аналізу споживаної потужності (DPA — Differential Power Analysis). Атаці піддавалася саме процедура вхідного вибілювання, оскільки вона безпосередньо використовує xor підключів з вхідними даними. У результаті дослідники показали, що можна повністю обчислити 128-бітовий ключ проаналізувавши всього 100 операцій шифрування довільних блоків.

Функція g — основа алгоритму Twofish. На вхід функції подається 32-бітове число X, яке потім розбивається на чотири байти x0, x1, x2, x3. Кожен з вийшов байтів пропускається через свій S-box. (Слід зазначити, що S-box'и в алгоритмі не фіксовані, а залежать від ключа). Отримані 4 байти на виходах S-box'ов інтерпретуються як вектор з чотирма компонентами. Цей вектор множиться на фіксовану матрицю MDS (maximum distance separable) розміром 4x4, причому обчислення проводяться в скінченному полі ${\displaystyle GF(2^{8})}$ по модулю непривідного многочлена ${\displaystyle x^{8}+x^{6}+x^{5}+x^{3}+1}$

MDS матриця — це така матриця над кінцевим полем K, що якщо взяти її як матрицю лінійного перетворення ${\displaystyle f(x)=(MDS)x}$ з простору ${\displaystyle K^{n}}$ у простір ${\displaystyle K^{m}}$, то будь-які два вектори з простору ${\displaystyle K^{n+m}}$ виду (x, f (x)) будуть мати як мінімум m+1 відмінностей в компонентах. Тобто набір векторів вигляду (x, f (x)) утворює код, що володіє властивістю максимального рознесення (maximum distance separable code). Таким кодом, наприклад, є код Ріда-Соломона.

В Twofish властивість максимальної рознесеність матриці MDS означає, що загальна кількість змінних байт вектора a і вектора ${\displaystyle b=(MDS)a}$ не менше п'яти. Іншими словами, будь-яка зміна тільки одного байта в a призводить до зміни всіх чотирьох байтів в b.

криптоперетворення Адамара — оборотне перетворення бітового рядка довжиною 2n. Рядок розбивається на дві частини a і b однакової довжини в n біт. Перетворення обчислюється таким чином:

${\displaystyle a'=a+b\,{\pmod {2^{n}}}\,}$

${\displaystyle b'=a+2b\,{\pmod {2^{n}}}\,}$

Ця операція часто використовується для «розсіювання» коду (наприклад в шифрі SAFER).

В Twofish це перетворення використовується при змішуванні результатів двох g-функцій (n = 32).

У кожному раунді два правих 32-бітових блоки, які xor-яться з результатами функції F, додатково циклічно зрушуються на один біт. Третій блок зрушується до операції xor, четвертий блок — після. Ці зрушення спеціально додані, щоб порушити вирівнювання по байтах, яке властиво S-box'ам та операції множення на MDS-матрицю. Проте шифр перестає бути повністю симетричним, так як при шифруванні й розшифровці зрушення слід здійснювати в протилежні сторони.

Twofish розрахований на роботу з ключами довжиною 128, 192 і 256 біт. З вихідного ключа генерується 40 32-бітних підключів, перші вісім з яких використовуються тільки в операціях вхідного і вихідного вибілювання, а решта 32 — в раундах шифрування, по два підключі на раунд. Особливістю Twofish є те, що вихідний ключ використовується також і для зміни самого алгоритму шифрування, так як використовуються у функції g S-box'и не фіксовані, а залежать від ключа.

Для формування раундових підключів вихідний ключ M розбивається з перестановкою байт на два однакові блоки ${\displaystyle M_{o}}$ і ${\displaystyle M_{e}}$. Потім за допомогою блоку ${\displaystyle M_{o}}$ і функції h шифрується значення 2 * i, а за допомогою блоку ${\displaystyle M_{e}}$ шифрується значення 2*i+1, де i — номер поточного раунду (0 — 15). Отримані зашифровані блоки змішуються криптоперетвореням Адамара, і потім використовуються як раундові підключі.

Функція виконується в k етапів. Тобто для довжини ключа 256 біт буде 4 етапи, для ключа в 192 біта - 3 етапи, для 128 біт - 2 етапи.

На кожному етапі вхідний 32-бітове слово розбивається на 4 байта, і кожен байт піддається фіксованою перестановці бітів q ₀ або q ₁

Результат представляється у вигляді вектора з 4 байтів і множиться на MDS матрицю. Обчислення проводяться в полі Галуа GF (2 ⁸ ) по модулю непривідного многочлена ${\displaystyle x^{8}+x^{6}+x^{5}+x^{3}+1}$.

Матриця MDS має вигляд:

${\displaystyle ~{\mbox{MDS}}={\begin{pmatrix}01&EF&5B&5B\\5B&EF&EF&01\\EF&5B&01&EF\\EF&01&EF&5B\end{pmatrix}}}$

q ₀ і q ₁ - фіксовані перестановки 8 бітів вхідного байта x.

Байт x розбивається на дві 4-бітні половинки a ₀ і b ₀ , над якими проводяться наступні перетворення:

${\displaystyle ~a_{0}=x/16}$            ${\displaystyle ~b_{0}=x{\bmod {16}}}$

${\displaystyle ~a_{1}=a_{0}\oplus b_{0}}$            ${\displaystyle ~b_{1}=a_{0}\oplus {\mbox{ROR}}_{4}(b_{0},1)\oplus 8a_{0}{\bmod {16}}}$

${\displaystyle ~a_{2}=t_{0}[a_{1}]}$            ${\displaystyle ~b_{2}=t_{1}[b_{1}]}$

${\displaystyle ~a_{3}=a_{2}\oplus b_{2}}$            ${\displaystyle ~b_{3}=a_{2}\oplus {\mbox{ROR}}_{4}(b_{2},1)\oplus 8a_{2}{\bmod {16}}}$

${\displaystyle ~a_{4}=t_{2}[a_{3}]}$            ${\displaystyle ~b_{4}=t_{3}[b_{3}]}$

${\displaystyle ~y=16b_{4}+a_{4}}$

Тут ${\displaystyle ~{\mbox{ROR}}_{4}}$ - 4-бітний циклічний зсув вправо, а t ₀ , t ₁ , t ₂ , t ₃ - табличні заміни 4-бітових чисел.

Для q ₀ таблиці мають вигляд:

t₀ = [ 8 1 7 D 6 F 3 2 0 B 5 9 E C A 4 ]

t₁ = [ E C B 8 1 2 3 5 F 4 A 6 7 0 9 D ]

t₂ = [ B A 5 E 6 D 9 0 C 8 F 3 2 4 7 1 ]

t₃ = [ D 7 F 4 1 2 6 E 9 B 3 0 8 5 C A ]

Для q ₁ таблиці мають вигляд:

t₀ = [ 2 8 B D F 7 6 E 3 1 9 4 0 A C 5 ]

t₁ = [ 1 E 2 B 4 C 3 7 6 D A 5 F 9 0 8 ]

t₂ = [ 4 C 7 5 1 6 9 A 0 E D 8 2 B 3 F ]

t₃ = [ B 9 5 1 C 3 D E 6 4 7 F 2 0 8 A ]

Нехай M - вихідний ключ, N - його довжина в бітах. Генерація підключів відбувається наступним чином:

• Оригінальний ключ розбивається на 8 * k байтів ${\displaystyle m_{0},...,m_{8k-1}}$, де k = N / 64.
• Ці 8 * k байтів розбиваються на слова по чотири байти, і в кожному слові байти переставляються у зворотному порядку. У підсумку виходить 2 * k 32-бітних слова ${\displaystyle M_{i}}$

${\displaystyle ~M_{i}=\sum _{j=0}^{3}m_{(4i+j)}\cdot 2^{8j}~~~~~i=0,...,2k-1}$

• Отримані 2 * k 32-бітних розбиваються на два вектора ${\displaystyle ~M_{e}}$ і ${\displaystyle ~M_{o}}$ розміром в k 32-бітових слів.

${\displaystyle ~M_{e}=(M_{0},M_{2},...,M_{2k-2})}$

${\displaystyle ~M_{o}=(M_{1},M_{3},...,M_{2k-1})}$

Підключі для i-го раунду обчислюються за формулами:

${\displaystyle ~\rho =2^{24}+2^{16}+2^{8}+2^{0}}$

${\displaystyle ~A_{i}=h(2i\rho ,M_{e})}$

${\displaystyle ~B_{i}={\mbox{ROL}}(h((2i+1)\rho ,M_{0}),8)}$

${\displaystyle ~K_{2i}=(A_{i}+B_{i}){\bmod {2^{32}}}}$

${\displaystyle ~K_{2i+1}={\mbox{ROL}}((A_{i}+2B_{i}){\bmod {2^{32}}},9)}$

Функція g визначається через функцію h: ${\displaystyle ~g(X)=h(X,S)}$

Вектор S, як і вектора M _e і M _o , теж формується з вихідного ключа і складається з k 32-бітових слів. Вихідні байти ключа розбиваються на k груп по вісім байт. Кожна така група розглядається як вектор з 8-ма компонентами і множиться на фіксовану RS матрицю розміром 4x8 байт. В результаті множення виходить вектор, що складається з чотирьох байт. Обчислення проводяться в полі Галуа ${\displaystyle GF(2^{8})}$ по модулю непріводімогомногочлена ${\displaystyle x^{8}+x^{6}+x^{3}+x^{2}+1}$.

RS-матриця має вигляд:

${\displaystyle ~{\mbox{RS}}={\begin{pmatrix}01&A4&55&87&5A&58&DB&9E\\A4&56&82&F3&1E&C6&68&E5\\02&A1&FC&C1&47&AE&3D&19\\A4&55&87&5A&58&DB&9E&03\end{pmatrix}}}$