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