Luffa (хеш-функция) (Luffa (]yo-srutenx))

Перейти к навигации Перейти к поиску
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 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

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

[править | править код]
Схема раундовой функции Luffa

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

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

[править | править код]

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

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

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

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

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

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

[править | править код]

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

Длина хеша Количество перестановок
224 3
256 3
384 4
512 5
Шаговая функция 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 — функция замены l-х битов в или по S-блоку , результатом выполнения является замена , индекс S-блока получается в результате конкатенации соответствующих битов : , биты заменяются на соответствующие биты из по следующей схеме:

MixWord — линейная функция перестановки, на вход принимает и , ; выходом являются и , полученные по алгоритму:

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

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,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.

Примечания

[править | править код]
  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 года.

Литература

[править | править код]