Криптографическая хеш-функция Tiger

Введение

Криптографическая хеш-функция

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

Алгоритм

"Тигр" основан на конструкции Меркла — Дамгорда. Односторонняя функция сжатия оперирует 64-битными словами, поддерживая 3 слова состояния и обрабатывая 8 слов данных. Алгоритм состоит из 24 раундов, использующих комбинацию операций перемешивания с XOR и сложения/вычитания, вращений и поиска в S-блоках, а также достаточно сложный алгоритм генерации ключей для получения 24 раундовых ключей из 8 входных слов. Несмотря на высокую скорость работы в программном обеспечении, большие S-блоки "Тигр" (четыре S-блока, каждый из которых содержит 256 64-битных элементов, общей суммой 8 КиБ) затрудняют реализацию в аппаратном обеспечении или микроконтроллерах.

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

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

ОИО

относится к TIGER как к алгоритму, не имеющему OID, в то время как стандарты кодирования GNU указывают TIGER как имеющий OID 1.3.6.1.4.1.11591.12.2. В поддереве IPSEC HMAC TIGER присвоен OID 1.3.6.1.5.5.8.1.3. OID для TTH пока не был объявлен.

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

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

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

В отличие от MD5 или SHA-0/1, не существует известных эффективных атак на полные 24 раунда Tiger. В то время как MD5 обрабатывает свое состояние с помощью 64 простых 32-битных операций на 512-битный блок, а SHA-1 – с 80, Tiger обновляет свое состояние с общей сложностью 144 таких операций на 512-битный блок, дополнительно усиленных использованием больших S-блоков. Джон Келси и Стефан Лукс обнаружили атаку, находящую коллизии в 16 раундах Tiger, с временной сложностью, эквивалентной примерно 2⁴⁴ вызовам функции сжатия, и другую атаку, находящую псевдо-близкие коллизии в 20 раундах Tiger, требующую вычислительных затрат меньше, чем 2⁴⁸ вызовов функции сжатия. Флориан Мендель и другие исследователи улучшили эти атаки, описав атаку, находящую коллизии в 19 раундах Tiger, и атаку, находящую псевдо-близкие коллизии в 22 раундах Tiger. Эти атаки требуют вычислительных затрат, эквивалентных примерно 2⁶² и 2⁴⁴ оценкам функции сжатия Tiger соответственно.