Kupyna

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Криптографическая
хеш-функция
Название

Kupyna

Опубликован

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]

Алгоритм[править | править вики-текст]

Сначала сообщение дополняется до длины, кратной размеру блока. Для этого к сообщению добавляется 1 бит , затем нулевых битов, где и 96 бит, содержащих длину сообщения в битах. Таким образом, максимальная длина сообщения бит.

После этого сообщение разбивается на блоков по бит каждый. Для вариантов функции, возвращающих до 256 бит, = 512. Для вариантов, возвращающих большие значения, = 1024.

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

где

, если l = 512, или , если l = 1024

- функция, возвращающая наиболее значимых битов блока размером

Перестановки T и T+[править | править вики-текст]

Эти преобразования управляют состоянием, которое представляется матрицей G, содержащей в каждой ячейке 1 байт информации. Матрица имеет размер 8Х8 (при ) или 8Х16 (при ).

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

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

Перестановки и определены как:

Функция прибавляет по модулю 2 вектор

к каждому столбцу матрицы состояния ( - номер раунда).

Функция прибавляет по модулю 64 вектор

к каждому столбцу матрицы состояния ( - номер раунда).

Функция заменяет элементы матрицы состояния подстановкой из одного из четырёх S-блоков (номер S-блока определяется как ).

Функция производит циклический сдвиг вправо элементов матрицы состояния. Строки с номерами сдвигаются на элементов, а строка 7 сдвигается на 7 элементов при или на 11 элементов при .

Для выполнения функции каждый элемент матрицы состояния представляется как элемент конечного поля , сформированного неприводимым полиномом . Каждый элемент результирующей матрицы состояния вычисляется по формуле:

где - вектор (0x01, 0x01, 0x05, 0x01, 0x08, 0x06, 0x07, 0x04), а - номер столбца матрицы состояния .

Криптостойкость[править | править вики-текст]

Создатели уверяют, что дифференциальные атаки и 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 2C AF 79 E0 97 FD 6F 4B 45 39
3E DD A3 4F B4 B6 9A 0E 1F BF 15 E1 49 D2 93 C6
92 72 9E 61 D1 63 FA EE F4 19 D5 AD 58 A4 BB A1
DC F2 83 37 42 E4 7A 32 9C CC AB 4A 8F 6E 04 27
2E E7 E2 5A 96 16 23 2B C2 65 66 0F BC A9 47 41
34 48 FC B7 6A 88 A5 53 86 F9 5B DB 38 7B C3 1E
22 33 24 28 36 C7 B2 3B 8E 77 BA F5 14 9F 08 55
9B 4C FE 60 5C DA 18 46 CD 7D 21 B0 3F 1B 89 FF
EB 84 69 3A 9D D7 D3 70 67 40 B5 DE 5D 30 91 B1
78 11 01 E5 00 68 98 A0 C5 02 A6 74 2D 0B A2 76
B3 BE CE BD AE E9 8A 31 1C EC F1 99 94 AA F6 26
2F EF E8 8C 35 03 D4 7F FB 05 C1 5E 90 20 3D 82
F7 EA 0A 0D 7E F8 50 1A C4 07 57 B8 3C 62 E3 C8
AC 52 64 10 D0 D9 13 0C 12 29 51 B9 CF D6 73 8D
81 54 C0 ED 4E 44 A7 2A 85 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://www.csm.kiev.ua/index.php?option=com_content&view=article&id=3022:2015-02-16-08-31-21&catid=1:latest-news&Itemid=120&lang=ru В Украине внедряются новые стандарты криптографической защиты информации
  2. http://eprint.iacr.org/2015/885.pdf A New Standard of Ukraine: The Kupyna Hash Function
  3. http://www.slideshare.net/oliynykov/kupyna 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.
  5. Jian Zou, Le Dong. Cryptanalysis of the Round-Reduced Kupyna Hash Function (англ.) (2015). Проверено 2 октября 2015.