Twofish

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

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

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

Общие сведения

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

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

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

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

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

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

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

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

Описание алгоритма

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

Отбеливание (whitening)

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

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

Функция g

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

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

В Twofish свойство максимальной разнесённости матрицы MDS означает, что общее количество меняющихся байт вектора a и вектора $b=(MDS)a$ не меньше пяти. Другими словами, любое изменение только одного байта в a приводит к изменению всех четырёх байтов в b.

Криптопреобразование Адамара (Pseudo-Hadamar Transform, PHT)

Криптопреобразование Адамара — обратимое преобразование битовой строки длиной 2n. Строка разбивается на две части a и b одинаковой длины в n бит. Преобразование вычисляется следующим образом:

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

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

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

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

Циклический сдвиг на 1 бит

В каждом раунде два правых 32-битных блока, которые xor-ятся с результатами функции F, дополнительно циклически сдвигаются на один бит. Третий блок сдвигается до операции xor, четвёртый блок — после. Эти сдвиги специально добавлены, чтобы нарушить выравнивание по байтам, которое свойственно S-box’ам и операции умножения на MDS-матрицу. Однако шифр перестаёт быть полностью симметричным, так как при шифрации и расшифровке сдвиги следует осуществлять в противоположные стороны.

Генерация ключей

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

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

Технические подробности

Схема одного раунда шифрования для 128-битного ключа

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

Функция h

Функция h для разных длин ключа

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

На каждом этапе входное 32-битное слово разбивается на 4 байта, и каждый байт подвергается фиксированной перестановке битов q₀ или q₁

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

Матрица MDS имеет вид:

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

Перестановки q₀ и q₁

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

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

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

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

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

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

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

$y=16b_{4}+a_{4}$

Здесь ${\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 байтов $m_{0},...,m_{8k-1}$, где k = N / 64.
• Эти 8*k байтов разбиваются на слова по четыре байта, и в каждом слове байты переставляются в обратном порядке. В итоге получается 2*k 32-битных слова $M_{i}$

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

• Полученные 2*k 32-битных слов разбиваются на два вектора $M_{e}$ и $M_{o}$ размером в k 32-битных слов.

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

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

Подключи для i-го раунда вычисляются по формулам:

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

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

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

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

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

Функция g и S-box’ы

Функция g определяется через функцию h: $g(X)=h(X,S)$.

Вектор S, как и векторы M_e и M_o, тоже формируется из исходного ключа и состоит из k 32-битных слов. Исходные байты ключа разбиваются на k групп по восемь байтов. Каждая такая группа рассматривается как вектор с 8 компонентами и умножается на фиксированную RS-матрицу размером 4×8 байтов. В результате умножения получается вектор, состоящий из четырёх байтов. Вычисления проводятся в поле Галуа $GF(2^{8})$ по модулю неприводимого многочлена $x^{8}+x^{6}+x^{3}+x^{2}+1$. RS-матрица имеет вид

${\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 предположили, что такое разделение дает возможность организовать атаку по принципу «разделяй и властвуй», то есть разбить задачу на две аналогичные, но более простые. Однако реально подобную атаку провести не удалось.

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

Ссылки

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