Tiger (хэш-функция)

Tiger — хеш-функция, разработанная Росом Андерсоном и Эли Бихамом в 1995 году. Tiger был предназначен для особенно быстрого выполнения на 64-разрядных компьютерах. Tiger не имеет патентных ограничений, может использоваться свободно как с эталонной реализацией, так и с ее модификациями. Размер значения хеша — 192 бита (Tiger/192), хотя имеются также более короткие версии для совместимости с SHA-1 (Tiger/160) и с MD4, MD5, RIPEMD, Snefru (Tiger/128). Скорость работы — 132 Мбит/с (проверено на одном процессоре Alpha 7000, модель 660). На современных процессорах значительно быстрее (даже при тесте на 32-битном AMD Sempron 3000+ скорость около 225 Мбит/с).

Tiger2 — версия Tiger, которая отличается от основной только другим алгоритмом добавления битов, сходным с MD5/SHA-1. Для Tiger2 доступны тестовые векторы.

История возникновения

Алгоритм был разработан в 1995 году Россом Андерсоном и Эли Бихамом. То время характеризовалось тем, что для популярных хэш-функций MD4 и Snefru были уже найдены коллизии. Последнее, по мнению авторов, ставило под вопрос и надежность их производных, таких как MD5 и Snefru-8. Основными целями при разработке Tiger были:

• безопасность;
• быстрая работа на новых 64-битных процессорах при разумной скорости на 32-битных;
• замена по возможности серий MD и SHA.

Алгоритм

Количество используемых S-box’ов — 4. S-box выполняет преобразование 8 бит в 64 бита. То есть в каждом из них 256 64-битных слов и общий размер памяти, требуемой для хранения S-box’ов 4*256*8 = 8096 = 8 Кбайт. Для этого хватает кэша большинства процессоров, хотя могут быть сложности при реализации на микроконтроллерах.

Как и в семействе MD4, к сообщению добавляется бит ‘1’, за которым следуют нули. Входные данные делятся на n блоков по 512 бит.

Выбираем первый 512-битный блок. Этот блок делится на восемь 64-битных слов x0, x1, …, x7. Порядок байтов — little-endian.

Берутся три 64-битных регистра с начальными значениями (значение хеша $h_0$):

a = 0x0123456789ABCDEF
b = 0xFEDCBA9876543210
c = 0xF096A5B4C3B2E187

Теперь для перехода от значения $h_i$ к значению $h_{i+1}$ выполняются следующие операции:

1. save_abc
2. pass(a, b, c,5)
3. key_schedule
4. pass(c, a, b,7)
5. key_schedule
6. pass(b, c, a,9)
7. feedforward

Здесь save_abc сохраняет значение $h_i$:

aa = a 
bb = b 
cc = c 

pass(a, b, c, mul) означает:

round(a,b,c,x0,mul)
round(b,c,a,x1,mul)
round(c,a,b,x2,mul)
round(a,b,c,x3,mul)
round(b,c,a,x4,mul)
round(c,a,b,x5,mul)
round(a,b,c,x6,mul)
round(b,c,a,x7,mul)

Один раунд преобразований Tiger

где round(a, b, c, x, mul):

c ^= x 
a -= t1[c_0] ^ t2[c_2] ^ t3[c_4] ^ t4[c_6] 
b += t4[c_1] ^ t3[c_3] ^ t2[c_5] ^ t1[c_7] 
b *= mul

c_i — i-й байт c (0 <= i <= 7);

^ — операция XOR;

ti — i-й S-box

key_schedule — генерация ключей, обратимая функция, которая отвечает за то, чтобы изменение небольшого числа бит сообщения x вызвало изменение большого числа бит на следующем выполнении pass:

x0 -= x7 ^ 0xA5A5A5A5A5A5A5A5
x1 ^= x0 
x2 += x1
x3 -= x2 ^ ((~x1)<<19) 
x4 ^= x3
x5 += x4 
x6 -= x5 ^ ((~x4)>>23) 
x7 ^= x6 
x0 += x7 
x1 -= x0 ^ ((~x7)<<19) 
x2 ^= x1 
x3 += x2 
x4 -= x3 ^ ((~x2)>>23) 
x5 ^= x4 
x6 += x5 
x7 -= x6 ^ 0x0123456789ABCDEF

где << и >> — логические сдвиги влево и вправо, ~ — инвертирование

feedforward — обратная связь:

a ^= aa 
b -= bb 
c += cc 

То есть всего получаем 24 раунда. Конкатенация полученных значений a, b, c дает промежуточное значение хеш-функции $h_{i+1}$, которое используется как начальное значение для следующего 512-битного блока данных. Промежуточное значение $h_n$ на последнем блоке дает 192-битное значение Tiger/192.

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

Примеры хеш-значений, полученных с помощью программы testtiger с авторской страницы.

Hash("") = 
24F0130C63AC9332 16166E76B1BB925F F373DE2D49584E7A

Hash("Tiger") = 
9F00F599072300DD 276ABB38C8EB6DEC 37790C116F9D2BDF

Hash("abc") =
F258C1E88414AB2A 527AB541FFC5B8BF 935F7B951C132951

Hash("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+-") = 
87FB2A9083851CF7 470D2CF810E6DF9E B586445034A5A386

Hash("ABCDEFGHIJKLMNOPQRSTUVWXYZ=abcdefghijklmnopqrstuvwxyz+0123456789") =
467DB80863EBCE48 8DF1CD1261655DE9 57896565975F9197

Безопасность

Основные аспекты безопасности Tiger:

• нелинейность преобразования S-box’ов;
• использование 64-битных регистров ускоряет лавинообразное изменение всех трех регистров при изменении любого бита сообщения;
• генерация ключей обеспечивает значительные изменения всех бит на последующих преобразованиях при незначительном изменении сообщения;
• умножение регистра b в каждом раунде также способствует перемешиванию и увеличивает сопротивление атакам на связанные ключи;
• обратная связь препятствует промежуточным атакам дней рождения.

Атака на связанные ключи представляет из себя атаку, при которой криптоаналитик может вычислять хеш для нескольких различных значений инициализирующих векторов, которые он не знает, но знает некоторую взаимосвязь между ними (например, что они отличаются на один бит или какая-то часть всех векторов одна и та же). Из-за атаки такого типа с шифрования WEP пришлось перейти на WPA.

Промежуточная атака дней рождения — атака дней рождения, применённая на промежуточных раундах для достижения желаемых хеш-значений. Хотя, по мнению авторов, атаки подобного типа вряд ли приведут к сложности меньше $2^{96}$ (в соответствии с парадоксом дней рождения).

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

Пусть h(x, m) — хеш-функция, где x — инициализирующий вектор, m — блок сообщения. ^ — операция XOR, w{} — вес Хэмминга (число ненулевых компонент двоичного числа). Тогда:

• под коллизией будем понимать ситуацию, когда

  w{h(x, m1) ^ h(x, m2)} = 0;

• под почти коллизией -

  w{h(x, m1) ^ h(x, m2)} = a, где a — небольшое значение;

• под псевдоколлизией -

  w{h(x1,m1) ^ h(x2,m2)} = 0;

• под почти псевдоколлизией -

  w{h(x1,m1) ^ h(x2,m2)} = a, где a — небольшое значение.

В идеале, в соответствии с парадоксом дней рождений, для нахождения коллизии N-разрядной хеш-функции потребуется не менее $O(2^{N/2})$ операций.

В 2006 году Джон Келси и Стефан Лакс представили коллизию для Tiger-16 (c 16 раундами вместо 24) со сложностью $2^{44}$, а также почти псевдоколлизию для Tiger-20 со сложностью $2^{48}$. Далее в этом же году Флориан Мендель и соавторы показали, как применить технику атаки Джона Келси и Стефана Лакса, чтобы получить коллизию для Tiger-19, а также предложили две различные техники для получения этой коллизии со сложностями $2^{62}$ и $2^{69}$.

Обзор атак на Tiger

Число раундов	Тип	Сложность	Описание
Tiger-16	коллизия	$2^{44}$	[1]
Tiger-19	коллизия	$2^{62}$ и $2^{69}$	[2]
Tiger-19	псевдоколлизия	$2^{44}$	[2]
Tiger-21	псевдоколлизия	$2^{66}$	[2]
Tiger-23/128	псевдоколлизия	$2^{44}$	[2]
Tiger-23	псевдоколлизия	$2^{47}$	[3]
Tiger-20	почти псевдоколлизия	$2^{48}$	[1]
Tiger-21	почти псевдоколлизия	$2^{44}$	[2]
Tiger-22	почти псевдоколлизия	$2^{44}$	[2]
Tiger-24	почти псевдоколлизия	$2^{47}$	[3]

Атака на Tiger-16

Поясним идею нахождения коллизии для Tiger-16, то есть для Tiger с 16 раундами, изложенную Джоном Келси и Стефаном Лаксом.^[1]

Рассматриваем 64-битные слова. Мы будем иметь дело с различием между словами двух типов: xor-различие и аддитивное различие. Первое из них есть результат обычной разности по модулю $2^{64}$, а второе — результат операции XOR. Обычно преобразование одного типа различия в другой дело вероятностное. Но есть случай когда два типа различий равны друг другу с вероятностью 1. А именно, когда различие $I = 2^{63}$, действительно в этом случае слова просто отличаются друг от друга старшим битом. Также отметим свойство различия — оно не меняется если домножить слово на нечетное число (что очень удобно, так как в алгоритме используются нечетные mul = 5, 7, 9).

Пусть $I = 2^{63}$. Под набором

(I0, I1, I2, I3, I4, I5, I6, I7)

подразумеваем, что различие между j-ми (j = 0, 1, …, 7) 64-битными словами ключей равно $Ij$ (все равно какого типа, так как рассматривать мы будем только различия $2^{63}$ и 0). То есть $Ij$ = xj ^ xj’.

Джон Келси и Стефан Лакс предложили взять два блока (по 512 бит) с вектором различий $(I, I, I, I, 0, 0, 0, 0)$. Если проследить по ходу алгоритма, учитывая свойства различий, можно показать, что после первого pass (по прошествии раундов 0, 1, …, 7) и key_schedule будет вектор $(I, I, 0, 0, 0, 0, 0, 0)$. После раундов 8-9 получаем $(0, 0, 0, 0, 0, 0, 0, 0)$, а раунды раунды 10-15 на различие не влияют. Таким образом, получаем технику удержания различий между ключами с вероятностью 1.

При этом с помощью модификаций сообщений посредством промежуточных атак дней рождений решается проблема поддержания различия хеш-значений a, b, c, так что после раунда 6 был вектор различий $(I, I, 0)$, а по прошествии раундов 7-9 — $(0, 0, 0)$. Техника модификаций сообщений является самой трудоемкой, где и получается результирующая сложность $2^{44}$. Раунды 10-15 на различие не повлияют (действительно, ключи к этому шагу уже одинаковые).

То есть после 16 раундов хеш-значения совпадут.

Использование

Tiger используется в технологии TTH, где хеш вычисляется в древовидной форме. TTH в свою очередь применяется в протоколах файлового обмена Gnutella, Gnutella2, Direct Connect, а также в файлообменниках Phex, BearShare, LimeWire, Shareaza, DC++ и Valknut.

Ссылки

• Страница авторов Tiger

Статьи

1. ↑ ^{1 2 3} John Kelsey and Stefan Lucks, Collisions and Near-Collisions for Reduced-Round Tiger, proceedings of Fast Software Encryption 13, Graz, 2006 (PDF)
2. ↑ ^{1 2 3 4 5 6} Florian Mendel, Bart Preneel, Vincent Rijmen, Hirotaka Yoshida, and Dai Watanabe, Update on Tiger, proceedings of Indocrypt 7, Kolkata, 2006 (PDF)
3. ↑ ^{1 2} Mendel, Florian; Rijmen Vincent., Cryptanalysis of the Tiger Hash Function, ASIACRYPT 2007. Springer Berlin / Heidelberg. pp. 536-550 (PDF)