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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «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 = 8192 = 8 Кбайт. Для этого хватает кэша большинства процессоров, хотя могут быть сложности при реализации на микроконтроллерах.

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

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

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

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

Теперь для перехода от значения к значению выполняются следующие операции:

  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 сохраняет значение :

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 даёт промежуточное значение хеш-функции , которое используется как начальное значение для следующего 512-битного блока данных. Промежуточное значение на последнем блоке даёт 192-битное значение Tiger/192.

Тестовые векторы[править | править вики-текст]

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

Hash("") = 
5263A716FEB71B5 5D27A60A7E967320 6CC0D67319255EA4
Hash("Tiger") = 
28A5CC95DFEC854A 641D9857A8E86363 427FAEEC76E94D14

Hash("abc") = 3E9EF7ED8B161634 3C8674F8C513C725 677336B59296B8E2
Hash("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+-") = 
66C8DE0E89C65204 712FC941475931CF 7A3A6B53D28E157A

Hash("ABCDEFGHIJKLMNOPQRSTUVWXYZ=abcdefghijklmnopqrstuvwxyz+0123456789") = 5AEB5F93590DC80D B83BD092846CABB 34BAED53D291E67EA
Безопасность

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

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

Атака на связанные ключи представляет собой атаку, при которой криптоаналитик может вычислять хеш для нескольких различных значений инициализирующих векторов, которые он не знает, но знает некоторую взаимосвязь между ними (например, что они отличаются на один бит или какая-то часть всех векторов одна и та же). Из-за атаки такого типа с шифрования 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[править | править вики-текст]

Число раундов Тип Сложность Описание
Tiger-16 коллизия [1]
Tiger-19 коллизия и [2]
Tiger-19 псевдоколлизия [2]
Tiger-21 псевдоколлизия [2]
Tiger-23/128 псевдоколлизия [2]
Tiger-23 псевдоколлизия [3]
Tiger-20 почти псевдоколлизия [1]
Tiger-21 почти псевдоколлизия [2]
Tiger-22 почти псевдоколлизия [2]
Tiger-24 почти псевдоколлизия [3]

Атака на Tiger-16[править | править вики-текст]

Поясним идею нахождения коллизии для Tiger-16, то есть для Tiger с 16 раундами, изложенную Джоном Келси и Стефаном Лаксом[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.

Ссылки[править | править вики-текст]

Статьи[править | править вики-текст]

  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)