SM3 (хеш-функция)

SM3 — криптографическая хэш-функция, являющаяся частью национального криптографического стандарта Китая. Она была опубликована Государственным управлением криптографии 17 декабря 2010 под названием «GM/T 0004-2012: криптографический хэш алгоритм SM3»^[1][2]. SM3 в основном используется в электронных подписях, имитовставках и генераторах псевдослучайных чисел^[3].

Функция SM3 определена в стандарте «GM/T 0004-2012: криптографический хэш алгоритм SM3».

Приказом от 2016 года Национальное управление криптографии утвердило SM3 как один из отраслевых стандартов^[1].

SM3 — 256-битный хэш алгоритм. Он является модификацией SHA-2. Создательница алгоритма — Ван Сяоюнь^[англ.], которая известна открытием новых способов атак для разных криптографических хэш-функций (MD5 и SHA-1). SM3 был опубликован в 2010 году. SM3 использует структуру Меркла — Дамгора^[4].

Алгоритм принимает на вход сообщение ${\displaystyle m}$ длины ${\displaystyle l}$. После процедуры пэддинга и нескольких итераций компрессии на выходе получится 256-битное значение хэш-функции.

Значения для инициализации следующие:

• ${\displaystyle V_{0}^{(0)}=7380166f}$
• ${\displaystyle V_{1}^{(0)}=4914b2b9}$
• ${\displaystyle V_{2}^{(0)}=172442d7}$
• ${\displaystyle V_{3}^{(0)}=da8a0600}$
• ${\displaystyle V_{4}^{(0)}=a96f30bc}$
• ${\displaystyle V_{5}^{(0)}=163138aa}$
• ${\displaystyle V_{6}^{(0)}=e38dee4d}$
• ${\displaystyle V_{7}^{(0)}=b0fb0e4e}$

${\displaystyle T_{j}={\begin{cases}79cc4519,&{\mbox{if }}0\leq j\leq 15\\7a879d8a,&{\mbox{if }}16\leq j\leq 63\end{cases}}}$

${\displaystyle FF_{j}={\begin{cases}X\oplus Y\oplus Z,&{\mbox{for }}0\leq j\leq 15\\(X\wedge Y)\lor (Y\wedge Z)\lor (X\wedge Z),&{\mbox{if }}16\leq j\leq 63\end{cases}}}$
${\displaystyle GG_{j}={\begin{cases}X\oplus Y\oplus Z,&{\mbox{for }}0\leq j\leq 15\\(X\wedge Y)\lor (\neg X\wedge Z),&{\mbox{if }}16\leq j\leq 63\end{cases}}}$

${\displaystyle P_{0}(X)=X\oplus (X<<<9)\oplus (X<<<17)}$

${\displaystyle P_{1}(X)=X\oplus (X<<<15)\oplus (X<<<23)}$

Сообщение ${\displaystyle m}$ cосостоит из ${\displaystyle l}$ бит. Добавим бит 1 к концу сообщения, а также ${\displaystyle k}$ нулевых бит, где ${\displaystyle k}$ — наименьшее неотрицательное число, удовлетворяющее соотношению ${\displaystyle l+k+1\equiv 488{\mbox{ mod }}512}$. Затем к полученному сообщению необходимо добавить 64-битную строку, являющуюся двоичным представлением числа ${\displaystyle l}$, изначальной длины сообщения. В результате будет получена строка ${\displaystyle m'}$, длина которой кратна 512.

Сообщение ${\displaystyle m'}$, уже прошедшее пэддинг, разделяется на 512-битные блоки (в обозначениях ${\displaystyle m'=B^{(0)}B^{(1)}\dots B^{(n-1)}}$, где ${\displaystyle n={\frac {l+k+65}{512}}}$).

Далее алгоритм следующий:

${\displaystyle {\mbox{FOR }}i=0{\mbox{ to }}n-1:}$

${\displaystyle V(i+1)=CF(V(i),B(i))}$

${\displaystyle ENDFOR}$

Здесь ${\displaystyle CF}$ — функция компрессии, ${\displaystyle V^{(0)}}$ — 256-битный вектор инициализации. Результат после итерации есть ${\displaystyle V^{(n)}}$.

Блок сообщения ${\displaystyle B^{(i)}}$ расширяется до 132 слов ${\displaystyle W_{0},W_{1}\dots W_{67},W'_{1}\dots W'_{63}}$, которые добавлены к компрессионной функции ${\displaystyle CF}$:

Делим блок ${\displaystyle B^{(i)}}$ на 16 слов.

${\displaystyle {\mbox{FOR }}j=16{\mbox{ to }}j=67:}$

${\displaystyle W_{j}\leftarrow P_{1}(W_{j-16}\oplus W_{j-9}\oplus (W_{j-3}<<<15))\oplus (W_{j-13}<<<7)\oplus W_{j-6}}$

${\displaystyle ENDFOR}$

${\displaystyle {\mbox{FOR }}j=0{\mbox{ to }}j=63:}$

${\displaystyle W_{j}=W_{j}\oplus W_{j+4}}$

${\displaystyle ENDFOR}$

Пусть ${\displaystyle A{\mbox{, }}B{\mbox{, }}C{\mbox{, }}D{\mbox{, }}E{\mbox{, }}F{\mbox{, }}G{\mbox{, }}H}$ — 8 слов регистров, ${\displaystyle SS1{\mbox{, }}SS2{\mbox{, }}TT1{\mbox{, }}TT2}$ — 4 промежуточные переменные. Вычислительная процедура следующая:

${\displaystyle ABCDEFGH\leftarrow V(i)}$
${\displaystyle {\mbox{FOR }}j=0{\mbox{ to }}63}$
${\displaystyle SS1\leftarrow ((A<<<12)+E+(T_{j}<<<(j{\mbox{ mod }}32)))<<<7}$${\displaystyle SS2\leftarrow SS1\oplus (A<<<12)}$
${\displaystyle TT1\leftarrow FF_{j}(A,B,C)+D+SS2+W'_{j}}$
${\displaystyle TT2\leftarrow GG_{j}(E,F,G)+H+SS1+W'_{j}}$
${\displaystyle D\leftarrow C}$
${\displaystyle C\leftarrow B<<<9}$
${\displaystyle B\leftarrow A}$
${\displaystyle A\leftarrow TT1}$
${\displaystyle H\leftarrow G}$
${\displaystyle G\leftarrow F<<<19}$
${\displaystyle F\leftarrow E}$
${\displaystyle E\leftarrow P_{0}(TT2)}$
${\displaystyle ENDFOR}$
${\displaystyle V(i+1)\leftarrow ABCDEFGH\oplus V(i)}$

Итого, ${\displaystyle ABCDEFGH\leftarrow V^{(n)}}$. Отсюда окончательное значение хэш-функции ${\displaystyle y:=ABCDEFGH}$^[3].

Для входного сообщения «abc» (и его ASCII версии 616263 соответственно) значение хэш-функции равно:

66c7f0f4 62eeedd9 d1f2d46b dc10e4e2 4167c487 5cf2f7a2 297da02b 8f4ba8e0

Для входного сообщения с кодом длиной 512 бит:

61626364 61626364 61626364 61626364 61626364 61626364 61626364 61626364
61626364 61626364 61626364 61626364 61626364 61626364 61626364 61626364

Хэш-функция будет равна:

debe9ff9 2275b8a1 38604889 c18e5a4d 6fdb70e5 387e5765 293dcba3 9c0c5732

Результаты сравнения эффективности алгоритма SM3, оригинального и 2 его оптимизаций, а также SHA-256 представлены в таблице ниже^[5]. Эффективность оценивается для параметров, которые указаны в заглавии колонок.

Не существует никаких формальных доказательств относительно качества этого алгоритма, тем не менее, не зарегистрировано успешных атак на SM3^[3].

Криптоаналитические результаты для различных атак на алгоритм SM3 агрегированы в следующей таблице.

Алгоритм является открытым и, по утверждениям Китайского информационного интернет-центра, является аналогом SHA-256 в вопросах безопасности и эффективности^[4].

Так как SM3 является единственной функцией, разрешенной для использования в Китае Национальным управлением криптографии, ее реализация в аппаратуре необходима для применения в китайском оборудовании^[3].

Примеры прикладного применения SM3 указаны в таблице:

• SHA-2