MAGENTA

MAGENTA — блочный шифр, разработанный Майклом Якобсоном и Клаусом Хубером для немецкой телекоммуникационной компании Deutsche Telekom AG. MAGENTA является сокращением от Multifunctional Algorithm for General-purpose Encryption and Network Telecommunication Applications (Многофункциональный алгоритм для шифрования в общих целях и телекоммуникационных приложениях).

История

Разработка MAGENTA началась в 1990 году с основными принципами описанными в неопубликованной книге^[1].Основная идея заключалась в применении простой техники, без магических таблиц и постоянных, которая могла быть выполнена как аппаратно, так и программно. Планы заключались в разработке чипа, который мог бы передавать данных со скоростью до 1 Гбит/c и использоваться для шифрования в ATM. К сожалению, аппаратная реализация не появилась на свет, как планировалось, из-за узкого применения, но, несмотря на это, исследования показали, что такой чип возможно разработать^[2]. MAGENTA участвовал в конкурсе AES в 1998 году, но выбыл после первого раунда. Шифр стал доступен участникам конференции только в день презентации в отличие от других принимавших участие шифров. MAGENTA использовалась для шифрования данных внутри компании Deutsche Telekom. Следует отметить, что до MAGENTA быстрое преобразование Фурье в криптографических целях использовалось в 2 шифрах. Конкретное название первого не удалось найти^[3], он изобретен Жан-Пьером Вассером и зарегистрирован 2 июня 1959 года. Вторым шифром является одна из реализаций алгоритма A3 — Comp-128.

Шифрование

MAGENTA имеет структуру сети Фейстеля. Раундовая функция основана на быстром Адамаровом преобразовании (англ.)^[4], за исключением того, что вместо сложения и вычитания на каждом этапе к одному из слагаемых применяется S-блок, задаваемый функцией f(x), и затем они складываются по модулю 2.

Пусть множество $B=\{0,1\}^{8}$.Размер блока $M=(x_0,...,x_{15}) \in B^{16}$ исходного текста — 128 бит. Размер ключа может принимать 3 значения:

• 128 бит : $K=(K_1,K_2)$,
• 192 бит : $K=(K_1,K_2,K_3)$,
• 256 бит : $K=(K_1,K_2,K_3,K_4)$, где $K_1=(y_0,...,y_7) \ K_2=(y_8,...,y_{15}) \ K_3=(y_{16},...,y_{23}) \ K_4=(y_{24},...,y_{31})$.

Пусть F — раундовая функция. Шифр блока M вычисляется таким образом: $Enc_K(M)= \begin{cases} F_{K_1}(F_{K_1}(F_{K_2}(F_{K_2}(F_{K_1}(F_{K_1}(M)))))), & K=(K_1,K_2) \in B^{16}, \\ F_{K_1}(F_{K_2}(F_{K_3}(F_{K_3}(F_{K_2}(F_{K_1}(M)))))), & K=(K_1,K_2,K_3) \in B^{24}, \\ F_{K_1}(F_{K_2}(F_{K_3}(F_{K_4}(F_{K_4}(F_{K_3}(F_{K_2}(F_{K_1}(M)))))))), & K=(K_1,K_2,K_3,K_4) \in B^{32}; \end{cases}$

• 128 бит — ключ К разбивается на 2 части — К₁ и К₂. Количество раундов 6. Ключи применяются в таком порядке:

Раунд	1	2	3	4	5	6
Применяемый ключ	К1	К1	К2	К2	К1	К1

• 192 бит — ключ К разбивается на 3 части — К₁, К₂ и К₃. Количество раундов 6. Ключи применяются в таком порядке:

Раунд	1	2	3	4	5	6
Применяемый ключ	К1	К2	К3	К3	К2	К1

• 256 бит — ключ К разбивается на 4 части — К₁, К₂, К₃ и К₄. Количество раундов 8. Ключи применяются в таком порядке:

Раунд	1	2	3	4	5	6	7	8
Применяемый ключ	К1	К2	К3	К4	К4	К3	К2	К1

Дешифрование

Следует заметить, что последовательность используемых частей ключа является палиндромом. Пусть $V(x_0,...,x_{15}) \ = \ (x_8,x_9,...,x_{15},x_0,x_1,...,x_7)$. Тогда

$V((Enc_K(x_0,...,x_{15})) \ = \ Enc_K^{-1}(V(x_0,...,x_{15})).$^[5][6]

Таким образом, дешифрование $Dec_K(M) \ = \ V(Enc_K(V(M))).$

Раундовая функция F

Входной блок X размером 128 бит раунда n c раундовым ключом K_n разбивается на 2 части X₁ и X₂ размером 64 бита каждая.

X = X₁X₂

После прохождения раунда получаем X^' = X₂F(X₂K_n)

Из зависимости деления на части исходного ключа от количества раундов : длина части ключа, используемая в каждом раунде равна всегда 64 бита.

Следовательно, функция F принимает 128 битовый аргумент и должна возвращать 64-битный или 8-байтовый результат.

Введем вспомогательные функции, через которые затем выразим F:

Функция	Размер принимаемых(ого) аргументов(а)	Размер возвращаемого значения	Описание
f(x)	1 байт	1 байт	Возвращает элемент с номером x в S-блоке
A(x, y)	1 байт	1 байт	f(x ⊕ f(y))
PE(x, y)	1 байт	2 байта	(A(x, y)A(y, x)) — конкатенирует результаты A(x, y) и A(y, x)
П(X)	16 байт	16 байт	X=X0X1...X14X15 (PE(X0,X8)PE(X1,X9)...PE(X6,X14)PE(X7,X15)) - конкатенирует результаты PE(Xi,Xi+8) i=0...7, Xi имеет размер 1 байт.
T(X)	16 байт	16 байт	П(П(П(П(X)))) — применяет к X 4 раза функцию П.
S(X)	16 байт	16 байт	(X0X2X4…X14X1X3X5…X15) — выполняет перестановку байтов X: сначала записываются байты с четным порядковым номером затем с нечетным.
С(k, X)	k∈Ν X — 16 байт	16 байт	Рекурсивная функция: С(1,X) = T(X)) С(k,X) = T(X ⊕ S(C(k-1,X)))

Схема работы функции П(X) :

F полагают равной первым 8 байтам от S(C(n, (X₂K_n))), то есть байтам C(n, (X₂K_n)) с четным порядковым номером. Изначально n положили равным 7, но тесты показали, что в этом случае шифр возможно взломать. Поэтому затем положили n = 3. Как показали тесты это наилучший выбор, не допускающий криптографических слабостей, сказывающихся на всем шифре. Таким образом,

F полагают равной первым 8 байтам от S(C(3,(X₂K_n)))

S-блок

S-блок образуется следующим образом:

Первый элемент — 1, последующие образуются битовым сдвигом влево предудыщего, пока 1 не выйдет за левую границу байта. Соответственно начало блока — 1 2 4 8 16 32 64 128

256₁₀=1 0000 0000₂, 1 вышла за границу байта. В этом случае нужно сложить по модулю 2 полученное сдвинутое число 0000 0000₂ c числом 101₁₀=0110 0101₂:

0000 0000₂ ⊕ 0110 0101₂ = 0110 0101₂ = 101₁₀, то есть после 128 будет стоять 101.

101₁₀=0110 0101₂ << 1 = 1100 1010₂=202₁₀, 1 не вышла за границу, следовательно следующий элемент 202.
202₁₀ << 1= 1100 1010₂ << 1 = 1001 0100₂, 1 вышла за границу:

1001 0100₂ ⊕ 0110 0101₂ = 1111 0001₂ = 241₁₀.

Последний 256 элемент полагается равным 0. В результате получается такой S-блок:

   1    2    4    8   16   32   64  128
 101  202  241  135  107  214  201  247
 139  115  230  169   55  110  220  221
 223  219  211  195  227  163   35   70
 140  125  250  145   71  142  121  242
 129  103  206  249  151   75  150   73
 146   65  130   97  194  225  167   43
  86  172   61  122  244  141  127  254
 153   87  174   57  114  228  173   63
 126  252  157   95  190   25   50  100
 200  245  143  123  246  137  119  238
 185   23   46   92  184   21   42   84
 168   53  106  212  205  255  155   83
 166   41   82  164   45   90  180   13
  26   52  104  208  197  239  187   19
  38   76  152   85  170   49   98  196
 237  191   27   54  108  216  213  207
 251  147   67  134  105  210  193  231
 171   51  102  204  253  159   91  182
   9   18   36   72  144   69  138  113
 226  161   39   78  156   93  186   17
  34   68  136  117  234  177    7   14
  28   56  112  224  165   47   94  188
  29   58  116  232  181   15   30   60
 120  240  133  111  222  217  215  203
 243  131   99  198  233  183   11   22
  44   88  176    5   10   20   40   80
 160   37   74  148   77  154   81  162
  33   66  132  109  218  209  199  235
 179    3    6   12   24   48   96  192
 229  175   59  118  236  189   31   62
 124  248  149   79  158   89  178    0

Углубляясь в теорию, можно подытожить: Пусть имеется поле Галуа GF(2⁸) и задающий это поле многочлен — p(x)=x⁸+x⁶+x⁵+x²+1 и пусть α — примитивный элемент поля, p(α)=0. Тогда элемент f(x) в S-блоке с индексом x можно представить как $f(x)=\left\{\begin{matrix} \alpha^x, & x\ne 255, \\ 0, & x= 255; \\ \end{matrix}\right.$

Свойства используемых функций

f(x)

В течение одного выполнения MAGENTA функция f(x) вычисляется 2304 раза для ключей в 128 и 192 бита и 3072 раза для ключа в 256 бит. Так как функция представляет нелинейную часть алгоритма, она имеет особую важность для анализа всего алгоритма. Следующие свойства f(x) известны:

1. f(x) — взаимно-однозначная функция, то есть перестановка над множеством B={0,1}⁸ — всех восьмибитных двоичных векторов.
2. Данная перестановка может быть представлена как результат действия 6 несвязанных циклов длины 198 38 9 5 5 и 1. Согласно комбинаторному анализу, эти значения — «нормальные» и не имеют значительных расхождений с подобными циклами для случайных перестановок. Единственное число остающееся на месте — 161.
3. ∀x ∈ B и такого, что f(x) ∈ {1,2,…127} выполнено:

f(x+1) = 2∙f(x), где ∙ — произведение десятичных чисел. ∀(x, y)∈B² и таких, что f(x)∙f(y)∈{1,2,…255} выполнено: f((x+y) mod 255) = f(x)∙f(y)

1. Если рассматривать f(x) как вектор функцию, то есть f(x) = (f₇(x), f₆(x),…f₀(x)), то каждая из 8 булевых функций нелинейна и степени 7. Также всевозможные нетривиальные XOR-комбинации этих функций нелинейны. Явное представление этих функций можно найти здесь.^[7] Еще одно интересное свойство заключается в том, что каждая такая функция имеет 128 слагаемых.

PE(x, y)

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

Дифференциальный криптоанализ

Оказывается, по крайней мере часть MAGENTA может быть вскрыта методами данного криптоанализа. В качестве разницы между двумя элементами(открытыми текстами или шифрами) берется сложение по модулю 2 между этими элементами. Такое определение разницы обусловлено частым использованием операции xor в данном шифре. Строковые индексы XOR-таблицы представляют собой всевозможные разницы между открытыми текстами, а столбцовые индексы — между шифротекстами. На пересечении конкретного различия открытых текстов, то есть строкового индекса, и конкретного различия шифров, то есть столбцового индекса, стоит число пар открытых текстов, удовлетворяющих данному различию, шифры которых различаются на столбцовый индекс. XOR-таблица для функции f имеет размеры 256*256. Сумма каждой строки и столбца равна 256. Первый элемент первой строки(с индексом 0), отвечающей нулевому различию открытых текстов и шифров, равен 256. Все остальные первой строки элементы равны 0. Аналогично все элементы 1 столбца, кроме первого, равного 256, равны 0. Особенный интерес для дифференциального анализа представляют большие значения — самое большое значение в этой таблицы равно 8. Оно имеет место при таких различиях

Различие между открытыми текстами	Различие между шифрами
51	35, 66, 154, 155, 250
102	111, 114, 232, 233, 244
153	96, 97, 115, 229, 247
204	18, 19, 38, 207, 251

В остальных ячейках таблицы расположены числа 0, 2, 4, 6. Максимальная вероятность перехода для ненулевых различий — $\tfrac{8}{256}=2^{-5}$.
Для функции PE — также были определены максимальные значения — оно равно 36 для разницы в открытом тексте (234, 234) и нулевой разницы шифров. Максимальная вероятность перехода — $\tfrac{36}{256^2}$ ≈ $\tfrac{1}{1820}$.
Максимальная вероятность перехода для функции T — $2^{-20}$, для C(3,X) — $2^{-60}$. Так как число необходимых пар шифров больше чем величина, обратная вероятности перехода, данный тип дифференциального анализа, основанный на xor-таблицах не применим к MAGENTA. Однако вопрос о других типах остается открытым.

Линейный криптоанализ

Линейная аппроксимационная таблица для S-блока была вычислена.^[8]. Для функций $f_0, ..., f_7$ и для каждой xor-суммы $f_0 \oplus f_1, f_0 \oplus f_2, ..., f_0 \oplus f_1 \oplus ... \oplus f_7$, как и для всех линейных функций, было определено, как много цифр значений в таблице согласуется с соответствующими цифрами рассматриваемых линейных функций. В итоге получилось 255 значений между 0 и 256. Нормировка заключалась в вычитании 128. Все значения в таблице лежали на отрезке [-24;26]. Данные значения соответствуют ожидаемым для произвольно выбранных $f_0, ..., f_7$. Значение 26 получается при следующих линейных комбинациях:

$f_1 \oplus f_2 \oplus f_3, f_1 \oplus f_3 \oplus f_4 \oplus f_6,$

$f_1 \oplus f_3 \oplus f_6, f_2 \oplus f_3 \oplus f_4 \oplus f_6,$

$f_1 \oplus f_4 \oplus f_7, f_2 \oplus f_3 \oplus f_5 \oplus f_6,$

$f_2 \oplus f_6 \oplus f_7, f_3 \oplus f_4 \oplus f_5 \oplus f_6.$

Применяя лемму о набегании знаков (англ.) к раундовой функции F($p_i=0.6$, l=12)

$\frac{1}{2} + 2^{l-1} \prod_{i=1}^l p_i \approx \frac{1}{2} + 2 \cdot 10^{-9}$ Полученное значение является верхней границей наилучшего аффинного преобразования для F. Приблизительно $p^{-2}$ пар открытый текст — шифр нужно чтобы использовать аффинное линейное приближение с вероятностью $\frac{1}{2} + p$^[8]. Учитывая предыдущие результаты, для атаки на F необходимо $2.5 \cdot 10^{17}$. Следовательно, благодаря нелинейности f(x), MAGENTA не удастся взломать атаками, основанными на линейном криптоанализе.

Примечания

1. ↑ K. Huber. Neue Kryptographische Verfahren durch Kombination von Operationen in endlichen Körpern mit der schnellen Walshtransformation. Unpublished manuscript, 1990.
2. ↑ K. Huber and S. Wolter. Telekom’s MAGENTA algorithm for en-/decryption in the gigabit/sec range. In ICASSP 1996 Conference Proceedings, volume 6, pages 3233 — 3235, 1996.
3. ↑ J.P Vaseur. Verschluesselungsanordnung mit Mischverdrahtung. Deutsches Patentamt Auslegeschrift 1148397, Anmeldetag: 2.Juni 1959, Auslegeschrift: 9.Mai 1963, Anmelder: Compagnie Generale de Telegraphie sans Fil, Paris.
4. ↑ S.Y. Kung. VLSI Array Processors. Prentice Hall, 1988.
5. ↑ M. Luby and C. Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Computing, 17(2):373-386, April 1988.
6. ↑ J. Pieprzyk and B. Sadeghiyan. Design of Hashing Algorithms, volume 756 of Lecture Notes in Computer Science. Springer, 1993.
7. ↑ SIT GmbH. Abschlussbericht — Untersuchung eines universellen Kryptoalgorithmus. Technical report, SIT GmbH, 1994.
8. ↑ ^{1 2} E. Biham. On Matsui’s linear cryptanalysis. In Proc. EUROCRYPT '94, volume 658 of Lecture Notes in Computer Science, pages 81-91, 1995.

Ссылки

• M. J. Jacobson, Jr. and K. Hubery The MAGENTA Block Cipher Algorithm
• J. J. G. Savard. The Computer Era. Towards the 128-bit era: AES Candidates. Magenta // A Cryptographic Compendium
• El. Biham, Al. Biryukov, N. Ferguson, L. R. Knudsen, B. Schneier, Ad. Shamir Cryptanalysis of Magenta