MacGuffin (шифр)

MacGuffin
Создатель	Брюс Шнайер, Мэтт Блэйз
Создан	1994 год
Опубликован	1994.12.14
Размер ключа	128 бит
Размер блока	64 бит
Число раундов	32
Тип	Сеть Фейстеля

В криптографии, Макгаффин — симметричный блочный шифр, построенный на основе сети Фейстеля. Алгоритм придуман Брюсом Шнайером и Мэттом Блэйзом в 1994 году в рамках Fast Software Encryption. И в том же году Винсент Рэймен и Барт Пренель показали его уязвимость к дифференциальному криптоанализу, также имеющуюся у похожего шифра DES. Предназначался для исследования такой структуры шифров, как несбалансированная сеть Фейстеля.

Введение

Традиционно, шифры, использующие сеть Фейстеля, делят входной блок на равные части — левую(целевой блок) и правую(управляющий блок). При каждом раунде блоки меняются местами. Макгаффин базируется на структуре, в которой целевой блок меньшей длины, чем управляющий. Шифр оперирует входными блоками длиной 64 бита, где целевая часть длиной 16 бит, а управляющая 48. Используется 128 битный ключ. Однако, количество раундов и размер ключа могут варьироваться.

Архитектура

Большая часть дизайна заимствована у DES. Входной не зашифрованный текст разделён на 4 16 битных слова. S-блоки заимствованы у DES. Их используется 8, каждый возвращает результат из 4-х бит, принимая 6 бит на входе. Но учитываются только 2 бита (суммарный результат должен быть 16 бит). Выход S-блока не становится на позиции битов, использующихся для входа самого же блока, в течение следующих 4-х раундов. Шифр предназначен для реализации в оборудовании или программном обеспечении. Перестановки выбраны так, чтобы минимизировать количество операций сдвига и маски.

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

Ключевым элементом в структуре шифра является несбалансированная сеть Фейстеля. Входные блоки поделены на четыре регистра, по два байта каждый. В новом раунде три последних правых блока объединяются в контрольный блок и складываются по модулю 2 с раундовым ключом, созданным из основного при помощи алгоритма ключевого расписания. Полученные 48 бит разбиваются на 8 частей и становятся входными параметрами шести S-блоков. В свою очередь, каждый S-блок преобразует 6 входных битов в 2 выходных. 16-битный результат S-блоков складывается по модулю 2 с крайним слева входным блоком, и результат становится крайним справа регистром входного блока следующего раунда. Три крайних справа регистра текущего раунда смещаются без изменений на одну позицию влево. Таким образом формируется входной блок для следующего раунда.

S-блоки и перестановки

Нелинейность процесса шифрования и раундовых ключей обеспечивается преимущественно восемью S-блоками, S₁…S₈. На вход выбираются биты из поданных 16-битных регистров a, b и c. Порядок выбора определяется таблицей 1 (бит с позицией 0 наименее значащий):

Таблица 1. Перестановка входных бит

S-блоки	входные биты
	0	1	2	3	4	5
S1	a2	a5	b6	b9	c11	c13
S2	a1	a4	b7	b10	c8	c14
S3	a3	a6	b8	b13	c0	c15
S4	a12	a14	b1	b2	c4	c10
S5	a0	a10	b3	b14	c6	c12
S6	a7	a8	b12	b15	c1	c5
S7	a9	a15	b5	b11	c2	c7
S8	a11	a13	b0	b4	c3	c9

Ключевое расписание

В каждом раунде шифра используется секретный ключевой параметр, который сложением по модулю 2 влияет на входы S-блоков. Соответственно, при каждом раунде запрашивается 48 бит. Для конвертации 128 бит ключа в последовательность из 48 бит, Макгаффин использует итерированную версию своей функции шифрования блоков.

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

Как и DES, Макгаффин поддаётся дифференциальному криптоанализу, суть которого в анализе вероятностей получения определённой разности значений функции Фейстеля при заданной разности аргументов. Оптимальная 4-раундовая характеристика имеет вероятность ${\frac {1}{149}}$, в то время, как 2-раундовая DES ${\frac {1}{234}}$. Таким образом, 32 раунда Макгаффина менее устойчивы, чем 16 DES.

Литература

Matt Blaze, Bruce Schneier. The MacGuffin block cipher algorithm (англ.) // Springer-Verlag. — Springer, Berlin, Heidelberg, 1994. — ISBN 978-3-540-47809-6. — ISSN 0302-9743. — doi:10.1007/3-540-60590-8_8.

Vincent Rijmen, Bart Preneel. Cryptanalysis of McGuffin (англ.) // Springer-Verlag. — Springer, Berlin, Heidelberg, 1995. — ISBN 978-3-540-47809-6. — ISSN 0302-9743. — doi:10.1007/3-540-60590-8_27.

Bruce Schneier, John Kelsey. Unbalanced Feistel networks and block cipher design (англ.) // Springer-Verlag. — Springer, Berlin, Heidelberg, 1996. — ISBN 978-3-540-49652-6. — ISSN 0302-9743. — doi:10.1007/3-540-60865-6_49.