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. Порядок байтів — Порядок від молодшого до старшого.

Беруться три 64-бітових регістра з початковими значеннями (значення хешу $h_{0}$ ):

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

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

Save_abc
Pass (a, b, c, 5)
Key_schedule
Pass (c, a, b, 7)
Key_schedule
Pass (b, c, a, 9)
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.

Тестові вектори

Приклади хеш-значень.

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}$ (відповідно до парадоксу днів народження).

Посилання

biham/Reports/Tiger/Сторінка авторів Tiger^{[недоступне посилання з червня 2019]}