Kupyna

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

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

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

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

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

${\displaystyle h_{0}=IV}$

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

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

где

${\displaystyle \nu =1,2,...,k}$

${\displaystyle IV=1<<510}$, если l = 512, или ${\displaystyle 1<<1023}$, если l = 1024

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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