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

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

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

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

Алгоритм 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^[3]. Разработчики Twofish утверждают^[4], что в Twofish отбеливание также существенно усложняет задачу подбора ключа, поскольку криптоаналитик не может узнать, какие данные попадают на вход функции F первого раунда.

Тем не менее, обнаружились и негативные стороны. Интересное исследование провели специалисты исследовательского центра компании IBM.^[5] Они выполнили реализацию алгоритма 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, причем вычисления проводятся в поле Галуа по модулю неприводимого многочлена

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

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

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

Криптопреобразование Адмара — обратимое преобразование битовой строки длиной 2n. Строка разбивается на две части a и b одинаковой длины в 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 разбивается с перестановкой байт на два одинаковых блока и . Затем с помощью блока и функции h шифруется значение 2*i, а с помощью блока шифруется значение 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-битное слово.

Функция h

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

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

Результат представляется в виде вектора из 4 байтов и умножается на MDS матрицу. Вычисления производятся в поле Галуа GF(2⁸) по модулю неприводимого многочлена .

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

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

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

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

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

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

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

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

Функция g определяется через функцию h:

Вектор S, как и вектора M_e и M_o, тоже формируется из исходного ключа и состоит из k 32-битных слов. Исходные байты ключа разбиваются на k групп по восемь байт. Каждая такая группа рассматривается как вектор с 8-ю компонентами и умножается на фиксированную RS матрицу размером 4x8 байт. В результате умножения получается вектор, состоящий из четырех байт. Вычисления проводятся в поле Галуа по модулю неприводимого многочлена .

RS-матрица имеет вид:

Криптоанализ

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

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

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

Примечания