В криптографии, атака прообраза на криптографических хэш-функций пытается найти сообщение, которое имеет определенное хеш-значение. Криптографическая хеш-функция должна противостоять атакам на свой прообраз (набор возможных входов).
В контексте атаки существует два типа сопротивления прообразу:
Их можно сравнить с сопротивлением столкновению, в котором вычислительно невозможно найти любые два различных входа x, x ', которые хешируют один и тот же выход; т.е. такая, что h (x) = h (x ').
Сопротивление столкновению подразумевает сопротивление второму прообразу, но не гарантирует стойкость прообраз. Напротив, атака второго прообраза подразумевает атаку столкновения (тривиально, поскольку, помимо x ', x уже известен с самого начала).
По определению, идеальная хеш-функция такова, что самый быстрый способ вычисления первого или второго прообраза - это атака полным перебором. Для n-битного хэша эта атака имеет временную сложность 2, что считается слишком высоким для типичного выходного размера n = 128 бит. Если такая сложность - лучшее, что может быть достигнуто злоумышленником, то хеш-функция считается устойчивой к прообразу. Однако есть общий результат, что квантовые компьютеры выполняют атаку структурированного прообраза в √2 = 2, что также подразумевает второй прообраз и, следовательно, атаку столкновения.
Более быстрые атаки с использованием прообраза могут быть обнаружены с помощью криптоанализа определенных хэш-функций, специфичных для этой функции. Некоторые существенные атаки с использованием прообраза уже обнаружены, но они еще не применимы. Если будет обнаружена практическая атака с использованием прообраза, она серьезно повлияет на многие интернет-протоколы. В этом случае «практичный» означает, что злоумышленник может выполнить его с разумным количеством ресурсов. Например, атака с прообразом, которая стоит триллионы долларов и требует десятилетий, чтобы прообразить одно желаемое значение хеш-функции или одно сообщение, нецелесообразна; тот, который стоит несколько тысяч долларов и занимает несколько недель, может оказаться очень практичным.
Все известные в настоящее время практические или почти практические атаки на MD5 и SHA-1 являются атаками с коллизией. В общем, атаку столкновения легче организовать, чем атаку прообраза, поскольку она не ограничена никаким установленным значением (для столкновения могут использоваться любые два значения). Временная сложность атаки с коллизией, напротив, составляет 2.
| 1 =
()