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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Криптографическая
хэш-функция
Название

SIMD

Создан

2008

Опубликован

Октябрь 2008

Размер хэша

256 или 512 бит

Число раундов

4

Тип

хеш-функция

SIMD — итеративная криптографическая хеш-функция, разработанная Gaëtan Leurent, Charles Bouillaguet, Pierre-Alain Fouque. Была выдвинута как кандидат на конкурс стандарта SHA-3, проводимый Национальным институтом стандартов и технологий (США), где прошла во второй раунд[1]. Существуют два варианта хеш-функции: SIMD-256 и SIMD-512, преобразующие сообщение произвольной длины в 256 или 512-битное хеш-значение, называемое также дайджестом сообщения. Кроме того возможно определить хеш-функции SIMD-n как усечение функций SIMD-256 и SIMD-512 для n<256 и 256<n<512 соответственною[2]. Как утверждают создатели, главной особенностью хеш функции является значительное расширение сообщения, которое позволяет защититься от дифференциального криптоанализа[3].

Алгоритм[править | править вики-текст]

Общее описание и параметры[править | править вики-текст]

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

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

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

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

Внутреннее состояние представлено матрицей 32-х битных слов размером 4x4 для SIMD-256 и 8x4 для 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 h используется функция C(h,m) = E_m(h \otimes m) \otimes h.

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

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

Расширение сообщения[править | править вики-текст]

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

Использование сети Фейстеля[править | править вики-текст]

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

 
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)^{\lll r_i}}

 
C_j^{(i)} = B_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

где \phi_i - логическая функция, \boxplus - сложение по модулю 2^{32} и \lll s_i - циклический сдвиг влево на s_i бит.

Используются 4 параллельные ячейки Фейстеля для SIMD-256 (соотв. 8 для SIMD-512), которые взаимодействуют между собой из-за перестановок 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} если необходимо.

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

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

Соответственно, для SIMD-512 вместо O(M) = NTT_{256}(M + X^{255}) используется 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 для 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 для 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

Вектор инициализации[править | править вики-текст]

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

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

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


\begin{array}{|c c c c c|}
  \hline
  & & SIMD-224 IV & & \\
  \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}{|c c c c c|}
  \hline
  & & SIMD-256 IV & & \\
  \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}{|c c c c c|}
  \hline
  & & SIMD-384 IV & & \\
  \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}{|c c c c c|}
  \hline
  & & SIMD-512 IV & & \\
  \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)} и циклические сдвиги (rotations)[5].

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

  • Перестановки должны обеспечивать полное перемешивание после трех раундов (соотв. двух для 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{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 \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{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 \mod 7}. Таким образом, количество перестановок увеличилось с 4 до 7.

Псевдокод SIMD[6][править | править вики-текст]

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

Примеры результатов[7][править | править вики-текст]

Сообщение 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))[8][3]:

Процессор 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 от многих типов атак (например multi-collision attack). Кроме того, изменения, проведенные для второго раунда, смогли защитить хеш-функцию SIMD от атаки на основе дифференциального криптоанализа, проведенную Mendel и Nad, которой была подвержена SIMD в своей изначальной реализации[9].

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

Примечания[править | править вики-текст]

Литература[править | править вики-текст]