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


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

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

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

Алгоритм

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

Главной частью хеш-функции h является функция сжатия C : { 0 , 1 } p × { 0 , 1 } m → { 0 , 1 } p {displaystyle Ccolon {0,1}^{p} imes {0,1}^{m} o {0,1}^{p}} . Чтобы вычислить h(M), сообщение M разбивается на k частей M i {displaystyle M_{i}} по m бит. Затем к частям сообщения итеративно применяется функция сжатия: H i + 1 = C ( H i , M i ) {displaystyle H_{i+1}=C(H_{i},M_{i})} . Начальное состояние H 0 {displaystyle H_{0}} или вектор инициализации обозначается I V {displaystyle IV} и является фиксированным для каждой функции семейства SIMD. Окончательный результат работы хеш-функции получается применением финализирующей функции (finalization function) D : { 0 , 1 } p → { 0 , 1 } n {displaystyle Dcolon {0,1}^{p} o {0,1}^{n}} к H k − 1 {displaystyle H_{k-1}} .

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

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

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


S 256 = [ 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 ] ; S 512 = [ 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 ] {displaystyle S_{256}={egin{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}={egin{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 ) ⊗ h {displaystyle C(h,m)=E_{m}(h)otimes h} используется функция C ( h , m ) = E m ( h ⊗ m ) ⊗ h {displaystyle C(h,m)=E_{m}(hotimes m)otimes h} .

Во-вторых, вместо операции XOR для E m ( h ⊗ m ) {displaystyle E_{m}(hotimes m)} и h {displaystyle h} в SIMD применяются несколько дополнительных раундов Фейстеля с h в качестве входного ключа. Это действие выполняет функция P : { 0 , 1 } p × { 0 , 1 } p → { 0 , 1 } p {displaystyle Pcolon {0,1}^{p} imes {0,1}^{p} o {0,1}^{p}} .

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

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

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

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

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

A j ( i ) = ( D j ( i − 1 ) ⊞ W j ( i ) ⊞ ϕ i ( A j ( i − 1 ) , B j ( i − 1 ) , C j ( i − 1 ) ) ) ⋘ s i ⊞ A p i ( j ) ( i − 1 ) ⋘ r i {displaystyle A_{j}^{(i)}=left(D_{j}^{(i-1)}oxplus W_{j}^{(i)}oxplus phi _{i}(A_{j}^{(i-1)},B_{j}^{(i-1)},C_{j}^{(i-1)}) ight)^{lll s_{i}}oxplus A_{p_{i}(j)}^{(i-1)^{lll r_{i}}}}

B j ( i ) = A j ( i − 1 ) ⋘ r i {displaystyle B_{j}^{(i)}=A_{j}^{(i-1)^{lll r_{i}}}}

C j ( i ) = B j ( i − 1 ) {displaystyle C_{j}^{(i)}=B_{j}^{(i-1)}}

D j ( i ) = C j ( i − 1 ) {displaystyle D_{j}^{(i)}=C_{j}^{(i-1)}}

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

S t e p ( [ 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 ] , [ W 0 W 1 W 2 W 3 ] , ϕ , r , s , p ) = [ ( D 0 ⊞ W 0 ⊞ ϕ i ( A 0 , B 0 , C 0 ) ) ⋘ s ⊞ A p ( 0 ) ⋘ r A 0 ⋘ r B 0 C 0 ( D 1 ⊞ W 1 ⊞ ϕ i ( A 1 , B 1 , C 1 ) ) ⋘ s ⊞ A p ( 1 ) ⋘ r A 1 ⋘ r B 1 C 1 ( D 2 ⊞ W 2 ⊞ ϕ i ( A 2 , B 2 , C 2 ) ) ⋘ s ⊞ A p ( 2 ) ⋘ r A 2 ⋘ r B 2 C 2 ( D 3 ⊞ W 3 ⊞ ϕ i ( A 3 , B 3 , C 3 ) ) ⋘ s ⊞ A p ( 3 ) ⋘ r A 3 ⋘ r B 3 c 3 ] {displaystyle Stepleft({egin{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}},{egin{bmatrix}W_{0}W_{1}W_{2}W_{3}end{bmatrix}},phi ,r,s,p ight)={egin{bmatrix}left(D_{0}oxplus W_{0}oxplus phi _{i}(A_{0},B_{0},C_{0}) ight)^{lll s}oxplus A_{p(0)}^{lll r}&A_{0}^{lll r}&B_{0}&C_{0}left(D_{1}oxplus W_{1}oxplus phi _{i}(A_{1},B_{1},C_{1}) ight)^{lll s}oxplus A_{p(1)}^{lll r}&A_{1}^{lll r}&B_{1}&C_{1}left(D_{2}oxplus W_{2}oxplus phi _{i}(A_{2},B_{2},C_{2}) ight)^{lll s}oxplus A_{p(2)}^{lll r}&A_{2}^{lll r}&B_{2}&C_{2}left(D_{3}oxplus W_{3}oxplus phi _{i}(A_{3},B_{3},C_{3}) ight)^{lll s}oxplus A_{p(3)}^{lll r}&A_{3}^{lll r}&B_{3}&c_{3}end{bmatrix}}} для SIMD-256

S t e p ( [ 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 ] , [ W 0 W 1 W 2 W 3 W 4 W 5 W 6 W 7 ] , ϕ , r , s , p ) = [ ( D 0 ⊞ W 0 ⊞ ϕ i ( A 0 , B 0 , C 0 ) ) ⋘ s ⊞ A p ( 0 ) ⋘ r A 0 ⋘ r B 0 C 0 ( D 1 ⊞ W 1 ⊞ ϕ i ( A 1 , B 1 , C 1 ) ) ⋘ s ⊞ A p ( 1 ) ⋘ r A 1 ⋘ r B 1 C 1 ( D 2 ⊞ W 2 ⊞ ϕ i ( A 2 , B 2 , C 2 ) ) ⋘ s ⊞ A p ( 2 ) ⋘ r A 2 ⋘ r B 2 C 2 ( D 3 ⊞ W 3 ⊞ ϕ i ( A 3 , B 3 , C 3 ) ) ⋘ s ⊞ A p ( 3 ) ⋘ r A 3 ⋘ r B 3 c 3 ( D 4 ⊞ W 4 ⊞ ϕ i ( A 4 , B 4 , C 4 ) ) ⋘ s ⊞ A p ( 4 ) ⋘ r A 4 ⋘ r B 4 C 4 ( D 5 ⊞ W 5 ⊞ ϕ i ( A 5 , B 5 , C 5 ) ) ⋘ s ⊞ A p ( 5 ) ⋘ r A 5 ⋘ r B 5 C 5 ( D 6 ⊞ W 6 ⊞ ϕ i ( A 6 , B 6 , C 6 ) ) ⋘ s ⊞ A p ( 6 ) ⋘ r A 6 ⋘ r B 6 C 6 ( D 7 ⊞ W 7 ⊞ ϕ i ( A 7 , B 7 , C 7 ) ) ⋘ s ⊞ A p ( 7 ) ⋘ r A 7 ⋘ r B 7 c 7 ] {displaystyle Stepleft({egin{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}},{egin{bmatrix}W_{0}W_{1}W_{2}W_{3}W_{4}W_{5}W_{6}W_{7}end{bmatrix}},phi ,r,s,p ight)={egin{bmatrix}left(D_{0}oxplus W_{0}oxplus phi _{i}(A_{0},B_{0},C_{0}) ight)^{lll s}oxplus A_{p(0)}^{lll r}&A_{0}^{lll r}&B_{0}&C_{0}left(D_{1}oxplus W_{1}oxplus phi _{i}(A_{1},B_{1},C_{1}) ight)^{lll s}oxplus A_{p(1)}^{lll r}&A_{1}^{lll r}&B_{1}&C_{1}left(D_{2}oxplus W_{2}oxplus phi _{i}(A_{2},B_{2},C_{2}) ight)^{lll s}oxplus A_{p(2)}^{lll r}&A_{2}^{lll r}&B_{2}&C_{2}left(D_{3}oxplus W_{3}oxplus phi _{i}(A_{3},B_{3},C_{3}) ight)^{lll s}oxplus A_{p(3)}^{lll r}&A_{3}^{lll r}&B_{3}&c_{3}left(D_{4}oxplus W_{4}oxplus phi _{i}(A_{4},B_{4},C_{4}) ight)^{lll s}oxplus A_{p(4)}^{lll r}&A_{4}^{lll r}&B_{4}&C_{4}left(D_{5}oxplus W_{5}oxplus phi _{i}(A_{5},B_{5},C_{5}) ight)^{lll s}oxplus A_{p(5)}^{lll r}&A_{5}^{lll r}&B_{5}&C_{5}left(D_{6}oxplus W_{6}oxplus phi _{i}(A_{6},B_{6},C_{6}) ight)^{lll s}oxplus A_{p(6)}^{lll r}&A_{6}^{lll r}&B_{6}&C_{6}left(D_{7}oxplus W_{7}oxplus phi _{i}(A_{7},B_{7},C_{7}) ight)^{lll s}oxplus A_{p(7)}^{lll r}&A_{7}^{lll r}&B_{7}&c_{7}end{bmatrix}}} для SIMD-512

где ϕ i {displaystyle phi _{i}} - логическая функция, ⊞ {displaystyle oxplus } - сложение по модулю 2 32 {displaystyle 2^{32}} и ⋘ s i {displaystyle lll s_{i}} - циклический сдвиг влево на s i {displaystyle s_{i}} бит.

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

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

p ( i ) ( x ) = { x + 1 ( mod 4 ) , if  i  is even x + 2 ( mod 4 ) , if  i  is odd {displaystyle p^{(i)}(x)={egin{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 ) = { x + 1 ( mod 8 ) , if  x = 0 ( mod 2 ) x − 1 ( mod 8 ) , otherwise {displaystyle p^{(0)}(x)={egin{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 {displaystyle 2^{2^{m}}} если необходимо.

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

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

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

S I M D − 224 I V A 0..3 0 x e e b f e a 74 0 x 70 c 30346 0 x 4 b 538718 0 x 4 f 06 a 655 B 0..3 0 x a 22 a a d 99 0 x 434 a 528 c 0 x 355 e 2 a 29 0 x 8523 b 76 e C 0..3 0 x 20 b c f 05 e 0 x 9 e b 5 b 91 a 0 x 4 d d c 22 e 8 0 x c e 0 a e 099 D 0..3 0 x 9 d 4 d d a 03 0 x a e 00 f c 41 0 x 40279 f c 8 0 x 9 f 0 e c 1 f 5 S I M D − 256 I V A 0..3 0 x 99 d a e 06 a 0 x c 3 d 43239 0 x 4979 d e 73 0 x 3 e e 5 d 052 B 0..3 0 x d a 4 d 98 d 0 0 x c f 5 c 52 b e 0 x 655 c b a f 9 0 x 2 a 9 d 238 e C 0..3 0 x f d 892 a 60 0 x 8 a 471 f 8 c 0 x 86 c e 033 f 0 x 0 f f 768 d 3 D 0..3 0 x f a d 01 f 14 0 x 9 e e e f 3 b 3 0 x 68 a e c 37 a 0 x 6 b 209 d 72 {displaystyle {egin{array}{|c c c c c|}hline &&SIMD-224IV&&hline A_{0..3}&0xeebfea74&0x70c30346&0x4b538718&0x4f06a655B_{0..3}&0xa22aad99&0x434a528c&0x355e2a29&0x8523b76eC_{0..3}&0x20bcf05e&0x9eb5b91a&0x4ddc22e8&0xce0ae099D_{0..3}&0x9d4dda03&0xae00fc41&0x40279fc8&0x9f0ec1f5hline end{array}}{egin{array}{|c c c c c|}hline &&SIMD-256IV&&hline A_{0..3}&0x99dae06a&0xc3d43239&0x4979de73&0x3ee5d052B_{0..3}&0xda4d98d0&0xcf5c52be&0x655cbaf9&0x2a9d238eC_{0..3}&0xfd892a60&0x8a471f8c&0x86ce033f&0x0ff768d3D_{0..3}&0xfad01f14&0x9eeef3b3&0x68aec37a&0x6b209d72hline end{array}}}

S I M D − 384 I V A 0..3 0 x 3 a 8 f 3 d 6 f 0 x 756 a 1087 0 x 5 d 5318 a a 0 x b b c a 76 f 7 A 4..7 0 x 26 a 3 a 959 0 x a c a 1 e 37 e 0 x b 40 c 4642 0 x 904085 d 9 B 0..3 0 x f 46 f 6 c 9 b 0 x 9 a b 248 e f 0 x d b b f c 9 c c 0 x c c 8821 f a B 4..7 0 x 354 d 3 c 2 e 0 x d a 334 f b 1 0 x 68 e d 79 c e 0 x a 5 b c 107 d C 0..3 0 x 2 d a 6 f d c 3 0 x f b a f c e 00 0 x 4 c 9 a 6954 0 x b 61 f 0 f a f C 4..7 0 x f 56099 b 5 0 x a 3 a 5 b d f b 0 x f 83 e 0977 0 x 7 e b 15372 D 0..3 0 x 91195 b 41 0 x f c b 9404 e 0 x 214 e 6 c 84 0 x 88740 b 3 a D 4..7 0 x b a 03 a 4 b 1 0 x a 82202 f c 0 x 994 f d d f b 0 x b 2 e 1 a 1 d e S I M D − 512 I V A 0..3 0 x b 314 b 806 0 x 676 c f 96 e 0 x e d 91 a 471 0 x 5 f 306791 A 4..7 0 x 4 e a 515 e e 0 x d e 2 a 06 c f 0 x c 9 c 96851 0 x 4 f 49 a 403 B 0..3 0 x f 778 d 95 b 0 x 6 e 5 e 21 d a 0 x a d 570671 0 x 4584 c 064 B 4..7 0 x a c 201 a 0 f 0 x d 4 c e 2 a 86 0 x c 6 d 663 f 4 0 x 8 e c 5 d 766 C 0..3 0 x 14 c 1303 a 0 x b 5 b 890 d 5 0 x 82 e 61 e 95 0 x 94 f 47683 C 4..7 0 x 6 e b c 9 c e 7 0 x f 9 a f 5 b 29 0 x f 4177798 0 x f 6 c e c 3 e e D 0..3 0 x d 10 e c a 9 e 0 x e a 3 c 1 b 82 0 x 5061 c 319 0 x 0 c 2 a 9 f 5 c D 4..7 0 x f c f c 980 e 0 x b a b 373 c 6 0 x 1699 d 7 c 9 0 x 0822 d 6 a f {displaystyle {egin{array}{|c c c c c|}hline &&SIMD-384IV&&hline A_{0..3}&0x3a8f3d6f&0x756a1087&0x5d5318aa&0xbbca76f7A_{4..7}&0x26a3a959&0xaca1e37e&0xb40c4642&0x904085d9B_{0..3}&0xf46f6c9b&0x9ab248ef&0xdbbfc9cc&0xcc8821faB_{4..7}&0x354d3c2e&0xda334fb1&0x68ed79ce&0xa5bc107dC_{0..3}&0x2da6fdc3&0xfbafce00&0x4c9a6954&0xb61f0fafC_{4..7}&0xf56099b5&0xa3a5bdfb&0xf83e0977&0x7eb15372D_{0..3}&0x91195b41&0xfcb9404e&0x214e6c84&0x88740b3aD_{4..7}&0xba03a4b1&0xa82202fc&0x994fddfb&0xb2e1a1dehline end{array}}{egin{array}{|c c c c c|}hline &&SIMD-512IV&&hline A_{0..3}&0xb314b806&0x676cf96e&0xed91a471&0x5f306791A_{4..7}&0x4ea515ee&0xde2a06cf&0xc9c96851&0x4f49a403B_{0..3}&0xf778d95b&0x6e5e21da&0xad570671&0x4584c064B_{4..7}&0xac201a0f&0xd4ce2a86&0xc6d663f4&0x8ec5d766C_{0..3}&0x14c1303a&0xb5b890d5&0x82e61e95&0x94f47683C_{4..7}&0x6ebc9ce7&0xf9af5b29&0xf4177798&0xf6cec3eeD_{0..3}&0xd10eca9e&0xea3c1b82&0x5061c319&0x0c2a9f5cD_{4..7}&0xfcfc980e&0xbab373c6&0x1699d7c9&0x0822d6afhline end{array}}}

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

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

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

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


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

p ( i ) ( x ) = { x + 1 ( mod 4 ) , if  i  is even x + 2 ( mod 4 ) , if  i  is odd {displaystyle p^{(i)}(x)={egin{cases}{x+1}{pmod {4}},&{mbox{if }}i{mbox{ is even}}{x+2}{pmod {4}},&{mbox{if }}i{mbox{ is odd}}end{cases}}}

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

{ p ( 0 ) ( j ) = j ⊗ 1 p ( 1 ) ( j ) = j ⊗ 2 p ( 2 ) ( j ) = j ⊗ 3 {displaystyle {egin{cases}p^{(0)}(j)=jotimes 1p^{(1)}(j)=jotimes 2p^{(2)}(j)=jotimes 3end{cases}}}

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


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

p ( 0 ) ( x ) = { x + 1 ( mod 8 ) , if  x = 0 ( mod 2 ) x − 1 ( mod 8 ) , otherwise {displaystyle p^{(0)}(x)={egin{cases}{x+1}{pmod {8}},&{mbox{if }}x=0{pmod {2}}{x-1}{pmod {8}},&{mbox{otherwise}}end{cases}}}

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

{ p ( 0 ) ( j ) = j ⊗ 1 p ( 1 ) ( j ) = j ⊗ 6 p ( 2 ) ( j ) = j ⊗ 2 p ( 3 ) ( j ) = j ⊗ 3 p ( 4 ) ( j ) = j ⊗ 5 p ( 5 ) ( j ) = j ⊗ 7 p ( 6 ) ( j ) = j ⊗ 4 {displaystyle {egin{cases}p^{(0)}(j)=jotimes 1p^{(1)}(j)=jotimes 6p^{(2)}(j)=jotimes 2p^{(3)}(j)=jotimes 3p^{(4)}(j)=jotimes 5p^{(5)}(j)=jotimes 7p^{(6)}(j)=jotimes 4end{cases}}}

где p ( i ) = p i mod 7 {displaystyle p^{(i)}=p^{imod 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

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

Быстродействие

Независимые тесты производительности алгоритма SIMD, проведенные с помощью бенчмарка eBASH, показали следующие результаты (скорость указана в циклах на байт (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 не попала в финальную стадию конкурса.