Twofish

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

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, которая за один такт позволяет вычислить преобразование Адамара $({T}_{0}+2{T}_{1}+{K}_{2r+9})~mod~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^[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, причем вычисления проводятся в поле Галуа $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^3_{j=0}m_{(4i+j)}\cdot2^{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 матрицу размером 4x8 байт. В результате умножения получается вектор, состоящий из четырех байт. Вычисления проводятся в поле Галуа $GF(2^8)$ по модулю неприводимого многочлена $x^8 + x^6 + x^3 + x^2 + 1$.

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

$~\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}$

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

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

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

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

Примечания

1. ↑ «Announcing Request for Candidate Algorithm Nominations for the Advanced Encryption Standard (AES)» (англ.). Department of Commerce — National Institute of Standards and Technology — Federal Register: September 12, 1997
2. ↑ Nechvatal J., Barker E., Bassham L., Burr W., Dworkin M., Foti J., Roback E. «Report on the Development of the Advanced Encryption Standard (AES)» (англ.). — National Institute of Standards and Technology.
3. ↑ J. Kilian and P. Rogaway «How to Protect DES Against Exhaustive Key Search» (англ.) February 2, 2000
4. ↑ N. Ferguson, J. Kelsey, B. Schneier, D. Whiting «A Twofish Retreat: Related-Key Attacks Against Reduced-Round Twofish» (англ.) Twofish Technical Report #6, February 14, 2000
5. ↑ Suresh Chari, Charanjit Jutla, Josyula R. Rao, Pankaj Rohatgi «A Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards» (англ.), 1999
6. ↑ Fauzan Mirza, Sean Murphy «An Observation on the Key Schedule of Twofish» (англ.) — Information Security Group, Royal Holloway, University of London — January 26, 1999
7. ↑ Shiho Moriai, Yiqun Lisa Yin «Cryptanalysis of Twofish (II)» (англ.) — The Institute of Economics, Information and Communication Engineers
8. ↑ Bruce Schneier «Twofish Cryptanalysis Rumors» (англ.) blog

Ссылки

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