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]

Структура хеш-функции Lúffa

Обработка сообщения производится цепочкой раундовых функций смешивания с фиксированной входной и выходной длиной, которая представляет собой функцию губку. Цепочка состоит из блоков промежуточного смешивания C’ (раундовых функций) и блока завершения C’’. Раундовые функции образованы семейством нелинейных перестановок, так называемых шаговых функций. На вход функции первого раунда подается : первый блок сообщения и инициализирующие значения , где  — количество перестановок. Входными параметрами -го раунда является : выход предыдущего раунда и -й блок сообщения .

Дополнение сообщения

Дополнение сообщения длины до кратности 256 битам производится строкой , где число нулей определяется из сравнения

Инициализация

Кроме первого блока сообщения на вход функции первого раунда в качестве инициализурующих значений подаются векторы .

i j
0 1 2 3 4 5 6 7
0 0x6d251e690x44b051e00x4eaa6fb40xdbf784650x6e2920110x90152df40xee0581390xdef610bb
1 0xc3b44b950xd9d2f2560x70eee9a00xde099fa30x5d9b05570x8fc944b30xcf1ccf0e0x746cd581
2 0xf7efc89d0x5dba57810x04016ce50xad659c050x0306194f0x666d18360x24aa230a0x8b264ae7
3 0x858075d50x36d79cce0xe571f7d70x204b1f670x35870c6a0x57e9e9230x14bcb8080x7cde72ce
4 0x6c68e9be0x5ec41e220xc825b7c70xaffb43630xf5df39990x0fc688f10xb07224cc0x03e86cea

Раундовая функция

Схема раундовой функции Luffa

Раундовая функция является последовательным применением функции инжекции сообщения MI и перестановочной функции P.

Функции инжекции сообщения

Функция инжекции сообщения может быть представлена в виде матрицы преобразования над кольцом . Порождающий полином поля .

Функции инжекции сообщения

где числа соответственно обозначают полиномы

Функции инжекции сообщения

Функции инжекции сообщения

Функция перестановки

Нелинейная функция перестановки имеет битовый вход, длина суб-перестановки — фиксирована в спецификации Lúffa[6], ; количество — перестановок зависит от размера хеша и приведено в таблице.

Длина хеша Количество перестановок
2243
2563
3844
5125
Шаговая функция Luffa

Функция перестановки является восьмикратным повторением шаговой функции над блоком , полученным из функции инжекции сообщения . Блок представляется в виде 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 — линейная функция перестановки, на вход принимает и , ; выходом являются и , полученные по алгоритму:

  1. , (<<< 2 — циклический сдвиг влево на 2 бита)
AddConstant

AddConstant — функция добавления константы к

Таблица констант приведена в дополнении B к спецификации Lúffa[6].

Блок завершения

Блок завершения Luffa

Завершающий этап формирования дайджеста сообщения состоит из последовательных итераций функции выхода и раундовой функции с нулевым блоком сообщения 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,00xf29311b80xf29311b80x9a7abb790xf4024597
Z0,10x7e9e40de0x7e9e40de0x7a840e2d0x3e80d79d
Z0,20x7699be230x7699be230x423c34c90x0f4b9b20
Z0,30xfbeb5a470xfbeb5a470x1f559f680x2ddd4505
Z0,40xcb16ea4f0xcb16ea4f0x09bdb2910xb81b8830
Z0,50x5556d47c0x5556d47c0x6fb2e9ef0x501bea31
Z0,60xa40c12ad0xa40c12ad0xfec2fa0a0x612b5817
Z0,70x764a73bd0x7a69881b0xaae38792
Z1,00xe98724800x1dcefd80
Z1,10xc635d20d0x8ca2c780
Z1,20x2fd6e95d0x20aff593
Z1,30x046601a70x45d6f91f
Z1,40x0ee6b2ee
Z1,50xe113f0cb
Z1,60xcf22b643
Z1,70x81387e8a

Криптоанализ

В ходе второго тура конкурса 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-256Luffa-384Luffa-512
Оригинальная реализация 2009 год
Однопоточная реализация274258
Томас Оливиера 2010 год
Однопоточная реализация244246
Многопоточная реализация202436
  • С использованием SSE:
Реализация алгоритмаLuffa-256Luffa-384Luffa-512
Оригинальная реализация 2009 год
Однопоточная реализация171930
Томас Оливиера 2010 год
Однопоточная реализация151624
Многопоточная реализация151825

Для сравнения, реализация Keccak (победитель конкурса SHA-3) в тестах[9] на аналогичном процессоре c использованием SSE показала следующие результаты: Keccak-256 — 15 c/b, Keccak-512 — 12 c/b.

Примечания

  1. The Hash Function Family Luffa. Дата обращения: 22 ноября 2013. Архивировано 28 декабря 2013 года.
  2. 1 2 NIST sha-3 competition. Дата обращения: 22 ноября 2013. Архивировано 9 июля 2011 года.
  3. 1 2 Second round candidates. Дата обращения: 28 декабря 2013. Архивировано 10 апреля 2012 года.
  4. The second SHA-3 candidate conference. Дата обращения: 28 декабря 2013. Архивировано 12 января 2014 года.
  5. 1 2 Status Report on the Second Round of the SHA-3. Дата обращения: 28 декабря 2013. Архивировано 14 марта 2011 года.
  6. 1 2 3 4 Luffa Specification V.2.01. Дата обращения: 29 ноября 2013. Архивировано 20 февраля 2013 года.
  7. Finding Collisions for Reduced Luffa-256 v2. Дата обращения: 4 января 2014. Архивировано 20 февраля 2013 года.
  8. Improving the perfomance of Luffa Hash Algorithm. Дата обращения: 28 декабря 2013. Архивировано 21 марта 2014 года.
  9. The Keccak sponge function family: Software performance. Дата обращения: 4 января 2014. Архивировано 4 января 2014 года.

Литература

Ссылки