Введение

Модель атаки на криптографические хеш-функции
В криптографии атака по предварительному образу на криптографические хеш-функции пытается найти сообщение, которое имеет заданное хеш-значение. Криптографическая хеш-функция должна быть устойчива к атакам на её свойство устойчивости к предварительному образу (множеству возможных входов). В контексте атак выделяют два типа устойчивости к предварительному образу:

устойчивость к предварительному образу: для подавляющего большинства заранее заданных выходных значений вычислительно невозможно найти какой-либо вход, который хешируется в это выходное значение; то есть, при заданном , сложно найти такое , что устойчивость ко второму предварительному образу: для заданного входа вычислительно невозможно найти другой вход, который производит такое же выходное значение; то есть, при заданном , сложно найти второй вход , такой что , и, следовательно, это атака на коллизии. Более быстрые атаки по предварительному образу можно найти путем криптоанализа определенных хеш-функций, и они специфичны для данной функции. Некоторые значимые атаки по предварительному образу уже обнаружены, но пока не являются практическими. Если будет обнаружена практическая атака по предварительному образу, это серьезно повлияет на многие интернет-протоколы. В этом случае "практичный" означает, что он может быть выполнен злоумышленником, располагающим разумным количеством ресурсов. Например, атака по предварительному образу, которая стоит триллионы долларов и занимает десятилетия для получения одного желаемого хеш-значения или одного сообщения, не является практичной; тогда как атака, которая стоит несколько тысяч долларов и занимает несколько недель, может быть вполне практичной. Все известные в настоящее время практические или почти практические атаки на MD5 и SHA-1 являются атаками на коллизии. В общем случае, атаку на коллизии легче осуществить, чем атаку по предварительному образу, поскольку она не ограничена каким-либо заданным значением (можно использовать любые два значения для создания коллизии). Временная сложность атаки на коллизии полным перебором, в отличие от атаки по предварительному образу, составляет всего .

Ограниченные атаки в пространстве перед изображением

Вычислительная сложность проведения атаки первого прообраза на идеальную хеш-функцию основывается на предположении, что множество возможных входных данных для хеширования слишком велико для перебора. Однако, если известно, что данное хеш-значение было получено из относительно небольшого множества входных данных или из множества, упорядоченного по вероятности, то перебор может оказаться эффективным. Практичность зависит от размера множества входных данных и скорости или стоимости вычисления хеш-функции. Типичным примером является использование хешей для хранения данных проверки паролей при аутентификации. Вместо хранения паролей пользователей в открытом виде, система контроля доступа хранит хеш-значение пароля. При запросе доступа введенный пользователем пароль хешируется и сравнивается с сохраненным значением. Если данные проверки будут похищены, злоумышленник получит только хеш-значения, а не сами пароли. Однако большинство пользователей выбирают предсказуемые пароли, и многие из них достаточно короткие, чтобы можно было перебрать все возможные комбинации, если используются быстрые хеш-функции, даже если хеш считается устойчивым к атакам по прообразу. Для замедления перебора были разработаны специальные хеш-функции, называемые функциями вывода ключей. См. Взлом паролей. О методе предотвращения перебора коротких паролей см. соль (криптография).