В криптографии атака с использованием прообраза на криптографические хэш-функции пытается найти сообщение с определенным значением хеш-функции. Криптографическая хеш-функция должна противостоять атакам на свой прообраз (набор возможных входов).
В контексте атаки существует два типа сопротивления прообразу:
- сопротивление прообразу : практически для всех заранее заданных выходов невозможно с вычислительной точки зрения найти какой-либо вход, хэширующий для этого выхода; т.е. при заданном y трудно найти такое x , что h ( x ) = y . [1]
- сопротивление второму прообразу : с вычислительной точки зрения невозможно найти какой-либо второй вход, который имеет тот же выход, что и заданный вход; т.е. для заданного x трудно найти второй прообраз x ′ ≠ x такой, что h ( x ) = h ( x ′) . [1]
Их можно сравнить с сопротивлением столкновениям , при котором с вычислительной точки зрения невозможно найти любые два различных входа x , x ', которые хешируют один и тот же выход; т.е. такой, что h ( x ) = h ( x ′) . [1]
Сопротивление столкновению подразумевает сопротивление второму прообразу [1], но не гарантирует стойкость прообраз. [1] Напротив, атака второго прообраза подразумевает атаку коллизии (тривиально, поскольку, помимо x ', x уже известен с самого начала).
Примененные атаки прообразов
По определению, идеальная хеш-функция такова, что самый быстрый способ вычисления первого или второго прообраза - это атака полным перебором . Для n- битного хэша эта атака имеет временную сложность 2 n , которая считается слишком высокой для типичного выходного размера n = 128 бит. Если такая сложность - лучшее, что может быть достигнуто злоумышленником, то хеш-функция считается устойчивой к прообразу. Однако есть общий результат, что квантовые компьютеры выполняют атаку структурированного прообраза в √ 2 n = 2 n / 2 , что также подразумевает второй прообраз [2] и, следовательно, атаку столкновения.
Более быстрые атаки с использованием прообраза могут быть обнаружены путем криптоанализа определенных хэш-функций, специфичных для этой функции. Некоторые существенные атаки с использованием прообраза уже обнаружены, но они еще не применимы. Если будет обнаружена практическая атака с использованием прообраза, она серьезно повлияет на многие Интернет-протоколы. В этом случае «практичный» означает, что злоумышленник может выполнить его с разумным количеством ресурсов. Например, атака с прообразом, которая стоит триллионы долларов и требует десятилетий, чтобы прообразить одно желаемое значение хеш-функции или одно сообщение, нецелесообразна; тот, который стоит несколько тысяч долларов и занимает несколько недель, может оказаться очень практичным.
Все известные в настоящее время практические или почти практические атаки [3] [4] [5] на MD5 и SHA-1 являются атаками с коллизией [ необходима цитата ] . В общем, атаку столкновения легче организовать, чем атаку прообраза, поскольку она не ограничена никаким установленным значением (для столкновения могут использоваться любые два значения). Временная сложность атаки методом прямого перебора, в отличие от атаки по прообразу, составляет всего 2 n / 2 .
Ограниченные космические атаки на прообраз
Вычислительная неосуществимость атаки первого прообраза на идеальную хеш-функцию предполагает, что набор возможных входных хеш-значений слишком велик для поиска методом грубой силы. Однако, если известно, что данное значение хеш-функции было получено из набора входных данных, который является относительно небольшим или каким-то образом упорядочен по вероятности, тогда поиск методом грубой силы может быть эффективным. Практичность зависит от размера входного набора и скорости или стоимости вычисления хеш-функции.
Типичный пример - использование хэшей для хранения данных проверки пароля для аутентификации. Вместо того, чтобы хранить открытый текст паролей пользователей, система контроля доступа хранит хэш пароля. Когда пользователь запрашивает доступ, отправленный им пароль хешируется и сравнивается с сохраненным значением. Если сохраненные данные проверки украдены, вор будет иметь только хеш-значения, но не пароли. Однако большинство пользователей выбирают пароли предсказуемым образом, и многие пароли достаточно короткие, чтобы можно было проверить все возможные комбинации, если используются быстрые хэши, даже если хэш оценивается как защищенный от атак по прообразу. [6] Для замедления поиска были созданы специальные хэши, называемые функциями вывода ключей . См. Взлом пароля .
Смотрите также
- Атака на день рождения
- Криптографическая хеш-функция
- Сводка по безопасности хеш-функции
- Радужный стол
- Случайный оракул
- RFC 4270 : Атаки на криптографические хэши в интернет-протоколах
Рекомендации
- ^ а б в г д Rogaway, P .; Шримптон, Т. (2004). «Основы криптографической хеш-функции: определения, значения и разделения для сопротивления прообразу, сопротивления второму прообразу и сопротивления столкновениям» (PDF) . Быстрое программное шифрование . Springer-Verlag . Проверено 17 ноября 2012 года .
- ^ Дэниел Дж. Бернштейн (12 ноября 2010 г.). «Квантовые атаки против Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD и Skein» (PDF) . Иллинойсский университет в Чикаго . Проверено 29 марта 2020 .
- ^ Брюс Мортон, Клейтон Смит (30 января 2014 г.). «Почему нам нужно переходить на SHA-2» . Совет Безопасности Центра Сертификации .CS1 maint: использует параметр авторов ( ссылка )
- ^ «MD5 и перспективы» . 2009-01-01.
- ^ «Блог Google Online Security: объявление о первом конфликте SHA1» . Проверено 23 февраля 2017 .
- ^ Гудин, Дэн (2012-12-10). «Кластер на 25 GPU взламывает каждый стандартный пароль Windows менее чем за 6 часов» . Ars Technica . Проверено 23 ноября 2020 .