30-01-2024
Криптографическая хэш-функция |
|
Название |
Lúffa |
---|---|
Разработчики |
Даи Ватанабэ, Хисайоши Сато, Кристоф Де Канньере |
Создан | |
Опубликован | |
Размер хэша |
224, 256, 384, 512 |
Тип |
LúffaYokohama Research Laboratory и Кристофом Де Канньере (нидерл. Christophe De Cannière) из исследовательской группы COSIC (en:COSIC) Лёвенского католического университета для участия в конкурсе[2], Национального института стандартов и технологий США (NIST). Lúffa является вариантом функции губки, предложенной Гвидо Бертони (англ. Guido Bertoni) и соавторами, криптостойкость которой основана только на случайности основной перестановки. В отличие от оригинальной губки, 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[6], ; количество — перестановок зависит от размера хеша и приведено в таблице.
Длина хеша | Количество перестановок |
---|---|
224 | 3 |
256 | 3 |
384 | 4 |
512 | 5 |
Функция перестановки является восьмикратным повторением шаговой функции над блоком , полученным из функции инжекции сообщения . Блок представляется в виде 8-ми 32-битных слов: . Шаговая функция состоит из 3-х функций: SubCrumb, MixWord, AddConstant.
Permute(a[8], j){ //Permutation Q_j for (r = 0; r < 8; r++){ SubCrumb(a[0],a[1],a[2],a[3]); SubCrumb(a[5],a[6],a[7],a[4]); for (k = 0; k < 4; k++) MixWord(a[k],a[k+4]); AddConstant(a, j, r); } }
SubCrumb — функция замены l-ых битов в или по S-блоку , результатом выполнения является замена , индекс S-блока получается в результате конкатенации соответствующих битов : , биты заменяются на соответствующие биты из по следующей схеме:
MixWord — линейная функция перестановки, на вход принимает и , ; выходом являются и , полученные по алгоритму:
AddConstant — функция добавления константы к
Таблица констант приведена в дополнении B к спецификации Lúffa[6].
Завершающий этап формирования дайджеста сообщения состоит из последовательных итераций функции выхода и раундовой функции с нулевым блоком сообщения 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[5]:
Барт Пренель (Bart Preneel) представил успешную атаку[7] по поиску коллизий для 4-х раундов шаговой функции Luffa за операций хэширования и для 5-тираундовой, показав тем самым границу стойкости дизайна к диференциальному поиску коллизий.
В 2010 году Томас Оливиера и Джулио Лопез провели успешные исследования[8] возможности увеличения производительности оригинальной реализации Luffa. Оптимизированная реализация алгоритма имеет 20% увеличение производительности вычисления хеша Luffa-512 при исполнении в 1 потоке, для Luffa-256/384 прирост производительности однопоточной реализации в различных тестах составляет не более 5%. Результаты тестов приведены в таблице в циклах на байт:
Реализация алгоритма | Luffa-256 | Luffa-384 | Luffa-512 |
---|---|---|---|
Оригинальная реализация 2009 год | |||
Однопоточная реализация | 27 | 42 | 58 |
Томас Оливиера 2010 год | |||
Однопоточная реализация | 24 | 42 | 46 |
Многопоточная реализация | 20 | 24 | 36 |
Реализация алгоритма | Luffa-256 | Luffa-384 | Luffa-512 |
---|---|---|---|
Оригинальная реализация 2009 год | |||
Однопоточная реализация | 17 | 19 | 30 |
Томас Оливиера 2010 год | |||
Однопоточная реализация | 15 | 16 | 24 |
Многопоточная реализация | 15 | 18 | 25 |
Для сравнения, реализация Keccak (победитель конкурса SHA-3) в тестах[9] на аналогичном процессоре c использованием SSE показала следующие результаты: Keccak-256 - 15 c/b, Keccak-512 - 12 c/b.
Хеш-функции | |
---|---|
Общего назначения | |
Криптографические |
JH • HAVAL • Keccak (SHA-3) • LM-хеш • Luffa • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • Scrypt • SHA-1 • SHA-2 • Skein • Snefru • Tiger • Whirlpool • ГОСТ Р 34.11-94 • ГОСТ Р 34.11-2012 |
Luffa aegyptiaca, luffa finally fruiting, luffa operculata что это, luffa fresh and simple healthy dish.