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

Lúffa
Разработчики	Даи Ватанабэ, Хисайоши Сато, Кристоф Де Канньере
Создан	2008
Опубликован	2008
Размер хеша	224, 256, 384, 512
Тип	хеш-функция

Lúffa (хеш-функция, произносится как «люффа») — криптографический алгоритм (семейство алгоритмов) хеширования переменной разрядности, разработанный Даи Ватанабэ (англ. Dai Watanabe), Хисайоши Сато (англ. Hisayoshi Sato) из Hitachi Yokohama Research Laboratory и Кристофом Де Канньере (нидерл. Christophe De Cannière) из исследовательской группы COSIC (en:COSIC) Лёвенского католического университета для участия в конкурсе, Национального института стандартов и технологий США (NIST). Lúffa является вариантом функции губки, предложенной Гвидо Бертони (англ. Guido Bertoni) и соавторами, криптостойкость которой основана только на случайности основной перестановки. В отличие от оригинальной функции губки, Lúffa использует множественное число параллельных перестановок и функции инжекции сообщений.

История участия в конкурсе NIST SHA-3

• 9 декабря 2008 года Luffa в числе 51 кандидата прошла в первый раунд конкурса SHA-3.
• 25-28 февраля 2009 года хеш-функция была представлена на конференция NIST.
• 24 июля 2009 года был опубликован список из 14 кандидатов прошедших во второй раунд, в который вошла Luffa.
• 23-24 августа 2010 года состоялась конференция, на которой были рассмотрены кандидаты, прошедшие во второй раунд.
• 10 декабря 2010 года произошло объявление 5 кандидатов последнего тура конкурса SHA-3, Luffa выбыла из соревнования из-за низкой криптостойкости функции сжатия.

Алгоритм Lúffa

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

Обработка сообщения производится цепочкой раундовых функций смешивания с фиксированной входной и выходной длиной, которая представляет собой функцию губку. Цепочка состоит из блоков промежуточного смешивания C’ (раундовых функций) и блока завершения C’’. Раундовые функции образованы семейством нелинейных перестановок, так называемых шаговых функций. На вход функции первого раунда $(i=1)$ подается $(M^{(1)},V_{0},\ V_{1},\cdots ,\ V_{w-1})$: первый блок сообщения $M^{(1)}$ и инициализирующие значения $V_{0},\ V_{1},\cdots ,\ V_{w-1}$, где $w$ — количество перестановок. Входными параметрами $i$-го раунда является $(M^{(i)},H_{0}^{(i-1)},\ H_{1}^{(i-1)},\cdots ,\ H_{w-1}^{(i-1)})$: выход предыдущего $(i-1)$ раунда и $i$-й блок сообщения $M^{(i)}$.

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

Дополнение сообщения $M$ длины $l$ до кратности 256 битам производится строкой $1000\cdots 0$, где число нулей $k$ определяется из сравнения $l+1+k\equiv 0\mod 256$

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

Кроме первого блока сообщения $M^{(1)}$ на вход функции первого раунда в качестве инициализурующих значений подаются векторы $V_{i}$.

$V_{i,j}$
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.

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

Функция инжекции сообщения может быть представлена в виде матрицы преобразования над кольцом $GF(2^{8})^{32}$. Порождающий полином поля $f(x)=x^{8}+x^{4}+x^{3}+x+1$.

Функции инжекции сообщения $w=3$

${\begin{pmatrix}X_{0}\\X_{1}\\X_{2}\end{pmatrix}}={\begin{pmatrix}3&2&2&1\\2&3&2&2\\2&2&3&4\end{pmatrix}}{\begin{pmatrix}H_{0}^{(i-1)}\\H_{1}^{(i-1)}\\H_{2}^{(i-1)}\\M_{i}\end{pmatrix}}$

где числа ${1,2,3,4}$ соответственно обозначают полиномы ${1,x,x+1,x^{2}}$

Функции инжекции сообщения $w=4$

${\begin{pmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{pmatrix}}={\begin{pmatrix}4&6&6&7&1\\7&4&6&6&2\\6&7&4&6&4\\6&6&7&4&8\end{pmatrix}}{\begin{pmatrix}H_{0}^{(i-1)}\\H_{1}^{(i-1)}\\H_{2}^{(i-1)}\\H_{3}^{(i-1)}\\M_{i}\end{pmatrix}}$

Функции инжекции сообщения $w=5$

${\begin{pmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\\X_{4}\end{pmatrix}}={\begin{pmatrix}0F&08&0A&0A&08&01\\08&0F&08&0A&0A&02\\0A&08&0F&08&0A&04\\0A&0A&08&0F&08&08\\08&0A&0A&08&0F&10\end{pmatrix}}{\begin{pmatrix}H_{0}^{(i-1)}\\H_{1}^{(i-1)}\\H_{2}^{(i-1)}\\H_{3}^{(i-1)}\\H_{4}^{(i-1)}\\M_{i}\end{pmatrix}}$

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

Нелинейная функция перестановки имеет $w\cdot n_{b}$ битовый вход, длина суб-перестановки — $n_{b}$ фиксирована в спецификации Lúffa, $n_{b}=256$; количество — $w$ перестановок зависит от размера хеша и приведено в таблице.

Длина хеша $n_{h}$	Количество перестановок $w$
224	3
256	3
384	4
512	5

Шаговая функция Luffa

Функция перестановки является восьмикратным повторением шаговой функции над блоком $Q_{i}$, полученным из функции инжекции сообщения $MI$. Блок $Q_{i}$ представляется в виде 8 32-битных слов: $a_{0},a_{1},a_{2},a_{3},a_{4},a_{5},a_{6},a_{7}$. Шаговая функция состоит из 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-х битов в $a_{0},a_{1},a_{2},a_{3}$ или $a_{4},a_{5},a_{6},a_{7}$ по S-блоку $S[16]={13,14,0,1,5,10,7,6,11,3,9,12,15,8,2,4}$, результатом выполнения является замена $a_{i}\rightarrow x_{i}$, индекс $i$ S-блока получается в результате конкатенации соответствующих битов $a_{j,l}$: $i=a_{3,l}||a_{2,l}||a_{1,l}||a_{0,l}$, биты $x_{j,l}$ заменяются на соответствующие биты из $S[i]$ по следующей схеме:

1. $x_{3,l}||x_{2,l}||x_{1,l}||x_{0,l}=S[i]=S[a_{3,l}||a_{2,l}||a_{1,l}||a_{0,l}],0\leq l<32$
2. $x_{4,l}||x_{7,l}||x_{6,l}||x_{5,l}=S[i]=S[a_{4,l}||a_{7,l}||a_{6,l}||a_{5,l}],0\leq l<32,$

MixWord

MixWord — линейная функция перестановки, на вход принимает $x_{k}$ и $x_{k+4}$, $0\leq k<4$; выходом являются $y_{k}$ и $y_{k+4}$, полученные по алгоритму:

1. $y_{k+4}=x_{k+4}\oplus x_{k}$
2. $y_{k}=x_{k}<<<2$, (<<< 2 — циклический сдвиг влево на 2 бита)
3. $y_{k}=y_{k}\oplus y_{k+4}$
4. $y_{k+4}=y_{k+4}<<<14$
5. $y_{k+4}=y_{k+4}\oplus y_{k}$
6. $y_{k}=y_{k}<<<10$
7. $y_{k}=y_{k}\oplus y_{k+4}$
8. $y_{k+4}=y_{k+4}<<<1$

AddConstant

AddConstant — функция добавления константы $c_{j,k}^{(r-1)}$ к $a_{j,k}^{(r-1)}$

$a_{j,k}^{(r)}=a_{j,k}^{(r-1)}\oplus c_{j,k}^{(r-1)},k=0,4$

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

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

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

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

$Z_{i}=\bigoplus _{k=0}^{w-1}H_{k}^{(N+j)}$, где $j=i$, если $N=1$, иначе $j=i+1$

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

Длина хеша $n_{h}$	Значение хеша $H$
224	$Z_{0,0}||\cdots ||Z_{0,6}$
256	$Z_{0,0}||\cdots ||Z_{0,7}$
384	$Z_{0,0}||\cdots ||Z_{0,6}||Z_{1,0}||\cdots ||Z_{1,3}$
512	$Z_{0,0}||\cdots ||Z_{0,6}||Z_{1,0}||\cdots ||Z_{1,7}$

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

Тестовые векторы

Дайджесты сообщения «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 в первоначальном варианте показали низкую криптостойкость, для успешной атаки потребовалось $2^{216}$ сообщений. После чего, алгоритм был модифицирован Даи Ватанабэ и получил название Luffa v.2. Изменения Luffa v.2:

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

Барт Пренель (Bart Preneel) представил успешную атаку по поиску коллизий для 4 раундов шаговой функции Luffa за $2^{90}$ операций хеширования и $2^{224}$ для 5-раундовой, показав тем самым границу стойкости дизайна к диференциальному поиску коллизий.

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

В 2010 году Томас Оливиера и Джулио Лопез провели успешные исследования возможности увеличения производительности оригинальной реализации 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) в тестах на аналогичном процессоре c использованием SSE показала следующие результаты: Keccak-256 — 15 c/b, Keccak-512 — 12 c/b.

Литература

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

Ссылки

• The Hash Function Family Luffa
• NIST website for competition
• Second round candidates
• The second SHA-3 candidate conference
• Classification of the SHA-3 Candidates