CS-Cipher

Cs-cipher (фр. Chiffrement Symètrique, симметричный шифр) — симметричный 64 битный блочный алгоритм шифрования данных , использующий длину ключа до 128 бит. По принципу работы является 8 раундовой SP-сетью.

История

Cs-cipher разработали в 1998 году Жак Штерн (англ. Jacques Stern) и Серж Водене (англ. Serge Vaudenay) при поддержке Compagnie des Signaux . Он был представлен в качестве кандидата в проекте NESSIE в рамках программы Европейской комиссии IST (англ. Information Societies Technology, информационные общественные технологии) в конкурсной группе 64-битных блочных шифров. Несмотря на то, что при исследовании не было обнаружено уязвимостей, шифр не был выбран для 2 фазы проекта, потому что оказался самым медленным в своей группе.

Основные обозначения

Используемые функции

Для начала обозначим следующие обозначения:

• [math]\displaystyle{ P(x) = z_l \parallel z_r }[/math] - независимая перестановка 8-битных строк . Определяется как трех-раундовая сеть Фейстеля:
  • 8-битная входная строка делится на две 4-битных [math]\displaystyle{ x = x_l\parallel x_r }[/math]
  • [math]\displaystyle{ y = x_l \oplus f(x_r) }[/math]
  • [math]\displaystyle{ z_r = x_r \oplus g(y) }[/math]
  • [math]\displaystyle{ z_l = y\oplus f(z_r) }[/math]
  • Результатом является строка [math]\displaystyle{ z = z_l\parallel z_r }[/math]
    • Функции [math]\displaystyle{ f(x) }[/math] и [math]\displaystyle{ g(x) }[/math] задаются таблицей:

таблица [math]\displaystyle{ f(x) }[/math] и [math]\displaystyle{ g(x) }[/math]

x	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
[math]\displaystyle{ f(x) }[/math]	f	d	b	b	7	5	7	7	e	d	a	b	e	d	e	f
[math]\displaystyle{ g(x) }[/math]	a	6	0	2	b	e	1	8	d	4	5	3	f	c	7	9

В конечном итоге [math]\displaystyle{ P(x) }[/math] задается с помощью таблицы:

таблица [math]\displaystyle{ P(x) }[/math]

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

• Например [math]\displaystyle{ P( }[/math] 26[math]\displaystyle{ _{16}) }[/math]:
  • [math]\displaystyle{ y = }[/math]2[math]\displaystyle{ _{16} \oplus f( }[/math] 6[math]\displaystyle{ _{16}) = }[/math] 2[math]\displaystyle{ _{16} \oplus }[/math] 7[math]\displaystyle{ _{16} = }[/math] 5[math]\displaystyle{ _{16} }[/math]
  • [math]\displaystyle{ z_r = }[/math] 6[math]\displaystyle{ _{16} \oplus g(y) = }[/math] 6[math]\displaystyle{ _{16}\oplus }[/math] e[math]\displaystyle{ _{16} = 8 }[/math]
  • [math]\displaystyle{ z_l = y \oplus f(z_r) = }[/math] 5[math]\displaystyle{ _{16} \oplus }[/math] e[math]\displaystyle{ _{16} = }[/math] b[math]\displaystyle{ _{16} }[/math]
  • Итого: [math]\displaystyle{ P( }[/math] 26[math]\displaystyle{ _{16}) = }[/math] b8[math]\displaystyle{ _{16} }[/math]

• [math]\displaystyle{ P^8(x) = P(x_{63..56})\parallel P(x_{55..48})\parallel P(x_{47..40})\parallel P(x_{39..32})\parallel P(x_{31..24})\parallel P(x_{23..16})\parallel P(x_{15..8})\parallel P(x_{7..0}) }[/math] - преобразование 64-битной строки, используется для генерации ключей и в раундовой функции
• [math]\displaystyle{ T(z) = z_{63}\parallel z_{55}\parallel \dots\parallel z_7\parallel z_{62}\parallel z_{54}\parallel \dots \parallel z_0 }[/math] - битовая транспозиция, в данном случае транспонирование матрицы , составленной из 8 битных строк, используется при генерации ключей. На вход функция принимает 64-битную строку
• [math]\displaystyle{ R_l(x) }[/math] - функция циклического битового сдвига влево, в данном случае принимает 8-битную строку: [math]\displaystyle{ R(x_7\parallel x_6\parallel x_5\parallel x_4\parallel x_3\parallel x_2\parallel x_1\parallel x_0) = x_6\parallel x_5\parallel x_4\parallel x_3\parallel x_2\parallel x_1\parallel x_0\parallel x_7 }[/math]
• [math]\displaystyle{ \varphi(x) = (R_l(x) \land 55_{16})\oplus x }[/math] - преобразование, используется в раундовой функции. На вход принимает 8-битную строку, если упростить получим:
  • [math]\displaystyle{ \varphi(x_7\parallel x_6\parallel x_5\parallel x_4\parallel x_3\parallel x_2\parallel x_1\parallel x_0) = x_7\parallel( x_6\oplus x_5) \parallel x_5\parallel( x_4\oplus x_3)\parallel x_3\parallel( x_2\oplus x_1)\parallel x_1\parallel (x_0\oplus x_7) }[/math]
• [math]\displaystyle{ \phi^'(x) = (R_l(x)\land aa_{16})\oplus x }[/math] - преобразование, используется при расшифровке. На вход принимает 8-битную строку
• [math]\displaystyle{ M(x) }[/math] - преобразование, используется в раундовой функции, берет на вход 16-битные строки [math]\displaystyle{ x=x_l\parallel x_r }[/math], результатом является 16-битная строка [math]\displaystyle{ M(x)=y_l\parallel y_r }[/math], в свою очередь:
  • [math]\displaystyle{ y_l = P( \varphi (x_l)\oplus x_r) }[/math]
  • [math]\displaystyle{ y_r = P( R_l(x_l)\oplus x_r) }[/math]
• [math]\displaystyle{ M^{-1}(y_l \parallel y_r) }[/math] - преобразование, используется при расшифровке, берет на вход 16-битные строки [math]\displaystyle{ y=y_l\parallel y_r }[/math], результатом является 16-битная строка [math]\displaystyle{ M^{-1}(y)=x_l\parallel x_r }[/math], в свою очередь:
  • [math]\displaystyle{ x_l = \phi^{'}(P(y_l)\oplus P(y_r)) }[/math]
  • [math]\displaystyle{ x_r = R_l(x_l)\oplus P(y_r) }[/math]
• [math]\displaystyle{ F_{c_i}(x) = T (P^8(x\oplus c^i)) }[/math] - используется для генерации ключей

Константы алгоритма

Ниже представлен список констант, заданных создателями алгоритма:

• [math]\displaystyle{ c = }[/math] b7e151628aed2a6a[math]\displaystyle{ _{16} }[/math], требуется для раундовой функции
• [math]\displaystyle{ c^' = }[/math] bf7158809cf4f3c7[math]\displaystyle{ _{16} }[/math], требуется для раундовой функции
• [math]\displaystyle{ c^0 = }[/math] 290d61409ceb9e8f[math]\displaystyle{ _{16} }[/math], требуется для генерации ключей
• [math]\displaystyle{ c^1 = }[/math] 1f855f585b013986[math]\displaystyle{ _{16} }[/math], требуется для генерации ключей
• [math]\displaystyle{ c^2 = }[/math] 972ed7d635ae1716[math]\displaystyle{ _{16} }[/math], требуется для генерации ключей
• [math]\displaystyle{ c^3 = }[/math] 21b6694ea5728708[math]\displaystyle{ _{16} }[/math], требуется для генерации ключей
• [math]\displaystyle{ c^4 = }[/math] 3c18e6e7faadb889[math]\displaystyle{ _{16} }[/math], требуется для генерации ключей
• [math]\displaystyle{ c^5 = }[/math] b700f76f73841163[math]\displaystyle{ _{16} }[/math], требуется для генерации ключей
• [math]\displaystyle{ c^6 = }[/math] 3f967f6ebf149dac[math]\displaystyle{ _{16} }[/math], требуется для генерации ключей
• [math]\displaystyle{ c^7 = }[/math] a40e7ef6204a6230[math]\displaystyle{ _{16} }[/math], требуется для генерации ключей
• [math]\displaystyle{ c^8 = }[/math] 03c54b5a46a34465[math]\displaystyle{ _{16} }[/math], требуется для генерации ключей

Генерация ключей

Если секретный ключ, используемый в шифре меньше 128 бит, то первые биты заполняются нулями , поэтому в дальнейшем будем считать секретный ключ 128 битным.

Алгоритм генерации ключей

Согласно следующему алгоритму в шифре из 128-битного ключа генерируется 9 подключей [math]\displaystyle{ k^0, k^1, ... , k^8 }[/math] размером 64 бита:

• первоначально ключ делится на две 64 битные половины, таким образом мы получаем начальные параметры:

[math]\displaystyle{ k = k^{-1}\parallel k^{-2} }[/math]

• Для генерации последующих ключей используется рекуррентная формула:

[math]\displaystyle{ k^i= k^{i-2}\oplus F_{c^i}(k^{i-1}) }[/math]

Пример генерации ключей

Рассмотрим пример генерации ключей, описанный создателями CS-cipher. В нем используется секретный ключ

[math]\displaystyle{ k = }[/math] 0123456789abcdeffedcba9876543210[math]\displaystyle{ _{16} }[/math].

Согласно рассмотренному выше, получаем начальные параметры для генерирования раундовых ключей:

[math]\displaystyle{ k^{-1} = }[/math] 0123456789abcdef[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^{-2} = }[/math] fedcba9876543210[math]\displaystyle{ _{16} }[/math]

Рассмотрим подробно генерацию ключа [math]\displaystyle{ k^0 }[/math]:

[math]\displaystyle{ k^0 = k^{-2} \oplus F_{c_0}(k^{-1}) = k^{-2} \oplus T(P^8(k^{-1}\oplus c^0))= }[/math]

[math]\displaystyle{ = k^{-2} \oplus T(P^8( }[/math] 0123456789abcdef[math]\displaystyle{ _{16}\oplus }[/math] 290d61409ceb9e8f[math]\displaystyle{ _{16} ))= }[/math]

[math]\displaystyle{ = k^{-2} \oplus T( }[/math] b711fa89ae0394e4[math]\displaystyle{ _{16}) = }[/math] fedcba9876543210[math]\displaystyle{ _{16}\oplus }[/math] bb21a9e2388bacd4[math]\displaystyle{ _{16} }[/math]

Конечный результат работы алготитма генерации:

[math]\displaystyle{ k^0 = }[/math] 45fd137a4edf9ec4[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^1 = }[/math] 1dd43f03e6f7564c[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^2 = }[/math] ebe26756de9937c7[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^3 = }[/math] 961704e945bad4fb[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^4 = }[/math] 0b60dfe9eff473d4[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^5 = }[/math] 76d3e7cf52c466cf[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^6 = }[/math] 75ec8cef767d3a0d[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^7 = }[/math] 82da3337b598fd6d[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^8 = }[/math] fbd820da8dc8af8c[math]\displaystyle{ _{16} }[/math]

Шифрование

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

Каждый раунд шифровки начинается с операции XOR над входящей 64-битной строкой и подключа. Затем 64-битная строка разделяется на 4 16-битных строки, над которыми происходит нелинейное преобразование( [math]\displaystyle{ M(x) }[/math]). После этого строки снова делятся, на этот раз в результате получается 8 8-битных строк, которые затем переставляются. Данные действия повторяются еще дважды в каждом раунде, разница лишь в том, что операция XOR происходит с заданными константами, а не со сгенерированным ключом. После последнего раунда следует дополнительная операция XOR с оставшимся сгенерированным ключом.

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

Первоначально определим:

• [math]\displaystyle{ m^i }[/math] - 64-битная строка, приходит на вход раундовой функции [math]\displaystyle{ R(x) }[/math] в [math]\displaystyle{ i }[/math] итерации
• [math]\displaystyle{ t^i = t^i_{63..56}\parallel t^i_{55..48}\parallel t^i_{47..40}\parallel t^i_{39..32}\parallel t^i_{31..24}\parallel t^i_{23..16}\parallel t^i_{15..8}\parallel t^i_{7..0} }[/math] - временное 64-битное значение, вычисленное на [math]\displaystyle{ i }[/math] шаге раундовой функции
• [math]\displaystyle{ S }[/math] - 64-битная строка, конечный зашифрованный текст

Раундовая функции [math]\displaystyle{ R(x) }[/math]

Раундовая функция состоит из следующих действий:

1. [math]\displaystyle{ t^1= x }[/math]
2. [math]\displaystyle{ t^2 = M(t^1_{63..48})\parallel M(t^1_{47..32})\parallel M(t^1_{31..16})\parallel M(t^1_{15..0}) }[/math]
3. [math]\displaystyle{ t^3 = t^2_{63..56}\parallel t^2_{47..40}\parallel t^2_{31..24}\parallel t^2_{15..8} \parallel t^2_{55..48}\parallel t^2_{39..32}\parallel t^2_{23..16}\parallel t^2_{7..0} }[/math]
4. [math]\displaystyle{ t^4= t^3 \oplus c }[/math]
5. [math]\displaystyle{ t^5 = M(t^4_{63..48})\parallel M(t^4_{47..32})\parallel M(t^4_{31..16})\parallel M(t^4_{15..0}) }[/math]
6. [math]\displaystyle{ t^6 = t^5_{63..56}\parallel t^5_{47..40}\parallel t^5_{31..24}\parallel t^5_{15..8} \parallel t^5_{55..48}\parallel t^5_{39..32}\parallel t^5_{23..16}\parallel t^5_{7..0} }[/math]
7. [math]\displaystyle{ t^7= t^6 \oplus c^' }[/math]
8. [math]\displaystyle{ t^8 = M(t^7_{63..48})\parallel M(t^7_{47..32})\parallel M(t^7_{31..16})\parallel M(t^7_{15..0}) }[/math]
9. [math]\displaystyle{ m^{i+1} = t^9 = t^8_{63..56}\parallel t^8_{47..40}\parallel t^8_{31..24}\parallel t^8_{15..8} \parallel t^8_{55..48}\parallel t^8_{39..32}\parallel t^8_{23..16}\parallel t^8_{7..0} }[/math]

Зашифровывание

Зашифрование состоит из 8 раундов, конечный 64-битный зашифрованный текст [math]\displaystyle{ S }[/math] можно вычислить из фрагмента открытого текста [math]\displaystyle{ m }[/math] по формуле:

[math]\displaystyle{ S = k^8\oplus R(k^7\oplus \dots R(k^1\oplus R(k^0\oplus m)\dots) }[/math]

Где [math]\displaystyle{ R(x) }[/math] — раундовая функция, описана выше.

Пример зашифровывания открытого текста

Рассмотрим пример зашифровывания открытого текста, описанный создателями CS-cipher. В нем используется следующие секретный ключ и открытый текст:

[math]\displaystyle{ m^0= }[/math] 0123456789abcdef[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k = }[/math] 0123456789abcdeffedcba9876543210[math]\displaystyle{ _{16} }[/math]

Секретный ключ соответствует вышележащему примеру генерации раундовых ключей, то есть раундовые ключи были подсчитаны выше:

[math]\displaystyle{ k^0 = }[/math] 45fd137a4edf9ec4[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^1 = }[/math] 1dd43f03e6f7564c[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^2 = }[/math] ebe26756de9937c7[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^3 = }[/math] 961704e945bad4fb[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^4 = }[/math] 0b60dfe9eff473d4[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^5 = }[/math] 76d3e7cf52c466cf[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^6 = }[/math] 75ec8cef767d3a0d[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^7 = }[/math] 82da3337b598fd6d[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ k^8 = }[/math] fbd820da8dc8af8c[math]\displaystyle{ _{16} }[/math]

Промежуточные результаты для вычисления [math]\displaystyle{ m^1 }[/math]:

[math]\displaystyle{ t^3 = }[/math] d85c19785690b0e3[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ t^6 = }[/math] 0f4bfb9e2f8ac7e2[math]\displaystyle{ _{16} }[/math]

Получим следующие значения на раундах:

[math]\displaystyle{ m^1 = }[/math] c3feb96c0cf4b649[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ m^2 = }[/math] 3f54e0c8e61a84d1[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ m^3 = }[/math] b15cb4af3786976e[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ m^4 = }[/math] 76c122b7a562ac45[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ m^5 = }[/math] 21300b6ccfaa08d8[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ m^6 = }[/math] 99b8d8ab9034ec9a[math]\displaystyle{ _{16} }[/math]

[math]\displaystyle{ m^7 = }[/math] a2245ba3697445d2[math]\displaystyle{ _{16} }[/math]

В итоге получили следующий зашифрованный текст:

[math]\displaystyle{ S = }[/math] 88fddfbe954479d7[math]\displaystyle{ _{16} }[/math]

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

Расшифровывание состоит из 8 раундов, обратных зашифровыванию. Важно, что алгоритм расшифровки использует сгенерированные ключи в обратном порядке, т. е. [math]\displaystyle{ k^8, k^7, k^6, k^5, k^4, k^3, k^2, k^1, k^0 }[/math]. Перед началом происходит операция [math]\displaystyle{ m^0 = S \oplus k^8 }[/math].

Для удобства и соответствия обозначений, еще раз укажем:

• [math]\displaystyle{ i }[/math] - номер итерации: от 0 до 7 включительно - всего 8 раундов
• [math]\displaystyle{ m^i }[/math] - 64-битная строка, приходит на вход обратной к раундовой функции [math]\displaystyle{ R^{-1}(x) }[/math] в [math]\displaystyle{ i }[/math] итерации, [math]\displaystyle{ m^8 }[/math] - открытый текст
• [math]\displaystyle{ k^{7-i} }[/math] - 64-битный сгенерированный ключ, приходит на вход обратной к раундовой функции [math]\displaystyle{ R^{-1}(x) }[/math] в [math]\displaystyle{ i }[/math] итерации
• [math]\displaystyle{ t^i = t^i_{63..56}\parallel t^i_{55..48}\parallel t^i_{47..40}\parallel t^i_{39..32}\parallel t^i_{31..24}\parallel t^i_{23..16}\parallel t^i_{15..8}\parallel t^i_{7..0} }[/math] - временное 64-битное значение, вычисленное на [math]\displaystyle{ i }[/math] шаге обратной к раундовой функции.

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

[math]\displaystyle{ t^1 = m^i_{63..56}\parallel m^i_{31..24}\parallel m^i_{55..48}\parallel m^i_{23..16}\parallel m^i_{47..40}\parallel m^i_{15..8} \parallel m^i_{39..32}\parallel m^i_{7..0} }[/math]

[math]\displaystyle{ t^2 = M^{-1}(t^1_{63..48})\parallel M^{-1}(t^1_{47..32})\parallel M^{-1}(t^1_{31..16})\parallel M^{-1}(t^1_{15..0}) }[/math]

[math]\displaystyle{ t^3 = t^2 \oplus c^' }[/math]

[math]\displaystyle{ t^4 = t^3_{63..56}\parallel t^3_{31..24}\parallel t^3_{55..48}\parallel t^3_{23..16}\parallel t^3_{47..40}\parallel t^3_{15..8} \parallel t^3_{39..32}\parallel t^3_{7..0} }[/math]

[math]\displaystyle{ t^5 = M^{-1}(t^4_{63..48})\parallel M^{-1}(t^4_{47..32})\parallel M^{-1}(t^4_{31..16})\parallel M^{-1}(t^4_{15..0}) }[/math]

[math]\displaystyle{ t^6 = t^5 \oplus c }[/math]

[math]\displaystyle{ t^7 = t^6_{63..56}\parallel t^6_{31..24}\parallel t^6_{55..48}\parallel t^6_{23..16}\parallel t^6_{47..40}\parallel t^6_{15..8} \parallel t^6_{39..32}\parallel t^6_{7..0} }[/math]

[math]\displaystyle{ t^8 = M^{-1}(t^7_{63..48})\parallel M^{-1}(t^7_{47..32})\parallel M^{-1}(t^7_{31..16})\parallel M^{-1}(t^7_{15..0}) }[/math]

[math]\displaystyle{ m^{i+1} = t^9 = t^8 \oplus k^{7-i} }[/math]

Статистическая оценка зашифрованных данных

В ходе участия в проекте NESSIE были проведены множество статистических тестов над зашифрованными данными, в том числе:

• Универсальный статистический тест Маурера
• Тест на корреляцию
• Тест на линейную сложность
• Тест собирателя купонов
• Тест на совпадение перекрывающихся шаблонов
• Тест подпоследовательностей

В результате тестирования шифра не было обнаружено его отклонений от случайного распределения.

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

Марковский шифр

Предположим, у нас есть [math]\displaystyle{ r }[/math] раундовый шифр, зашифрованный текст можно получить по формуле: [math]\displaystyle{ S = Enc(x) = (\rho_r \circ ... \circ \rho_1)(x) }[/math], в котором каждый раунд [math]\displaystyle{ \rho_i }[/math] использует свой ключ [math]\displaystyle{ k_i }[/math].

Тогда Марковским шифром называется шифр, для которого для любого раунда [math]\displaystyle{ i }[/math] и любых [math]\displaystyle{ x }[/math], [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] выполнено:

[math]\displaystyle{ Pr_{k_i}[\rho_i(x\oplus a) \oplus \rho_i(x) = b] =Pr_{k_i, X}[\rho_i(X\oplus a) \oplus \rho_i(X) = b] }[/math]

Определение анализируемого шифра

В ходе анализа используется модифицированный шифр CS-cipher, называемый в дальнейшем CSC.

Он получается из шифра CS-cipher следующей заменой:

• для шифровки CS-cipher использует следующую последовательность ключей и констант:

[math]\displaystyle{ k^0, c, c^', k^1, c, c^',...,k^7, c, c^', k^8 }[/math]. Для удобства переобозначим их как [math]\displaystyle{ k_0, k_1, ..., k_{24} }[/math].

• По определению CSC получается из CS-cipher заменой полученной с помощью генерации ключей и констант последовательности [math]\displaystyle{ k_0, k_1, ..., k_{24} }[/math] на 1600-битный случайный ключ [math]\displaystyle{ k= (k_0, k_1, ..., k_{24}) }[/math] с равномерным распределением.

Полученный шифр CSC является 24 раундовым блочным Марковским шифром.

Устойчивость к атакам

Для шифра CSC были доказаны:

• устойчивость к дифференциальному криптоанализу
• устойчивость к линейному криптоанализу
• устойчивость к методу невозможных дифференциалов (англ. Impossible differential cryptanalysis)
• устойчивость к методу усеченных разностей (англ. Truncated differential cryptanalysis)

Поэтому предполагается, что CS-cipher:

• устойчив к дифференциальному криптоанализу после 4 раундов шифровки
• устойчив к методу усеченных разностей (англ. Truncated differential cryptanalysis)
• устойчив к линейному криптоанализу
• устойчив к методу невозможных дифференциалов (англ. Impossible differential cryptanalysis) после 6 раундов шифровки

Реализация

Существует реализации данного алгоритма шифрования на С( предоставлена авторами):

# define CSC_C10 0xbf
# define CSC_C11 0x71
# define CSC_C12 0x58
# define CSC_C13 0x80
# define CSC_C14 0x9c
# define CSC_C15 0xf4
# define CSC_C16 0xf3
# define CSC_C17 0xc7
uint8 tbp[256]={
0x29,0x0d,0x61,0x40,0x9c,0xeb,0x9e,0x8f,
0x1f,0x85,0x5f,0x58,0x5b,0x01,0x39,0x86,
0x97,0x2e,0xd7,0xd6,0x35,0xae,0x17,0x16,
0x21,0xb6,0x69,0x4e,0xa5,0x72,0x87,0x08,
0x3c,0x18,0xe6,0xe7,0xfa,0xad,0xb8,0x89,
0xb7,0x00,0xf7,0x6f,0x73,0x84,0x11,0x63,
0x3f,0x96,0x7f,0x6e,0xbf,0x14,0x9d,0xac,
0xa4,0x0e,0x7e,0xf6,0x20,0x4a,0x62,0x30,
0x03,0xc5,0x4b,0x5a,0x46,0xa3,0x44,0x65,
0x7d,0x4d,0x3d,0x42,0x79,0x49,0x1b,0x5c,
0xf5,0x6c,0xb5,0x94,0x54,0xff,0x56,0x57,
0x0b,0xf4,0x43,0x0c,0x4f,0x70,0x6d,0x0a,
0xe4,0x02,0x3e,0x2f,0xa2,0x47,0xe0,0xc1,
0xd5,0x1a,0x95,0xa7,0x51,0x5e,0x33,0x2b,
0x5d,0xd4,0x1d,0x2c,0xee,0x75,0xec,0xdd,
0x7c,0x4c,0xa6,0xb4,0x78,0x48,0x3a,0x32,
0x98,0xaf,0xc0,0xe1,0x2d,0x09,0x0f,0x1e,
0xb9,0x27,0x8a,0xe9,0xbd,0xe3,0x9f,0x07,
0xb1,0xea,0x92,0x93,0x53,0x6a,0x31,0x10,
0x80,0xf2,0xd8,0x9b,0x04,0x36,0x06,0x8e,
0xbe,0xa9,0x64,0x45,0x38,0x1c,0x7a,0x6b,
0xf3,0xa1,0xf0,0xcd,0x37,0x25,0x15,0x81,
0xfb,0x90,0xe8,0xd9,0x7b,0x52,0x19,0x28,
0x26,0x88,0xfc,0xd1,0xe2,0x8c,0xa0,0x34,
0x82,0x67,0xda,0xcb,0xc7,0x41,0xe5,0xc4,
0xc8,0xef,0xdb,0xc3,0xcc,0xab,0xce,0xed,
0xd0,0xbb,0xd3,0xd2,0x71,0x68,0x13,0x12,
0x9a,0xb3,0xc2,0xca,0xde,0x77,0xdc,0xdf,
0x66,0x83,0xbc,0x8d,0x60,0xc6,0x22,0x23,
0xb2,0x8b,0x91,0x05,0x76,0xcf,0x74,0xc9,
0xaa,0xf1,0x99,0xa8,0x59,0x50,0x3b,0x2a,
0xfe,0xf9,0x24,0xb0,0xba,0xfd,0xf8,0x55,
};
void enc_csc(uint8 m[8],uint8* k)
{
  uint8 tmpx,tmprx,tmpy;
  int i;
  #define APPLY_M(cl,cr,adl,adr) \
  code=tmpx=m[adl]^cl; \
  code=tmprx=(tmpx<<1)^(tmpx>>7); \
  code=tmpy=m[adr]^cr; \
  code=m[adl]=tbp[(tmprx&0x55)^tmpx^tmpy]; \
  code=m[adr]=tbp[tmprx^tmpy];
  for(code=i=0;i<8;i++,k+=8) 
  {
    APPLY_M(k[0],k[1],0,1)
    APPLY_M(k[2],k[3],2,3)
    APPLY_M(k[4],k[5],4,5)
    APPLY_M(k[6],k[7],6,7)
    APPLY_M(CSC_C00,CSC_C01,0,2)
    APPLY_M(CSC_C02,CSC_C03,4,6)
    APPLY_M(CSC_C04,CSC_C05,1,3)
    APPLY_M(CSC_C06,CSC_C07,5,7)
    APPLY_M(CSC_C10,CSC_C11,0,4)
    APPLY_M(CSC_C12,CSC_C13,1,5)
    APPLY_M(CSC_C14,CSC_C15,2,6)
    APPLY_M(CSC_C16,CSC_C17,3,7)
  }
  for(code=i=0;i<8;i++) 
    code=m[i]^=k[i];
}

код алгоритма шифровки на С

Также авторами собрана статистика скорости зашифровки данных, оказавшаяся быстрее DES:

Скорость зашифровки данных CS-cipher

платформа	тактовая частота	скорость шифровки
VLSI 1216nand 1mm	230 МГц	73 Мбит/с
VLSI 30000nand 15mm	230 МГц	2 Гбит/с
standard C 32bits	133 МГц	2 Мбит/с
bit slice (Pentium)	133 МГц	11 Мбит/с
bit slice (Alpha)	300 МГц	196 Мбит/с
Pentium assembly code	133 МГц	8 Мбит/с
6805 assembly code	4 МГц	20 Кбит/с

Дальнейшее развитие

На основе CS-cipher в 2004 году Томом Ст. Денис был разработан 128-битный шифр [math]\displaystyle{ CS^2 }[/math]-cipher .

Полученный шифр был проверен и оказался устойчивым к:

• линейному и дифференциалному криптоанализу
• сдвиговой атаке и атаке методом бумеранга
• атаке на связанных ключах

Литература

• Bart Van Rompay, Vincent Rijmen, Jorge Nakahara Jr. A first report on CS-Cipher, Hierocrypt, Grand Cru, SAFER++ and SHACAL*† NES/DOC/KUL/WP3/006/1 (англ.). — Katholieke Universiteit Leuven, ESAT-COSIC, 2001. — March.
• Fast Software Encryption: 5th International Workshop (англ.) / Vaudenay S. — Paris, France, 1998. — P. 189-204. — 342 p.
• Preneel, B. et al. NESSIE D20-NESSIE security report (англ.). — 2003. — 342 p.
• Raddum H. The Statistical Evaluation of the NESSIE Submission CS-cipher NES/DOC/UIB/WP3/010 (англ.). — 2002.

• Fast Software Encryption: 6th International Workshop (англ.) / Knudsen L.. — Rome, Italy, 1999. — P. 260-274. — 317 p.

• St Denis, T. The CS2 Block Cipher (англ.). — 2004.
• Le Thi Hoai An, Bouvry P., Dinh T. P. Modelling. Modelling, computation and optimization in information systems and management sciences (англ.). — 2008. — P. 597-606. — 618 p.
• Preneel B. et al. NESSIE Public Report D18: Update on the selection of algorithms for further investigation during the second round (англ.). — 2002. — P. 1. — 15 p.
• NESSIE Public Report D14: Report on the Performance Evaluation of NESSIE Candidates I (англ.) / Mathieu Ciet and Francesco Sica. — 2001. — P. 6.