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]:

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  

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

править

Зашифрование состоит из 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.