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 подключів ${\displaystyle K_{0},...,K_{32}\,}$ довжиною 128 біт. Довжина використовуваного ключа може приймати різні значення, але для конкретики зафіксуємо їх довжину в 128, 192 або 256 біт. Короткі ключі довжиною менше 256 біт доповнюються до повної довжини в 256 біт.

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

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

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

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

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

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

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

де

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \,}$

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

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

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

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

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

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

Початкова перестановка ${\displaystyle 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

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

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

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

Таблиця підстановок ${\displaystyle 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

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

Таблиця інверсних підстановок ${\displaystyle 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

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

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

Линійне перетворення ${\displaystyle 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}

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

Зворотне лінійне перетворення ${\displaystyle 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}

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

Кінцева перестановка ${\displaystyle 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 раундів. Відкритий текст є першими проміжними даними ${\displaystyle B_{0}=P\,}$. Потім виконується 32 раунди, кожен i-й раунд складається з:

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

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

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

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

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

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

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

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

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

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

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

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

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

де ${\displaystyle <<<\,}$ позначає циклічний бітовий зсув, а ${\displaystyle <<\,}$ - бітовий зсув. В останньому раунді це лінійне перетворення замінено додатковим змішуванням з ключем ${\displaystyle 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
• ~ rja14/Papers/serpentcase.pdf|author = Ross Anderson, Eli Biham and Lars Knudsen. The Case for Serpent
• ~ rja14/Papers/ventura.pdf|author = Ross Anderson, Eli Biham, Lars Knudsen. Serpent: A Flexible Block Cipher With Maximum Assurance
• T. Courtois, Josef Pieprzyk. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations ^{[недоступне посилання з червня 2019]}

• ~ rja14/serpent.html Домашня сторінка Serpent
• # Serpent SCAN's entry for Serpent
• Serpent
• In Pellicano Case, Lessons in Wiretapping Skills
• Конкурс AES
• Конкурс на новий криптостандарт
• Основні параметри