Тигр (хэш-функция)
Криптографическая хэш-функция
Тигр
Общий
ДизайнерыРосс Андерсон и Эли Бихам
Впервые опубликовано1996
Деталь
Размеры дайджеста192, 128, 160
Раунды24

В криптографии Tiger [1] — криптографическая хеш-функция, разработанная Россом Андерсоном и Эли Бихамом в 1995 году для эффективности на 64-битных платформах. Размер хеш-значения Tiger составляет 192 бита. Усеченные версии (известные как Tiger/128 и Tiger/160) могут использоваться для совместимости с протоколами, предполагающими определенный размер хеш-функции. В отличие от семейства SHA-2 , не определены никакие отличительные значения инициализации; они являются просто префиксами полного хеш-значения Tiger/192.

Tiger2 [2] — это вариант, в котором сообщение дополняется путем предварительного добавления байта с шестнадцатеричным значением 0x80, как в MD4 , MD5 и SHA , а не с шестнадцатеричным значением 0x01, как в случае Tiger. В остальном оба варианта идентичны.

Алгоритм

Tiger основан на конструкции Меркла–Дамгарда . Односторонняя функция сжатия работает с 64-битными словами, поддерживая 3 слова состояния и обрабатывая 8 слов данных. Существует 24 раунда, использующих комбинацию смешивания операций с XOR и сложения/вычитания, поворотов и поиска S-box , а также довольно сложный алгоритм планирования ключей для получения 24 ключей раунда из 8 входных слов.

Несмотря на быстроту программного обеспечения, большие S-блоки Tiger (четыре S-блока, каждый с 256 64-битными записями общим объемом 8 КБ ) затрудняют реализацию в аппаратном обеспечении или микроконтроллерах . [ необходима цитата ]

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

Tiger часто используется в форме хэш-дерева Меркла , где он упоминается как TTH ( Tiger Tree Hash ). TTH используется многими клиентами в сетях обмена файлами Direct Connect и Gnutella и может быть опционально включен в метафайл BitTorrent [3] для лучшей доступности контента.

Tiger рассматривался для включения в стандарт OpenPGP , но был отклонен в пользу RIPEMD -160. [4] [5]

ОИД

RFC  2440 ссылается на TIGER как на не имеющий OID , тогда как в стандартах кодирования GNU TIGER указан как имеющий OID 1.3.6.1.4.1.11591.12.2. [6] В поддереве IPSEC HMAC-TIGER назначен OID 1.3.6.1.5.5.8.1.3. [7] OID для TTH пока не объявлен.

Порядок байтов

Спецификация Tiger не определяет способ печати его выходных данных, а только определяет результат как три упорядоченных 64-битных целых числа. Программа "testtiger" на домашней странице автора была предназначена для обеспечения простого тестирования исходного кода теста, а не для определения какого-либо конкретного порядка печати. ​​Протоколы Direct Connect и ADC , а также программа tthsumиспользуют порядок байтов little-endian, который также предпочитает один из авторов. [8]

Примеры

В примере ниже 192-битные (24-байтовые) хэши Tiger представлены как 48 шестнадцатеричных цифр в порядке байтов little-endian . Ниже показан 43-байтовый ввод ASCII и соответствующие хэши Tiger:

Тигр("Быстрая коричневая лиса перепрыгивает через ленивую собаку ") =6d12a41e72e644f017b6f0e2f7b44c6285f06dd5d2c5b075Tiger2("Быстрая коричневая лиса перепрыгивает через ленивую собаку ") =976abff8062a2e9dcea3a1ace966ed9c19cb85558b4976d8

Даже небольшое изменение в сообщении (с очень высокой вероятностью) приведет к совершенно другому хешу, например, изменение d на c : 

Тигр("Быстрая коричневая лиса перепрыгивает через ленивого кога ") =a8f04b0f7201a0d728101c9d26525b31764a3493fcd8458fTiger2("Быстрая коричневая лиса перепрыгивает через ленивого лисицу ") =09c11330283a27efb51930aa7dc1ec624ff738a8d9bdd3df

Хэш строки нулевой длины:

Тигр("") =3293ac630c13f0245f92bbb1766e16167a4e58492dde73f3Тигр2("") =4441be75f6018773c206c22745374b924aa8313fef919f41

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

В отличие от MD5 или SHA-0/1, не существует известных эффективных атак на полный 24-раундовый Tiger [9], за исключением псевдо-почти-коллизии. [10] В то время как MD5 обрабатывает свое состояние с помощью 64 простых 32-битных операций на 512-битный блок, а SHA-1 — с помощью 80, Tiger обновляет свое состояние с помощью в общей сложности 144 таких операций на 512-битный блок, дополнительно усиленных большими поисками S-box.

Джон Келси и Стефан Лакс нашли атаку поиска столкновений на 16-раундовом Tiger с временной сложностью, эквивалентной примерно 2 44 вызовам функции сжатия, и другую атаку, которая находит псевдо-близкие столкновения в 20-раундовом Tiger с работой, меньшей, чем 2 48 вызовов функции сжатия. [9] Флориан Мендель и др. улучшили эти атаки, описав атаку столкновений, охватывающую 19 раундов Tiger, и атаку псевдо-близких столкновений из 22 раундов. Эти атаки требуют трудозатрат, эквивалентных примерно 2 62 и 2 44 оценкам функции сжатия Tiger соответственно. [11]

Смотрите также

Ссылки

  1. ^ Росс Андерсон и Эли Бихам (1996-02-08). "Tiger: A Fast New Hash Function". Fast Software Encryption 3 . Кембридж . Получено 2017-03-03 .
  2. ^ "Tiger2 Test Vectors". Проект NESSIE . 2005-02-25 . Получено 2017-03-03 .
  3. ^ Фейт, Гарольд (2012-02-12). "P2P:Протокол:Спецификации:Необязательные хэши: TTH Root" . Получено 2017-11-18 .
  4. ^ Каллас, Джон (2004-08-18). "Re: переосмысление TIGER". Архивировано из оригинала 2014-07-14.
  5. ^ Порнин, Томас (25.10.2013). «Как использовать хэш-функцию Tiger с GPG?».
  6. ^ "Поведение программ для всех программ: распределение OID". GNU . Получено 2017-11-18 .
  7. ^ "Справочная запись для OID 1.3.6.1.5.5.8.1.3 – hmacTIGER". 1998-10-18 . Получено 2017-11-18 .
  8. ^ "Digest::Модуль Tiger". CPAN . Получено 2017-03-03 .
  9. ^ ab John Kelsey; Stefan Lucks (2006). "Столкновения и близкие столкновения для алгоритма Reduced-Round Tiger" (PDF) . Fast Software Encryption 13 . Graz . Архивировано из оригинала (PDF) 2016-03-04.
  10. ^ Мендель, Флориан; Винсент, Реймен. «Криптоанализ хэш-функции Tiger». ASIACRYPT 2007. Springer Berlin / Heidelberg. стр.  536–550 . doi : 10.1007/978-3-540-76900-2_33 .
  11. ^ Флориан Мендель; Барт Пренил; Винсент Реймен; Хиротака Ёсида; Дай Ватанабэ (2006). «Обновленная информация о Тигре» (PDF) . Индокрипт 7 . Калькутта .
  • Домашняя страница Tiger
Взято с "https://en.wikipedia.org/w/index.php?title=Tiger_(hash_function)&oldid=1177928948"