Kupyna (Kupyna)

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]

Алгоритм

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

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

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

$h_{0}=IV$

$h_{\nu }=T_{l}^{\oplus }$ $($ $h_{\nu -1}\oplus$ $m_{\nu })\oplus$ $T_{l}^{+}(m_{\nu }){\oplus }h_{\nu -1}$

$H(IV,M)=R_{l,n}(T_{l}^{\oplus }(h_{k}){\oplus }h_{k})$

где

$\nu =1,2,...,k$

$IV=1<<510$ , если l = 512, или $1<<1023$ , если l = 1024

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

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

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

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

${\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}}$

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

Перестановки $T_{l}^{\oplus }$ и $T_{l}^{+}$ определены как:

$T_{l}^{\oplus }$ $=$ $\prod _{\nu =0}^{t-1}(\psi \circ \tau ^{(l)}\circ \pi '\circ \kappa _{\nu }^{(l)})$

$T_{l}^{+}$ $=$ $\prod _{\nu =0}^{t-1}(\psi \circ \tau ^{(l)}\circ \pi '\circ \eta _{\nu }^{(l)})$

Функция $\kappa _{\nu }^{(l)}$ прибавляет по модулю 2 вектор

$\omega _{j}^{(\nu )}=((j<<4)\oplus \nu ,0,0,0,0,0,0,0)^{T}$

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

Функция $\eta _{\nu }^{(l)}$ прибавляет по модулю 64 вектор

$\varsigma _{j}^{(\nu )}=(0xF3,0xF0,0xF0,0xF0,0xF0,0xF0,0xF0(c-1-j)<<4)^{T}$

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

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

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

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

$u_{i,j}=(v>>>i)\bigotimes G_{j}$

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

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

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

Вид атаки	Kupyna-256	Kupyna-512
Коллизия	2¹²⁸	2²⁵⁶
Прообраз	2²⁵⁶	2⁵¹²
Второй прообраз	2²⁵⁶	2⁵¹²
Фиксированные точки	2²⁵⁶	2⁵¹²

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

S-блоки

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

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

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

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

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

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

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

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

Примечания

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

[1] ttp://csm.kiev.ua/index.php?view=article&id=3022 Архивная копия от 21 ноября 2021 на Wayback Machine В Украине внедряются новые стандарты криптографической защиты информации

[2] ttp://eprint.iacr.org/2015/885.pdf Архивная копия от 25 сентября 2015 на Wayback Machine A New Standard of Ukraine: The Kupyna Hash Function

[3] ttp://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 года.

[1]

[2]

[3]

[4]

[5]

Хеш-функции
Общего назначения	Adler-32 CRC Контрольная сумма Флетчера FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH-Дерево хешей Jenkins hash Хеш-сумма
Криптографические	ГОСТ Р 34.11-94 Стрибог BelT BLAKE Blue Midnight Wish CubeHash ECHO Edonkey2k FSB Fugue Grøstl HAVAL Hamsi JH Kupyna LM-хеш Luffa MASH-1 MD2 MD4 MD5 MD6 N-Hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 SHA-3 (Keccak) SHABAL SHAvite-3 SIMD SWIFFT Skein Snefru Tiger Whirlpool
Функции формирования ключа	bcrypt PBKDF2 scrypt Argon2 Lyra2
Контрольное число (сравнение)	Контрольная сумма Алгоритм Верхуффа Алгоритм Дамма Алгоритм Луна Штрих-код Банковских счетов Банковских карт ISIN СНИЛС ОКПО ИНН ОКАТО ISBN ОГРН и ОГРНИП VIN
Применение хешей	Сравнение контрольных чисел Коллизия хеш-функции Протоколы аутентификации Сравнение штрихкодов Криптография Magnet-ссылка Подпись Меркла ed2k URN

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

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