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

Не следует путать с SIMD.

SIMD — итеративная криптографическая хеш-функция, разработанная Gaëtan Leurent, Charles Bouillaguet, Pierre-Alain Fouque. Была выдвинута как кандидат на конкурс стандарта SHA-3, проводимый Национальным институтом стандартов и технологий (США), где прошла во второй раунд.

SIMD
Создан	2008
Опубликован	Октябрь 2008
Размер хеша	256 или 512 бит
Число раундов	4
Тип	хеш-функция

Существуют два варианта хеш-функции: SIMD-256 и SIMD-512, преобразующие сообщение произвольной длины в 256 или 512-битное хеш-значение, называемое также дайджестом сообщения. Кроме того возможно определить хеш-функции SIMD-n как усечение функций SIMD-256 и SIMD-512 для n<256 и 256<n<512 соответственною.

Как утверждают создатели, главной особенностью хеш функции является значительное расширение сообщения, которое позволяет защититься от дифференциального криптоанализа.

АлгоритмПравить

Общее описание и параметрыПравить

Главной частью хеш-функции h является функция сжатия $C:<!--\; :\; -->\{0,1{\}}^p\times <!--\; \times \; -->\{0,1{\}}^m\to <!--\; \to \; -->\{0,1{\}}^p$$C\colon \{0,1\}^{p}\times \{0,1\}^{m}\to \{0,1\}^{p}$ . Чтобы вычислить h(M), сообщение M разбивается на k частей $M_i$$M_{i}$  по m бит. Затем к частям сообщения итеративно применяется функция сжатия: $H_{i+1}=C(H_i,M_i)$$H_{{i+1}}=C(H_{i},M_{i})$ . Начальное состояние $H_0$$H_{0}$  или вектор инициализации^[en] обозначается $IV$$IV$  и является фиксированным для каждой функции семейства SIMD. Окончательный результат работы хеш-функции получается применением финализирующей функции (finalization function) $D:<!--\; :\; -->\{0,1{\}}^p\to <!--\; \to \; -->\{0,1{\}}^n$$D\colon \{0,1\}^{p}\to \{0,1\}^{n}$  к $H_{k-<!--\; -\; -->1}$$H_{{k-1}}$ .

Функция сжатия C в режиме Дэвиса-Мейера обычно строится с использованием функции блочного шифрования $E_m$$E_m$ : $C(h,m)=E_m(h)\otimes <!--\; \otimes \; -->h$$C(h,m)=E_{m}(h)\otimes h$ , однако для хеш-функции SIMD используются несколько улучшений.

Семейство хеш-функций SIMD использует следующие параметры:

	Размер хеша, n	Размер блока сообщения, m	Размер внутреннего состояния($H_i$$H_{{i}}$ ), p
SIMD-256	256	512	512
SIMD-512	512	1024	1024

Внутреннее состояние представлено матрицей 32-битных слов размером 4×4 для SIMD-256 и 8×4 для SIMD-512.

$S_{{256}}={\begin{bmatrix}A_{0}&B_{0}&C_{0}&D_{0}\\A_{1}&B_{1}&C_{1}&D_{1}\\A_{2}&B_{2}&C_{2}&D_{2}\\A_{3}&B_{3}&C_{3}&D_{3}\end{bmatrix}};\qquad S_{{512}}={\begin{bmatrix}A_{0}&B_{0}&C_{0}&D_{0}\\A_{1}&B_{1}&C_{1}&D_{1}\\A_{2}&B_{2}&C_{2}&D_{2}\\A_{3}&B_{3}&C_{3}&D_{3}\\A_{4}&B_{4}&C_{4}&D_{4}\\A_{5}&B_{5}&C_{5}&D_{5}\\A_{6}&B_{6}&C_{6}&D_{6}\\A_{7}&B_{7}&C_{7}&D_{7}\end{bmatrix}}$ 

Функция сжатияПравить

Функция сжатия SIMD построена на основе конструкции Дэвиса-Мейера с некоторыми изменениями.

Во-первых, вместо функции сжатия $C(h,m)=E_m(h)\otimes <!--\; \otimes \; -->h$$C(h,m)=E_{m}(h)\otimes h$  используется функция $C(h,m)=E_m(h\otimes <!--\; \otimes \; -->m)\otimes <!--\; \otimes \; -->h$$C(h,m)=E_{m}(h\otimes m)\otimes h$ .

Во-вторых, вместо операции XOR для $E_m(h\otimes <!--\; \otimes \; -->m)$$E_{m}(h\otimes m)$  и $h$$h$  в SIMD применяются несколько дополнительных раундов Фейстеля с h в качестве входного ключа. Это действие выполняет функция $P:<!--\; :\; -->\{0,1{\}}^p\times <!--\; \times \; -->\{0,1{\}}^p\to <!--\; \to \; -->\{0,1{\}}^p$$P\colon \{0,1\}^{p}\times \{0,1\}^{p}\to \{0,1\}^{p}$ .

Таким образом, функция сжатия определена как $C(h,m)=P(h,E_m(h\otimes <!--\; \otimes \; -->m))$$C(h,m)=P(h,E_{m}(h\otimes m))$ . Как утверждают авторы хеш-функции SIMD, эти модификации обеспечивают такой же уровень безопасности, как и оригинальная конструкция Дэвиса-Мейера, но в то же время предотвращают некоторые виды атак множественных блоков (multi-block attacks).

Расширение сообщенияПравить

Расширение сообщения (message expansion) хеш-функции SIMD-256 (соотв. SIMD-512) преобразует блок сообщения в 512 бит (соотв. 1024 бита) в расширенное сообщение размером 4096 бит (соотв. 8192 бит) с минимальным расстоянием в 520 (соотв. 1032).

Использование сети ФейстеляПравить

Использование структуры Фейстеля хеш-функцией SIMD построено аналогично семейству хеш-функций MD/SHA:

$A_j^{(i)}={\left(D_j^{(i-<!--\; -\; -->1)}⊞<!--\; ⊞\; -->W_j^{(i)}⊞<!--\; ⊞\; -->{\mathrm{\varphi <!--\; \varphi \; -->}}_i(A_j^{(i-<!--\; -\; -->1)},B_j^{(i-<!--\; -\; -->1)},C_j^{(i-<!--\; -\; -->1)})\right)}^{⋘<!--\; ⋘\; -->s_i}⊞<!--\; ⊞\; -->A_{p_i(j)}^{(i-<!--\; -\; -->1{)}^{⋘<!--\; ⋘\; -->r_i}}$$A_{j}^{{(i)}}=\left(D_{j}^{{(i-1)}}\boxplus W_{j}^{{(i)}}\boxplus \phi _{i}(A_{j}^{{(i-1)}},B_{j}^{{(i-1)}},C_{j}^{{(i-1)}})\right)^{{\lll s_{i}}}\boxplus A_{{p_{i}(j)}}^{{(i-1)^{{\lll r_{i}}}}}$ 

$B_j^{(i)}=A_j^{(i-<!--\; -\; -->1{)}^{⋘<!--\; ⋘\; -->r_i}}$$B_{j}^{{(i)}}=A_{j}^{{(i-1)^{{\lll r_{i}}}}}$ 

$C_j^{(i)}=B_j^{(i-<!--\; -\; -->1)}$$C_{j}^{{(i)}}=B_{j}^{{(i-1)}}$ 

$D_j^{(i)}=C_j^{(i-<!--\; -\; -->1)}$$D_{j}^{{(i)}}=C_{j}^{{(i-1)}}$ 

или в более удобном формате:

$Step\left({\begin{bmatrix}A_{0}&B_{0}&C_{0}&D_{0}\\A_{1}&B_{1}&C_{1}&D_{1}\\A_{2}&B_{2}&C_{2}&D_{2}\\A_{3}&B_{3}&C_{3}&D_{3}\end{bmatrix}},{\begin{bmatrix}W_{0}\\W_{1}\\W_{2}\\W_{3}\end{bmatrix}},\phi ,r,s,p\right)={\begin{bmatrix}\left(D_{0}\boxplus W_{0}\boxplus \phi _{i}(A_{0},B_{0},C_{0})\right)^{{\lll s}}\boxplus A_{{p(0)}}^{{\lll r}}&A_{0}^{{\lll r}}&B_{0}&C_{0}\\\left(D_{1}\boxplus W_{1}\boxplus \phi _{i}(A_{1},B_{1},C_{1})\right)^{{\lll s}}\boxplus A_{{p(1)}}^{{\lll r}}&A_{1}^{{\lll r}}&B_{1}&C_{1}\\\left(D_{2}\boxplus W_{2}\boxplus \phi _{i}(A_{2},B_{2},C_{2})\right)^{{\lll s}}\boxplus A_{{p(2)}}^{{\lll r}}&A_{2}^{{\lll r}}&B_{2}&C_{2}\\\left(D_{3}\boxplus W_{3}\boxplus \phi _{i}(A_{3},B_{3},C_{3})\right)^{{\lll s}}\boxplus A_{{p(3)}}^{{\lll r}}&A_{3}^{{\lll r}}&B_{3}&c_{3}\end{bmatrix}}$  для SIMD-256

$Step\left({\begin{bmatrix}A_{0}&B_{0}&C_{0}&D_{0}\\A_{1}&B_{1}&C_{1}&D_{1}\\A_{2}&B_{2}&C_{2}&D_{2}\\A_{3}&B_{3}&C_{3}&D_{3}\\A_{4}&B_{4}&C_{4}&D_{4}\\A_{5}&B_{5}&C_{5}&D_{5}\\A_{6}&B_{6}&C_{6}&D_{6}\\A_{7}&B_{7}&C_{7}&D_{7}\end{bmatrix}},{\begin{bmatrix}W_{0}\\W_{1}\\W_{2}\\W_{3}\\W_{4}\\W_{5}\\W_{6}\\W_{7}\end{bmatrix}},\phi ,r,s,p\right)={\begin{bmatrix}\left(D_{0}\boxplus W_{0}\boxplus \phi _{i}(A_{0},B_{0},C_{0})\right)^{{\lll s}}\boxplus A_{{p(0)}}^{{\lll r}}&A_{0}^{{\lll r}}&B_{0}&C_{0}\\\left(D_{1}\boxplus W_{1}\boxplus \phi _{i}(A_{1},B_{1},C_{1})\right)^{{\lll s}}\boxplus A_{{p(1)}}^{{\lll r}}&A_{1}^{{\lll r}}&B_{1}&C_{1}\\\left(D_{2}\boxplus W_{2}\boxplus \phi _{i}(A_{2},B_{2},C_{2})\right)^{{\lll s}}\boxplus A_{{p(2)}}^{{\lll r}}&A_{2}^{{\lll r}}&B_{2}&C_{2}\\\left(D_{3}\boxplus W_{3}\boxplus \phi _{i}(A_{3},B_{3},C_{3})\right)^{{\lll s}}\boxplus A_{{p(3)}}^{{\lll r}}&A_{3}^{{\lll r}}&B_{3}&c_{3}\\\left(D_{4}\boxplus W_{4}\boxplus \phi _{i}(A_{4},B_{4},C_{4})\right)^{{\lll s}}\boxplus A_{{p(4)}}^{{\lll r}}&A_{4}^{{\lll r}}&B_{4}&C_{4}\\\left(D_{5}\boxplus W_{5}\boxplus \phi _{i}(A_{5},B_{5},C_{5})\right)^{{\lll s}}\boxplus A_{{p(5)}}^{{\lll r}}&A_{5}^{{\lll r}}&B_{5}&C_{5}\\\left(D_{6}\boxplus W_{6}\boxplus \phi _{i}(A_{6},B_{6},C_{6})\right)^{{\lll s}}\boxplus A_{{p(6)}}^{{\lll r}}&A_{6}^{{\lll r}}&B_{6}&C_{6}\\\left(D_{7}\boxplus W_{7}\boxplus \phi _{i}(A_{7},B_{7},C_{7})\right)^{{\lll s}}\boxplus A_{{p(7)}}^{{\lll r}}&A_{7}^{{\lll r}}&B_{7}&c_{7}\end{bmatrix}}$  для SIMD-512

где ${\mathrm{\varphi <!--\; \varphi \; -->}}_i$$\phi_i$  - логическая функция, $⊞<!--\; ⊞\; -->$$\boxplus$  - сложение по модулю $2^{32}$$2^{32}$  и $⋘<!--\; ⋘\; -->s_i$$\lll s_{i}$  - циклический сдвиг влево на $s_i$$s_{i}$  бит.

Используются 4 параллельные ячейки Фейстеля для SIMD-256 (соотв. 8 для SIMD-512), которые взаимодействуют между собой из-за перестановок $p_i$$p_{i}$ . Перестановки выбираются таким образом, чтобы обеспечить хорошее перемешивание.

Для SIMD-256 определено:

$p^{{(i)}}(x)={\begin{cases}{x+1}{\pmod 4},&{\mbox{if }}i{\mbox{ is even}}\\{x+2}{\pmod 4},&{\mbox{if }}i{\mbox{ is odd}}\end{cases}}$ 

Соответственно для SIMD-512:

$p^{{(0)}}(x)={\begin{cases}{x+1}{\pmod 8},&{\mbox{if }}x=0{\pmod 2}\\{x-1}{\pmod 8},&{\mbox{otherwise}}\end{cases}}$ 

В целом функция сжатия отрабатывает за 4 раунда, каждый из которых состоит из 8 шагов (step), плюс один дополнительный финальный раунд.

Финальная функция сжатияПравить

После того как все блоки сообщения были сжаты совершается еще один дополнительный вызов функции сжатия с размером сообщения в качестве входного параметра. При этом длина сообщения вычисляется в битах по модулю $2^{2^m}$$2^{{2^{m}}}$  если необходимо.

Для финальной функции сжатия используется немного измененный метод расширения сообщения:

для SIMD-256 вместо $O(M)=NT{T}_{128}(M+X^{127})$$O(M)=NTT_{{128}}(M+X^{{127}})$  используется $O(M)=NT{T}_{128}(M+X^{127}+X^{125})$$O(M)=NTT_{{128}}(M+X^{{127}}+X^{{125}})$ .

Соответственно, для SIMD-512 вместо $O(M)=NT{T}_{256}(M+X^{255})$$O(M)=NTT_{{256}}(M+X^{{255}})$  используется $O(M)=NT{T}_{256}(M+X^{255}+X^{253})$$O(M)=NTT_{{256}}(M+X^{{255}}+X^{{253}})$ 

Таким образом, диапазон расширенных сообщений для финального этапа отличается от диапазона расширенных сообщений блоков тела сообщения.

После применения финальной функции сжатия на выход подается следующее строковой представление:

$A_0,A_1,A_2,A_3,B_0,B_1,B_2,B_3$$A_{0},A_{1},A_{2},A_{3},B_{0},B_{1},B_{2},B_{3}$  для SIMD-256

$A_0,A_1,A_2,A_3,A_4,A_5,A_6,A_7,B_0,B_1,B_2,B_3,B_4,B_5,B_6,B_7$$A_{0},A_{1},A_{2},A_{3},A_{4},A_{5},A_{6},A_{7},B_{0},B_{1},B_{2},B_{3},B_{4},B_{5},B_{6},B_{7}$  для SIMD-512

В случай SIMD-n на выход подаются первые n бит SIMD-256 (n < 256) или SIMD 512 (256 < n < 512). Например, для SIMD-384 на выходе будет $A_0,A_1,A_2,A_3,A_4,A_5,A_6,A_7,B_0,B_1,B_2,B_3$$A_{0},A_{1},A_{2},A_{3},A_{4},A_{5},A_{6},A_{7},B_{0},B_{1},B_{2},B_{3}$ 

Вектор инициализацииПравить

Каждая хеш-функция семейства SIMD использует собственный вектор инициализации IV, чтобы избежать связей между выходными результатами различных функций SIMD-n. IV для функции SIMD-n определяется следующим образом:

IV = SIMD-Compress(0, "SIMD-(i)" v1.0, 0), где строка записана в ASCII и дополнена нулями, а (i) - десятичное представление n.

Значения IV для различных хеш-функций семейства SIMD:

${\begin{array}{|ccccc|}\hline &&SIMD-224IV&&\\\hline A_{{0..3}}&0xeebfea74&0x70c30346&0x4b538718&0x4f06a655\\B_{{0..3}}&0xa22aad99&0x434a528c&0x355e2a29&0x8523b76e\\C_{{0..3}}&0x20bcf05e&0x9eb5b91a&0x4ddc22e8&0xce0ae099\\D_{{0..3}}&0x9d4dda03&0xae00fc41&0x40279fc8&0x9f0ec1f5\\\hline \end{array}}{\begin{array}{|ccccc|}\hline &&SIMD-256IV&&\\\hline A_{{0..3}}&0x99dae06a&0xc3d43239&0x4979de73&0x3ee5d052\\B_{{0..3}}&0xda4d98d0&0xcf5c52be&0x655cbaf9&0x2a9d238e\\C_{{0..3}}&0xfd892a60&0x8a471f8c&0x86ce033f&0x0ff768d3\\D_{{0..3}}&0xfad01f14&0x9eeef3b3&0x68aec37a&0x6b209d72\\\hline \end{array}}$ 

${\begin{array}{|ccccc|}\hline &&SIMD-384IV&&\\\hline A_{{0..3}}&0x3a8f3d6f&0x756a1087&0x5d5318aa&0xbbca76f7\\A_{{4..7}}&0x26a3a959&0xaca1e37e&0xb40c4642&0x904085d9\\B_{{0..3}}&0xf46f6c9b&0x9ab248ef&0xdbbfc9cc&0xcc8821fa\\B_{{4..7}}&0x354d3c2e&0xda334fb1&0x68ed79ce&0xa5bc107d\\C_{{0..3}}&0x2da6fdc3&0xfbafce00&0x4c9a6954&0xb61f0faf\\C_{{4..7}}&0xf56099b5&0xa3a5bdfb&0xf83e0977&0x7eb15372\\D_{{0..3}}&0x91195b41&0xfcb9404e&0x214e6c84&0x88740b3a\\D_{{4..7}}&0xba03a4b1&0xa82202fc&0x994fddfb&0xb2e1a1de\\\hline \end{array}}{\begin{array}{|ccccc|}\hline &&SIMD-512IV&&\\\hline A_{{0..3}}&0xb314b806&0x676cf96e&0xed91a471&0x5f306791\\A_{{4..7}}&0x4ea515ee&0xde2a06cf&0xc9c96851&0x4f49a403\\B_{{0..3}}&0xf778d95b&0x6e5e21da&0xad570671&0x4584c064\\B_{{4..7}}&0xac201a0f&0xd4ce2a86&0xc6d663f4&0x8ec5d766\\C_{{0..3}}&0x14c1303a&0xb5b890d5&0x82e61e95&0x94f47683\\C_{{4..7}}&0x6ebc9ce7&0xf9af5b29&0xf4177798&0xf6cec3ee\\D_{{0..3}}&0xd10eca9e&0xea3c1b82&0x5061c319&0x0c2a9f5c\\D_{{4..7}}&0xfcfc980e&0xbab373c6&0x1699d7c9&0x0822d6af\\\hline \end{array}}$ 

Улучшения для второго раунда конкурса SHA-3Править

Изменениям подверглись 2 части алгоритма: перестановки (permutations) $p^{(i)}$$p^{{(i)}}$  и циклические сдвиги (rotations).

При выборе новых перестановок авторы хеш-функции руководствовались следующими критериями:

• Перестановки должны обеспечивать полное перемешивание после трех раундов (соотв. двух для SIMD-256)
• Необходимо использовать нечетное число перестановок
• Результат композиции любых двух перестановок не должен быть фиксированным
• Результат четырех последовательных перестановок не должен давать исходный результат

SIMD-256. Исходные перестановки:

$p^{{(i)}}(x)={\begin{cases}{x+1}{\pmod 4},&{\mbox{if }}i{\mbox{ is even}}\\{x+2}{\pmod 4},&{\mbox{if }}i{\mbox{ is odd}}\end{cases}}$ 

Новые перестановки:

$\{\begin{array}{l}{p}^{(0)}(j)=j\otimes <!--\; \otimes \; -->1\\ p^{(1)}(j)=j\otimes <!--\; \otimes \; -->2\\ p^{(2)}(j)=j\otimes <!--\; \otimes \; -->3\end{array}$${\begin{cases}p^{{(0)}}(j)=j\otimes 1\\p^{{(1)}}(j)=j\otimes 2\\p^{{(2)}}(j)=j\otimes 3\end{cases}}$ 

где $p^{(i)}=p^{i\mathrm{mod}3}$$p^{{(i)}}=p^{{i\mod 3}}$ . Таким образом, количество перестановок увеличилось с 2 до 3.

SIMD-512. Исходные перестановки:

$p^{{(0)}}(x)={\begin{cases}{x+1}{\pmod 8},&{\mbox{if }}x=0{\pmod 2}\\{x-1}{\pmod 8},&{\mbox{otherwise}}\end{cases}}$ 

Новые перестановки:

$\{\begin{array}{l}{p}^{(0)}(j)=j\otimes <!--\; \otimes \; -->1\\ p^{(1)}(j)=j\otimes <!--\; \otimes \; -->6\\ p^{(2)}(j)=j\otimes <!--\; \otimes \; -->2\\ p^{(3)}(j)=j\otimes <!--\; \otimes \; -->3\\ p^{(4)}(j)=j\otimes <!--\; \otimes \; -->5\\ p^{(5)}(j)=j\otimes <!--\; \otimes \; -->7\\ p^{(6)}(j)=j\otimes <!--\; \otimes \; -->4\end{array}$${\begin{cases}p^{{(0)}}(j)=j\otimes 1\\p^{{(1)}}(j)=j\otimes 6\\p^{{(2)}}(j)=j\otimes 2\\p^{{(3)}}(j)=j\otimes 3\\p^{{(4)}}(j)=j\otimes 5\\p^{{(5)}}(j)=j\otimes 7\\p^{{(6)}}(j)=j\otimes 4\end{cases}}$ 

где $p^{(i)}=p^{i\mathrm{mod}7}$$p^{{(i)}}=p^{{i\mod 7}}$ . Таким образом, количество перестановок увеличилось с 4 до 7.

Псевдокод SIMDПравить

1:  function MessageExpansion(M, f)   		        //f помечает финальную функцию сжатия
2:      if f = 0 then
3:          y(i) = NTT(M + X127) 			//соответственно X255 для SIMD-512
4:      else
5:          y(i) = NTT(M + X127 + X125)  		//соответственно X255 + X253 для SIMD-512
6:      end if
7:      Вычислить Z(i,j) применяя внутренние коды I(185) и I(233) к y(i).
8:      Вычислить W(i,j) применяя перестановки для Z(i,j)
9:      Вернуть W(i,j)
10: end function
11:
12: function Round(S, i, r)
13:     S = Step(S; W(8i+0); IF; r0; r1)
14:     S = Step(S; (W8i+1); IF; r1; r2)
15:     S = Step(S; W(8i+2); IF; r2; r3)
16:     S = Step(S; W(8i+3); IF; r3; r0)
17:     S = Step(S; W(8i+4);MAJ; r0; r1)
18:     S = Step(S; W(8i+5);MAJ; r1; r2)
19:     S = Step(S; W(8i+6);MAJ; r2; r3)
20:     S = Step(S; W(8i+7);MAJ; r3; r0)
21:     return S
22: end function
23:
24: function SIMD-Compress(IV, M, f)
25:     W = MessageExpansion(M; f)
26:     S = IV xor M
27:     S = Round(S; 0; [3; 20; 14; 27])
28:     S = Round(S; 1; [26; 4; 23; 11])
29:     S = Round(S; 2; [19; 28; 7; 22])
30:     S = Round(S; 3; [15; 5; 29; 9])
31:     S = Step(S; IV(0); IF; 15; 5)
32:     S = Step(S; IV(1); IF; 5; 29)
33:     S = Step(S; IV(2); IF; 29; 9)
34:     S = Step(S; IV(3); IF; 9; 15)
35:     return S
36: end function
37:
38: function SIMD(M)
39:     Разделить сообщение M на части M(i); 0 =< i < k.
40:     M(k-1) дополняется нулями.
41:     S  = IV
42:     for 0 =< i < k do
43:         S = SIMD-Compress(S; M(i); 0)
44:     end for
45:     S = SIMD-Compress(S; ||M||; 1)
46:     return Truncate(S)
47: end function

Примеры результатовПравить

Сообщение M	SIMD-256(M)
Пустое сообщение	8029e81e7320e13ed9001dc3d8021fec695b7a25cd43ad805260181c35fcaea8
0x00; 0x01; 0x02; … 0x3f	5bebdb816cd3e6c8c2b5a42867a6f41570c4b917f1d3b15aabc17f24679e6acd

Сообщение M	SIMD-512(M)
Пустое сообщение	51a5af7e243cd9a5989f7792c880c4c3168c3d60c4518725fe5757d1f7a69c63 66977eaba7905ce2da5d7cfd07773725f0935b55f3efb954996689a49b6d29e0
0x00; 0x01; 0x02; … 0x3f	8851ad0a57426b4af57af3294706c0448fa6accf24683fc239871be58ca913fb ee53e35c1dedd88016ebd131f2eb0761e97a3048de6e696787fd5f54981d6f2c

БыстродействиеПравить

Независимые тесты производительности алгоритма SIMD, проведенные с помощью бенчмарка eBASH, показали следующие результаты (скорость указана в циклах на байт (cpb)):

Процессор	Core i5	Core 2 (45 nm)	Core 2 (65 nm)
SIMD-256	7.51 cpb	9.18 cpb	11.34 cpb
SIMD-512	8.63 cpb	10.02 cpb	12.05 cpb

При этом около половины времени работы хеш-функции уходит на операцию расширения сообщения: Number-Theoretic Transform (NTT) является самой дорогостоящей в плане производительности частью алгоритма.

Функция сжатия SIMD обладает частично параллельной архитектурой, что позволяет создавать эффективные реализации алгоритма с использованием векторных инструкций (SIMD). Данные инструкции доступны на многих широко-известных архитектурах: SSE на x86, AltiVec на PowerPC, IwMMXt на ARM.

Что касается требований, предъявляемых к RAM, хеш-функции SIMD необходима память для хранения внутреннего состояния (64 байта для SIMD-256 и 128 байт для SIMD-512) и память для выходных значений NTT (4*64 = 256 байт для SIMD-256 и 4*128 = 512 байт для SIMD-512).

Результаты конкурса SHA-3 для SIMDПравить

Хеш-функция SIMD не была отобрана в качестве финалиста конкурса SHA-3.

Эксперты конкурса отметили, что, хотя хеш-функция SIMD во многом повторяет алгоритмы семейств MD/SHA, но улучшения, сделанные авторами, действительно позволили защитить SIMD от многих типов атак (например, коллизионная атака). Кроме того, изменения, проведённые для второго раунда, смогли защитить хеш-функцию SIMD от атаки на основе дифференциального криптоанализа, проведённую Mendel и Nad, которой была подвержена SIMD в своей изначальной реализации.

Однако, высокие требования к RAM и наличию SIMD инструкций для хорошей производительности делают хеш-функцию плохим кандидатом для реализации на FPGA. Главным образом по этой причине хеш-функция SIMD не попала в финальную стадию конкурса.

ЛитератураПравить

• The SIMD Hash Function official website (англ.). Дата обращения: 18 декабря 2013. Архивировано из оригинала 2 декабря 2013 года.
• SHA-3 competition(2007-2012) (англ.). Дата обращения: 18 декабря 2013. Архивировано 19 декабря 2013 года.
• SHA-3 second round candidates (англ.). Дата обращения: 18 декабря 2013. Архивировано 10 апреля 2012 года.
• eBASH: Encrypt benchmark official site (англ.). Дата обращения: 18 декабря 2013. Архивировано из оригинала 4 декабря 2013 года.
• Meltem Sönmez Turan, Ray Perlner. Status Report on the Second Round of the SHA-3 Cryptographic Hash Algorithm Competition (англ.).
• Gaëtan Leurent. SHA-3 submission SIMD Is a Message Digest (англ.). Архивировано 12 июня 2011 года.
• Gaëtan Leurent. SIMD Is a Message Digest: Presentation (англ.). Архивировано 12 июня 2011 года.
• Gaetan Leurent. Tweaking SIMD (англ.). Архивировано 12 июня 2011 года.
• Charles Bouillaguet, Pierre-Alain Fouque, Gaëtan Leurent. Security Analysis of SIMD (англ.).
• Hongbo Yu and Xiaoyun Wang. Cryptanalysis of the Compression Function of SIMD (англ.).