Купина (геш-функція)

Державний стандарт України
	Купина (геш-функція)
Позначення	ДСТУ 7564:2014
Назва	Інформаційні технології. Криптографічний захист інформації. Функція хешування
Інформаційні дані
Розробники	Приватне акціонерне товариство «Інститут інформаційних технологій»
Внесено	Мінекономрозвитку України
Введено в дію	наказ від 2 грудня 2014 р. № 1431
Чинний від	1 квітня 2015 року
Статус	Чинний
Останні зміни	ІПС №11-2015
Пов'язані стандарти	ДСТУ 7624:2014, ДСТУ 4145-2002, ГОСТ 34.311-95[ru]
Кількість сторінок	40
	База нормативних документів

У Вікіпедії є статті про інші значення цього терміна: Купина.

«Купина» (англ. Kupyna) — ітеративна криптографічна геш-функція описана у національному стандарті України ДСТУ 7564:2014 «Інформаційні технології. Криптографічний захист інформації. Функція хешування». Стандарт набрав чинності з 1 квітня 2015 року наказом Мінекономрозвитку від 2 грудня 2014 року №1431^[2]. Текст стандарту є у вільному доступі ^[3].

Стандарт ДСТУ 7564:2014 розроблено задля поступової заміни міждержавного стандарту ГОСТ 34.311-95^[ru]^[4] та згідно чинного наказу Мінцифри від 30 вересня 2020 року №140/614^[5] може застосовуватися для створення кваліфікованого електронного підпису з 01 січня 2021 року, та обов'язковий для застосування після 1 січня 2022 року замість функції гешування за ГОСТ 34.311-95^[ru].

Функція стиснення Купини складається з двох фіксованих 2n-бітних перестановок T^⊕ і T⁺, структура яких запозичена у шифра Калина. Зокрема, використовуються чотири таких самих S-блока. Результат роботи геш-функції може мати довжину від 8 до 512 біт. Варіант, який повертає n біт, позначається як Купина-n.^[6]

Алгоритм[ред. | ред. код]

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

Далі повідомлення розбивається на $t$ блоків $m_{1},m_{2},...,m_{t}$ по $l$ біт у кожному. Для варіантів функції, які повертають до 256 біт включно, $l$ = 512. Для варіантів, які повертають значення, довші 256 біт, $l$ = 1024.

Далі, будується геш-функція, з використанням наступного ітеративного алгоритму^[6].

$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$ ^[6]

Кількість ітерацій для варіантів функції, які повертають до 256 біт включно — 10. Кількість ітерацій для варіантів функції, які повертають значення, довші 256 біт, — 14^[6].

Перестановки T^⊕ і T⁺[ред. | ред. код]

Ці перетворення керують станом, представленим матрицею G, яка містить у кожній комірці 1 байт інформації^[6]. Матриця має розмір 8Х8 (при $l=512$ ) або 8Х16 (при $l=1024$ )^[6].

Спочатку матриця G заповнюється послідовністю байт^[6]. Наприклад для послідовності 00 01 02 … 3f матриця G виглядає так^[6].

${\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}}$ ^[6]

Аналогічно заповнюється матриця 8 X 16^[6].

Перестановки $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)})$ ^[6]

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

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

до кожного стовпця матриці стану ( $\nu$ — номер раунду)^[6].

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

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

до кожного стовпця матриці стану ( $\nu$ — номер раунду)^[6].

Функція $\pi '$ підміняє елементи матриці стану $g_{i,j}$ підстановкою з одного з чотирьох S-блоків (номер S-блока визначається як $i\ mod\ 4$ )^[6].

Функція $\tau _{l}$ виконує циклічний зсув вправо елементів матриці стану. Рядки з номерами $i=0,1,2,3,4,5,6$ зсуваються на $i$ елементів, а рядок 7 зсувається на 7 елементів при $l=512$ або на 11 елементів при $l=1024$ ^[6].

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

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

де $v$ — вектор (0x01, 0x01, 0x05, 0x01, 0x08, 0x06, 0x07, 0x04), а $j$ — номер стовпця матриці стану $G$ ^[6].

S-блоки[ред. | ред. код]

Підстановка π₀[ред. | ред. код]

A8	43	5F	06	6B	75	6C	59	71	DF	87	95	17	F0	D8	09
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

Підстановка π₁[ред. | ред. код]

CE	BB	EB	92	EA	CB	13	C1	E9	3A	D6	B2	D2	90	17	F8
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

Підстановка π₂[ред. | ред. код]

93	D9	9A	B5	98	22	45	FC	BA	6A	DF	02	9F	DC	51	59
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

Підстановка π₃[ред. | ред. код]

68	8D	CA	4D	73	4B	4E	2A	D4	52	26	B3	54	1E	19	1F
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

Криптостійкість[ред. | ред. код]

Автори запевняють, що диференціальні атаки і rebound-атаки неефективні вже після 4 ітерацій функцій перестановок. У таблиці наведені заявлені авторами показники криптостійкості.

Вид атаки	Купина-256	Купина-512
Колізія	2¹²⁸	2²⁵⁶
Першовзір	2²⁵⁶	2⁵¹²
Другий першовзір	2²⁵⁶	2⁵¹²
Фіксовані точки	2²⁵⁶	2⁵¹²

У результаті незалежного криптоаналізу вдалося провести атаку тільки на перші 5 раундів; складність знаходження колізії для скороченої до 5 раундів функції Купина-256 складає 2¹²⁰.^[7]^[8]

Використання[ред. | ред. код]

Kupyna-reference — код референсної реалізаціі на C

cppcrypto — Бібліотека з відкритим вихідним кодом на C++

cryptonite — бібліотека криптографічних перетворень від ПриватБанку з відкритим програмним кодом на C, має експертний висновок UA.14360570.00001-01 90 01-1 за результатами державної експертизи у галузі КЗІ

Примітки[ред. | ред. код]

↑ ДСТУ 7564:2014 в Каталозі НД України
↑ Про прийняття національних стандартів України, гармонізованих з європейськими стандартами, міжнародних стандартів як національних стандартів України, затвердження національних стандартів України, скасування міждержавних стандартів в Україні та внесення зміни до наказу Державного комітету стандартизації, метрології та сертифікації України від 12.06.2002 №357
↑ Текст стандарту ДСТУ 7564:2014 на сайті Державного підприємства «Український науково-дослідний і навчальний центр проблем стандартизації, сертифікації та якості». Архів оригіналу за 14 травня 2019. Процитовано 5 травня 2019.
↑ Держспецзв’язку впроваджує нові стандарти криптографічного захисту інформації
↑ Наказ № 140/614 від 30.09.2020 "Про встановлення вимог до технічних засобів, процесів їх створення, використання та функціонування у складі інформаційно-телекомунікаційних систем під час надання кваліфікованих електронних довірчих послуг". zakon.rada.gov.ua (укр.). Міністерство цифрової трансформації України. 30 вересня 2020. Процитовано 4 січня 2021.
↑ ^а ^б ^в ^г ^д ^е ^ж ^и ^к ^л ^м ^н ^п ^р ^с ^т https://eprint.iacr.org/2015/885.pdf Roman Oliynykov, Ivan Gorbenko, Oleksandr Kazymyrov, Victor Ruzhentsev, Oleksandr Kuznetsov, Yurii Gorbenko, Artem Boiko, Oleksandr Dyrda, Viktor Dolgov, Andrii Pushkaryov A New Standard of Ukraine: The Kupyna Hash Function
↑ Christoph Dobraunig, Maria Eichlseder, and Florian Mendel (2015). Analysis of the Kupyna-256 Hash Function (PDF) (англ.). Процитовано 1 жовтня 2015.
↑ Jian Zou, Le Dong (2015). Cryptanalysis of the Round-Reduced Kupyna Hash Function (PDF) (англ.). Процитовано 2 жовтня 2015.

Див. також[ред. | ред. код]

Портал «Програмування»

[1] ДСТУ 7564:2014 в Каталозі НД України

[2] Про прийняття національних стандартів України, гармонізованих з європейськими стандартами, міжнародних стандартів як національних стандартів України, затвердження національних стандартів України, скасування міждержавних стандартів в Україні та внесення зміни до наказу Державного комітету стандартизації, метрології та сертифікації України від 12.06.2002 №357

[3] Текст стандарту ДСТУ 7564:2014 на сайті Державного підприємства «Український науково-дослідний і навчальний центр проблем стандартизації, сертифікації та якості». Архів оригіналу за 14 травня 2019. Процитовано 5 травня 2019.

[4] Держспецзв’язку впроваджує нові стандарти криптографічного захисту інформації

[5] Наказ № 140/614 від 30.09.2020 "Про встановлення вимог до технічних засобів, процесів їх створення, використання та функціонування у складі інформаційно-телекомунікаційних систем під час надання кваліфікованих електронних довірчих послуг". zakon.rada.gov.ua (укр.). Міністерство цифрової трансформації України. 30 вересня 2020. Процитовано 4 січня 2021.

[eprint-desc-6] а ^б ^в ^г ^д ^е ^ж ^и ^к ^л ^м ^н ^п ^р ^с ^т https://eprint.iacr.org/2015/885.pdf Roman Oliynykov, Ivan Gorbenko, Oleksandr Kazymyrov, Victor Ruzhentsev, Oleksandr Kuznetsov, Yurii Gorbenko, Artem Boiko, Oleksandr Dyrda, Viktor Dolgov, Andrii Pushkaryov A New Standard of Ukraine: The Kupyna Hash Function

[7] Christoph Dobraunig, Maria Eichlseder, and Florian Mendel (2015). Analysis of the Kupyna-256 Hash Function (PDF) (англ.). Процитовано 1 жовтня 2015.

[8] Jian Zou, Le Dong (2015). Cryptanalysis of the Round-Reduced Kupyna Hash Function (PDF) (англ.). Процитовано 2 жовтня 2015.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Купина (геш-функція)

Зміст