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

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

Раундовая функция является последовательным применением функции инжекции сообщения MI и перестановочной функции P.
Функции инжекции сообщения
Функция инжекции сообщения может быть представлена в виде матрицы преобразования над кольцом . Порождающий полином поля .
Функции инжекции сообщения
где числа соответственно обозначают полиномы
Функции инжекции сообщения
Функции инжекции сообщения
Функция перестановки
Нелинейная функция перестановки имеет битовый вход, длина суб-перестановки — фиксирована в спецификации Lúffa[6], ; количество — перестановок зависит от размера хеша и приведено в таблице.

Функция перестановки является восьмикратным повторением шаговой функции над блоком , полученным из функции инжекции сообщения . Блок представляется в виде 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 являются составленные последовательно . Символ "||" обозначает конкатенацию.
Хеш Lúffa-224 фактически представляет собой хеш Lúffa-256 без последнего 32-битного слова.
Remove ads
Тестовые векторы[6]
Дайджесты сообщения «abc» при различном размере хеша.
Криптоанализ
В ходе второго тура конкурса 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:
- С использованием SSE:
Для сравнения, реализация Keccak (победитель конкурса SHA-3) в тестах[9] на аналогичном процессоре c использованием SSE показала следующие результаты: Keccak-256 — 15 c/b, Keccak-512 — 12 c/b.
Remove ads
Примечания
Литература
Ссылки
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads