Лучшие вопросы
Таймлайн
Чат
Перспективы

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

Из Википедии, свободной энциклопедии

Remove ads

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 использует множественное число параллельных перестановок и функции инжекции сообщений.

Краткие факты Lúffa, Разработчики ...
Remove ads

История участия в конкурсе 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].
Remove ads

Алгоритм Lúffa[6]

Суммиров вкратце
Перспектива
Thumb
Структура хеш-функции Lúffa

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

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

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

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

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

Подробнее ...

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

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

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

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

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

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

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

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

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

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

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

Подробнее Длина хеша ...
Thumb
Шаговая функция 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].

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

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

Завершающий этап формирования дайджеста сообщения состоит из последовательных итераций функции выхода и раундовой функции с нулевым блоком сообщения 0x000 на входе. Функция выхода представляет собой XOR всех промежуточных значений, а в качестве результата представляет 256-битное слово . На i-й итерации значение выходной функции определяется как

, где , если , иначе

Через обозначим 32-битные слова в , тогда выходом Lúffa являются составленные последовательно . Символ "||" обозначает конкатенацию.

Подробнее Длина хеша ...

Хеш Lúffa-224 фактически представляет собой хеш Lúffa-256 без последнего 32-битного слова.

Remove ads

Тестовые векторы[6]

Дайджесты сообщения «abc» при различном размере хеша.

Подробнее Z0,0, Z0,1 ...

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

В ходе второго тура конкурса SHA-3 Luffa-224 и Luffa-256 в первоначальном варианте показали низкую криптостойкость, для успешной атаки потребовалось сообщений. После чего, алгоритм был модифицирован Даи Ватанабэ и получил название Luffa v.2. Изменения Luffa v.2[5]:

  • добавлен пустой раунд функции завершения для всех размеров хеша
  • изменен S-блок
  • увеличено количество повторений шаговой функции с 7 до 8

Барт Пренель (Bart Preneel) представил успешную атаку[7] по поиску коллизий для 4 раундов шаговой функции Luffa за операций хеширования и для 5-раундовой, показав тем самым границу стойкости дизайна к дифференциальному поиску коллизий.

Remove ads

Производительность

Суммиров вкратце
Перспектива

В 2010 году Томас Оливиера и Джулио Лопез провели успешные исследования[8] возможности увеличения производительности оригинальной реализации Luffa. Оптимизированная реализация алгоритма имеет 20 % увеличение производительности вычисления хеша Luffa-512 при исполнении в 1 потоке, для Luffa-256/384 прирост производительности однопоточной реализации в различных тестах составляет не более 5 %. Результаты тестов приведены в таблице в циклах на байт:

  • На 64-битных платформах без SSE:
Подробнее Реализация алгоритма, Оригинальная реализация 2009 год ...
  • С использованием SSE:
Подробнее Реализация алгоритма, Оригинальная реализация 2009 год ...

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

Remove ads

Примечания

Литература

Ссылки

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads