Курс "Защита информации", кафедра радиотехники, Московский физико-технический институт (МФТИ)

2010: Главная Экзамен Лекции Семинары Проекты Эссе | Преподаватели Литература | Архив: 2009 2008-fall 2008 2007 2006 2005 2004 2003 | English
HTML-версия эссе "Twofish block cipher description", Kozitsky, 2004, сгенерированная из pdf/rtf.
Конвертация не вcегда корректна. Смотрите исходный pdf.

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ

(ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)

Описание блочного шифра Twofish

(Twofish block cipher description)

Эссе по курсу «Защита информации»

студента 015 группы ФРТК Козицкого Петра.

Долгопрудный, 2004.

Преамбула

Симметричный блочный шифр Twofish является одной из наиболее удачных разработок компании Counterpane Systems (ныне Counterpane Internet Security, Inc.), основанной и возглавляемой Брюсом Шнайером, автором бестселлера «Прикладная криптография». Широкую известность и популярность Twofish приобрел после выхода в финал конкурса на новый американский правительственный стандарт шифрования в августе 1999 года. В создании криптоалгоритма приняли участие: сам Брюс Шнайер (Bruce Schneier), Джон Келси (John Kelsey), Даг Уайтинг (Doug Whiting), Дэвид Вагнер (David Wagner), Крис Холл (Chris Hall) и Нильс Фергюсон (Niels Ferguson).

Основные криптохарактеристики Twofish таковы:

• Длина блока шифрования 128 бит.
• Допустимые длины ключей шифрования 128, 192 и 256 бит.
• Предусмотрена возможность использования ключей шифрования с длинами, отличными от допустимых и не превосходящими 256 бит.
• Отсутствие «слабых» ключей.

В настоящее время Twofish с успехом применяется в различных программных продуктах (см. http://www.schneier.com/twofish-products.html ).

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

На рисунке 1. показана блок-схема алгоритма. Twofish использует 16-раундовую сеть Фейстеля (Feistel Network) с биективной (взаимно однозначной) функцией F и дополнительными «отбеливаниями» (Whitenings) на входе и выходе. Единственное отличие от «чистой» фейстелевской структуры заключается в наличии функциональных блоков, выполняющих циклические однобитовые сдвиги вправо и влево.

128-битовый блок P открытого текста (16 байт p0,…, p15) разбивается на четыре 32-битовых слова , , и с сохранением прямого порядка байтов (Little-Endian Convention):

i = 0,…, 3

На этапе входного «отбеливания» выполняется операция XOR между этими словами и четырьмя ключами , , и :

i = 0,…, 3

После этого следуют 16 раундов шифрования. В каждом раунде два «левых» слова являются входными для функций g (биты одного из входных слов сначала циклически сдвигаются на 8 позиций влево). К полученным выходным словам функций g затем применяется псевдопреобразование Адамара (PHT – Pseudo-Hadamard Transform) и добавляются два раундовых ключа и , где r – номер раунда шифрования. Далее между модифицированными таким образом «левыми» словами и двумя «правыми» словами (биты одного из которых прежде циклически сдвигаются на одну позицию влево) выполняется операция XOR, после чего циклическому сдвигу на 1 бит вправо подвергается другое из теперь уже видоизмененных «правых» слов. «Левая» и «правая» пары слов затем меняются местами для следующего раунда шифрования. Таким образом,

ROR

ROL

где r = 0,…, 15, а аббревиатурами ROR и ROL обозначены функции двух аргументов,

Рис. 1: блок-схема алгоритма шифрования Twofish

K4

P (128 бит)

P0(32 бита)

P1(32 бита)

P3(32 бита)

P2(32 бита)

S-box 0

S-box 1

S-box 2

S-box 3

S-box 0

S-box 1

S-box 2

S-box 3

K3

входное

«отбелива-

ние»

<<<8

K1

K2

MDS

MDS

K0

>>>1

<<<1

один

раунд

шифрова-

ния

C (128 бит)

C0(32 бита)

C3(32 бита)

C1(32 бита)

C2(32 бита)

отмена по-

следнего обмена местами пар слов

K7

выходное

«отбелива-

ние»

еще 15

раундов

g

g

PHT

F

K6

K5

K2

K2

:: ::

::::

выполняющие побитовый циклический сдвиг первого аргумента вправо и влево соответственно на число позиций, равное второму аргументу.

После реализации всех 16-ти раундов шифрования последний обмен местами «левой» и «правой» пар слов отменяется, и между полученными 32-битовыми словами и ключами , , и выполняется операция XOR (этап выходного «отбеливания»):

i = 0,…, 3

Полученные слова , , и затем объединяются в 128-битовый блок (16 байт ,…, ) зашифрованного текста:

mod 2 i = 0,…, 15

где - целая часть .

1. Функция F

Функция представляет собой функцию трех аргументов: двух входных слов и и номера раунда шифрования , необходимого для выбора надлежащих раундовых ключей. Преобразование функцией дает . Биты сначала циклически сдвигаются влево на 8 позиций, далее результат сдвига преобразуется функцией в . Затем к и , прошедшим PHT, добавляются два раундовых ключа:

(ROL (, 8))

mod

mod

где и - выходы функции .

2. Функция g

Функция g составляет основу алгоритма шифрования. Входное 32-битовое слово X разбивается на четыре байта. Каждый байт проходит через соответствующий S-box, зависящий от раундового ключа. Каждый S-box описывается биективной функцией, преобразующей «входной» байт в «выходной». Четыре результирующих байта интерпретируются как вектор длины 4 над полем Галуа GF(), который умножается слева на MDS-матрицу размеров 4×4 (вычисления также производятся над полем GF()). Полученный в ходе преобразований вектор рассматривается как 32-битовое слово, которое и является «выходом» функции g. Итак,

mod i = 0,…, 3

i = 0,…, 3

где - функции S-box’ов, - выход функции g.

Несколько слов о соответствии между байтовыми величинами и элементами поля GF(). Будем рассматривать GF( как GF(2)[]/, где - примитивный полином степени 8 над полем GF(2). Элемент поля , где GF(2), отождествляется с байтовой величиной . Сложение в поле GF( эквивалентно операции XOR между двумя байтами.

MDS-матрица имеет следующий вид:

Элементы MDS-матрицы представляют собой байтовые величины, записанные в шестнадцатиричной системе счисления.

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

В ходе шифрования одного блока открытого текста алгоритму генерации ключей необходимо сформировать сорок 32-битовых ключей ,…, , а также четыре зависящих от вида раундового ключа S-box’а, используемых функцией g. Twofish принимает ключи с длинами N, равными 128, 192 и 256 бит. Ключи с длинами, отличными от указанных и меньшими 256 бит, также могут быть использованы посредством дополнения их нулями до следующей большей из упомянутых основных длин. Например, 80-битовый ключ ,…, будет дополнен до 128-битового ключа таким образом: ,…, , , где i= 10,…, 15.

Положим k = N / 64 (возможные значения k равны 2, 3 и 4). Ключ M состоит из 8k байт ,…, . Эти байты прежде всего преобразуются в 2k слов длиной в 32 бита каждое:

i = 0,…, 2k – 1

и, далее, в два вектора длины k:

Третий вектор длины k, S, также формируется из ключа следующим образом: ключ разбивается на группы по 8 байт в каждой; каждая из групп рассматривается как вектор длины 8 над полем Галуа GF(28), на который умножается справа матрица размеров 8×4, получаемая из RS-кода (Reed-Solomon Code). Результат умножения (размером в четыре байта) рассматривается как 32-битовое слово. Из этих слов и составляется вектор S:

где i = 0,…, k – 1, и, наконец,

Следует обратить внимание на обратный порядок записи слов в векторе S.

Для определения операции умножения RS-матрицы справа на вектор-столбец представим GF(28) как GF(2)[]/, где - другой примитивный полином степени 8 над полем GF(2). Соответствие между байтовыми величинами и элементами поля GF(2) задается подобно тому, как это было сделано в предыдущем разделе в случае с MDS-матрицей. RS-матрица записывается следующим образом:

Таким образом, векторы , и составляют основу алгоритма генерации ключей.

3. 1. Функция h

На рисунке 2. показана блок-схема функции h. Она представляет собой функцию двух аргументов: 32-битового слова X и списка 32-битовых слов длины k. Возвращаемое функцией h значение представляет собой 32-битовое слово. Режим работы функции h включает k этапов. На каждом этапе каждый из четырех байтов слова X проходит через фиксированный S-box, после чего между ним и соответствующим байтом слова из списка выполняется операция XOR. Далее байты снова проходят через фиксированный S-box, а затем умножаются слева (как вектор) на MDS-матрицу. Таким образом,

mod 2

mod 2

где i = 0,…, k – 1 и j = 0,…, 3. Далее следует последовательность замен и операций XOR.

j = 0,…, 3

Если k = 4, получаем:

При k = 3, 4 получаем:

Во всех случаях (k = 2, 3, 4) получаем:

Здесь и - фиксированные перестановки 8-битовых величин, которые мы определим

Рисунок 2: блок-схема функции h

X

MDS

Z

k=4

k=3

k=2

k = 3, 4

позднее. Результирующий вектор, составленный из байтов , j = 0,…, 3, умножается слева на MDS-матрицу точно так же, как и в случае с функцией g:

Здесь Z – выход функции h.

3. 2 Зависящие от вида раундового ключа S-box’ы

Определим теперь S-box’ы в функции g следующим образом:

Следовательно, для j = 0,…, 3 функция зависящего от ключа S-box’а формируется преобразованием в внутри функции h, где список L есть вектор S, формируемый из ключа.

3. 3 Раундовые ключи

Раундовые ключи формируются функцией h:

ROL

mod 232

ROL (() mod 2,9)

Константа «дублирует» байты: для i = 0,…, 255 32-битовое слово состоит из четырех одинаковых байтов, значение (десятичное) каждого из которых равно i. Функция h оперирует двумя словами такого типа. Для значения байтов равны 2i, а вторым аргументом берется . Для значения байтов равны 2i + 1, в качестве же второго аргумента выступает , причем биты возвращаемого функцией h значения циклически сдвигаются на 8 позиций влево. Затем вычисленные значения и проходят через PHT, после чего биты одного из полученных результатов циклически сдвигаются влево на 9 позиций. В результате получаются два раундовых ключа.

3. 4 Перестановки q0 и q

Перестановки и представляют собой фиксированные перестановки 8-битовых величин. Они формируются из четырех различных 4-битовых перестановок. Из входного значения x выходное значение y (x, y – байтовые величины) получается следующим образом:

, mod 16

, ROR(,1) mod 16

,

, ROR(,1) mod 16

Рисунок 3: блок-схема функции F (при длине ключа 128 бит)

MDS

MDS

MDS

MDS

2i

2i

2i

2i

h

2i+1

2i+1

2i+1

2i+1

h

<<<8

PHT

g

<<<8

<<<9

g

PHT

,

где функция ROR аналогична функции ROR с той лишь разницей, что в качестве ее первого аргумента выступает 4-битовая величина. Таким образом, сначала байт разбивается на два полубайта (). Затем следует этап биективного преобразования, приводящий к двум новым полубайтам (). Далее каждый из полубайтов проходит через свой 4-битовый фиксированный S-box (), после чего вновь следуют этапы биективного преобразования и прохождения через надлежащие S-box’ы (). Наконец, два результирующих полубайта () формируют байтовое выходное значение y. Для 4-битовые S-box’ы имеют такой вид:

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

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

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

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

а для такой:

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

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

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

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

где каждый 4-битовый S-box представляет собой таблицу значений в шестнадцатиричной системе счисления.

4. Обзор раундовой функции

На рисунке 3. показана блок-схема функции F при длине ключа шифрования 128 бит (k = 2). Внедрение S-box’ов и алгоритма генерации раундовых ключей значительно усложняет ее вид, однако это необходимо для формирования полноценной картины, отображающей работу алгоритма.

Заключение

Несколько слов по поводу криптостойкости Twofish.

Разработчики алгоритма уже изначально были уверены в неприступности своего творения для криптоаналитиков. Во время первого раунда конкурса на новый американский правительственный стандарт шифрования Б. Шнайером был даже объявлен конкурс на лучшую криптоатаку против Twofish с призовым фондом в 10 тысяч долларов. Задача была действительно непростая: сложность алгоритма сыграла свою роль (и стала, кстати, одной из причин, по которой Twofish не стал новым стандартом шифрования США).

Тем не менее, определенные успехи в криптоанализе Twofish все же были достигнуты. Один из известных методов (Impossible Differential Attack), принадлежащий Ларсу Нудсену (Lars Knudsen), для 6-раундового Twofish (без «отбеливаний») имеет сложность 2128 для 128-битового ключа, 2160 для 192-битового ключа и 2192 для 256-битового ключа. Также была предложена атака на 7-раундовый Twofish (опять же без «отбеливаний») со сложностью 2256 для 256-битового ключа.

С «отбеливаниями» наилучшая атака «ломала» 6-раундовый Twofish cо сложностью 2256 и только с длиной ключа, равной 256 бит.

Таким образом, значительный запас криптостойкости Twofish очевиден.

Источники:

1. Twofish: A 128-Bit Block Cipher ( http://www.schneier.com/paper-twofish-paper.pdf )
2. Impossible Differentials in Twofish ( http://www.schneier.com/paper-twofish-impossible.pdf )


Page last update: Fri Jun 10 10:12:31 2005 MSD.
Website last update:
Rambler's Top100 Рейтинг@Mail.ru