Lúffa (хеш-функция, произносится как «люффа») — криптографический алгоритм (семейство алгоритмов) хеширования переменной разрядности, разработанный Даи Ватанабэ (), Хисайоши Сато () из Hitachi Yokohama Research Laboratory и Кристофом Де Канньере () из исследовательской группы COSIC (:en:COSIC) Лёвенского католического университета для участия в конкурсе, Национального института стандартов и технологий США (NIST). Lúffa является вариантом функции губки, предложенной Гвидо Бертони () и соавторами, криптостойкость которой основана только на случайности основной перестановки. В отличие от оригинальной функции губки, Lúffa использует множественное число параллельных перестановок и функции инжекции сообщений.
История участия в конкурсе NIST SHA-3 9 декабря 2008 года Luffa в числе 51 кандидата прошла в первый раунд конкурса SHA-3. 25-28 февраля 2009 года хеш-функция была представлена на конференция NIST. 24 июля 2009 года был опубликован список из 14 кандидатов прошедших во второй раунд, в который вошла Luffa. 23-24 августа 2010 года состоялась конференция, на которой были рассмотрены кандидаты, прошедшие во второй раунд. 10 декабря 2010 года произошло объявление 5 кандидатов последнего тура конкурса SHA-3, Luffa выбыла из соревнования из-за низкой криптостойкости функции сжатия.
Алгоритм Lúffa
Обработка сообщения производится цепочкой раундовых функций смешивания с фиксированной входной и выходной длиной, которая представляет собой функцию губку. Цепочка состоит из блоков промежуточного смешивания C’ (раундовых функций) и блока завершения C’’. Раундовые функции образованы семейством нелинейных перестановок, так называемых шаговых функций. На вход функции первого раунда подается : первый блок сообщения и инициализирующие значения , где — количество перестановок. Входными параметрами -го раунда является : выход предыдущего раунда и -й блок сообщения .
Дополнение сообщения Дополнение сообщения длины до кратности 256 битам производится строкой , где число нулей определяется из уравнения
Инициализация Кроме первого блока сообщения на вход функции первого раунда в качестве инициализурующих значений подаются векторы .
i j 0 1 2 3 4 5 6 7 0 0x6d251e69 0x44b051e0 0x4eaa6fb4 0xdbf78465 0x6e292011 0x90152df4 0xee058139 0xdef610bb 1 0xc3b44b95 0xd9d2f256 0x70eee9a0 0xde099fa3 0x5d9b0557 0x8fc944b3 0xcf1ccf0e 0x746cd581 2 0xf7efc89d 0x5dba5781 0x04016ce5 0xad659c05 0x0306194f 0x666d1836 0x24aa230a 0x8b264ae7 3 0x858075d5 0x36d79cce 0xe571f7d7 0x204b1f67 0x35870c6a 0x57e9e923 0x14bcb808 0x7cde72ce 4 0x6c68e9be 0x5ec41e22 0xc825b7c7 0xaffb4363 0xf5df3999 0x0fc688f1 0xb07224cc 0x03e86cea
Раундовая функция
Раундовая функция является последовательным применением функции инжекции сообщения MI и перестановочной функции P.
Функции инжекции сообщения Функция инжекции сообщения может быть представлена в виде матрицы преобразования над кольцом . Порождающий полином поля .
Функции инжекции сообщения
где числа соответственно обозначают полиномы
Функции инжекции сообщения
Функции инжекции сообщения
Функция перестановки Нелинейная функция перестановки имеет битовый вход, длина суб-перестановки — фиксирована в спецификации Lúffa, ; количество — перестановок зависит от размера хеша и приведено в таблице.
Длина хеша Количество перестановок 224 3 256 3 384 4 512 5
Функция перестановки является восьмикратным повторением шаговой функции над блоком , полученным из функции инжекции сообщения . Блок представляется в виде 8 32-битных слов: . Шаговая функция состоит из 3 функций: SubCrumb, MixWord, AddConstant. Permute(a, j){ //Permutation Q_j for (r = 0; r < 8; r++){ SubCrumb(a,a,a,a); SubCrumb(a,a,a,a); for (k = 0; k < 4; k++) MixWord(a[k],a[k+4]); AddConstant(a, j, r);
SubCrumb SubCrumb — функция замены l-х битов в или по S-блоку , результатом выполнения является замена , индекс S-блока получается в результате конкатенации соответствующих битов : , биты заменяются на соответствующие биты из по следующей схеме:
MixWord MixWord — линейная функция перестановки, на вход принимает и , ; выходом являются и , полученные по алгоритму:
, (<<< 2 — циклический сдвиг влево на 2 бита)
AddConstant AddConstant — функция добавления константы к
Таблица констант приведена в дополнении B к спецификации Lúffa.
Блок завершения
Завершающий этап формирования дайджеста сообщения состоит из последовательных итераций функции выхода и раундовой функции с нулевым блоком сообщения 0x000 на входе. Функция выхода представляет собой XOR всех промежуточных значений, а в качестве результата представляет 256-битное слово . На i-й итерации значение выходной функции определяется как
, где , если , иначе
Через обозначим 32-битные слова в , тогда выходом Lúffa являются составленные последовательно . Символ "||" обозначает конкатенацию.
Длина хеша Значение хеша 224 256 384 512
Хеш Lúffa-224 фактически представляет собой хеш Lúffa-256 без последнего 32-битного слова.
Тестовые векторы Дайджесты сообщения «abc» при различном размере хеша.
224 256 384 512 Z0,0 0xf29311b8 0xf29311b8 0x9a7abb79 0xf4024597 Z0,1 0x7e9e40de 0x7e9e40de 0x7a840e2d 0x3e80d79d Z0,2 0x7699be23 0x7699be23 0x423c34c9 0x0f4b9b20 Z0,3 0xfbeb5a47 0xfbeb5a47 0x1f559f68 0x2ddd4505 Z0,4 0xcb16ea4f 0xcb16ea4f 0x09bdb291 0xb81b8830 Z0,5 0x5556d47c 0x5556d47c 0x6fb2e9ef 0x501bea31 Z0,6 0xa40c12ad 0xa40c12ad 0xfec2fa0a 0x612b5817 Z0,7 0x764a73bd 0x7a69881b 0xaae38792 Z1,0 0xe9872480 0x1dcefd80 Z1,1 0xc635d20d 0x8ca2c780 Z1,2 0x2fd6e95d 0x20aff593 Z1,3 0x046601a7 0x45d6f91f Z1,4 0x0ee6b2ee Z1,5 0xe113f0cb Z1,6 0xcf22b643 Z1,7 0x81387e8a
Криптоанализ В ходе второго тура конкурса SHA-3 Luffa-224 и Luffa-256 в первоначальном варианте показали низкую криптостойкость, для успешной атаки потребовалось сообщений. После чего, алгоритм был модифицирован Даи Ватанабэ и получил название Luffa v.2. Изменения Luffa v.2: добавлен пустой раунд функции завершения для всех размеров хеша изменен S-блок увеличено количество повторений шаговой функции с 7 до 8
Барт Пренель (Bart Preneel) представил успешную атаку по поиску коллизий для 4 раундов шаговой функции Luffa за операций хеширования и для 5-раундовой, показав тем самым границу стойкости дизайна к дифференциальному поиску коллизий.
Производительность В 2010 году Томас Оливиера и Джулио Лопез провели успешные исследования возможности увеличения производительности оригинальной реализации Luffa. Оптимизированная реализация алгоритма имеет 20 % увеличение производительности вычисления хеша Luffa-512 при исполнении в 1 потоке, для Luffa-256/384 прирост производительности однопоточной реализации в различных тестах составляет не более 5 %. Результаты тестов приведены в таблице в циклах на байт:
На 64-битных платформах без SSE: Реализация алгоритма Luffa-256 Luffa-384 Luffa-512 Оригинальная реализация 2009 год Однопоточная реализация 27 42 58 Томас Оливиера 2010 год Однопоточная реализация 24 42 46 Многопоточная реализация 20 24 36
С использованием SSE: Реализация алгоритма Luffa-256 Luffa-384 Luffa-512 Оригинальная реализация 2009 год Однопоточная реализация 17 19 30 Томас Оливиера 2010 год Однопоточная реализация 15 16 24 Многопоточная реализация 15 18 25
Для сравнения, реализация Keccak (победитель конкурса SHA-3) в тестах на аналогичном процессоре c использованием SSE показала следующие результаты: Keccak-256 — 15 c/b, Keccak-512 — 12 c/b.
Примечания
Литература
Ссылки The Hash Function Family Luffa NIST website for competition Second round candidates The second SHA-3 candidate conference Classification of the SHA-3 Candidates
Категория:Криптографические хеш-функции