CS-Cipher (CS-Cipher)
Cs-cipher (фр. Chiffrement Symètrique, симметричный шифр) — симметричный 64 битный [1] блочный алгоритм шифрования данных [2], использующий длину ключа до 128 бит[1]. По принципу работы является 8 раундовой SP-сетью[3].
История
[править | править код]Cs-cipher разработали в 1998 году Жак Штерн (англ. Jacques Stern) и Серж Водене (англ. Serge Vaudenay) [4] при поддержке Compagnie des Signaux[5] . Он был представлен в качестве кандидата в проекте NESSIE в рамках программы Европейской комиссии IST (англ. Information Societies Technology, информационные общественные технологии) в конкурсной группе 64-битных блочных шифров[6]. Несмотря на то, что при исследовании не было обнаружено уязвимостей[7], шифр не был выбран для 2 фазы проекта[8], потому что оказался самым медленным в своей группе[7].
Основные обозначения
[править | править код]Используемые функции
[править | править код]Для начала обозначим следующие обозначения:
- - независимая перестановка 8-битных строк [9]. Определяется как трех-раундовая сеть Фейстеля[10]:
- 8-битная входная строка делится на две 4-битных
- Результатом является строка
- Функции и задаются таблицей:
x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f |
f | d | b | b | 7 | 5 | 7 | 7 | e | d | a | b | e | d | e | f | |
a | 6 | 0 | 2 | b | e | 1 | 8 | d | 4 | 5 | 3 | f | c | 7 | 9 |
- В конечном итоге задается с помощью таблицы[11]:
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 |
- Например 26:
- 2 6 2 7 5
- 6 6 e
- 5 e b
- Итого: 26 b8
- Например 26:
- [9] - преобразование 64-битной строки, используется для генерации ключей и в раундовой функции
- - битовая транспозиция, в данном случае транспонирование матрицы [9], составленной из 8 битных строк, используется при генерации ключей. На вход функция принимает 64-битную строку
- - функция циклического битового сдвига влево, в данном случае принимает 8-битную строку:
- - преобразование[12], используется в раундовой функции. На вход принимает 8-битную строку, если упростить получим[12]:
- - преобразование[13], используется при расшифровке. На вход принимает 8-битную строку
- - преобразование, используется в раундовой функции[12], берет на вход 16-битные строки , результатом является 16-битная строка , в свою очередь:
- - преобразование, используется при расшифровке[13], берет на вход 16-битные строки , результатом является 16-битная строка , в свою очередь:
- - используется для генерации ключей[9]
Константы алгоритма
[править | править код]Ниже представлен список констант, заданных создателями алгоритма:
- b7e151628aed2a6a[14], требуется для раундовой функции
- bf7158809cf4f3c7[14], требуется для раундовой функции
- 290d61409ceb9e8f[9], требуется для генерации ключей
- 1f855f585b013986[9], требуется для генерации ключей
- 972ed7d635ae1716[9], требуется для генерации ключей
- 21b6694ea5728708[9], требуется для генерации ключей
- 3c18e6e7faadb889[9], требуется для генерации ключей
- b700f76f73841163[9], требуется для генерации ключей
- 3f967f6ebf149dac[9], требуется для генерации ключей
- a40e7ef6204a6230[9], требуется для генерации ключей
- 03c54b5a46a34465[9], требуется для генерации ключей
Генерация ключей
[править | править код]Если секретный ключ, используемый в шифре меньше 128 бит, то первые биты заполняются нулями [1], поэтому в дальнейшем будем считать секретный ключ 128 битным.
Алгоритм генерации ключей
[править | править код]Согласно следующему алгоритму в шифре из 128-битного ключа генерируется 9 подключей размером 64 бита:
- первоначально ключ делится на две 64 битные половины[2], таким образом мы получаем начальные параметры:
- Для генерации последующих ключей используется рекуррентная формула[2]:
Пример генерации ключей
[править | править код]Рассмотрим пример генерации ключей, описанный создателями CS-cipher[13]. В нем используется секретный ключ
- 0123456789abcdeffedcba9876543210.
Согласно рассмотренному выше, получаем начальные параметры для генерирования раундовых ключей:
- 0123456789abcdef
- fedcba9876543210
Рассмотрим подробно генерацию ключа :
- 0123456789abcdef 290d61409ceb9e8f
- b711fa89ae0394e4 fedcba9876543210 bb21a9e2388bacd4
Конечный результат работы алготитма генерации:
- 45fd137a4edf9ec4
- 1dd43f03e6f7564c
- ebe26756de9937c7
- 961704e945bad4fb
- 0b60dfe9eff473d4
- 76d3e7cf52c466cf
- 75ec8cef767d3a0d
- 82da3337b598fd6d
- fbd820da8dc8af8c
Шифрование
[править | править код]Краткое описание зашифровки
[править | править код]Каждый раунд шифровки начинается с операции XOR над входящей 64-битной строкой и подключа. Затем 64-битная строка разделяется на 4 16-битных строки, над которыми происходит нелинейное преобразование( ). После этого строки снова делятся, на этот раз в результате получается 8 8-битных строк, которые затем переставляются. Данные действия повторяются еще дважды в каждом раунде, разница лишь в том, что операция XOR происходит с заданными константами, а не со сгенерированным ключом. После последнего раунда следует дополнительная операция XOR с оставшимся сгенерированным ключом[3].
Формальное описание алгоритма
[править | править код]Первоначально определим:
- - 64-битная строка, приходит на вход раундовой функции в итерации
- - временное 64-битное значение, вычисленное на шаге раундовой функции
- - 64-битная строка, конечный зашифрованный текст
Раундовая функции
[править | править код]Раундовая функция состоит из следующих действий[15]:
Зашифровывание
[править | править код]Зашифрование состоит из 8 раундов, конечный 64-битный зашифрованный текст можно вычислить из фрагмента открытого текста по формуле[9]:
Где — раундовая функция[10], описана выше.
Пример зашифровывания открытого текста
[править | править код]Рассмотрим пример зашифровывания открытого текста, описанный создателями CS-cipher[13]. В нем используется следующие секретный ключ и открытый текст:
- 0123456789abcdef
- 0123456789abcdeffedcba9876543210
Секретный ключ соответствует вышележащему примеру генерации раундовых ключей, то есть раундовые ключи были подсчитаны выше:
- 45fd137a4edf9ec4
- 1dd43f03e6f7564c
- ebe26756de9937c7
- 961704e945bad4fb
- 0b60dfe9eff473d4
- 76d3e7cf52c466cf
- 75ec8cef767d3a0d
- 82da3337b598fd6d
- fbd820da8dc8af8c
Промежуточные результаты для вычисления :
- d85c19785690b0e3
- 0f4bfb9e2f8ac7e2
Получим следующие значения на раундах:
- c3feb96c0cf4b649
- 3f54e0c8e61a84d1
- b15cb4af3786976e
- 76c122b7a562ac45
- 21300b6ccfaa08d8
- 99b8d8ab9034ec9a
- a2245ba3697445d2
В итоге получили следующий зашифрованный текст:
- 88fddfbe954479d7
Расшифровывание
[править | править код]Расшифровывание состоит из 8 раундов, обратных зашифровыванию[16]. Важно, что алгоритм расшифровки использует сгенерированные ключи в обратном порядке, т. е. [2]. Перед началом происходит операция .
Для удобства и соответствия обозначений, еще раз укажем:
- - номер итерации: от 0 до 7 включительно - всего 8 раундов
- - 64-битная строка, приходит на вход обратной к раундовой функции в итерации, - открытый текст
- - 64-битный сгенерированный ключ, приходит на вход обратной к раундовой функции в итерации
- - временное 64-битное значение, вычисленное на шаге обратной к раундовой функции.
Для каждого раунда вызывается следующая последовательность действий[13]:
Статистическая оценка зашифрованных данных
[править | править код]В ходе участия в проекте NESSIE были проведены множество статистических тестов над зашифрованными данными[17], в том числе:
- Универсальный статистический тест Маурера[18]
- Тест на корреляцию[19]
- Тест на линейную сложность[20]
- Тест собирателя купонов[21]
- Тест на совпадение перекрывающихся шаблонов[22]
- Тест подпоследовательностей[21]
В результате тестирования шифра не было обнаружено его отклонений от случайного распределения[23].
Криптоанализ
[править | править код]Марковский шифр
[править | править код]Предположим, у нас есть раундовый шифр, зашифрованный текст можно получить по формуле: , в котором каждый раунд использует свой ключ .
Тогда Марковским шифром называется шифр, для которого для любого раунда и любых , и выполнено[24]:
Определение анализируемого шифра
[править | править код]В ходе анализа используется модифицированный шифр CS-cipher, называемый в дальнейшем CSC.
Он получается из шифра CS-cipher следующей заменой:
- для шифровки CS-cipher использует следующую последовательность ключей и констант:
- . Для удобства переобозначим их как .
- По определению[25] CSC получается из CS-cipher заменой полученной с помощью генерации ключей и констант последовательности на 1600-битный случайный ключ с равномерным распределением.
Полученный шифр CSC является 24 раундовым блочным Марковским шифром[26].
Устойчивость к атакам
[править | править код]Для шифра CSC были доказаны:
- устойчивость к дифференциальному криптоанализу [27]
- устойчивость к линейному криптоанализу[28]
- устойчивость к методу невозможных дифференциалов (англ. Impossible differential cryptanalysis)[29]
- устойчивость к методу усеченных разностей (англ. Truncated differential cryptanalysis)[30]
Поэтому предполагается, что CS-cipher:
- устойчив к дифференциальному криптоанализу после 4 раундов шифровки[27]
- устойчив к методу усеченных разностей (англ. Truncated differential cryptanalysis)[30]
- устойчив к линейному криптоанализу[30]
- устойчив к методу невозможных дифференциалов (англ. Impossible differential cryptanalysis) после 6 раундов шифровки[29]
Реализация
[править | править код]Существует реализации данного алгоритма шифрования на С[31]( предоставлена авторами):
# 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[5]:
платформа | тактовая частота | скорость шифровки |
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-битный шифр -cipher [32].
Полученный шифр был проверен и оказался устойчивым к:
- линейному и дифференциалному криптоанализу [33]
- сдвиговой атаке и атаке методом бумеранга[34]
- атаке на связанных ключах[34]
Примечания
[править | править код]- ↑ 1 2 3 A first report on CS-Cipher, 2001, p. 1.
- ↑ 1 2 3 4 Cs-Cipher, 1998, p. 190.
- ↑ 1 2 NESSIE Public Report D14, 2001, p. 6.
- ↑ Cs-Cipher, 1998, p. 189.
- ↑ 1 2 Cs-Cipher, 1998, p. 201.
- ↑ NESSIE D20-NESSIE security report, 2003, pp. 4.
- ↑ 1 2 NESSIE Public Report D18, 2002, p. 1.
- ↑ NESSIE D20-NESSIE security report, 2003, p. 77.
- ↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Cs-Cipher, 1998, p. 192.
- ↑ 1 2 Cs-Cipher, 1998, p. 195.
- ↑ Cs-Cipher, 1998, p. 196.
- ↑ 1 2 3 Cs-Cipher, 1998, p. 194.
- ↑ 1 2 3 4 5 Cs-Cipher, 1998, p. 197.
- ↑ 1 2 Cs-Cipher, 1998, p. 193.
- ↑ Cs-Cipher, 1998, pp. 193-195.
- ↑ Cs-Cipher, 1998, pp. 196-197.
- ↑ The Statistical Evaluation, 2002, pp. 1, 4, 7-16, 18, 21, 22-29.
- ↑ The Statistical Evaluation, 2002, pp. 10, 24.
- ↑ The Statistical Evaluation, 2002, pp. 12, 25.
- ↑ The Statistical Evaluation, 2002, pp. 13, 26.
- ↑ 1 2 The Statistical Evaluation, 2002, pp. 9, 23.
- ↑ The Statistical Evaluation, 2002, pp. 8, 21.
- ↑ The Statistical Evaluation, 2002, p. 30.
- ↑ On the security of CS-cipher, 1999, p. 262.
- ↑ On the security of CS-cipher, 1999, p. 266.
- ↑ On the security of CS-cipher, 1999, p. 267.
- ↑ 1 2 On the security of CS-cipher, 1999, p. 269.
- ↑ On the security of CS-cipher, 1999, p. 270.
- ↑ 1 2 Security against impossible differential cryptanalysis, 2008, p. 10.
- ↑ 1 2 3 On the security of CS-cipher, 1999, p. 272.
- ↑ Cs-Cipher, 1998, pp. 203-204.
- ↑ The CS2 Block Cipher, 2004, p. 1.
- ↑ The CS2 Block Cipher, 2004, p. 8.
- ↑ 1 2 The CS2 Block Cipher, 2004, p. 9.
Литература
[править | править код]- 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.