Атака прообраза

Модель атаки на криптографические хеш-функции

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

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

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

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

Устойчивость к столкновениям подразумевает устойчивость ко второму прообразу. Сопротивление второму прообразу подразумевает сопротивление прообразу только в том случае, если размер входных данных хеш-функции может быть существенно (например, в 2 раза) больше, чем размер выходных данных хеш-функции. ^[1] И наоборот, атака по второму прообразу подразумевает атаку коллизией (тривиально, поскольку, в дополнение к x ′ , x уже известен с самого начала).

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

По определению, идеальная хэш-функция такова, что самый быстрый способ вычислить первый или второй прообраз — это атака методом перебора . Для n -битного хеша эта атака имеет временную сложность 2 ⁿ , которая считается слишком высокой для типичного выходного размера n = 128 бит. Если такая сложность — лучшее, чего может достичь злоумышленник, то хеш-функция считается устойчивой к прообразу. Однако есть общий результат: квантовые компьютеры выполняют атаку структурированного прообраза в , что также подразумевает атаку второго прообраза ^[2] и, следовательно, атаку коллизией. ${\displaystyle {\sqrt {2^{n}}}=2^{\frac {n}{2}}}$

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

Все известные на данный момент практические или почти практические атаки ^{[3] [4] [5]} на MD5 и SHA-1 являются атаками коллизии . ^{[ нужна цитация ]} В общем, атаку столкновением легче смонтировать, чем атаку прообраза, поскольку она не ограничена каким-либо установленным значением (для столкновения можно использовать любые два значения). Временная сложность атаки перебором коллизий, в отличие от атаки прообраза, составляет всего 0,000 . ${\displaystyle 2^{\frac {n}{2}}}$

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

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

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

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

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

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

1. Рогауэй, П.; Шримптон, Т. (2004). «Основы криптографических хеш-функций: определения, последствия и разделение устойчивости к прообразу, устойчивости к второму прообразу и устойчивости к столкновениям» (PDF) . Быстрое программное шифрование . Конспекты лекций по информатике. Том. 3017. Шпрингер-Верлаг. стр. 371–388. дои : 10.1007/978-3-540-25937-4_24. ISBN 978-3-540-22171-5. Проверено 17 ноября 2012 г.
2. Дэниел Дж. Бернштейн (12 ноября 2010 г.). «Квантовые атаки на Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD и Skein» (PDF) . Университет Иллинойса в Чикаго . Проверено 29 марта 2020 г.
3. Брюс Мортон; Клейтон Смит (30 января 2014 г.). «Почему нам нужно перейти на SHA-2». Совет безопасности центра сертификации .
4. «MD5 и перспективы». 01 января 2009 г.
5. «Блог Google Online Security: объявление о первом столкновении SHA1» . Проверено 23 февраля 2017 г.
6. Гудин, Дэн (10 декабря 2012 г.). «Кластер из 25 графических процессоров взламывает любой стандартный пароль Windows менее чем за 6 часов». Арс Техника . Проверено 23 ноября 2020 г.