Twofish

Twofish
Создатель	группа специалистов во главе с Брюсом Шнайером
Создан	1998
Размер ключа	128/192/256 бит
Размер блока	128 бит
Число раундов	16
Тип	Сеть Фейстеля

Twofish — симметричный алгоритм блочного шифрования с размером блока 128 бит и длиной ключа до 256 бит. Число раундов 16. Разработан группой специалистов во главе с Брюсом Шнайером. Являлся одним из пяти финалистов второго этапа конкурса AES. Алгоритм разработан на основе алгоритмов Blowfish, SAFER и SQUARE.

Отличительными особенностями алгоритма являются использование предварительно вычисляемых и зависящих от ключа узлов замены и сложная схема развёртки подключей шифрования. Половина n-битного ключа шифрования используется как собственно ключ шифрования, другая — для модификации алгоритма (от неё зависят узлы замены).

Twofish разрабатывался специально с учетом требований и рекомендаций NIST для AES^[1]:

• 128-битный блочный симметричный шифр,
• длина ключей 128, 192 и 256 бит,
• отсутствие слабых ключей,
• эффективная программная (в первую очередь на 32-битных процессорах) и аппаратная реализация,
• гибкость (возможность использования дополнительных длин ключа, использование в поточном шифровании, хеш-функциях и т. д.),
• простота алгоритма — для возможности его эффективного анализа.

Однако именно сложность структуры алгоритма и, соответственно, сложность его анализа на предмет слабых ключей или скрытых связей, а также достаточно большое время выполнения по сравнению с Rijndael на большинстве платформ сыграло не в его пользу^[2].

Алгоритм Twofish возник в результате попытки модифицировать алгоритм Blowfish для 128-битового входного блока. Новый алгоритм должен был быть легко реализуемым аппаратно (в том числе использовать таблицы меньшего размера), иметь более совершенную систему расширения ключа (англ. key schedule) и иметь однозначную функцию F.

В результате алгоритм был реализован в виде смешанной сети Фейстеля с четырьмя ветвями, которые модифицируют друг друга с использованием криптопреобразования Адамара (англ. pseudo-Hadamar transform, PHT).

Возможность эффективной реализации на современных (для того времени) 32-битных процессорах (а также в смарт-картах и подобных устройствах) — один из ключевых принципов, которым руководствовались разработчики Twofish.

Например, в функции F при вычислении PHT и сложении с частью ключа K намеренно используется сложение вместо традиционного xor. Это даёт возможность использовать команду LEA семейства процессоров Pentium, которая за один такт позволяет вычислить преобразование Адамара ${\displaystyle (T_{0}+2T_{1}+K_{2r+9}){\bmod {2}}^{32}}$ (правда, в таком случае код приходится компилировать под конкретное значение ключа).

Алгоритм Twofish не запатентован и может быть использован кем угодно без какой-либо платы или отчислений. Он используется во многих программах шифрования, хотя и получил меньшее распространение, чем Blowfish.

Twofish разбивает входной 128-битный блок данных на четыре 32-битных подблока, над которыми, после процедуры входного отбеливания (input whitening), производится 16 раундов преобразований. После последнего раунда выполняется выходное отбеливание (output whitening).

Отбеливание — это процедура 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). Полученные зашифрованные блоки смешиваются криптопреобразованием Адамара, и затем используются в качестве раундовых подключей.

Рассмотрим более подробно алгоритм формирования раундовых подключей, а также зависящей от ключа функции g. Как для формирования подключей, так и для формирования функции g в Twofish используется одна основная функция: h(X, L₀, L₁, … , L_k). Здесь X, L₀, L₁, … , L_k — 32 битные слова, а k = N / 64, где N — длина исходного ключа в битах. Результатом функции является одно 32-битное слово.

Функция выполняется в 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-матрицу размером 4×8 байтов. В результате умножения получается вектор, состоящий из четырёх байтов. Вычисления проводятся в поле Галуа ${\displaystyle GF(2^{8})}$ по модулю неприводимого многочлена ${\displaystyle x^{8}+x^{6}+x^{3}+x^{2}+1}$. RS-матрица имеет вид

${\displaystyle {\text{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}}.}$

Изучение Twofish с сокращенным числом раундов показало, что алгоритм обладает большим запасом прочности, и, по сравнению с остальными финалистами конкурса AES, он оказался самым стойким. Однако его необычное строение и относительная сложность породили некоторые сомнения в качестве этой прочности.

Нарекания вызвало разделение исходного ключа на две половины при формировании раундовых подключей. Криптографы Fauzan Mirza и Sean Murphy предположили, что такое разделение дает возможность организовать атаку по принципу «разделяй и властвуй», то есть разбить задачу на две аналогичные, но более простые^[6]. Однако реально подобную атаку провести не удалось.

На 2008 год лучшим вариантом криптоанализа Twofish является вариант усечённого дифференциального криптоанализа, который был опубликован Shiho Moriai и Yiqun Lisa Yin в Японии в 2000 году^[7]. Они показали, что для нахождения необходимых дифференциалов требуется 2⁵¹ подобранных открытых текстов. Тем не менее исследования носили теоретический характер, никакой реальной атаки проведено не было. В своём блоге создатель Twofish Брюс Шнайер утверждает, что в реальности провести такую атаку невозможно^[8].

• Twofish web page (англ.).
• Исходные коды Twofish (англ.).
• Twofish: A 128-Bit Block Cipher Архивная копия от 29 августа 2008 на Wayback Machine (англ.).
• Алгоритмы шифрования — финалисты конкурса AES.
• Список продуктов, использующих Twofish.