Kupyna

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
Kupyna
Разработчики ЧАО «Институт информационных технологий» (г. Харьков)
Создан 2014
Опубликован 2 декабря 2014
Предшественник ГОСТ 34.311-95
Стандарты ДСТУ 7564:2014
Размер хеша переменный, 8-512 бит (рекомендуемые значения 256, 384, 512)
Число раундов 10 при длине хеша 8-256 бит; 14 при длине хеша 264-512 бит
Тип хеш-функция

Kupyna (укр. Купина) — итеративная криптографическая хеш-функция. Принята в качестве национального стандарта Украины ДСТУ 7564:2014[1] в качестве замены устаревшей хеш-функции ГОСТ 34.311-95. Сжимающая функция Kupyna состоит из двух фиксированных 2n-битных перестановок T⊕ и T+, структура которых заимствована у шифра Kalyna. В частности, используется четыре таких же S-блока. Результат работы хеш-функции может иметь длину от 8 до 512 бит. Вариант, возвращающий n бит, называется «Kupyna-n»[2].

Происхождение названия

Купена аптечная — растение семейства Иглицевые (Ruscaceae), произрастающие на территории всей Украины в хвойных и смешанных лесах, занесена в Красную книгу Украины.[3]

Алгоритм

Сначала сообщение [math]\displaystyle{ M }[/math] дополняется до длины, кратной размеру блока. Для этого к сообщению добавляется 1 бит [math]\displaystyle{ 1 }[/math], затем [math]\displaystyle{ d }[/math] нулевых битов, где [math]\displaystyle{ d=(-N-97)\ mod\ l }[/math] и 96 бит, содержащих длину сообщения в битах. Таким образом, максимальная длина сообщения [math]\displaystyle{ 2^{96}-1 }[/math] бит.

После этого сообщение разбивается на [math]\displaystyle{ t }[/math] блоков [math]\displaystyle{ m_1, m_2, ..., m_t }[/math] по [math]\displaystyle{ l }[/math] бит каждый. Для вариантов функции, возвращающих до 256 бит, [math]\displaystyle{ l }[/math] = 512. Для вариантов, возвращающих большие значения, [math]\displaystyle{ l }[/math] = 1024.

Далее, строится хеш-функция, используя следующий итеративный алгоритм.

[math]\displaystyle{ h_0 = IV }[/math]

[math]\displaystyle{ h_\nu = T_l^\oplus }[/math][math]\displaystyle{ ( }[/math][math]\displaystyle{ h_{\nu-1}\oplus }[/math][math]\displaystyle{ m_\nu)\oplus }[/math][math]\displaystyle{ T_l^+(m_\nu){\oplus}h_{\nu-1} }[/math]

[math]\displaystyle{ H(IV,M) = R_{l,n}(T_l^\oplus(h_k){\oplus}h_k) }[/math]

где

[math]\displaystyle{ \nu = 1, 2, ..., k }[/math]

[math]\displaystyle{ IV = 1 \lt \lt 510 }[/math], если l = 512, или [math]\displaystyle{ 1 \lt \lt 1023 }[/math], если l = 1024

[math]\displaystyle{ R_{l,n}(X) }[/math] - функция, возвращающая [math]\displaystyle{ n }[/math] наиболее значимых битов блока размером [math]\displaystyle{ l }[/math]

Перестановки T⊕ и T+

Эти преобразования управляют состоянием, которое представляется матрицей G, содержащей в каждой ячейке 1 байт информации. Матрица имеет размер 8Х8 (при [math]\displaystyle{ l = 512 }[/math]) или 8Х16 (при [math]\displaystyle{ l = 1024 }[/math]).

Сначала матрица G заполняется последовательностью байт. Например для последовательности 00 01 02 … 3f матрица G выглядит следующим образом.

[math]\displaystyle{ \begin{bmatrix} 00 & 08 & 10 & 18 & 20 & 28 & 30 & 38 \\ 01 & 09 & 11 & 19 & 21 & 29 & 31 & 39 \\ 02 & 0a & 12 & 1a & 22 & 2a & 32 & 3a \\ 03 & 0b & 13 & 1b & 23 & 2b & 33 & 3b \\ 04 & 0c & 14 & 1c & 24 & 2c & 34 & 3c \\ 05 & 0d & 15 & 1d & 25 & 2d & 35 & 3d \\ 06 & 0e & 16 & 1e & 26 & 2e & 36 & 3e \\ 07 & 0f & 17 & 1f & 27 & 2f & 37 & 3f \end{bmatrix} }[/math]

Аналогичным образом заполняется матрица 8 X 16.

Перестановки [math]\displaystyle{ T_l^\oplus }[/math] и [math]\displaystyle{ T_l^+ }[/math] определены как:

[math]\displaystyle{ T_l^\oplus }[/math] [math]\displaystyle{ = }[/math] [math]\displaystyle{ \prod_{\nu=0}^{t-1}(\psi\circ\tau^{(l)}\circ\pi'\circ\kappa_\nu^{(l)}) }[/math]

[math]\displaystyle{ T_l^+ }[/math] [math]\displaystyle{ = }[/math] [math]\displaystyle{ \prod_{\nu=0}^{t-1}(\psi\circ\tau^{(l)}\circ\pi'\circ\eta_\nu^{(l)}) }[/math]

Функция [math]\displaystyle{ \kappa_\nu^{(l)} }[/math] прибавляет по модулю 2 вектор

[math]\displaystyle{ \omega_j^{(\nu)} = ((j\lt \lt 4)\oplus\nu,0,0,0,0,0,0,0)^T }[/math]

к каждому столбцу матрицы состояния ([math]\displaystyle{ \nu }[/math] - номер раунда).

Функция [math]\displaystyle{ \eta_\nu^{(l)} }[/math] прибавляет по модулю 64 вектор

[math]\displaystyle{ \varsigma_j^{(\nu)} = (0xF3, 0xF0, 0xF0, 0xF0, 0xF0, 0xF0, 0xF0 (c-1-j)\lt \lt 4)^T }[/math]

к каждому столбцу матрицы состояния ([math]\displaystyle{ \nu }[/math] - номер раунда).

Функция [math]\displaystyle{ \pi' }[/math] заменяет элементы матрицы состояния [math]\displaystyle{ g_{i,j} }[/math] подстановкой из одного из четырёх S-блоков (номер S-блока определяется как [math]\displaystyle{ i\ mod\ 4 }[/math]).

Функция [math]\displaystyle{ \tau_l }[/math] производит циклический сдвиг вправо элементов матрицы состояния. Строки с номерами [math]\displaystyle{ i = 0,1,2,3,4,5,6 }[/math] сдвигаются на [math]\displaystyle{ i }[/math] элементов, а строка 7 сдвигается на 7 элементов при [math]\displaystyle{ l=512 }[/math] или на 11 элементов при [math]\displaystyle{ l=1024 }[/math].

Для выполнения функции [math]\displaystyle{ \psi }[/math] каждый элемент матрицы состояния представляется как элемент конечного поля [math]\displaystyle{ GF(2^8) }[/math], сформированного неприводимым полиномом [math]\displaystyle{ x^8+x^4+x^3+x^2+1 }[/math]. Каждый элемент результирующей матрицы состояния [math]\displaystyle{ u_{i,j} }[/math] вычисляется по формуле:

[math]\displaystyle{ u_{i,j} = (v \gt \gt \gt i)\bigotimes G_j }[/math]

где [math]\displaystyle{ v }[/math] - вектор (0x01, 0x01, 0x05, 0x01, 0x08, 0x06, 0x07, 0x04), а [math]\displaystyle{ j }[/math] - номер столбца матрицы состояния [math]\displaystyle{ G }[/math].

Криптостойкость

Создатели уверяют, что дифференциальные атаки и rebound атаки неэффективны уже после 4 итераций функций перестановок. В таблице приведены заявленные создателями показатели криптостойкости.

Вид атаки Kupyna-256 Kupyna-512
Коллизия 2128 2256
Прообраз 2256 2512
Второй прообраз 2256 2512
Фиксированные точки 2256 2512

В результате независимого криптоанализа удалось провести атаку только на первые 5 раундов; сложность нахождения коллизии для сокращённой до 5 раундов функции Kupyna-256 составляет 2120.[4][5]

S-блоки

Подстановка π0

6D F3 1D CB C9 4D 79 2C E0 97 FD 6F 4B 45 39
3E DD A3 4F B4 B6 1F 9A BF 15 E1 49 D2 93 C6
92 72 9E 61 D1 63 F4 FA 19 D5 AD 58 A4 BB A1
DC F2 83 37 42 E4 9C 7A CC AB 4A 8F 6E 04 27
2E E7 E2 5A 96 16 C2 23 65 66 0F BC A9 47 41
34 48 FC B7 6A 88 86 A5 F9 5B DB 38 7B C3 1E
22 33 24 28 36 C7 8E B2 77 BA F5 14 9F 08 55
9B 4C FE 60 5C DA CD 18 7D 21 B0 3F 1B 89 FF
EB 84 69 3A 9D D7 67 D3 40 B5 DE 5D 30 91 B1
78 11 01 E5 00 68 C5 98 02 A6 74 2D 0B A2 76
B3 BE CE BD AE E9 1C 8A EC F1 99 94 AA F6 26
2F EF E8 8C 35 03 FB D4 05 C1 5E 90 20 3D 82
F7 EA 0A 0D 7E F8 C4 50 07 57 B8 3C 62 E3 C8
AC 52 64 10 D0 D9 12 13 29 51 B9 CF D6 73 8D
81 54 C0 ED 4E 44 85 A7 25 E6 CA 7C 8B 56 80

Подстановка π1

42 15 56 B4 65 1C 88 43 C5 5C 36 BA F5 57 67 8D
31 F6 64 58 9E F4 22 AA 75 0F 02 B1 DF 6D 73 4D
7C 26 2E F7 08 5D 44 3E 9F 14 C8 AE 54 10 D8 BC
1A 6B 69 F3 BD 33 AB FA D1 9B 68 4E 16 95 91 EE
4C 63 8E 5B CC 3C 19 A1 81 49 7B D9 6F 37 60 CA
E7 2B 48 FD 96 45 FC 41 12 0D 79 E5 89 8C E3 20
30 DC B7 6C 4A B5 3F 97 D4 62 2D 06 A4 A5 83 5F
2A DA C9 00 7E A2 55 BF 11 D5 9C CF 0E 0A 3D 51
7D 93 1B FE C4 47 09 86 0B 8F 9D 6A 07 B9 B0 98
18 32 71 4B EF 3B 70 A0 E4 40 FF C3 A9 E6 78 F9
8B 46 80 1E 38 E1 B8 A8 E0 0C 23 76 1D 25 24 05
F1 6E 94 28 9A 84 E8 A3 4F 77 D3 85 E2 52 F2 82
50 7A 2F 74 53 B3 61 AF 39 35 DE CD 1F 99 AC AD
72 2C DD D0 87 BE 5E A6 EC 04 C6 03 34 FB DB 59
B6 C2 01 F0 5A ED A7 66 21 7F 8A 27 C7 C0 29 D7

Подстановка π2

4A 17 2B C2 94 F4 BB A3 62 E4 71 D4 CD 70 16 E1
49 3C C0 D8 5C 9B AD 85 53 A1 7A C8 2D E0 D1 72
A6 2C C4 E3 76 78 B7 B4 09 3B 0E 41 4C DE B2 90
25 A5 D7 03 11 00 C3 2E 92 EF 4E 12 9D 7D CB 35
10 D5 4F 9E 4D A9 55 C6 D0 7B 18 97 D3 36 E6 48
56 81 8F 77 CC 9C B9 E2 AC B8 2F 15 A4 7C DA 38
1E 0B 05 D6 14 6E 6C 7E 66 FD B1 E5 60 AF 5E 33
87 C9 F0 5D 6D 3F 88 8D C7 F7 1D E9 EC ED 80 29
27 CF 99 A8 50 0F 37 24 28 30 95 D2 3E 5B 40 83
B3 69 57 1F 07 1C 8A BC 20 EB CE 8E AB EE 31 A2
73 F9 CA 3A 1A FB 0D C1 FE FA F2 6F BD 96 DD 43
52 B6 08 F3 AE BE 19 89 32 26 B0 EA 4B 64 84 82
6B F5 79 BF 01 5F 75 63 1B 23 3D 68 2A 65 E8 91
F6 FF 13 58 F1 47 0A 7F C5 A7 E7 61 5A 06 46 44
42 04 A0 DB 39 86 54 AA 8C 34 21 8B F8 0C 74 67

Подстановка π3

22 03 46 3D 2D 4A 53 83 13 8A B7 D5 25 79 F5 BD
58 2F 0D 02 ED 51 9E 11 F2 3E 55 5E D1 16 3C 66
70 5D F3 45 40 CC E8 94 56 08 CE 1A 3A D2 E1 DF
B5 38 6E 0E E5 F4 F9 86 E9 4F D6 85 23 CF 32 99
31 14 AE EE C8 48 D3 30 A1 92 41 B1 18 C4 2C 71
72 44 15 FD 37 BE 5F AA 9B 88 D8 AB 89 9C FA 60
EA BC 62 0C 24 A6 A8 EC 67 20 DB 7C 28 DD AC 5B
34 7E 10 F1 7B 8F 63 A0 05 9A 43 77 21 BF 27 09
C3 9F B6 D7 29 C2 EB C0 A4 8B 8C 1D FB FF C1 B2
97 2E F8 65 F6 75 07 04 49 33 E4 D9 B9 D0 42 C7
6C 90 00 8E 6F 50 01 C5 DA 47 3F CD 69 A2 E2 7A
A7 C6 93 0F 0A 06 E6 2B 96 A3 1C AF 6A 12 84 39
E7 B0 82 F7 FE 9D 87 5C 81 35 DE B4 A5 FC 80 EF
CB BB 6B 76 BA 5A 7D 78 0B 95 E3 AD 74 98 3B 36
64 6D DC F0 59 A9 4C 17 7F 91 B8 C9 57 1B E0 61


Примеры хешей Kupyna

Значения разных вариантов хеша от пустой строки. 

Kupyna-256("")
0x cd5101d1ccdf0d1d1f4ada56e888cd724ca1a0838a3521e7131d4fb78d0f5eb6
Kupyna-512("")
0x 656b2f4cd71462388b64a37043ea55dbe445d452aecd46c3298343314ef04019
   bcfa3f04265a9857f91be91fce197096187ceda78c9c1c021c294a0689198538

Малое изменение сообщения с большой вероятностью приводит к значительным изменениям в значении хеш-функции благодаря лавинному эффекту, как показано в следующем примере: 

Kupyna-256("The quick brown fox jumps over the lazy dog")
0x 996899f2d7422ceaf552475036b2dc120607eff538abf2b8dff471a98a4740c6
Kupyna-256("The quick brown fox jumps over the lazy dog.")
0x 88ea8ce988fe67eb83968cdc0f6f3ca693baa502612086c0dcec761a98e2fb1f


Примечания

  1. ↑ http://csm.kiev.ua/index.php?view=article&id=3022 Архивная копия от 21 ноября 2021 на Wayback Machine В Украине внедряются новые стандарты криптографической защиты информации
  2. ↑ http://eprint.iacr.org/2015/885.pdf Архивная копия от 25 сентября 2015 на Wayback Machine A New Standard of Ukraine: The Kupyna Hash Function
  3. ↑ http://www.slideshare.net/oliynykov/kupyna Архивная копия от 25 сентября 2015 на Wayback Machine Main properties of the new Ukrainian national standard on cryptographic hash function
  4. ↑ Christoph Dobraunig, Maria Eichlseder, and Florian Mendel. Analysis of the Kupyna-256 Hash Function (англ.) (2015). Дата обращения: 1 октября 2015. Архивировано 4 марта 2016 года.
  5. ↑ Jian Zou, Le Dong. Cryptanalysis of the Round-Reduced Kupyna Hash Function (англ.) (2015). Дата обращения: 2 октября 2015. Архивировано 4 марта 2016 года.
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Kupyna&oldid=5904764