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

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

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

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

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

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

${\displaystyle 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

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

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

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

${\displaystyle {\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}}}$

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

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

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

1. ${\displaystyle 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. ${\displaystyle 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 — линейная функция перестановки, на вход принимает ${\displaystyle x_{k}}$ и ${\displaystyle x_{k+4}}$, ${\displaystyle 0\leq k<4}$; выходом являются ${\displaystyle y_{k}}$ и ${\displaystyle y_{k+4}}$, полученные по алгоритму:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 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