Serpent (криптографія)

Serpent

Розробники	Росс Андерсон, Елі Біхам, Ларс Кнудсен
Уперше оприлюднений	1998 р.
Раундів	32
Тип	SP-мережа

Serpent («змія», деякі попередні розробки авторів теж носили назви на честь тварин, наприклад Tiger, Bear) - симетричний блочний алгоритм шифрування, розроблений Россом Андерсоном, Елі Біхамом та Ларсом Кнудсеном. Алгоритм був одним з фіналістів 2-го етапу конкурсу AES. Як і інші алгоритми, які брали участь у конкурсі AES, Serpent має розмір блоку 128 біт і можливі довжини ключа 128, 192 або 256 біт. Алгоритм являє собою 32-раундовий шифр на основі SP-мережі, і працює з блоком з чотирьох 32-бітових слів. Serpent був розроблений так, що всі операції можуть бути виконані паралельно, використовуючи 32-а 1-бітних «потоків».

При розробці Serpent використовувався консервативніший підхід до безпеки, ніж у інших фіналістів AES, проектувальники шифру вважали, що 16 раундів достатньо, щоб протистояти відомим видам криптоаналізу, але збільшили число раундів до 32, щоб алгоритм міг краще протистояти ще не відомим методам криптоаналізу.

Ставши фіналістом конкурсу AES, алгоритм Serpent в результаті голосування зайняв 2 місце.

Шифр Serpent не запатентований і є громадським надбанням.

Основні принципи

Алгоритм створювався під гаслом «криптографічний алгоритм 21 століття» для участі в конкурсі AES. При створенні нового алгоритму Serpent його автори дотримувалися консервативних поглядів на проектування, що підтверджується первісним рішенням про використання таблиць підстановки з відомого багато років раніше алгоритму шифрування DES, який протягом довгого часу вивчався провідними фахівцями в області криптографії та захисту інформації і чиї властивості і особливості були добре відомі науковому світу. Одночасно з цим до нового алгоритму міг бути застосований вичерпний аналіз, вже розроблений для DES. Не використовувалися нові, неперевірені і невипробувані технології при створенні шифру, який у разі прийняття був би використаний для захисту величезних масивів фінансових транзакцій та урядової інформації. Основною вимогою до учасників конкурсу AES було те, що алгоритм-претендент повинен бути швидшим, ніж 3DES, і надавати як мінімум такий же рівень безпеки: він повинен мати блок даних довжиною 128 біт і ключ завдовжки 256 біт. 16-раундовий Serpent був би таким же надійним, як 3DES, але в два рази швидшим. Однак, автори вирішили, що для більшої надійності варто збільшити кількість раундів до 32. Це зробило шифр таким же швидким, як DES, і набагато надійнішим, ніж 3DES.

Структура алгоритму

Алгоритм Serpent є SP-мережею, у котрій весь блок даних довжиною 128 біт на кожному раунді розбивається на 4 слова довжиною 32 біти. Всі значення, що використовуються при шифруванні є бітовими потоками. Бітові індекси змінюють значення від 0 до 31 для 32-бітових слів, від 0 до 127 - для 128-бітових блоків та від 0 до 255 для 256-бітових ключів тощо. Для внутрішніх обчислень всі біти величин представлені в прямому порядку (little-endian).

Serpent шифрує відкритий текст P довжиною 128 біт в шифротекст C довжиною таких же 128 біт за 32 раунд за допомогою 33 подключів $K_{0},...,K_{32}\,$ довжиною 128 біт. Довжина використовуваного ключа може приймати різні значення, але для конкретики зафіксуємо їх довжину в 128, 192 або 256 біт. Короткі ключі довжиною менше 256 біт доповнюються до повної довжини в 256 біт.

Шифрування складається з наступних основних кроків:

• Початкова перестановка;
• 32 раунд, кожен з яких складається з операції змішування з 128-бітовим ключем (побітове логічне виключаюче «або»), таблична заміна (S-box) і лінійне перетворення. В останньому раунді лінійне перетворення замінюється додатковим накладанням ключа;
• Кінцева перестановка;

Початкова і кінцева перестановки не мають будь-якої криптографічного значущості. Вони використовуються для спрощення оптимізованої реалізації алгоритму і підвищення обчислювальної ефективності.

Рівняння структури алгоритму:

${\hat {B}}_{0}=IP(P)\,$

${\hat {B}}_{i+1}=R_{i}({\hat {B}}_{i})\,$

$C=FP({\hat {B}}_{32})\,$,

де

$R_{i}(X)=L({\hat {S}}_{i}(X\oplus {\hat {K}}_{i})),i=0,...,30\,$

$R_{i}(X)={\hat {S}}_{i}(X\oplus {\hat {K}}_{i})\oplus {\hat {K}}_{32},i=31\,$,

де ${\hat {S}}_{i}\,$ - це застосування таблиці підстановки ${\hat {S}}_{imod8}\,$ 32 раз паралельно і $L\,$ - лінійне перетворення.

Розширення ключа

Як і інші алгоритми, що брали участь в конкурсі AES, Serpent має можливі довжини ключа 128, 192 або 256 біт. «Неповний» ключ довжиною менше 256 біт доповнюється за наступним правилом: додається одиничний біт справа, за ним слід стільки нульових бітів, щоб довжина ключа стала дорівнює 256 бітам.

Алгоритм вибору підключів з ключа

Спочатку при необхідності ключ доповнюється до 256 біт і перетвориться в 33 підключа $K_{0},...,K_{32}\,$ довжиною 128 біт наступним способом:

Вихідний ключ представляється у вигляді 8 32-бітових слів $w_{-8},...,w_{-1}$ для обчислення проміжного ключа за правилом:

$W_{i}=(w_{i-8}+w_{i-5}+w_{i-3}+w_{i-1}+\phi +i)<<<11\,$ ,

де $\phi \,$ - це дробова частина золотого перерізу ${\frac {{\sqrt {5}}+1}{2}}$ або 0x9e3779b9 в шістнадцятковій системі числення, а $<<<\,$ - це циклічний бітовий зсув.

Раундові ключі обчислюються з проміжних ключів використанням таблиць підстановки наступним чином:

$\left\{k_{0},k_{1},k_{2},k_{3}\right\}=S_{3}\left(w_{0},w_{1},w_{2},w_{3}\right)\,$

$\left\{k_{4},k_{5},k_{6},k_{7}\right\}=S_{2}\left(w_{4},w_{5},w_{6},w_{7}\right)\,$

$\left\{k_{8},k_{9},k_{10},k_{11}\right\}=S_{1}\left(w_{8},w_{9},w_{10},w_{11}\right)\,$

$\left\{k_{12},k_{13},k_{14},k_{15}\right\}=S_{0}\left(w_{12},w_{13},w_{14},w_{15}\right)\,$

$\left\{k_{16},k_{17},k_{18},k_{19}\right\}=S_{7}\left(w_{16},w_{17},w_{18},w_{19}\right)\,$

$\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \,$

$\left\{k_{124},k_{125},k_{126},k_{127}\right\}=S_{4}\left(w_{124},w_{125},w_{126},w_{127}\right)\,$

$\left\{k_{128},k_{129},k_{130},k_{131}\right\}=S_{3}\left(w_{128},w_{129},w_{130},w_{131}\right)\,$

Проміжні 32-бітові величини $k_{j}\,$ перенумеровуються і виходять 128-бітні підключі:

$K_{i}=\left\{k_{4i},k_{4i+1},k_{4i+2},k_{4i+3}\right\}\,$

При стандартному описі алгоритму ми повинні застосувати початкову перестановку $IP\,$ до раундового ключа, щоб розташувати біти ключа в належному порядку, тобто ${\hat {K}}_{i}=IP(K_{i})\,$

Початкова перестановка $IP\,$

Дана перестановка $IP\,$ задається наступною таблицею, де вказується позиція, на яку перейде відповідний біт (наприклад, біт 1 перейде на 32 позицію):

Початкова перестановка $IP\,$

0	32	64	96	1	33	65	97	2	34	66	98	3	35	67	99
4	36	68	100	5	37	69	101	6	38	70	102	7	39	71	103
8	40	72	104	9	41	73	105	10	42	74	106	11	43	75	107
12	44	76	108	13	45	77	109	14	46	78	110	15	47	79	111
16	48	80	112	17	49	81	113	18	50	82	114	19	51	83	115
20	52	84	116	21	53	85	117	22	54	86	118	23	55	87	119
24	56	88	120	25	57	89	121	26	58	90	122	27	59	91	123
28	60	92	124	29	61	93	125	30	62	94	126	31	63	95	127

S-бокси (таблиці замін)

В алгоритмі Serpent таблиці замін є 4-бітовими перестановками з властивостями стійкості до диференціального криптоаналізу, до лінійного криптоаналізу і такою властивістю, що порядок вихідних біт, як функції вхідних повинен бути максимальний, тобто бути рівним 3.

Таблиця підстановки генерується з відомих і добре вивчених таблиць для алгоритму DES в ітераційному процесі, поки не будуть отримані бажані диференціальні й лінійні властивості. Таким чином, створюється 8 таблиць підстановки.

Нижче представлені таблиці підстановки:

Таблиця підстановок $S_{i}\,$

S0:	3	8	15	1	10	6	5	11	14	13	4	2	7	0	9	12
S1:	15	12	2	7	9	0	5	10	1	11	14	8	6	13	3	4
S2:	8	6	7	9	3	12	10	15	13	1	14	4	0	11	5	2
S3:	0	15	11	8	12	9	6	3	13	1	2	4	10	7	5	14
S4:	1	15	8	3	12	0	11	6	2	5	4	10	9	14	7	13
S5:	15	5	2	11	4	10	9	12	0	3	14	8	13	6	7	1
S6:	7	2	12	5	8	4	6	11	14	9	1	15	13	3	10	0
S7:	1	13	15	0	14	8	2	11	7	4	12	10	9	3	5	6

І інверсні таблиці підстановки:

Таблиця інверсних підстановок $S_{i}^{-1}\,$

InvS0:	13	3	11	0	10	6	5	12	1	14	4	7	15	9	8	2
InvS1:	5	8	2	14	15	6	12	3	11	4	7	9	1	13	10	0
InvS2:	12	9	15	4	11	14	1	2	0	3	6	13	5	8	10	7
InvS3:	0	9	10	7	11	14	6	13	3	5	12	2	4	8	15	1
InvS4:	5	0	8	3	10	9	7	14	2	12	11	6	4	15	13	1
InvS5:	8	15	2	9	4	1	13	14	11	6	5	3	7	12	10	0
InvS6:	15	10	1	13	5	3	6	0	4	9	14	7	2	12	8	11
InvS7:	3	0	6	13	9	14	15	8	5	12	11	7	10	1	4	2

Лінійне перетворення $LT\,$

Лінійне перетворення $LT\,$ задається наступною таблицею, де біти перераховані від 0 до 127 (наприклад, вихідний 2 біт утворений 2, 9, 15, 30, 76, 84, 126 битами, складеними за модулем 2) . В кожному рядку описується 4 вихідних біти, які разом складають вхідні дані на одну таблицю замін в наступному раунді. Варто зазначити, що даний набір являє собою таблицю $IP(LT(FP(x)))\,$, де $LT\,$ і є те лінійне перетворення.

Таблиця лінійного перетворення:

Линійне перетворення $LT\,$

{16 52 56 70 83 94 105}	{72 114 125}	{ 2 9 15 30 76 84 126}	{36 90 103}
{20 56 60 74 87 98 109}	{ 1 76 118}	{ 2 6 13 19 34 80 88}	{40 94 107}
{24 60 64 78 91 102 113}	{ 5 80 122}	{ 6 10 17 23 38 84 92}	{44 98 111}
{28 64 68 82 95 106 117}	{ 9 84 126}	{10 14 21 27 42 88 96}	{48 102 115}
{32 68 72 86 99 110 121}	{ 2 13 88}	{14 18 25 31 46 92 100}	{52 106 119}
{36 72 76 90 103 114 125}	{ 6 17 92}	{18 22 29 35 50 96 104}	{56 110 123}
{ 1 40 76 80 94 107 118}	{10 21 96}	{22 26 33 39 54 100 108}	{60 114 127}
{ 5 44 80 84 98 111 122}	{14 25 100}	{26 30 37 43 58 104 112}	{ 3 118 }
{ 9 48 84 88 102 115 126}	{18 29 104}	{30 34 41 47 62 108 116}	{ 7 122 }
{ 2 13 52 88 92 106 119}	{22 33 108}	{34 38 45 51 66 112 120}	{11 126 }
{ 6 17 56 92 96 110 123}	{26 37 112}	{38 42 49 55 70 116 124}	{ 2 15 76}
{10 21 60 96 100 114 127}	{30 41 116}	{ 0 42 46 53 59 74 120}	{ 6 19 80}
{ 3 14 25 100 104 118 }	{34 45 120}	{ 4 46 50 57 63 78 124}	{10 23 84}
{ 7 18 29 104 108 122 }	{38 49 124}	{ 0 8 50 54 61 67 82}	{14 27 88}
{11 22 33 108 112 126 }	{ 0 42 53}	{ 4 12 54 58 65 71 86}	{18 31 92}
{ 2 15 26 37 76 112 116}	{ 4 46 57}	{ 8 16 58 62 69 75 90}	{22 35 96}
{ 6 19 30 41 80 116 120}	{ 8 50 61}	{12 20 62 66 73 79 94}	{26 39 100}
{10 23 34 45 84 120 124}	{12 54 65}	{16 24 66 70 77 83 98}	{30 43 104}
{ 0 14 27 38 49 88 124}	{16 58 69}	{20 28 70 74 81 87 102}	{34 47 108}
{ 0 4 18 31 42 53 92}	{20 62 73}	{24 32 74 78 85 91 106}	{38 51 112}
{ 4 8 22 35 46 57 96}	{24 66 77}	{28 36 78 82 89 95 110}	{42 55 116}
{ 8 12 26 39 50 61 100}	{28 70 81}	{32 40 82 86 93 99 114}	{46 59 120}
{12 16 30 43 54 65 104}	{32 74 85}	{36 90 103 118 }	{50 63 124}
{16 20 34 47 58 69 108}	{36 78 89}	{40 94 107 122 }	{ 0 54 67}
{20 24 38 51 62 73 112}	{40 82 93}	{44 98 111 126 }	{ 4 58 71}
{24 28 42 55 66 77 116}	{44 86 97}	{ 2 48 102 115 }	{ 8 62 75}
{28 32 46 59 70 81 120}	{48 90 101}	{ 6 52 106 119 }	{12 66 79}
{32 36 50 63 74 85 124}	{52 94 105}	{10 56 110 123 }	{16 70 83}
{ 0 36 40 54 67 78 89}	{56 98 109}	{14 60 114 127 }	{20 74 87}
{ 4 40 44 58 71 82 93}	{60 102 113}	{ 3 18 72 114 118 125 }	{24 78 91}
{ 8 44 48 62 75 86 97}	{64 106 117}	{ 1 7 22 76 118 122 }	{28 82 95}
{12 48 52 66 79 90 101}	{68 110 121}	{ 5 11 26 80 122 126 }	{32 86 99}

Таблиця зворотного лінійного перетворення, яке використовується при розшифровці:

Зворотне лінійне перетворення $ILT\,$

{ 53 55 72}	{ 1 5 20 90 }	{ 15 102}	{ 3 31 90 }
{ 57 59 76}	{ 5 9 24 94 }	{ 19 106}	{ 7 35 94 }
{ 61 63 80}	{ 9 13 28 98 }	{ 23 110}	{11 39 98 }
{ 65 67 84}	{13 17 32 102 }	{ 27 114}	{ 1 3 15 20 43 102 }
{ 69 71 88}	{17 21 36 106 }	{ 1 31 118}	{ 5 7 19 24 47 106 }
{ 73 75 92}	{21 25 40 110 }	{ 5 35 122}	{ 9 11 23 28 51 110 }
{ 77 79 96}	{25 29 44 114 }	{ 9 39 126}	{13 15 27 32 55 114 }
{ 81 83 100}	{ 1 29 33 48 118}	{ 2 13 43}	{ 1 17 19 31 36 59 118}
{ 85 87 104}	{ 5 33 37 52 122}	{ 6 17 47}	{ 5 21 23 35 40 63 122}
{ 89 91 108}	{ 9 37 41 56 126}	{10 21 51}	{ 9 25 27 39 44 67 126}
{ 93 95 112}	{ 2 13 41 45 60}	{14 25 55}	{ 2 13 29 31 43 48 71}
{ 97 99 116}	{ 6 17 45 49 64}	{18 29 59}	{ 6 17 33 35 47 52 75}
{101 103 120}	{10 21 49 53 68}	{22 33 63}	{10 21 37 39 51 56 79}
{105 107 124}	{14 25 53 57 72}	{26 37 67}	{14 25 41 43 55 60 83}
{ 0 109 111}	{18 29 57 61 76}	{30 41 71}	{18 29 45 47 59 64 87}
{ 4 113 115}	{22 33 61 65 80}	{34 45 75}	{22 33 49 51 63 68 91}
{ 8 117 119}	{26 37 65 69 84}	{38 49 79}	{26 37 53 55 67 72 95}
{ 12 121 123}	{30 41 69 73 88}	{42 53 83}	{30 41 57 59 71 76 99}
{ 16 125 127}	{34 45 73 77 92}	{46 57 87}	{34 45 61 63 75 80 103}
{ 1 3 20}	{38 49 77 81 96}	{50 61 91}	{38 49 65 67 79 84 107}
{ 5 7 24}	{42 53 81 85 100}	{54 65 95}	{42 53 69 71 83 88 111}
{ 9 11 28}	{46 57 85 89 104}	{58 69 99}	{46 57 73 75 87 92 115}
{ 13 15 32}	{50 61 89 93 108}	{62 73 103}	{50 61 77 79 91 96 119}
{ 17 19 36}	{54 65 93 97 112}	{66 77 107}	{54 65 81 83 95 100 123}
{ 21 23 40}	{58 69 97 101 116}	{70 81 111}	{58 69 85 87 99 104 127}
{ 25 27 44}	{62 73 101 105 120}	{74 85 115}	{ 3 62 73 89 91 103 108}
{ 29 31 48}	{66 77 105 109 124}	{78 89 119}	{ 7 66 77 93 95 107 112}
{ 33 35 52}	{ 0 70 81 109 113}	{82 93 123}	{11 70 81 97 99 111 116}
{ 37 39 56}	{ 4 74 85 113 117}	{86 97 127}	{15 74 85 101 103 115 120}
{ 41 43 60}	{ 8 78 89 117 121}	{ 3 90}	{19 78 89 105 107 119 124}
{ 45 47 64}	{12 82 93 121 125}	{ 7 94}	{ 0 23 82 93 109 111 123}
{ 49 51 68}	{ 1 16 86 97 125}	{ 11 98}	{ 4 27 86 97 113 115 127}

Кінцева перестановка $FP\,$

Дана перестановка є зворотною до початкової, тобто $FP=IP^{-1}\,$, і задається наступною таблицею:

Кінцева перестановка $FP\,$

0	4	8	12	16	20	24	28	32	36	40	44	48	52	56	60
64	68	72	76	80	84	88	92	96	100	104	108	112	116	120	124
1	5	9	13	17	21	25	29	33	37	41	45	49	53	57	61
65	69	73	77	81	85	89	93	97	101	105	109	113	117	121	125
2	6	10	14	18	22	26	30	34	38	42	46	50	54	58	62
66	70	74	78	82	86	90	94	98	102	106	110	114	118	122	126
3	7	11	15	19	23	27	31	35	39	43	47	51	55	59	63
67	71	75	79	83	87	91	95	99	103	107	111	115	119	123	127

Ефективна реалізація

Ефективна реалізація алгоритму

Бажання авторів зробити алгоритм саме таким, яким він є стає зрозумілим при розгляді його ефективної низькорівневої реалізації.

Serpent був створений таким чином, щоб всі операції в процесі шифрування і розшифрування одного блоку могли бути виконані паралельно в 32 потоках. До того ж низькорівневий опис алгоритму набагато простішій, ніж стандартний опис. Ніяких початкових і кінцевих перестановок не потрібно.

Шифрування складається з 32 раундів. Відкритий текст є першими проміжними даними $B_{0}=P\,$. Потім виконується 32 раунди, кожен i-й раунд складається з:

• Змішування з ключем. Проводиться побітове виключаюче «або» проміжних даних $B_{i}\,$ з ключем довжиною 128 біт;
• Застосування таблиць підстановки. Вхідні дані довжиною 128 біт поділяються на 4 слова по 32 біта. Таблиця підстановки, реалізована послідовністю логічних операцій (як якщо це було б реалізовано апаратно), застосовується до цих 4 словам. В результаті виходить 4 вихідних слова. Таким чином, центральний процесор виконує підстановку по 32 копій таблиці одночасно;
• Лінійне перетворення. 32-бітові слова перетворюються таким чином:

$X_{0},X_{1},X_{2},X_{3}=S_{i}(B_{i}\oplus K_{i})\,$

$X_{0}=X_{0}<<<13\,$

$X_{2}=X_{2}<<<3\,$

$X_{1}=X_{1}\oplus X_{0}\oplus X2\,$

$X_{3}=X_{3}\oplus X_{2}\oplus (X_{0}<<3)\,$

$X_{1}=X_{1}<<<1\,$

$X_{3}=X_{3}<<<7\,$

$X_{0}=X_{0}\oplus X_{1}\oplus X3\,$

$X_{2}=X_{2}\oplus X_{3}\oplus (X_{1}<<7)\,$

$X_{0}=X_{0}<<<5\,$

$X_{2}=X_{2}<<<22\,$

$B_{i+1}=X_{0},X_{1},X_{2},X_{3}\,$,

де $<<<\,$ позначає циклічний бітовий зсув, а $<<\,$ - бітовий зсув. В останньому раунді це лінійне перетворення замінено додатковим змішуванням з ключем $B_{32}=S_{7}(B_{31}\oplus K_{31})\oplus K_{32}\,$

Першою причиною вибору такого лінійного перетворення є максимізація лавинного ефекту. Такі таблиці підстановки мають властивість, що зміна кожного вхідного біта призведе до зміни 2 вихідних бітів. Таким чином, кожен вхідний біт відкритого тексту вже через 3 раунди впливає на всі вихідні біти. Аналогічно кожен біт ключа впливає на результат шифрування.

Друга причина полягає в простоті перетворення. Воно може бути реалізоване на будь-якому сучасному процесорі з мінімальними витратами.

Безпека і крипостійкість

При розробці та аналізі алгоритму Serpent не було виявлено будь-яких вразливостей в повній 32-раундовій версії. Але при виборі переможця конкурсу AES, це було справедливо і до решти алгоритмів-фіналістів.

На думку творців Serpent, алгоритм може бути зламаний, тільки якщо буде створена нова потужна математична теорія.

Варто відзначити, що XSL-атака, якщо буде доведена ефективність її проведення, послабить крипостійкість Serpent.

Література

• ~ rja14/Papers/serpent.pdf|author = Ross Anderson, Eli Biham, Lars Knudsen. Serpent: A Proposal for the Advanced Encryption Standard [Архівовано 11 серпня 2004 у Wayback Machine.]
• ~ rja14/Papers/serpentcase.pdf|author = Ross Anderson, Eli Biham and Lars Knudsen. The Case for Serpent [Архівовано 11 серпня 2004 у Wayback Machine.]
• ~ rja14/Papers/ventura.pdf|author = Ross Anderson, Eli Biham, Lars Knudsen. Serpent: A Flexible Block Cipher With Maximum Assurance [Архівовано 11 серпня 2004 у Wayback Machine.]
• T. Courtois, Josef Pieprzyk. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations ^{[недоступне посилання з червня 2019]}

Посилання

• ~ rja14/serpent.html Домашня сторінка Serpent [Архівовано 11 серпня 2004 у Wayback Machine.]
• # Serpent SCAN's entry for Serpent [Архівовано 28 січня 2012 у WebCite]
• Serpent
• In Pellicano Case, Lessons in Wiretapping Skills [Архівовано 27 травня 2012 у Wayback Machine.]
• Конкурс AES [Архівовано 10 лютого 2012 у Wayback Machine.]
• Конкурс на новий криптостандарт [Архівовано 3 липня 2011 у Wayback Machine.]
• Основні параметри [Архівовано 9 березня 2016 у Wayback Machine.]