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 = 8192 = 8 Кбайт. Для этого хватает кэша большинства процессоров, хотя могут быть сложности при реализации на микроконтроллерах.
Как и в семействе MD4, к сообщению добавляется бит «1», за которым следуют нули. Входные данные делятся на n блоков по 512 бит.
Выбираем первый 512-битный блок. Этот блок делится на восемь 64-битных слов x0, x1, …, x7. Порядок байтов — little-endian.
Берутся три 64-битных регистра с начальными значениями (значение хеша ):
a = 0x0123456789ABCDEF
b = 0xFEDCBA9876543210
c = 0xF096A5B4C3B2E187
Теперь для перехода от значения к значению выполняются следующие операции:
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:
где << и >> — логические сдвиги влево и вправо, ~ — инвертирование
feedforward — обратная связь:
a ^= aa
b -= bb
c += cc
То есть всего получаем 24 раунда.
Конкатенация полученных значений a, b, c даёт промежуточное значение хеш-функции , которое используется как начальное значение для следующего 512-битного блока данных. Промежуточное значение на последнем блоке даёт 192-битное значение Tiger/192.
Тестовые векторы
Примеры хеш-значений, полученных с помощью программы testtiger с авторской страницы[1].
Атака на связанные ключи представляет собой атаку, при которой криптоаналитик может вычислять хеш для нескольких различных значений инициализирующих векторов, которые он не знает, но знает некоторую взаимосвязь между ними (например, что они отличаются на один бит или какая-то часть всех векторов одна и та же). Из-за атаки такого типа с шифрования WEP пришлось перейти на WPA.
Промежуточная атака дней рождения — атака дней рождения, применённая на промежуточных раундах для достижения желаемых хеш-значений. Хотя, по мнению авторов, атаки подобного типа вряд ли приведут к сложности меньше (в соответствии с парадоксом дней рождения).
Криптоанализ
Пусть 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-разрядной хеш-функции потребуется не менее операций.
В 2006 году Джон Келси и Стефан Лакс представили коллизию для Tiger-16 (c 16 раундами вместо 24) со сложностью , а также почти псевдоколлизию для Tiger-20 со сложностью . Далее в этом же году Флориан Мендель и соавторы показали, как применить технику атаки Джона Келси и Стефана Лакса, чтобы получить коллизию для Tiger-19, а также предложили две различные техники для получения этой коллизии со сложностями и .
Поясним идею нахождения коллизии для Tiger-16, то есть для Tiger с 16 раундами, изложенную Джоном Келси и Стефаном Лаксом[article 1].
Рассматриваем 64-битные слова. Мы будем иметь дело с различием между словами двух типов: xor-различие и аддитивное различие. Первое из них есть результат обычной разности по модулю , а второе — результат операции XOR. Обычно преобразование одного типа различия в другой дело вероятностное. Но есть случай когда два типа различий равны друг другу с вероятностью 1. А именно, когда различие , действительно в этом случае слова просто отличаются друг от друга старшим битом. Также отметим свойство различия — оно не меняется если домножить слово на нечетное число (что очень удобно, так как в алгоритме используются нечетные mul = 5, 7, 9).
Пусть . Под набором
(I0, I1, I2, I3, I4, I5, I6, I7)
подразумеваем, что различие между j-ми (j = 0, 1, …, 7) 64-битными словами ключей равно (все равно какого типа, так как рассматривать мы будем только различия и 0).
То есть = xj ^ xj’.
Джон Келси и Стефан Лакс предложили взять два блока (по 512 бит) с вектором различий
.
Если проследить по ходу алгоритма, учитывая свойства различий, можно показать, что после первого pass (по прошествии раундов 0, 1, …, 7) и key_schedule будет вектор . После раундов 8-9 получаем , а раунды раунды 10-15 на различие не влияют. Таким образом, получаем технику удержания различий между ключами с вероятностью 1.
При этом с помощью модификаций сообщений посредством промежуточных атак дней рождений решается проблема поддержания различия хеш-значений a, b, c, так что после раунда 6 был вектор различий , а по прошествии раундов 7-9 — . Техника модификаций сообщений является самой трудоемкой, где и получается результирующая сложность . Раунды 10-15 на различие не повлияют (действительно, ключи к этому шагу уже одинаковые).
То есть после 16 раундов хеш-значения совпадут.
Использование
Tiger используется в технологии TTH, где хеш вычисляется в древовидной форме. TTH, в свою очередь, применяется в протоколах файлового обмена Gnutella, Gnutella2, Direct Connect, а также в файлообменниках Phex, BearShare, LimeWire, Shareaza, DC++ и Valknut.
↑ 123456Florian Mendel, Bart Preneel, Vincent Rijmen, Hirotaka Yoshida, and Dai Watanabe, Update on Tiger (недоступная ссылка), proceedings of Indocrypt 7, Kolkata, 2006 (PDF)