Атака на прообраз - Preimage attack

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

В контексте атаки существует два типа сопротивления прообразу:

  • сопротивление прообразу: практически для всех заранее заданных выходов невозможно с вычислительной точки зрения найти какой-либо вход, хеширующий этот выход; т.е. с учетом y, трудно найти Икс такой, что час(Икс) = y.[1]
  • сопротивление второму прообразу: вычислительно невозможно найти любой второй вход, который имеет тот же выход, что и указанный вход; то есть, учитывая Икс, трудно найти второй прообраз Икс′ ≠ Икс такой, что час(Икс) = час(Икс′).[1]

Их можно сравнить с сопротивление столкновению, в котором с вычислительной точки зрения невозможно найти любые два различных входа Икс, Икс'Этот хэш к тому же выходу; т.е. такой, что час(Икс) = час(Икс′).[1]

Сопротивление столкновению подразумевает сопротивление второму прообразу,[1] но не гарантирует устойчивости к прообразу.[1] Напротив, атака второго прообраза подразумевает атаку столкновения (тривиально, поскольку в дополнение к Икс′, Икс уже известно с самого начала).

Применяемые атаки прообраза

По определению идеальная хеш-функция такова, что самый быстрый способ вычисления первого или второго прообраза - через атака грубой силой. Для п-битный хэш, эта атака имеет временная сложность 2п, что считается слишком большим для типичного выходного размера п = 128 бит. Если такая сложность - лучшее, что может быть достигнуто злоумышленником, то хеш-функция считается устойчивой к прообразу. Однако есть общий результат, что квантовые компьютеры выполняют атаку структурированного прообраза в √2п = 2п/2, что также подразумевает второй прообраз[2] и, следовательно, столкновение.

Более быстрые атаки на прообраз можно найти криптоанализ определенные хэш-функции и относятся к этой функции. Некоторые серьезные атаки с использованием прообраза уже обнаружены, но они пока не применимы. Если будет обнаружена практическая атака с использованием прообраза, она серьезно повлияет на многие интернет-протоколы. В этом случае «практичный» означает, что злоумышленник может выполнить его с разумным количеством ресурсов. Например, атака с прообразом, которая стоит триллионы долларов и требует десятилетий, чтобы прообразить одно желаемое значение хеш-функции или одно сообщение, нецелесообразна; тот, который стоит несколько тысяч долларов и занимает несколько недель, может оказаться очень практичным.

Все известные в настоящее время практические или почти практические атаки[3][4][5] на MD5 и SHA-1 находятся столкновения атак[нужна цитата ]. В общем, атаку столкновения легче организовать, чем атаку прообраза, поскольку она не ограничена никаким установленным значением (для столкновения могут использоваться любые два значения). Временная сложность атаки столкновения, напротив, составляет 2п/2.

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

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

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

Смотрите также

  • Атака на день рождения
  • Криптографическая хеш-функция
  • Сводка по безопасности хеш-функции
  • Радужный стол
  • Случайный оракул
  • RFC  4270: Атаки на криптографические хэши в интернет-протоколах

Рекомендации

  1. ^ а б c d е Rogaway, P .; Шримптон, Т. (2004). «Основы криптографической хеш-функции: определения, значения и разделения для сопротивления прообразу, сопротивления второму прообразу и сопротивления столкновениям» (PDF). Быстрое программное шифрование. Springer-Verlag. Получено 17 ноября 2012.
  2. ^ Дэниел Дж. Бернштейн (12 ноября 2010 г.). «Квантовые атаки против Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD и Skein» (PDF). Иллинойский университет в Чикаго. Получено 2020-03-29.
  3. ^ Брюс Мортон, Клейтон Смит (30 января 2014 г.). «Почему нам нужно переходить на SHA-2». Совет Безопасности Центра Сертификации.CS1 maint: использует параметр авторов (связь)
  4. ^ «MD5 и перспективы». 2009-01-01.
  5. ^ "Блог Google Online Security: объявление о первом конфликте SHA1". Получено 2017-02-23.
  6. ^ Гудин, Дэн (2012-12-10). «Кластер на 25 GPU взламывает каждый стандартный пароль Windows менее чем за 6 часов». Ars Technica. Получено 2020-11-23.