Интернет магазин китайских планшетных компьютеров

Компьютеры - Tiger (хэш-функция) - Криптоанализ

Пусть h — хеш-функция, где x — инициализирующий вектор, m — блок сообщения. ^ — операция XOR, w{} — вес Хэмминга. Тогда:

• под коллизией будем понимать ситуацию, когда

  w{h ^ h} = 0;

• под почти коллизией -

  w{h ^ h} = a, где a — небольшое значение;

• под псевдоколлизией -

  w{h ^ h} = 0;

• под почти псевдоколлизией -

  w{h ^ h} = a, где a — небольшое значение.

В идеале, в соответствии с парадоксом дней рождений, для нахождения коллизии N-разрядной хеш-функции потребуется не менее O операций.

В 2006 году Джон Келси и Стефан Лакс представили коллизию для Tiger-16 со сложностью 2, а также почти псевдоколлизию для Tiger-20 со сложностью 2. Далее в этом же году Флориан Мендель и соавторы показали, как применить технику атаки Джона Келси и Стефана Лакса, чтобы получить коллизию для Tiger-19, а также предложили две различные техники для получения этой коллизии со сложностями 2 и 2.

Обзор атак на Tiger

Атака на Tiger-16

Поясним идею нахождения коллизии для Tiger-16, то есть для Tiger с 16 раундами, изложенную Джоном Келси и Стефаном Лаксом.

Рассматриваем 64-битные слова. Мы будем иметь дело с различием между словами двух типов: xor-различие и аддитивное различие. Первое из них есть результат обычной разности по модулю 2, а второе — результат операции XOR. Обычно преобразование одного типа различия в другой дело вероятностное. Но есть случай когда два типа различий равны друг другу с вероятностью 1. А именно, когда различие I = 2, действительно в этом случае слова просто отличаются друг от друга старшим битом. Также отметим свойство различия — оно не меняется если домножить слово на нечетное число.

Пусть I = 2. Под набором

подразумеваем, что различие между j-ми 64-битными словами ключей равно Ij. То есть Ij = xj ^ xj’.

Джон Келси и Стефан Лакс предложили взять два блока с вектором различий . Если проследить по ходу алгоритма, учитывая свойства различий, можно показать, что после первого pass и key_schedule будет вектор . После раундов 8-9 получаем , а раунды раунды 10-15 на различие не влияют. Таким образом, получаем технику удержания различий между ключами с вероятностью 1.

При этом с помощью модификаций сообщений посредством промежуточных атак дней рождений решается проблема поддержания различия хеш-значений a, b, c, так что после раунда 6 был вектор различий , а по прошествии раундов 7-9 — . Техника модификаций сообщений является самой трудоемкой, где и получается результирующая сложность 2. Раунды 10-15 на различие не повлияют.

То есть после 16 раундов хеш-значения совпадут.