CRYPTON

CRYPTON
CRYPTON
Создатель	Че Хун Лим (Future Systems, Inc.)
Создан	1998 г.
Опубликован	1998 - 1999
Размер ключа	128, 192, 256 бит
Размер блока	128 бит
Число раундов	12
Тип	Подстановочно-перестановочная сеть

CRYPTON — алгоритм симметричного блочного шифрования (размер блока 128 бит, ключ длиной до 256 бит), разработанный южнокорейским криптологом Че Хун Лим (англ. Chae Hoon Lim) из южнокорейской компании Future Systems, с конца 1980-х годов работающая на рынке сетевого обеспечения и защиты информации. Алгоритм был разработан в 1998 году в качестве шифра — участника конкурса AES. Как признавался автор, конструкция алгоритма опирается на алгоритм SQUARE.

В алгоритме Crypton нет традиционных для блочных шифров сети Фейстеля. Основу данного шифра составляет так называемая SP-сеть (повторяющаяся циклическая функция из замен-перестановок, ориентированная на распараллеленную нелинейную обработку^[1] всего блока данных). Кроме высокой скорости, преимуществами таких алгоритмов является облегчение исследования стойкости шифра к методам дифференциального и линейного криптоанализа, являющимся на сегодня основными инструментами вскрытия блочных шифров.

На конкурс AES была изначально представлена версия алгоритма Crypton v0.5. Однако, как говорил Че Хун Лим, ему не хватало времени для разработки полной версии. И уже в первом этапе конкурса AES в ходе анализа алгоритмов, версия Crypton v0.5 была заменена на версию Crypton v1.0. Отличие новой версии от первоначальной заключались в изменении таблиц замен, в модификации процесса расширения ключа.

Структура алгоритма. Основные характеристики

Как и другие участники конкурса AES, Crypton предназначен для шифрования 128-битовых блоков данных. При шифровании используются ключи шифрования нескольких фиксированных размеров — от 0 до 256 бит с кратностью 8 битов.

Структура алгоритма Crypton — структура «Квадрата» — во многом похожа на структуру алгоритма Square, созданного в 1997 году. Криптографические преобразования для алгоритмов с данной структурой могут быть выполнены как над целыми строками и столбцами массива, так и над отдельными его байтами. (Стоит отметить, что алгоритм Square был разработан авторами будущего победителя конкурса AES — авторами алгоритма Rijndael — Винсентом Рэйменом и Йоаном Дайменом.)

Шифрование

Алгоритм Crypton представляет 128-битовый блок шифруемых данных в виде байтового массива 4×4, над которыми в процессе шифрования производится несколько раундов преобразований. В каждом раунде предполагается последовательное выполнение следующих операций:

Табличная замена $\gamma$

Алгоритм Crypton использует 4 таблицы замен. Каждая из которых замещает 8-битовое входное значение на выходное такого же размера.

Все таблицы $S_{0}...S_{3}$ являются производными от основной таблицы $S$ (см. рисунок - вычисление производных таблиц замен).

Ниже представлен пример таблиц:

Таблица

S_{0}

:

63	ec	59	aa	db	8e	66	c0	37	3c	14	ff	13	44	a9	91
3b	78	8d	ef	c2	2a	f0	d7	61	9e	a5	bc	48	15	12	47
ed	42	1a	33	38	c8	17	90	a6	d5	5d	65	6a	fe	8f	a1
93	c2	2f	0c	68	58	df	f4	45	11	a0	a7	22	96	fb	7d
1d	b4	84	e0	bf	57	e9	0a	4e	83	cc	7a	71	39	c7	32
74	3d	de	50	85	06	6f	53	e8	ad	82	19	e1	ba	36	cb
0e	28	f3	9b	4a	62	94	1f	bd	f6	67	41	d8	d1	2d	a4
86	b7	01	c5	b0	75	02	f9	2c	29	6e	d2	f5	8b	fc	5a
e4	7f	dd	07	55	b1	2b	89	72	18	3a	4c	b6	e3	80	ce
49	cf	6b	b9	f2	0d	dc	64	95	46	f7	10	9a	20	a2	3f
d6	87	70	3e	21	fd	4d	7b	3c	ae	09	8a	04	b3	54	f8
30	00	56	d4	e7	25	bb	ac	98	73	ea	c9	9d	4f	7e	03
ab	92	a8	43	0f	fa	24	5c	1e	60	31	97	cd	c6	79	f5
5e	e5	34	76	1c	81	b2	af	0b	5d	d9	e2	27	6d	d0	88
c1	51	e6	9c	77	be	99	23	da	eb	52	2e	b5	08	05	6c
b8	1b	a3	69	8c	d3	40	26	f1	c4	9f	35	ee	7c	4b	16

Таблица

S_{1}

8d	b3	65	aa	6f	3a	99	03	dc	f0	50	ff	4c	11	a6	46
ec	e1	36	bf	0b	a8	c3	5f	85	7a	96	f2	21	54	48	1d
b7	09	68	cc	e0	23	5c	42	9a	57	75	95	a9	fb	3e	86
4e	2b	bc	30	a1	61	7f	d3	15	44	82	9e	88	5a	Ef	f5
74	d2	12	83	fe	5d	a7	28	39	0e	33	e9	c5	e4	1f	c8
d1	f4	7b	41	16	18	bd	4d	a3	b6	0a	64	87	ea	d8	2f
38	a0	cf	6e	29	89	52	7c	f6	db	9d	05	63	47	b4	92
1a	de	04	17	c2	d5	08	e7	b0	a4	b9	4b	7d	2e	f3	69
93	fd	77	1c	55	c6	ac	26	c9	60	e8	31	da	8f	02	3b
25	3f	ad	e6	cb	34	73	91	56	19	df	40	6a	80	8a	fc
5b	1e	c1	f8	84	f7	35	ed	0f	ba	24	2a	10	ce	51	e3
c0	00	59	53	9f	94	ee	b2	62	cd	ab	27	76	3d	f9	0c
ae	4a	a2	0d	3c	eb	90	71	78	81	c4	5e	37	1b	e5	d7
79	97	d0	d9	70	06	ca	be	2c	6d	67	8b	9c	b5	43	22
07	45	9b	72	dd	fa	66	8c	6b	af	49	b8	d6	20	14	b1
e2	6c	8e	a5	32	4f	01	98	c7	13	7e	d4	bb	f1	2d	58

Таблица

S_{2}

b1	72	76	bf	ac	ee	55	83	ed	aa	47	d8	33	95	60	c4
9b	39	1e	0c	0a	1d	ff	26	89	5b	22	f1	d4	40	c8	67
9d	a4	3c	e7	c6	b5	f7	dc	61	79	15	86	78	6e	eb	32
b0	ca	4f	23	d2	fb	5e	08	24	4d	8a	10	09	51	a3	9f
f6	6b	21	c3	0d	38	99	1f	1c	90	64	fe	8b	a6	48	bd
53	e1	ea	57	ae	84	b2	45	35	02	7f	d9	c7	2a	d0	7c
c9	18	65	00	97	2b	06	6a	34	f3	2c	92	ef	dd	7a	56
a2	c4	88	b9	50	75	d3	e4	11	ce	4b	a7	fd	3f	be	81
8e	d5	5a	49	42	54	70	a1	df	87	ab	7d	f4	12	05	2e
27	0f	c1	30	66	98	3d	cb	b8	e6	9c	63	e3	bc	19	fa
3a	2f	9e	f2	6f	1a	28	3b	c2	0e	03	c0	b7	59	a9	d7
74	85	d6	ad	41	ec	8c	71	f0	93	5d	b6	1b	68	e5	44
07	e0	14	8a	f9	73	cd	4e	25	bb	31	5f	4a	cc	8f	91
de	6d	7b	f5	b3	29	a0	17	6c	da	e8	04	96	82	52	36
43	5c	db	8d	80	d1	e2	b4	58	46	ba	e9	01	20	fc	13
16	f8	94	62	37	cf	69	9a	af	77	c5	3e	7e	a5	2d	0b

Таблица

S_{3}

:

b1	f6	8e	07	72	6b	d5	e0	76	21	5a	14	bf	c3	49	a8
ac	0d	42	f9	ee	38	54	73	55	99	70	cd	83	1f	a1	4e
ed	1c	df	25	aa	90	87	bb	47	64	ab	31	d8	fe	7d	5f
33	8b	f4	4a	95	a6	12	cc	60	48	05	8f	c4	bd	2e	91
9b	53	27	de	39	e1	0f	6d	1e	ea	c1	7b	0c	57	30	f5
0a	ae	66	b3	1d	84	98	29	ff	b2	3d	a0	26	45	cb	17
89	35	b8	6c	5b	02	e6	da	22	7f	9c	e8	f1	d9	63	04
d4	c7	e3	96	40	2a	bc	82	c8	d0	19	52	67	7c	fa	36
9d	c9	3a	43	a4	18	2f	5c	3c	65	9e	db	e7	00	f2	8d
c6	97	6f	80	b5	2b	1a	d1	f7	06	28	e2	dc	6a	3b	b4
61	34	c2	58	79	f3	0e	46	15	2c	03	ba	86	92	c0	e9
78	ef	b7	01	6e	dd	59	20	eb	7a	a9	fc	32	56	d7	13
b0	a2	74	16	ca	4c	85	f8	4f	88	d6	94	23	b9	ad	62
d2	50	41	37	fb	75	ec	cf	5e	d3	8c	69	08	e4	71	9a
24	11	f0	af	4d	ce	93	77	8a	4b	5d	c5	10	a7	b6	3e
09	fd	1b	7e	51	3f	68	a5	a3	be	e5	2d	9f	81	44	0b

В четных раундах используется операция $\gamma _{e}$ , в нечетных - $\gamma _{o}$ . Эти операции и таблицы замен обладают рядом свойств, которые важны, особенно для унификации операций шифрования и расшифрования. Свойства таблиц и операций:

\gamma _{e}(\gamma _{o}(A))=\gamma _{o}(\gamma _{e}(A))=A;

S^{-1}=S;

S_{2}=S_{0}^{-1};

S_{3}=S_{1}^{-1};

где $A$ — текущее значение блока шифруемых данных. Операции $\gamma _{e}$ и $\gamma _{o}$ можно определить следующим образом:

\gamma _{e}:b_{ij}=S_{(j+2+imod4)}(a_{ij});

\gamma _{o}:b_{ij}=S_{(j+imod4)}(a_{ij}).

где:

$a_{ij}$ — текущее значение конкретного байта данных;
$b_{ij}$ — значение байта данных после выполнения операции;

Линейное преобразование $\pi$

Здесь используется 4 специальных константы, шестнадцатеричные значения которых указаны ниже:

m_{0}=FC;

m_{1}=F3;

m_{2}=CF;

m_{3}=3F;

Эти константы объединены в маскирующие последовательности, перечисленные ниже:

M_{0}=m_{3}\bullet m_{2}\bullet m_{1}\bullet m_{0};

M_{1}=m_{0}\bullet m_{3}\bullet m_{2}\bullet m_{1};

M_{2}=m_{1}\bullet m_{0}\bullet m_{3}\bullet m_{2};

M_{3}=m_{2}\bullet m_{1}\bullet m_{0}\bullet m_{3};

где $\bullet$ — операция конкатенации.

Сама же операция $\pi$ — представляет собой битовую перестановку. В нечетных раундах используется операция $\pi _{o}$ :

B[0]=(A[3]\&M_{3})\oplus (A[2]\&M_{2})\oplus (A[1]\&M_{1})\oplus (A[0]\&M_{0});

B[1]=(A[3]\&M_{0})\oplus (A[2]\&M_{3})\oplus (A[1]\&M_{2})\oplus (A[0]\&M_{1});

B[2]=(A[3]\&M_{1})\oplus (A[2]\&M_{0})\oplus (A[1]\&M_{3})\oplus (A[0]\&M_{2});

B[3]=(A[3]\&M_{2})\oplus (A[2]\&M_{1})\oplus (A[1]\&M_{0})\oplus (A[0]\&M_{3});

где:

$\&$ — логическая побитовая операция «и»;
$A[i]$ и $B[i]$ — значение i-ой строки обрабатываемых данных до и после выполнения операции соответственно.

В четных раундах используется операция $\pi _{e}$ :

B[0]=(A[3]\&M_{1})\oplus (A[2]\&M_{0})\oplus (A[1]\&M_{3})\oplus (A[0]\&M_{2});

B[1]=(A[3]\&M_{2})\oplus (A[2]\&M_{1})\oplus (A[1]\&M_{0})\oplus (A[0]\&M_{3});

B[2]=(A[3]\&M_{3})\oplus (A[2]\&M_{2})\oplus (A[1]\&M_{1})\oplus (A[0]\&M_{0});

B[3]=(A[3]\&M_{0})\oplus (A[2]\&M_{3})\oplus (A[1]\&M_{2})\oplus (A[0]\&M_{1});

Фактически эта операция обеспечивает наличие в каждом результирующем байте каждого столбца двух битов каждого исходного байта того же столбца.

Байтовая перестановка $\tau$

Данная перестановка преобразует простейшим образом строку данных в столбец:

\tau :b_{ij}=a_{ji}

Операция $\sigma$

Побитовое сложение всего массива данных с ключом раунда

Данная операция является побитовым сложением всего массива данных с ключом раунда:

\sigma :B=A\oplus K_{r}

где: $B$ — новое значение блока шифруемых данных; $K_{r}$ — ключ текущего раунда $r$ .

Заметим, именно 12 раундов шифрования рекомендуется автором алгоритма Че Хун Лимой, однако строгое количество раундов не установлено. Кроме 12 раундов шифрования, перед первым раундом алгоритма выполняется предварительная операция $\sigma$ , а по завершении 12 раундов выполняется выходное преобразование $\phi _{e}$ , состоящее из последовательно выполняемых операций $\tau$ , $\pi _{e}$ и $\tau$ .

Расшифрование

Расшифрование выполняется применением обратных операций в обратной последовательности. Все операции, кроме $\gamma _{e}$ и $\gamma _{o}$ являются обратными самим себе, а сами $\gamma _{e}$ и $\gamma _{o}$ связаны следующими соотношениями:

\gamma _{e}^{-1}=\gamma _{o};

\gamma _{o}^{-1}=\gamma _{e},

поэтому при расшифровывании $\gamma _{o}$ — используется в четных раундах, а $\gamma _{e}$ — в нечетных.

Стоит отметить ещё одну особенность: каждый этап может быть выполняется параллельно, что важно при реализации на современных многоядерных и многопоточных системах. Алгоритм имеет структуру SP-сети, как и Rijndael (который является победителем конкурса AES) Также особенностью шифра является то, что для зашифрования и расшифрования может использоваться одна и та же процедура, но с разными подключами. Алгоритм эффективен как при программной, так и при аппаратной реализации. Шифр достаточно быстр — на конкурсе AES при использовании компилятора Borland C показал наилучшие результаты среди всех участников.

Процедура расширения ключа

Алгоритм Crypton требует наличие 128 — битового ключа для каждого раунда, а также 128 битового ключа для предварительной операции σ. Расширение ключа происходит в два этапа:

на первом этапе происходит формирование восьми расширенных ключей;
на втором этапе происходит вычисление ключей раундов из расширенных ключей.

Формирование расширенных ключей

Формирование расширенных ключей происходит так:

Если ключ шифрования имеет размер, меньший 256 бит, он дополняется битовыми нулями, пока не достигнет 32-байтового исходного ключа $K$ :

K=k_{31}\bullet ...\bullet k_{1}\bullet k_{0}

Ключ K разбирается на последовательности $U$ и $V$ , первая из которых содержит только четные байты ключа, вторая — только нечетные:

U=U_{3}\bullet U_{2}\bullet U_{1}\bullet U_{0};

V=V_{3}\bullet V_{2}\bullet V_{1}\bullet V_{0};

U=k_{8i+6}\bullet k_{8i+4}\bullet k_{8i+2}\bullet k_{8i};

V=k_{8i+7}\bullet k_{8i+5}\bullet k_{8i+3}\bullet k_{8i+1};

Над последовательностями $U$ и $V$ выполняется один раунд шифрования алгоритма Crypton с использованием ключа раунда, состоящего из нулевых битов. Соответственно для $U$ выполняются преобразования нечетного раунда, для $V$ происходит преобразование четного раунда. Результирующие последовательности обозначаются как $U'$ и $V'$ .
Происходит вычисление 8 расширенных ключей:

Ke_{i}=U'_{i}\oplus T_{1};

Ke_{i+4}=V'_{i}\oplus T_{0};

для $i=0,1,2,3,$ где $T_{1}$ и $T_{0}$ — последовательности, которые определяются следующими формулами:

T_{0}=U'_{0}\oplus U'_{1}\oplus U'_{2}\oplus U'_{3};

T_{1}=V'_{0}\oplus V'_{1}\oplus V'_{2}\oplus V'_{3}.

Вычисление ключей раундов

Для вычисления из расширенных ключей — ключей раундов, используются следующие константы:

C_{0}=A54FF53A;

C_{i}=C_{i-1}+3C6EF372mod2^{32};

Mc_{0}=ACACACAC;

Заметим, что псевдослучайные константы A54FF53A и 3C6EF372 получаются из дробных частей от чисел ${\sqrt {7}}$ и ${\sqrt {5}}$ соответственно.

Сначала вычисляются ключи для предварительной операции σ и первого раунда:

K_{0}[i]=Ke_{i}\oplus C_{0}\oplus Mc_{i};

K_{1}[i]=Ke_{i+4}\oplus C_{1}\oplus Mc_{i};

где $K_{r}[i]$ — i-ая строка ключа раунда $r$ . Как и для шифруемых данных, ключ предоставляется в виде таблицы..

Представление ключа в виде таблице аналогично шифруемым данным

Константы $Mc_{i}[i]$ вычисляются путём побитового циклического сдвига каждого байта константы $Mc_{i-1}$ на 1 бит влево.

Для второго и каждого последующего четного раунда ключ вычисляется следующим образом:

Выполняется модификация первых четырёх расширенных ключей:

\{Ke_{3},Ke_{2},Ke_{1},Ke_{0}\}\leftarrow \{Ke_{0}<<<6,Ke_{3}<<<6,Ke_{2}<<16,Ke_{1}<<24\};

где знаком <<< обозначена операция побитового циклического сдвига каждого байта (раздельно) расширенного ключа на указанное число битов влево, а << — побитового циклического сдвига всего ключа на указанное число битов влево.

Вычисление ключа раунда с помощью модифицированных расширенных ключей:

K_{r}[i]=Ke_{i}\oplus C_{r}\oplus Mc_{i};

Аналогично происходит вычисление ключей для нечетных раундов:

\{Ke_{7},Ke_{6},Ke_{5},Ke_{4}\}\leftarrow \{Ke_{6}<<16,Ke_{5}<<8,Ke_{4}<<<2,Ke_{7}<<<2\};

K_{r}[i]=Ke_{i+4}\oplus C_{r}\oplus Mc_{i};

Процедура расширения ключа позволяет генерировать ключи раундов «на лету», то есть в процессе шифрования по мере необходимости. Это явное достоинство алгоритма, по крайней мере потому, что не требуется памяти для хранения ключей раундов. Для расшифорвания возможно и выполнение прямой процедуры расширения ключа и использование полученных ключей раундов в обратном порядке.

Безопасность

Недостатки алгоритма Crypton

При анализе исходной версии алгоритма, Crypton v0.5, сразу двое экспертов независимо обнаружили класс слабых ключей: таковых оказалось 2 в степени 32 256-битовых ключей. Также, была обнаружена атака на шестираундовую версию алгоритма Crypton, похожая на атаку на алгоритм Square. Это было одной из причин появления новой версии алгоритма — Crypton v1.0.

Достоинства алгоритма Crypton

Однако по мнению экспертов института NIST, вышеперечисленные недостатки не являются грубыми. Кроме того, плюсов у алгоритма было вполне достаточно:

алгоритм эффективен на программном и аппаратном уровне благодаря высокой степени параллельности и использованию очень простых логических операций ANDS/XORS;
алгоритм не подвержен атакам по времени выполнения и потребляемой мощности;
хорошая стойкость к существующим атакам;
возможность распараллеливания операций в процессе шифрования;
быстрое расширение ключа, быстрое формирование ключей: шифрование со списоком ключей идет намного быстрее чем шифрование с одним блоком, так что это очень эффективно в приложениях, требующих частые замены ключей (например, в хеш-режиме).
достаточно высока скорость на всех целевых платформах;
небольшие требования к оперативной памяти и возможность расширения ключа «на лету» позволяют использовать алгоритм Crypton в смарткартах с минимальными ресурсами;
алгоритм поддерживает дополнительные размеры ключей, помимо тех, что были установлены конкурсом (128, 192, 256 битов).

Разработчиком была заявлена гарантированная устойчивость к линейному и дифференциальному криптоанализу и, в целом, всем существующим на момент разработки атакам. Переработанное ключевое расписание и новые таблицы S-Box исключили все обнаруженные недостатки и уязвимости.

Интегральная атака на шифр Crypton (4-х раундовый)

Анализ безопасности блочно-симметричного шифра (БСШ) Crypton показывает, что 12-раундовый самозаменяемый шифр (с одинаковыми процессами для кодирования и расшифровывания) с длиной блока 128 битов и длиной ключа до 128 битов обладает хорошей стойкостью к существующим атакам. Интегральная атака на 4-х раундовый БСШ Crypton намного эффективнее, чем полный перебор по всему ключевому пространству.

Краткое описание шифра

Crypton представляет собой блочный шифр. Длина ключа и длина блока 128 бит. Четыре преобразования работают с промежуточным результатом, называемым Состоянием (State). Состояние можно представить в виде прямоугольного массива из 16 байт:

(A_{i,j})

где

A\in \{0,...,3\}

Обозначим столбец из 4 байт как $A_{j}=(A_{0j},A_{1j},A_{2j},A_{3j})$

Так же представим ключ шифрования:

(K_{i,j})

где

K\in \{0,...,3\}

и

K_{j}=(K_{0j},K_{1j},K_{2j},K_{3j})

.

В шифре определено поле Галуа $GF(2^{8})$ , элементами которого являются байты. Байты рассматриваются как многочлены над $Z_{2}$

b\leftrightarrow b_{7}x^{7}+b_{6}x^{6}+b_{5}x^{5}+b_{4}x^{4}+b_{3}x^{3}+b_{2}x^{2}+b_{1}x^{1}+b_{0}

Операция сложения $\oplus$ — при сложении байт соответствующие им многочлены складываются над $Z_{2}$ .

Операция умножения — при умножении соответствующие им многочлены перемножаются над $Z_{2}$ и результирующий многочлен берется по модулю от простого многочлена

m(x)=x^{8}+x^{4}+x^{3}+x^{1}+1

В процессе работы алгоритма, ключ $(K_{i,j})$ расширяется (Key Schedule, Key Expansion). Первые 4 столбца (по 4 байта) являются исходным ключом $K^{0}$ . Каждый последующий $r$ -й набор из 4 столбцов вычисляется из предыдущего набора и используется для $r$ -го раунда, обозначим его $K^{r}=(K_{i,j}^{r})$ . Раунд состоит из четырёх различных элементарных преобразований, которые преобразуют состояние $A=(A_{i,j})$ в состояние $B=(B_{i,j})$ :

Замена байт — BS (Byte Substitution): применение перестановки $S$ или $B_{i,j}=S(A_{i,j})$
Сдвиг строк — SR (Shift Rows): циклический сдвиг байт по правилу: $B_{i,j}=A_{i,(j+1)mod4}$
Замешивание столбцов — MC (Mix Columns: каждый столбец состояния изменяется линейным преобразованием $\mu :(0,1)^{32}\rightarrow (0,1)^{32}$

Иначе говоря, это есть ничто иное, как умножение столбцов на матрицу слева: $B=\mu (A)=E={\begin{pmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{pmatrix}}$

Операция $\mu$ обратима : $A_{j}=\mu ^{-1}(B_{j})$

Добавление раундового ключа — KA (Key Addition): к текущему состоянию прибавляется раундовый ключ.

Финальный раунд не содержит операции MC. Формулы, связывающие состояния $A^{r}$ и $A^{r-1}$ :

A^{r}=MC(SR(S(A^{r-1})))\oplus K^{r-1}

;

A^{r-1}=S^{-1}(SR^{-1}(MC^{-1}(A^{r}\oplus K^{r-1})))

;

Алгоритм реализации интегральной атаки

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

Введем определения.

$\Lambda$ — набор из 256 входных блоков (массивов State), каждый из которых имеет байты (назовем их активными), значения которых различны для всех 256 блоков. Остальные байты (пассивные) остаются одинаковыми для всех 256 блоков из $\Lambda$ -набора. То есть для любых $A,B\in \Lambda$ то $A_{ij}\neq B_{ij}$ если байт с индексом (i, j) активный и иначе $A_{ij}=B_{ij}$ .

\Lambda ^{r}

—

\Lambda

c k активными байтами.

P_{r}

— множество состояний в конце раунда r.

$\Lambda$ -набор. После элементарных преобразований BS и KA блоки $\Lambda$ -набора дадут в результате другой $\Lambda$ -набор с активными байтами в тех же позициях, что и у исходного. Преобразование SR сместит эти байты соответственно заданным в ней смещениям. После преобразования MC $\Lambda$ -набора в общем случае необязательно останется $\Lambda$ -набором (результат операции может перестать удовлетворять определению $\Lambda$ -набора). Так как каждый байт $B_{ij}$ результата MC является линейной комбинацией (с обратимыми коэффициентами) четырёх входных байт того же столбца $B_{ij}=2A_{ij}\oplus 3A_{i+1mod4j}\oplus A_{i+2mod4j}\oplus A_{i+3mod4j}$ , то столбец с единственным активным байтом на входе даст в результате на выходе столбец со всеми четырьмя активными байтами.

Рассмотрим шифрование $\Lambda ^{1}$ -набора. Во всех блоках будет активен только один байт. Значение этого байта различно во всех 256 блоках, а остальные байты одинаковы. В первом раунде преобразование MC преобразует один активный байт в столбец из 4 активных байт, то есть $P_{1}$ является $\Lambda ^{4}$ . Во втором раунде эти 4 байта разойдутся по 4 различным столбцам в результате преобразования SR, $P_{2}$ является $\Lambda ^{16}$ -набором. Преобразование MC следующего, третьего раунда преобразует эти байты в 4 столбца, содержащие активные байты. Этот набор все ещё остается $\Lambda$ -набором до того момента, когда он поступает на вход MC третьего раунда.

Основное свойство $\Lambda$ -набора — поразрядная сумма по модулю 2 ( $\oplus$ ) всех байтов, находящихся на одних и тех же местах, по всему набору равна нулю (поразрядная сумма неактивных (с одинаковыми значениями) байт равна нулю по определению операции « $\oplus$ », а активные байты, пробегая все 256 значений, также при поразрядном суммировании дадут нуль)

Результат преобразования MC в третьем раунде байтов входного массива данных $A$ в байты выходного массива данных $B$ — поразрядная сумма всех блоков выходного набора будет равна нулю:

\oplus _{B=MC(A),A\in \Lambda ^{1}6}B_{ij}=\oplus _{A\in \Lambda ^{1}6}(2A_{ij}\oplus 3A_{i+1mod4j}\oplus A_{i+2mod4j}\oplus A_{i+3mod4j})=0

Таким образом $P_{3}$ есть $\Lambda ^{16}$ . Полная сумма данных на входе равна нулю. Это равнество нарушается последующим преобразованием BS.

Ключ $K^{r}$ однозначно задается в R представлении:

L^{r}=SR^{-1}(MC^{-1}(K^{r}))

K^{r}=MC(SR(L^{r}))

Для проведения атаки потребуется множество $Q_{4}$ , состоящее из 256 состояний. $Q_{r}=SR^{-1}(MC^{-1}(A)),A\in P_{r}$ Множество $Q_{4}$ можно получить применением 2 обратных преобразований SR и MC из входных данных шифра $P_{4}$ .

Схема базовой интегральной атаки на 4-раундовый Crypton:

Для всех $i,j\in {0,1,2,3}$

для $k\ inGF(2^{8})$

если $\oplus _{Z\in Q}S^{-1}(Z_{ij}\oplus k)\neq 0$ ,

то $L_{ij}^{4}\neq k$

В этой схеме инвертируется 4-й раунд шаг за шагом, чтобы получить байты $P_{3}$ , полная сумма которых равна 0. При $L_{ij}^{4}=k$ сумма $\oplus _{Z\in Q}S^{-1}(Z_{ij}\oplus k)=0$

Если предполагаемое значение байта ключа было верно, то оно будет включено в возможные варианты на место $L^{4}$ . Большая часть неверных значений байта будет отсеяно. За счет того, что поиск может производиться отдельно (параллельно) для каждого байта ключа, скорость подбора всего значения раундового ключа весьма велика. Далее по значению $L^{4}$ можно найти $K^{4}$ , а потом и $K^{0}$ — исходный ключ.

Конкурс AES

Первыми шагами навстречу изменению стандартов шифрования было создание конкурса AES. Это был открытый конкурс, проводимый институтом стандартов и технологий США — NIST (National Institute of Standart and Technology). Победитель этого конкурса должен был стать новым стандартом шифрования США. В конкурсе могли принимать частные лица, компании как внутри США так и за пределами страны.

Основные требования:

128 бит — размер блока шифруемых данных.
Три или более размеров ключей должно поддерживаться алгоритмом (128, 256, 192 — бит — обязательные размеры ключей для конкурса).

Однако несмотря на малое количество требований для алгоритмов, было много пожеланий:

алгоритм должен быть стоек от криптоаналитических атак, известных на момент проведения конкурса;
структура алгоритма должна быть ясной, простой и обоснованной;
должны отсутствовать слабые и эквивалентные ключи;
скорость шифрования данных должна быть высокой на всех потенциальных аппаратных платформах от 8 до 64 битовых.
структура алгоритма должна позволять распараллеливать операции в многопроцессорных системах и аппаратных реализациях.
алгоритм должен предъявлять минимальные требования к оперативной и энергонезависимой памяти.
не должно быть ограничений на использование алгоритмов.

Заметим, что участникам конкурса AES разрешалось вносить изменения в алгоритмы в ходе конкурса, если это незначительные модификации. Для алгоритма Crypton при предоставлении новой версии, жюри сочли изменения значительными, так как они касались таблицы замен, процедуру расширения ключа. В результате, на конкурсе участвовала версия Crypton v0.5.

Отсутствие явных минусов и наличие достоинств у алгоритма Crypton все равно не позволило ему выйти в финал конкурса AES. Причиной тому было участие в конкурсе двух алгоритмов: Rijndael и Twofish. Эти алгоритмы не имели проблем слабых ключей как у алгоритма Crypton. Более того они были быстрее чем Crypton на целевых платформах. Было решено, что в дальнейшем Crypton проиграет в любом случае этим алгоритмам, поэтому эксперты конкурса не пропустили Crypton в финал. (Rijndael — будущий победитель конкурса).

Версии алгоритма Crypton

В конкурсе участвовала первичная редакция алгоритма, которая получила индекс 0.5 через некоторое время. Через некоторое время было предложено ещё несколько редакций, последней из которой стала версия 1.0 с переработанным ключевым расписанием и новыми таблицами подстановки.

Примечания

↑ Бухаров О.Е., Боголюбов Д.П. Распараллеленная самообучающаяся система поддержки принятия решений на генетических алгоритмах и нейронных сетях (рус.) // Системный администратор. — 2014. — № Выпуск №9 (142). Архивировано 28 января 2021 года.

Литература

Chae Hoon Lim. CRYPTON: a new 128-bit Block Cipher–Specification and Analysis. — 1998. — doi:10.1.1.52.5771.
Алгоритмы Шифрования. Специальный Справочник/ Автор: Сергей Петрович Панасенко/ Изд: «БХВ-Санкт-Петербург», 2009

Ссылки

A New 128-bit Block Cipher. Specification and Analysis. (англ)
A New 128-bit Block Cipher Specification and Analysis Other (недоступная ссылка) (англ)
Спецификация алгоритма

[1] Бухаров О.Е., Боголюбов Д.П. Распараллеленная самообучающаяся система поддержки принятия решений на генетических алгоритмах и нейронных сетях (рус.) // Системный администратор. — 2014. — № Выпуск №9 (142). Архивировано 28 января 2021 года.

[1]

CRYPTON

Структура алгоритма. Основные характеристики

Шифрование

Табличная замена γ γ --> {\displaystyle \gamma }

Линейное преобразование π π --> {\displaystyle \pi }

Байтовая перестановка τ τ --> {\displaystyle \tau }

Операция σ σ --> {\displaystyle \sigma }

Расшифрование

Процедура расширения ключа

Формирование расширенных ключей

Вычисление ключей раундов

Безопасность

Недостатки алгоритма Crypton

Достоинства алгоритма Crypton

Интегральная атака на шифр Crypton (4-х раундовый)

Краткое описание шифра

Алгоритм реализации интегральной атаки

Конкурс AES

Версии алгоритма Crypton

Примечания

Литература

Ссылки

Табличная замена $\gamma$

Линейное преобразование $\pi$

Байтовая перестановка $\tau$

Операция $\sigma$