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

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

Определяющий стандарт

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

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

История создания

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

Описание алгоритма

Общее описание

Графическое представление работы алгоритма SM3

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

Значения вектора инициализации

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

• $V_0^{(0)}=7380166f$
• $V_1^{(0)}=4914b2b9$
• $V_2^{(0)}=172442d7$
• $V_3^{(0)}=da8a0600$
• $V_4^{(0)}=a96f30bc$
• $V_5^{(0)}=163138aa$
• $V_6^{(0)}=e38dee4d$
• $V_7^{(0)}=b0fb0e4e$

Константы

$T_j=\{\begin{array}{cc}79cc4519,& \text{if }0\le j\le 15\\ 7a879d8a,& \text{if }16\le j\le 63\end{array}$

Булевы функции

$F{F}_j=\{\begin{array}{cc}X\oplus Y\oplus Z,& \text{for }0\le j\le 15\\ (X\wedge Y)\vee (Y\wedge Z)\vee (X\wedge Z),& \text{if }16\le j\le 63\end{array}$
$G{G}_j=\{\begin{array}{cc}X\oplus Y\oplus Z,& \text{for }0\le j\le 15\\ (X\wedge Y)\vee (\mathrm{\neg }X\wedge Z),& \text{if }16\le j\le 63\end{array}$

Перестановки

$P_0(X)=X\oplus (X<<<9)\oplus (X<<<17)$

$P_1(X)=X\oplus (X<<<15)\oplus (X<<<23)$

Пэддинг

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

Процедура повторения функции компрессии

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

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

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

$V(i+1)=CF(V(i),B(i))$

$ENDFOR$

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

Расширение сообщения

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

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

$\text{FOR }j=16\text{ to }j=67:$

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

$ENDFOR$

$\text{FOR }j=0\text{ to }j=63:$

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

$ENDFOR$

Компрессионная функция

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

$ABCDEFGH\leftarrow V(i)$
$\text{FOR }j=0\text{ to }63$
$SS1\leftarrow ((A<<<12)+E+(T_j<<<(j\text{ mod }32)))<<<7$ $SS2\leftarrow SS1\oplus (A<<<12)$
$TT1\leftarrow F{F}_j(A,B,C)+D+SS2+W{\text{'}}_j$
$TT2\leftarrow G{G}_j(E,F,G)+H+SS1+W{\text{'}}_j$
$D\leftarrow C$
$C\leftarrow B<<<9$
$B\leftarrow A$
$A\leftarrow TT1$
$H\leftarrow G$
$G\leftarrow F<<<19$
$F\leftarrow E$
$E\leftarrow P_0(TT2)$
$ENDFOR$
$V(i+1)\leftarrow ABCDEFGH\oplus V(i)$

Значение хэш-функции

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

Примеры работы алгоритма на разных сообщениях

Пример 1

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

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

Пример 2

Для входного сообщения с кодом длиной 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 представлены в таблице ниже. Эффективность оценивается для параметров, которые указаны в заглавии колонок.

Сравнение эффективности SM3 и его модификаций с алгоритмом SHA-256

Название алгоритма	Девайс	Slices	Максимальная частота (MHz)	Бит/цикл	Пропускная способность (Mbps)	Пропускная способность/slice
Стандартный SM3	Virtex-5	384	214	7.53	1611	4.20
C-SM3	Virtex-5	234	215	7.53	1619	6.92
T-SM3	Virtex-5	328	362	7.53	2726	8.31
SHA-256	Virtex-5	319	221	7.76	1714	5.37

Криптоанализ

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

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

Результаты криптоаналитических атак на алгоритм SM3

Тип атаки	Число шагов	Сложность	Ссылка на исследование
Коллизионная атака	20	2^117.1
Коллизия инициализации	24	2^249
Атака нахождения прообраза	28	2^241.5
Атака нахождения прообраза	30	2^249
Атака нахождения прообраза	29	2^245
Атака нахождения прообраза	30	2^251.1
Псевдоатака нахождения прообраза	31	2^245
Псевдоатака нахождения прообраза	32	2^251.1
Методом бумеранга	33	2^125
Методом бумеранга	35	2^117.1
Методом бумеранга	35	2^33.6
Методом бумеранга	37	2^192

Реализация и применение

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

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

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

Область применения	Детали
X.509	Существует реализация SM3 для создания электронной цифровой подписи сертификата
PGP	SM3 наряду с SM2 и SM4 реализован в расширении PGP для использования на территории Китая
IPSec	Реализация IPSec IKEv1 поддерживает SM3
Financial IC Card	Одним из методов обеспечивания безопасности банковских карт, основанных на чипах, является SM3 .
OpenSSL	В криптографической библиотеке OpenSSL реализован алгоритм SM3
Hash Crypto Engine BA413	BA413 является блоком для проектирования микросхем, который используется для задачи формирования ключа и применения цифровой подписи. Для применения на территории Китая в нем внедрен SM3.

См. также

• SHA-2