Пример простого некорректного алгоритма хеширования, уязвимого для предвидения атак

Question

Я ищу пример простого алгоритма хеширования, который может показывать, что он уязвим для множества атак с прообразом при заданной длине ввода.

Например, если я знаю, что входные данные имеют размер 160 байтов и генерируют 16-байтовый хеш, то существует некоторый метод поиска других входных данных длиной 160 байтов и генерирования идентичного 16-байтового хеша безприбегая к чисто грубому принуждению.

Обратите внимание, что я не имею в виду использование чего-то вроде MD5 или SHA1.Я понимаю, что они предназначены для того, чтобы сделать это непрактичным.Этот алгоритм будет примером из учебника некорректной конструкции алгоритма хеширования и того, как этот недостаток может быть практически использован.Я пробовал Google, но большая часть того, что появляется, - это теоретические исследования известных безопасных алгоритмов.

Answer 1

Простой пример - хеш-функция на основе TEA, которая использовалась в XBOX.Эта хеш-функция была подвержена простой второстепенной атаке.Недостатком было то, что он использовал шифр TEA в конструкции Дэвиса-Мейера.Атака использует, что TEA имеет эквивалентные ключи.Хеш-коллизии могут быть обнаружены простым переключением битов.

Книга, которая описывает эту атаку, называется "Взлом XBOX" Эндрю "bunnie" Хуан.

Answer 2

То, что вы просите, это слабый алгоритм хеширования.Сильные алгоритмы хеширования сложны.Слабые - это просто.

Вот один из псевдокодов:

hash[0..15] = all 0
for i in range(0..159):
    hash[i % 16] ^= data[i]

Здесь каждый хеш-байт равен xor из десяти байтов данных.Очень легко решить, да?Я уверен, что вы можете думать о столь же простых.