Алгоритм шифрования Twofish

Размещено на http://www.allbest.ru/

РЕФЕРАТ

на тему: «Алгоритм шифрования Twofish»

Содержание

Введение

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

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

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

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

Список использованной литературы

Введение

ключ шифр алгоритм twofish

Twofish -- симметричный алгоритм блочного шифрования с размером блока 128 бит и длиной ключа до 256 бит. Число раундов 16. Разработан группой специалистов во главе с Брюсом Шнайером. Являлся одним из пяти финалистов второго этапа конкурса AES. Алгоритм разработан на основе алгоритмов Blowfish, SAFER и Square. Отличительными особенностями алгоритма являются использование предварительно вычисляемых и зависящих от ключа S-box'ов и сложная схема развёртки подключей шифрования. Половина n-битного ключа шифрования используется как собственно ключ шифрования, другая -- для модификации алгоритма (от неё зависят S-box'ы).

Создатель: группа специалистов во главе с Брюсом Шнайером

Размер ключа: 256

Размер блока: 128

Число раундов: 16

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

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

(Правда в таком случае код приходится компилировать под конкретное значение ключа).

Алгоритм 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(28) по модулю неприводимого многочлена x8 + x6 + x5 + x3 + 1

MDS матрица -- это такая матрица над конечным полем K, что если взять её в качестве матрицы линейного преобразования f(x) = (MDS)x из пространства Kn в пространство Km, то любые два вектора из пространства Kn + 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 бит. Преобразование вычисляется следующим образом:

Эта операция часто используется для «рассеивания» кода (например в шифре 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 разбивается с перестановкой байт на два одинаковых блока Mo и Me. Затем с помощью блока Mo и функции h шифруется значение 2*i, а с помощью блока Me шифруется значение 2*i+1, где i -- номер текущего раунда (0 -- 15). Полученные зашифрованные блоки смешиваются криптопреобразованием Адамара, и затем используются в качестве раундовых подключей.

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

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

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

Функция h

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

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

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

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

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

Перестановки q0 и q1

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

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

Здесь ROR₄-- 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 1 7 D 6 F 3 2 0 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 байтов m0,...,m8k ? 1, где k = N / 64.

- Эти 8*k байтов разбиваются на слова по четыре байта, и в каждом слове байты переставляются в обратном порядке. В итоге получается 2*k 32-битных слова Mi

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

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

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

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

Вектор S, как и вектора Me и Mo, тоже формируется из исходного ключа и состоит из k 32-битных слов. Исходные байты ключа разбиваются на k групп по восемь байт. Каждая такая группа рассматривается как вектор с 8-ю компонентами и умножается на фиксированную RS матрицу размером 4x8 байт. В результате умножения получается вектор, состоящий из четырех байт. Вычисления проводятся в поле Галуа GF(2⁸) по модулю неприводимого многочлена x8 + x6 + x3 + x2 + 1.

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

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

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

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

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

Список использованной литературы

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

Размещено на Allbest.ru