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 является функция сжатия . Чтобы вычислить 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). Главным образом по этой причине хеш-функция SIMD не попала в финальную стадию конкурса.
Примечания
- Кандидаты второго раунда конкурса SHA-3.
- Официальное описание хеш-функции SIMD, с. 9.
- Официальный сайт хеш-функции SIMD.
- Официальное описание хеш-функции SIMD, с. 7—8.
- Улучшения хеш-функции SIMD для второго раунда конкурса SHA-3, с. 1—2.
- Официальное описание хеш-функции SIMD, с. 22.
- Официальное описание хеш-функции SIMD, с. 43—270.
- Официальный сайт eBASH benchmark.
- Отчёт с результатах второго раунда конкурса SHA-3.
- Реализация на FPGA кандидатов конкурса SHA-3.
Литература
- (англ.). Дата обращения: 18 декабря 2013. Архивировано из оригинала 2 декабря 2013 года.
- SHA-3 competition(2007-2012) (англ.). Дата обращения: 18 декабря 2013. 19 декабря 2013 года.
- SHA-3 second round candidates (англ.). Дата обращения: 18 декабря 2013. Архивировано 10 апреля 2012 года.
- (англ.). Дата обращения: 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 (англ.).
Википедия, чтение, книга, библиотека, поиск, нажмите, истории, книги, статьи, wikipedia, учить, информация, история, скачать, скачать бесплатно, mp3, видео, mp4, 3gp, jpg, jpeg, gif, png, картинка, музыка, песня, фильм, игра, игры, мобильный, телефон, Android, iOS, apple, мобильный телефон, Samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Сеть, компьютер