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 является функция сжатия . Чтобы вычислить h(M), сообщение M разбивается на k частей по m бит. Затем к частям сообщения итеративно применяется функция сжатия: . Начальное состояние или обозначается и является фиксированным для каждой функции семейства SIMD. Окончательный результат работы хеш-функции получается применением финализирующей функции (finalization function) к .
Функция сжатия C в режиме Дэвиса-Мейера обычно строится с использованием функции блочного шифрования : , однако для хеш-функции SIMD используются несколько улучшений.
Семейство хеш-функций SIMD использует следующие параметры: Размер хеша, n Размер блока сообщения, m Размер внутреннего состояния(), p SIMD-256 256 512 512 SIMD-512 512 1024 1024 Внутреннее состояние представлено матрицей 32-битных слов размером 4×4 для SIMD-256 и 8×4 для SIMD-512.
Функция сжатия Функция сжатия SIMD построена на основе конструкции Дэвиса-Мейера с некоторыми изменениями.
Во-первых, вместо функции сжатия используется функция .
Во-вторых, вместо операции XOR для и в SIMD применяются несколько дополнительных раундов Фейстеля с h в качестве входного ключа. Это действие выполняет функция .
Таким образом, функция сжатия определена как . Как утверждают авторы хеш-функции SIMD, эти модификации обеспечивают такой же уровень безопасности, как и оригинальная конструкция Дэвиса-Мейера, но в то же время предотвращают некоторые виды атак множественных блоков (multi-block attacks).
Расширение сообщения Расширение сообщения (message expansion) хеш-функции SIMD-256 (соотв. SIMD-512) преобразует блок сообщения в 512 бит (соотв. 1024 бита) в расширенное сообщение размером 4096 бит (соотв. 8192 бит) с минимальным расстоянием в 520 (соотв. 1032).
Использование сети Фейстеля Использование структуры Фейстеля хеш-функцией SIMD построено аналогично семейству хеш-функций MD/SHA:
или в более удобном формате:
для SIMD-256
для SIMD-512
где - логическая функция, - сложение по модулю и - циклический сдвиг влево на бит.
Используются 4 параллельные ячейки Фейстеля для SIMD-256 (соотв. 8 для SIMD-512), которые взаимодействуют между собой из-за перестановок . Перестановки выбираются таким образом, чтобы обеспечить хорошее перемешивание.
Для SIMD-256 определено:
Соответственно для SIMD-512:
В целом функция сжатия отрабатывает за 4 раунда, каждый из которых состоит из 8 шагов (step), плюс один дополнительный финальный раунд.
Финальная функция сжатия После того как все блоки сообщения были сжаты совершается еще один дополнительный вызов функции сжатия с размером сообщения в качестве входного параметра. При этом длина сообщения вычисляется в битах по модулю если необходимо.
Для финальной функции сжатия используется немного измененный метод расширения сообщения:
для SIMD-256 вместо используется .
Соответственно, для SIMD-512 вместо используется
Таким образом, диапазон расширенных сообщений для финального этапа отличается от диапазона расширенных сообщений блоков тела сообщения.
После применения финальной функции сжатия на выход подается следующее строковой представление:
для SIMD-256
для SIMD-512
В случай SIMD-n на выход подаются первые n бит SIMD-256 (n < 256) или SIMD 512 (256 < n < 512). Например, для SIMD-384 на выходе будет
Вектор инициализации Каждая хеш-функция семейства SIMD использует собственный вектор инициализации IV, чтобы избежать связей между выходными результатами различных функций SIMD-n. IV для функции SIMD-n определяется следующим образом:
IV = SIMD-Compress(0, "SIMD-(i)" v1.0, 0), где строка записана в ASCII и дополнена нулями, а (i) - десятичное представление n.
Значения IV для различных хеш-функций семейства SIMD:
Улучшения для второго раунда конкурса SHA-3 Изменениям подверглись 2 части алгоритма: перестановки (permutations) и циклические сдвиги (rotations).
При выборе новых перестановок авторы хеш-функции руководствовались следующими критериями:
Перестановки должны обеспечивать полное перемешивание после трех раундов (соотв. двух для SIMD-256) Необходимо использовать нечетное число перестановок Результат композиции любых двух перестановок не должен быть фиксированным Результат четырех последовательных перестановок не должен давать исходный результат
SIMD-256. Исходные перестановки:
Новые перестановки:
где . Таким образом, количество перестановок увеличилось с 2 до 3.
SIMD-512. Исходные перестановки:
Новые перестановки:
где . Таким образом, количество перестановок увеличилось с 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Реализация на FPGA кандидатов конкурса SHA-3.. Главным образом по этой причине хеш-функция SIMD не попала в финальную стадию конкурса.
Примечания
Литература
Категория:Криптографические хеш-функции Категория:NIST hash function competition