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


  • [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 были доказаны:

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

Реализация

[править | править код]

Существует реализации данного алгоритма шифрования на С[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]:

Скорость зашифровки данных 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-битный шифр -cipher [32].

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

Примечания

[править | править код]
  1. 1 2 3 A first report on CS-Cipher, 2001, p. 1.
  2. 1 2 3 4 Cs-Cipher, 1998, p. 190.
  3. 1 2 NESSIE Public Report D14, 2001, p. 6.
  4. Cs-Cipher, 1998, p. 189.
  5. 1 2 Cs-Cipher, 1998, p. 201.
  6. NESSIE D20-NESSIE security report, 2003, pp. 4.
  7. 1 2 NESSIE Public Report D18, 2002, p. 1.
  8. NESSIE D20-NESSIE security report, 2003, p. 77.
  9. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Cs-Cipher, 1998, p. 192.
  10. 1 2 Cs-Cipher, 1998, p. 195.
  11. Cs-Cipher, 1998, p. 196.
  12. 1 2 3 Cs-Cipher, 1998, p. 194.
  13. 1 2 3 4 5 Cs-Cipher, 1998, p. 197.
  14. 1 2 Cs-Cipher, 1998, p. 193.
  15. Cs-Cipher, 1998, pp. 193-195.
  16. Cs-Cipher, 1998, pp. 196-197.
  17. The Statistical Evaluation, 2002, pp. 1, 4, 7-16, 18, 21, 22-29.
  18. The Statistical Evaluation, 2002, pp. 10, 24.
  19. The Statistical Evaluation, 2002, pp. 12, 25.
  20. The Statistical Evaluation, 2002, pp. 13, 26.
  21. 1 2 The Statistical Evaluation, 2002, pp. 9, 23.
  22. The Statistical Evaluation, 2002, pp. 8, 21.
  23. The Statistical Evaluation, 2002, p. 30.
  24. On the security of CS-cipher, 1999, p. 262.
  25. On the security of CS-cipher, 1999, p. 266.
  26. On the security of CS-cipher, 1999, p. 267.
  27. 1 2 On the security of CS-cipher, 1999, p. 269.
  28. On the security of CS-cipher, 1999, p. 270.
  29. 1 2 Security against impossible differential cryptanalysis, 2008, p. 10.
  30. 1 2 3 On the security of CS-cipher, 1999, p. 272.
  31. Cs-Cipher, 1998, pp. 203-204.
  32. The CS2 Block Cipher, 2004, p. 1.
  33. The CS2 Block Cipher, 2004, p. 8.
  34. 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.