Материал из РУВИКИ — свободной энциклопедии

Twofish

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

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

Технические подробности[править | править код]

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

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

Функция h[править | править код]

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

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

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

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

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

Перестановки q0 и q1[править | править код]

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

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

            
            
            
            
            

Здесь  — 4-битный циклический сдвиг вправо, а t0, t1, t2, t3 — табличные замены 4-битных чисел.

Для q0 таблицы имеют вид:

t0 = [ 8 1 7 D 6 F 3 2 0 B 5 9 E C A 4 ]
t1 = [ E C B 8 1 2 3 5 F 4 A 6 7 0 9 D ]
t2 = [ B A 5 E 6 D 9 0 C 8 F 3 2 4 7 1 ]
t3 = [ D 7 F 4 1 2 6 E 9 B 3 0 8 5 C A ]

Для q1 таблицы имеют вид:

t0 = [ 2 8 B D F 7 6 E 3 1 9 4 0 A C 5 ]
t1 = [ 1 E 2 B 4 C 3 7 6 D A 5 F 9 0 8 ]
t2 = [ 4 C 7 5 1 6 9 A 0 E D 8 2 B 3 F ]
t3 = [ 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, как и векторы Me и Mo, тоже формируется из исходного ключа и состоит из k 32-битных слов. Исходные байты ключа разбиваются на k групп по восемь байтов. Каждая такая группа рассматривается как вектор с 8 компонентами и умножается на фиксированную RS-матрицу размером 4×8 байтов. В результате умножения получается вектор, состоящий из четырёх байтов. Вычисления проводятся в поле Галуа по модулю неприводимого многочлена . RS-матрица имеет вид

Криптоанализ[править | править код]

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

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

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

Примечания[править | править код]

  1. «Announcing Request for Candidate Algorithm Nominations for the Advanced Encryption Standard (AES)» Архивная копия от 5 июня 2011 на Wayback Machine (англ.). Department of Commerce — National Institute of Standards and Technology — Federal Register: 12 September 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)» Архивная копия от 30 декабря 2010 на Wayback Machine (англ.). — National Institute of Standards and Technology.
  3. J. Kilian and P. Rogaway «How to Protect DES Against Exhaustive Key Search» Архивная копия от 11 июня 2010 на Wayback Machine (англ.) February 2, 2000
  4. N. Ferguson, J. Kelsey, B. Schneier, D. Whiting «A Twofish Retreat: Related-Key Attacks Against Reduced-Round Twofish» Архивная копия от 19 июля 2008 на Wayback Machine (англ.) 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» Архивная копия от 13 октября 2012 на Wayback Machine (англ.), 1999
  6. Fauzan Mirza, Sean Murphy «An Observation on the Key Schedule of Twofish» Архивная копия от 21 декабря 2016 на Wayback Machine (англ.) — Information Security Group, Royal Holloway, University of London — January 26, 1999
  7. Shiho Moriai, Yiqun Lisa Yin «Cryptanalysis of Twofish (II)» Архивная копия от 1 июня 2012 на Wayback Machine (англ.) — The Institute of Economics, Information and Communication Engineers
  8. Bruce Schneier «Twofish Cryptanalysis Rumors» Архивная копия от 9 июня 2012 на Wayback Machine (англ.) blog

Ссылки[править | править код]