Luffa (хеш-функция)
Lúffa | |
---|---|
Разработчики | Даи Ватанабэ, Хисайоши Сато, Кристоф Де Канньере |
Создан | 2008 |
Опубликован | 2008 |
Размер хеша | 224, 256, 384, 512 |
Тип | хеш-функция |
Lúffa[1] (хеш-функция, произносится как «люффа») — криптографический алгоритм (семейство алгоритмов) хеширования переменной разрядности, разработанный Даи Ватанабэ (англ. Dai Watanabe), Хисайоши Сато (англ. Hisayoshi Sato) из Hitachi Yokohama Research Laboratory и Кристофом Де Канньере (нидерл. Christophe De Cannière) из исследовательской группы COSIC (en:COSIC) Лёвенского католического университета для участия в конкурсе[2], Национального института стандартов и технологий США (NIST). Lúffa является вариантом функции губки, предложенной Гвидо Бертони (англ. Guido Bertoni) и соавторами, криптостойкость которой основана только на случайности основной перестановки. В отличие от оригинальной функции губки, Lúffa использует множественное число параллельных перестановок и функции инжекции сообщений.
История участия в конкурсе NIST SHA-3[2]
- 9 декабря 2008 года Luffa в числе 51 кандидата прошла в первый раунд конкурса SHA-3.
- 25-28 февраля 2009 года хеш-функция была представлена на конференция NIST.
- 24 июля 2009 года был опубликован список[3] из 14 кандидатов прошедших во второй раунд, в который вошла Luffa.
- 23-24 августа 2010 года состоялась конференция[4], на которой были рассмотрены кандидаты[3], прошедшие во второй раунд.
- 10 декабря 2010 года произошло объявление 5 кандидатов последнего тура конкурса SHA-3, Luffa выбыла из соревнования из-за низкой криптостойкости функции сжатия[5].
Алгоритм Lúffa[6]

Обработка сообщения производится цепочкой раундовых функций смешивания с фиксированной входной и выходной длиной, которая представляет собой функцию губку. Цепочка состоит из блоков промежуточного смешивания 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
SubCrumb — функция замены l-х битов в или по S-блоку , результатом выполнения является замена , индекс S-блока получается в результате конкатенации соответствующих битов : , биты заменяются на соответствующие биты из по следующей схеме:
MixWord
MixWord — линейная функция перестановки, на вход принимает и , ; выходом являются и , полученные по алгоритму:
- , (<<< 2 — циклический сдвиг влево на 2 бита)
AddConstant
AddConstant — функция добавления константы к
Таблица констант приведена в дополнении B к спецификации Lúffa[6].
Блок завершения

Завершающий этап формирования дайджеста сообщения состоит из последовательных итераций функции выхода и раундовой функции с нулевым блоком сообщения 0x000 на входе. Функция выхода представляет собой XOR всех промежуточных значений, а в качестве результата представляет 256-битное слово . На i-й итерации значение выходной функции определяется как
, где , если , иначе
Через обозначим 32-битные слова в , тогда выходом Lúffa являются составленные последовательно . Символ "||" обозначает конкатенацию.
Длина хеша | Значение хеша |
---|---|
224 | |
256 | |
384 | |
512 |
Хеш Lúffa-224 фактически представляет собой хеш Lúffa-256 без последнего 32-битного слова.
Тестовые векторы[6]
Дайджесты сообщения «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]:
- добавлен пустой раунд функции завершения для всех размеров хеша
- изменен S-блок
- увеличено количество повторений шаговой функции с 7 до 8
Барт Пренель (Bart Preneel) представил успешную атаку[7] по поиску коллизий для 4 раундов шаговой функции Luffa за операций хеширования и для 5-раундовой, показав тем самым границу стойкости дизайна к диференциальному поиску коллизий.
Производительность
В 2010 году Томас Оливиера и Джулио Лопез провели успешные исследования[8] возможности увеличения производительности оригинальной реализации 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) в тестах[9] на аналогичном процессоре c использованием SSE показала следующие результаты: Keccak-256 — 15 c/b, Keccak-512 — 12 c/b.
Примечания
- ↑ The Hash Function Family Luffa . Дата обращения: 22 ноября 2013. Архивировано 28 декабря 2013 года.
- ↑ 1 2 NIST sha-3 competition . Дата обращения: 22 ноября 2013. Архивировано 9 июля 2011 года.
- ↑ 1 2 Second round candidates . Дата обращения: 28 декабря 2013. Архивировано 10 апреля 2012 года.
- ↑ The second SHA-3 candidate conference . Дата обращения: 28 декабря 2013. Архивировано 12 января 2014 года.
- ↑ 1 2 Status Report on the Second Round of the SHA-3 . Дата обращения: 28 декабря 2013. Архивировано 14 марта 2011 года.
- ↑ 1 2 3 4 Luffa Specification V.2.01 . Дата обращения: 29 ноября 2013. Архивировано 20 февраля 2013 года.
- ↑ Finding Collisions for Reduced Luffa-256 v2 . Дата обращения: 4 января 2014. Архивировано 20 февраля 2013 года.
- ↑ Improving the perfomance of Luffa Hash Algorithm . Дата обращения: 28 декабря 2013. Архивировано 21 марта 2014 года.
- ↑ The Keccak sponge function family: Software performance . Дата обращения: 4 января 2014. Архивировано 4 января 2014 года.
Литература
- Hisayoshi Sato, Dai Watanabe, Christophe De Canni`ere. Luffa v.2 Specification.
- Status Report on the Second Round of the SHA-3. — С. 19-20.
- Bart Preneel, Hirotaka Yoshida, Dai Watanabe. Finding Collisions for Reduced Luffa-256 v2.
- Thomaz Oliveira, Julio Lopez. Improving the performance of Luffa Hash Algorithm.