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].

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

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

Алгоритм принимает на вход сообщение $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{cases}79cc4519,&{\mbox{if }}0\leq j\leq 15\\7a879d8a,&{\mbox{if }}16\leq j\leq 63\end{cases}}$

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

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

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

$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{\mbox{ mod }}512$ . Затем к полученному сообщению необходимо добавить 64-битную строку, являющуюся двоичным представлением числа $l$ , изначальной длины сообщения. В результате будет получена строка $m'$ , длина которой кратна 512.

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

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

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

${\mbox{FOR }}i=0{\mbox{ 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'_{1}\dots W'_{63}$ , которые добавлены к компрессионной функции $CF$ :

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

${\mbox{FOR }}j=16{\mbox{ 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$

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

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

$ENDFOR$

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

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

$ABCDEFGH\leftarrow V(i)$
${\mbox{FOR }}j=0{\mbox{ to }}63$
$SS1\leftarrow ((A<<<12)+E+(T_{j}<<<(j{\mbox{ mod }}32)))<<<7$ $SS2\leftarrow SS1\oplus (A<<<12)$
$TT1\leftarrow FF_{j}(A,B,C)+D+SS2+W'_{j}$
$TT2\leftarrow GG_{j}(E,F,G)+H+SS1+W'_{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$ ^[3].

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

Пример 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 представлены в таблице ниже^[5]. Эффективность оценивается для параметров, которые указаны в заглавии колонок.

Сравнение эффективности 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^[3].

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

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

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

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

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

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

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

См. также

SHA-2

Примечания

↑ ¹ ² Announcement No.23 of the State Cryptography Administration (кит.). The Office of Security Commercial Code Administration (OSCCA) (21 марта 2012). Архивировано 14 августа 2016 года.
↑ SM3 cryptographic hash algorithm (кит.). CNNIC (4 декабря 2013). Дата обращения: 27 октября 2020. Архивировано 19 сентября 2016 года.
↑ ¹ ² ³ ⁴ ⁵ The SM3 Cryptographic Hash Function (англ.). Internet Engineering Task Force (24 ноября 2017). Дата обращения: 27 октября 2020. Архивировано 4 октября 2020 года.
↑ ¹ ² SM3 Cryptographic Hash Algorithm (Chinese Standard) (неопр.) (22 февраля 2017). Дата обращения: 26 октября 2020. Архивировано 30 октября 2020 года.
↑ Yuan Ma, Luning Xia, Jingqiang Lin, Jiwu Jing, Zongbin Liu, and Xingjie Yu. Hardware Performance Optimization and Evaluation of SM3 Hash Algorithm on FPGA. — 2012. Архивировано 20 января 2022 года.
↑ ¹ ² Mendel, F., Nad, T. and M. Schlaffer. Finding collisions for round-reduced SM3. — 2013. Архивировано 20 января 2022 года.
↑ ¹ ² Zou, J., Wu, W., Wu, S., Su, B. and L. Dong. Preimage attacks on step-reduced SM3 hash function. — 2012. Архивировано 7 апреля 2019 года.
↑ ¹ ² ³ ⁴ Zou, G. and Y. Shen. Preimage and Pseudo-Collision Attacks on Step-Reduced SM3 Hash Function. — 2013.
↑ ¹ ² Kircanski, A., Wang, G., Shen, Y. and A. Youssef. Boomerang and slide-rotational analysis of the SM3 hash function. — 2013. Архивировано 23 мая 2022 года.
↑ ¹ ² Bai, D., Yu, H., Wang, G. and X. Wang. Improved Boomerang Attacks on Round-Reduced SM3 and Keyed Permutation of BLAKE-256. — 2015. Архивировано 30 октября 2020 года.
↑ Hua Jiang, Gang Zhang, Jinpo Fan. Structure Analysis and Generation of X.509 Digital Certificate Based on National Secret. — 2019. Архивировано 13 февраля 2020 года.
↑ SCA Extensions For OpenPGP (неопр.). Дата обращения: 16 ноября 2020. Архивировано 9 августа 2020 года.
↑ IPSec VPN
↑ China Financial Integrated Circuit (IC) Card Specifications
↑ Ye Hu, Liji Wu, An Wang, Beibei Wang. Hardware Design and Implementation of SM3 Hash Algorithm for Financial IC Card. — 2014.
↑ OpenSSL Documentation (неопр.). Дата обращения: 16 ноября 2020. Архивировано 9 марта 2018 года.
↑ ¹ ² Hash Crypto Engine (неопр.). Дата обращения: 16 ноября 2020. Архивировано 31 декабря 2020 года.

[oscca1228-1] ¹ ² Announcement No.23 of the State Cryptography Administration (кит.). The Office of Security Commercial Code Administration (OSCCA) (21 марта 2012). Архивировано 14 августа 2016 года.

[2] SM3 cryptographic hash algorithm (кит.). CNNIC (4 декабря 2013). Дата обращения: 27 октября 2020. Архивировано 19 сентября 2016 года.

[draft-oscca-cfrg-sm3-02-3] ¹ ² ³ ⁴ ⁵ The SM3 Cryptographic Hash Function (англ.). Internet Engineering Task Force (24 ноября 2017). Дата обращения: 27 октября 2020. Архивировано 4 октября 2020 года.

[tinyscript-4] ¹ ² SM3 Cryptographic Hash Algorithm (Chinese Standard) (неопр.) (22 февраля 2017). Дата обращения: 26 октября 2020. Архивировано 30 октября 2020 года.

[hard-5] Yuan Ma, Luning Xia, Jingqiang Lin, Jiwu Jing, Zongbin Liu, and Xingjie Yu. Hardware Performance Optimization and Evaluation of SM3 Hash Algorithm on FPGA. — 2012. Архивировано 20 января 2022 года.

[COL-6] ¹ ² Mendel, F., Nad, T. and M. Schlaffer. Finding collisions for round-reduced SM3. — 2013. Архивировано 20 января 2022 года.

[Pre-7] ¹ ² Zou, J., Wu, W., Wu, S., Su, B. and L. Dong. Preimage attacks on step-reduced SM3 hash function. — 2012. Архивировано 7 апреля 2019 года.

[Pre2-8] ¹ ² ³ ⁴ Zou, G. and Y. Shen. Preimage and Pseudo-Collision Attacks on Step-Reduced SM3 Hash Function. — 2013.

[Boom-9] ¹ ² Kircanski, A., Wang, G., Shen, Y. and A. Youssef. Boomerang and slide-rotational analysis of the SM3 hash function. — 2013. Архивировано 23 мая 2022 года.

[Boom2-10] ¹ ² Bai, D., Yu, H., Wang, G. and X. Wang. Improved Boomerang Attacks on Round-Reduced SM3 and Keyed Permutation of BLAKE-256. — 2015. Архивировано 30 октября 2020 года.

[11] Hua Jiang, Gang Zhang, Jinpo Fan. Structure Analysis and Generation of X.509 Digital Certificate Based on National Secret. — 2019. Архивировано 13 февраля 2020 года.

[12] SCA Extensions For OpenPGP (неопр.). Дата обращения: 16 ноября 2020. Архивировано 9 августа 2020 года.

[13] IPSec VPN

[14] China Financial Integrated Circuit (IC) Card Specifications

[15] Ye Hu, Liji Wu, An Wang, Beibei Wang. Hardware Design and Implementation of SM3 Hash Algorithm for Financial IC Card. — 2014.

[16] OpenSSL Documentation (неопр.). Дата обращения: 16 ноября 2020. Архивировано 9 марта 2018 года.

[BA413-17] ¹ ² Hash Crypto Engine (неопр.). Дата обращения: 16 ноября 2020. Архивировано 31 декабря 2020 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

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

Содержание

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

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

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

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

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

Константы

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

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

Пэддинг

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

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

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

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

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

Пример 1

Пример 2

Аппаратная оптимизация и оценка эффективности

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

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

См. также

Примечания

Навигация

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

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

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

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

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

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

Константы

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

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

Пэддинг

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

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

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

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

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

Пример 1

Пример 2

Аппаратная оптимизация и оценка эффективности

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

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

См. также

Примечания

Навигация

Поиск

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